Самый эффективный способ найти все режимы в списке случайно сгенерированных целых чисел и как часто они встречаются

Если методу, написанному на C#, будет передано значение NULL или где-то от 0 до 6 000 000 случайно сгенерированных и несортированных целых чисел, каков наиболее эффективный способ определить все режимы и сколько раз они возникали? В частности, может ли кто-нибудь помочь мне с решением на основе LINQ, с которым я борюсь?

Вот что у меня есть на данный момент:

Мое ближайшее решение LINQ пока захватывает только первый найденный режим и не указывает количество вхождений. На моем компьютере это примерно в 7 раз медленнее, чем моя уродливая и громоздкая реализация, что отвратительно.

    int mode = numbers.GroupBy(number => number).OrderByDescending(group => group.Count()).Select(k => k.Key).FirstOrDefault();

Мой метод, закодированный вручную.

    public class NumberCount
    {
        public int Value;
        public int Occurrences;

        public NumberCount(int value, int occurrences)
        {
            Value = value;
            Occurrences = occurrences;
        }
    }

    private static List<NumberCount> findMostCommon(List<int> integers)
    {
        if (integers == null)
            return null;
        else if (integers.Count < 1)
            return new List<NumberCount>();

        List<NumberCount> mostCommon = new List<NumberCount>();

        integers.Sort();

        mostCommon.Add(new NumberCount(integers[0], 1));
        for (int i=1; i<integers.Count; i++)
        {
            if (mostCommon[mostCommon.Count - 1].Value != integers[i])
                mostCommon.Add(new NumberCount(integers[i], 1));
            else
                mostCommon[mostCommon.Count - 1].Occurrences++;
        }

        List<NumberCount> answer = new List<NumberCount>();
        answer.Add(mostCommon[0]);
        for (int i=1; i<mostCommon.Count; i++) 
        {
            if (mostCommon[i].Occurrences > answer[0].Occurrences)
            {
                if (answer.Count == 1)
                {
                    answer[0] = mostCommon[i];
                }
                else
                {
                    answer = new List<NumberCount>();
                    answer.Add(mostCommon[i]);
                }
            }
            else if (mostCommon[i].Occurrences == answer[0].Occurrences)
            {
                answer.Add(mostCommon[i]);
            }
        }

        return answer;        
    }

По сути, я пытаюсь получить элегантное компактное решение LINQ, по крайней мере, так же быстро, как мой уродливый метод. Спасибо заранее за любые предложения.

Как вы думаете, почему linq сделает это лучше или менее уродливо? Ваш код кажется довольно простым. Кроме того, я до сих пор не понимаю того, чего вы действительно хотите достичь. Что такое режим в вашем случае? Как тебе это создать?

HimBromBeere 10.08.2018 15:41

LINQ выполняет большую часть этого за одну строку. Однако я застрял на последних вещах. Режим - это число или числа, которые встречаются чаще всего.

Random User 10.08.2018 15:50

@HimBromBeere: Я считаю, что в этом случае "mode" = "число, которое встречается максимальное количество раз". Итак, в массиве {1, 3, 2, 4, 1, 4, 5} режимы - 4 и 1, поскольку оба они встречаются дважды, и ничего не встречается более двух раз.

Jon Skeet 10.08.2018 15:50

Находятся ли ваши случайные числа в заданном диапазоне? Или вы знаете, что будет не более небольшого количества различных значений? Если есть только десять значений, например, вы можете создать простую коллекцию счетчиков, а затем перебрать эту коллекцию, чтобы увидеть, какое из них самое большое (что приятно и быстро, потому что вам нужно отсортировать / сравнить только десять вещей). Если у вас потенциально есть 5000000 различных целых чисел, этот метод станет намного менее эффективным ...

Chris 10.08.2018 15:54

Единственное ограничение - это действительные неотрицательные 32-битные целые числа.

Random User 10.08.2018 15:57

Я сильно подозреваю, что ваш метод будет лучшим вариантом, а не использовать linq. Несколько моментов - вы тратите время на integers.Sort();. Следующий код, похоже, не требует сортировки списка. Также вы можете пропустить mostCommon.Add(new NumberCount(integers[0], 1)); и начать цикл с i=0. наконец, вместо answer = new List<NumberCount>(); вы, вероятно, можете просто использовать answer.Clear(), чтобы сохранить создание нескольких списков.

Chris 10.08.2018 16:07

@Chris Для этого теста нужна сортировка: mostCommon[mostCommon.Count - 1].Value != integers[i], чтобы вы могли зафиксировать пробег.

NetMage 15.08.2018 03:08

@NetMage: О да. Я неправильно прочитал и предположил, что для хранения счетчиков используется словарь, а не список, и что он будет просто увеличивать соответствующий элемент каждый раз. Тогда добавьте это к моему предыдущему комментарию. :)

Chris 15.08.2018 15:42
0
8
162
5
Перейти к ответу Данный вопрос помечен как решенный

Ответы 5

Я бы лично использовал ConcurrentDictionary, который обновлял бы счетчик, и словарь стал бы доступнее. Я использую этот метод довольно часто, и он более читабельный.

  // create a dictionary
  var dictionary = new ConcurrentDictionary<int, int>();

  // list of you integers
  var numbers = new List<int>();

  // parallel the iteration ( we can because concurrent dictionary is thread safe-ish
  numbers.AsParallel().ForAll((number) =>
  {
      // add the key if it's not there with value of 1 and if it's there it use the lambda function to increment by 1
      dictionary.AddOrUpdate(number, 1, (key, old) => old + 1);
  });

Тогда дело только в том, чтобы получить наибольшее количество случаев. Есть много способов. Я не полностью понимаю вашу версию, но самая большая часть - это всего лишь одна совокупность, например:

var topMostOccurence = dictionary.Aggregate((x, y) => { return x.Value > y.Value ? x : y; });

Я протестировал приведенный ниже код на моем Intel i7-8700K и получил следующие результаты:

Лямбда: найдено 78 за 134 мс.

Вручную: найдено 78 за 368 мс.

Словарь: найдено 78 за 195 мс.

    static IEnumerable<int> GenerateNumbers(int amount)
    {
        Random r = new Random();
        for (int i = 0; i < amount; i++)
            yield return r.Next(100);
    }

    static void Main(string[] args)
    {
        var numbers = GenerateNumbers(6_000_000).ToList();

        Stopwatch sw = Stopwatch.StartNew();
        int mode = numbers.GroupBy(number => number).OrderByDescending(group => group.Count()).Select(k =>
        {
            int count = k.Count();
            return new { Mode = k.Key, Count = count };
        }).FirstOrDefault().Mode;
        sw.Stop();
        Console.WriteLine($"Lambda: found {mode} in {sw.ElapsedMilliseconds} ms.");


        sw = Stopwatch.StartNew();
        mode = findMostCommon(numbers)[0].Value;
        sw.Stop();
        Console.WriteLine($"Manual: found {mode} in {sw.ElapsedMilliseconds} ms.");

        // create a dictionary
        var dictionary = new ConcurrentDictionary<int, int>();

        sw = Stopwatch.StartNew();
        // parallel the iteration ( we can because concurrent dictionary is thread safe-ish
        numbers.AsParallel().ForAll((number) =>
        {
            // add the key if it's not there with value of 1 and if it's there it use the lambda function to increment by 1
            dictionary.AddOrUpdate(number, 1, (key, old) => old + 1);
        });
        mode = dictionary.Aggregate((x, y) => { return x.Value > y.Value ? x : y; }).Key;
        sw.Stop();
        Console.WriteLine($"Dictionary: found {mode} in {sw.ElapsedMilliseconds} ms.");


        Console.ReadLine();
    }

Лямбда и Словарь возвращают только один режим и не указывают числа и сколько раз они встречались.

Random User 10.08.2018 17:09

Кроме того, Словарь работает с отсортированным списком, потому что во всем используется один и тот же список. Кроме того, вы ограничиваете значения до 100. Когда используется int.MaxValue, мои результаты идут от: max 100 и повторного использования чисел, даже если они отсортированы между ними: Lambda = 173 Manual = 477 Dictionary = 210 max is int.MaxValue и каждый процесс получает новый массив: Lambda = 7276 Manual = 1431 Dictionary = 6381

Random User 10.08.2018 17:24

что вы хотите: 2+ числа могут появляться в массиве одинаково, например: {1,1,1,2,2,2,3,3,3}

ваш текущий код отсюда: Найдите наиболее часто встречающееся число в списке <int> но он возвращает только число, это совершенно неверный результат.

Проблема Linq: цикл не может закончиться, если вы не хотите, чтобы он продолжался.

Но здесь я привожу список с LINQ в соответствии с вашими требованиями:

List<NumberCount> MaxOccurrences(List<int> integers)
{
    return integers?.AsParallel()
        .GroupBy(x => x)//group numbers, key is number, count is count
        .Select(k => new NumberCount(k.Key, k.Count()))
        .GroupBy(x => x.Occurrences)//group by Occurrences, key is Occurrences, value is result
        .OrderByDescending(x => x.Key) //sort
        .FirstOrDefault()? //the first one is result
        .ToList();
}

Детали теста:

Размер массива: 30000

30000
MaxOccurrences only
MaxOccurrences1: 207
MaxOccurrences2: 38 
=============
Full List
Original1: 28
Original2: 23
ConcurrentDictionary1: 32
ConcurrentDictionary2: 34
AsParallel1: 27
AsParallel2: 19
AsParallel3: 36

Размер массива: 3000000

3000000
MaxOccurrences only
MaxOccurrences1: 3009
MaxOccurrences2: 1962 //<==this is the best one in big loop.
=============
Full List
Original1: 3200
Original2: 3234
ConcurrentDictionary1: 3391
ConcurrentDictionary2: 2681
AsParallel1: 3776
AsParallel2: 2389
AsParallel3: 2155

Вот код:

class Program
{
    static void Main(string[] args)
    {
        const int listSize = 3000000;
        var rnd = new Random();
        var randomList = Enumerable.Range(1, listSize).OrderBy(e => rnd.Next()).ToList();

        // the code that you want to measure comes here

        Console.WriteLine(randomList.Count);
        Console.WriteLine("MaxOccurrences only");

        Test(randomList, MaxOccurrences1);
        Test(randomList, MaxOccurrences2);


        Console.WriteLine("=============");
        Console.WriteLine("Full List");
        Test(randomList, Original1);
        Test(randomList, Original2);
        Test(randomList, AsParallel1);
        Test(randomList, AsParallel2);
        Test(randomList, AsParallel3);

        Console.ReadLine();
    }

    private static void Test(List<int> data, Action<List<int>> method)
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();
        method(data);
        watch.Stop();
        Console.WriteLine($"{method.Method.Name}: {watch.ElapsedMilliseconds}");
    }
    private static void Original1(List<int> integers)
    {
        integers?.GroupBy(number => number)
            .OrderByDescending(group => group.Count())
            .Select(k => new NumberCount(k.Key, k.Count()))
            .ToList();
    }

    private static void Original2(List<int> integers)
    {
        integers?.GroupBy(number => number)
            .Select(k => new NumberCount(k.Key, k.Count()))
            .OrderByDescending(x => x.Occurrences)
            .ToList();
    }

    private static void AsParallel1(List<int> integers)
    {
        integers?.GroupBy(number => number)
            .AsParallel() //each group will be count by a CPU unit
            .Select(k => new NumberCount(k.Key, k.Count())) //Grap result, before sort
            .OrderByDescending(x => x.Occurrences) //sort after result
            .ToList();
    }

    private static void AsParallel2(List<int> integers)
    {
        integers?.AsParallel()
            .GroupBy(number => number)
            .Select(k => new
            {
                Key = k.Key,
                Occurrences = k.Count()
            }) //Grap result, before sort
            .OrderByDescending(x => x.Occurrences) //sort after result
            .ToList();
    }

    private static void AsParallel3(List<int> integers)
    {
        integers?.AsParallel()
            .GroupBy(number => number)
            .Select(k => new NumberCount(k.Key, k.Count())) //Grap result, before sort
            .OrderByDescending(x => x.Occurrences) //sort after result
            .ToList();
    }


    private static void MaxOccurrences1(List<int> integers)
    {
        integers?.AsParallel()
            .GroupBy(number => number)
            .GroupBy(x => x.Count())
            .OrderByDescending(x => x.Key)
            .FirstOrDefault()?
            .ToList()
            .Select(k => new NumberCount(k.Key, k.Count()))
            .ToList();
    }

    private static void MaxOccurrences2(List<int> integers)
    {
        integers?.AsParallel()
            .GroupBy(x => x)//group numbers, key is number, count is count
            .Select(k => new NumberCount(k.Key, k.Count()))
            .GroupBy(x => x.Occurrences)//group by Occurrences, key is Occurrences, value is result
            .OrderByDescending(x => x.Key) //sort
            .FirstOrDefault()? //the first one is result
            .ToList();
    }
    private static void ConcurrentDictionary1(List<int> integers)
    {
        ConcurrentDictionary<int, int> result = new ConcurrentDictionary<int, int>();

        integers?.ForEach(x => { result.AddOrUpdate(x, 1, (key, old) => old + 1); });

        result.OrderByDescending(x => x.Value).ToList();
    }
    private static void ConcurrentDictionary2(List<int> integers)
    {
        ConcurrentDictionary<int, int> result = new ConcurrentDictionary<int, int>();

        integers?.AsParallel().ForAll(x => { result.AddOrUpdate(x, 1, (key, old) => old + 1); });

        result.OrderByDescending(x => x.Value).ToList();
    }

}
public class NumberCount
{
    public int Value;
    public int Occurrences;

    public NumberCount(int value, int occurrences)
    {
        Value = value;
        Occurrences = occurrences;
    }
}

Например, {1,1,2,2,2,3,3,3} должен возвращать 2 и 3 и указывать по 3 вхождения каждого из них.

Random User 10.08.2018 17:43
Ответ принят как подходящий

Различный код более эффективен для разной длины, но поскольку длина приближается к 6 миллионам, этот подход кажется самым быстрым. В общем, LINQ предназначен не для повышения скорости кода, а для улучшения понимания и поддержки, в зависимости от того, как вы относитесь к стилям функционального программирования.

Ваш код довольно быстр и превосходит простые подходы LINQ с использованием GroupBy. Он получает хорошее преимущество от использования того факта, что List.Sort сильно оптимизирован, и мой код также использует это, но в локальной копии списка, чтобы избежать изменения источника. Мой код похож по подходу на ваш, но основан на одном проходе, выполняющем все необходимые вычисления. Он использует метод расширения, который я повторно оптимизировал для решения этой проблемы, под названием GroupByRuns, который возвращает IEnumerable<IGrouping<T,T>>. Он также расширяется вручную, а не возвращается к универсальному GroupByRuns, который принимает дополнительные аргументы для выбора ключа и результата. Поскольку .Net не имеет доступной для конечного пользователя реализации IGrouping<,> (!), Я использовал свой собственный, который реализует ICollection для оптимизации Count().

Этот код работает примерно в 1,3 раза быстрее вашего (после того, как я немного оптимизировал ваш на 5%).

Сначала класс RunGrouping для возврата группы запусков:

public class RunGrouping<T> : IGrouping<T, T>, ICollection<T> {
    public T Key { get; }
    int Count;

    int ICollection<T>.Count => Count;
    public bool IsReadOnly => true;

    public RunGrouping(T key, int count) {
        Key = key;
        Count = count;
    }

    public IEnumerator<T> GetEnumerator() {
        for (int j1 = 0; j1 < Count; ++j1)
            yield return Key;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public void Add(T item) => throw new NotImplementedException();
    public void Clear() => throw new NotImplementedException();
    public bool Contains(T item) => Count > 0 && EqualityComparer<T>.Default.Equals(Key, item);
    public void CopyTo(T[] array, int arrayIndex) => throw new NotImplementedException();
    public bool Remove(T item) => throw new NotImplementedException();
}

Во-вторых, метод расширения на IEnumerable, который группирует прогоны:

public static class IEnumerableExt {
    public static IEnumerable<IGrouping<T, T>> GroupByRuns<T>(this IEnumerable<T> src) {
        var cmp = EqualityComparer<T>.Default;
        bool notAtEnd = true;
        using (var e = src.GetEnumerator()) {
            bool moveNext() {
                return notAtEnd;
            }
            IGrouping<T, T> NextRun() {
                var prev = e.Current;
                var ct = 0;
                while (notAtEnd && cmp.Equals(e.Current, prev)) {
                    ++ct;
                    notAtEnd = e.MoveNext();
                }
                return new RunGrouping<T>(prev, ct);
            }

            notAtEnd = e.MoveNext();
            while (notAtEnd)
                yield return NextRun();
        }
    }
}

Наконец, метод расширения, который находит режимы максимального количества. В основном он проходит через прогоны и ведет запись этих int с текущим самым длинным счетом прогонов.

public static class IEnumerableIntExt {
    public static IEnumerable<KeyValuePair<int, int>> MostCommon(this IEnumerable<int> src) {
        var mysrc = new List<int>(src);
        mysrc.Sort();
        var maxc = 0;
        var maxmodes = new List<int>();
        foreach (var g in mysrc.GroupByRuns()) {
            var gc = g.Count();

            if (gc > maxc) {
                maxmodes.Clear();
                maxmodes.Add(g.Key);
                maxc = gc;
            }
            else if (gc == maxc)
                maxmodes.Add(g.Key);
        }

        return maxmodes.Select(m => new KeyValuePair<int, int>(m, maxc));
    }
}

Учитывая существующий случайный список целых чисел rl, вы можете получить ответ с помощью:

var ans = rl.MostCommon();

Я попробовал ваш код, он замечательный! Linq в 3 раза медленнее вашего кода. но мне интересно, есть ли способ избежать полной сортировки (я имею в виду сортировку полного списка) в методах Linq?

Dongdong 13.08.2018 16:06

@Dongdong Есть, но это будет медленнее, потому что List.Sort - это оптимизированный код C++ и быстрее, чем даже однопроходный код LINQ сам по себе.

NetMage 13.08.2018 19:30

Пока что Netmage - самый быстрый, который я нашел. Единственное, что мне удалось сделать, чтобы превзойти его (по крайней мере, с допустимым диапазоном от 1 до 500000000), будет работать только с массивами от 1 до 500000000 или меньше на моем компьютере, потому что у меня только 8 ГБ ОЗУ. . Это не позволяет мне тестировать его с полным диапазоном от 1 до int.MaxValue, и я подозреваю, что он будет отставать с точки зрения скорости при таком размере, поскольку он, похоже, все больше и больше борется с большими диапазонами. Он использует значения как индексы, а значения в этих индексах как вхождения. С 6 миллионами случайно сгенерированных положительных 16-битных целых чисел это примерно в 20 раз быстрее, чем мой оригинальный метод с обоими в режиме выпуска. Это всего лишь примерно в 1,6 раза быстрее с 32-битными целыми числами от 1 до 500000000.

    private static List<NumberCount> findMostCommon(List<int> integers)
    {
        List<NumberCount> answers = new List<NumberCount>();

        int[] mostCommon = new int[_Max];

        int max = 0;
        for (int i = 1; i < integers.Count; i++)
        {
            int iValue = integers[i];
            mostCommon[iValue]++;
            int intVal = mostCommon[iValue];
            if (intVal > 1)
            {
                if (intVal > max)
                {
                    max++;
                    answers.Clear();
                    answers.Add(new NumberCount(iValue, max));
                }
                else if (intVal == max)
                {
                    answers.Add(new NumberCount(iValue, max));
                }
            }
        }

        if (answers.Count < 1)
            answers.Add(new NumberCount(0, -100)); // This -100 Occurrecnces value signifies that all values are equal.

        return answers;
    }

Возможно, такое ветвление было бы оптимальным:

if (list.Count < sizeLimit) 
    answers = getFromSmallRangeMethod(list);
else 
    answers = getFromStandardMethod(list);

замените int[] mostCommon = new int[_Max]; на Dictionary<int, int> mostCommon = new Dictionary<int, int>();, замените mostCommon[iValue]++; на if(!mostCommon.ContainsKey(iValue)) { mostCommon[iValue] = 1; } else { mostCommon[iValue]++; }

Dongdong 14.08.2018 18:44

Другие вопросы по теме