Скорость работы алгоритма на C#

132

18 июля 2019, 21:30

Есть такая задачка простенькая. Подсчитать количество повторений строковых элементов в неотсортированных коллекциях. Коллекции от 200 тыс. элементов.

До этого мало работал с TPL в C#. Реализация работает конечно быстрее однопоточной версии, но всё равно очень долго, около 3 мин. (на 4-х ядерном Core i7)

        List<string> _list = new List<string>();
        Dictionary<string, int> _dictionary = new Dictionary<string, int>();
        Parallel.For(0, _list.Count, i => {
            int cout = 0;
            for (int j = 0; j < _list.Count; j++) {
                if (_list[i] == _list[j]) {
                    cout++;
                }
            }
            lock (_dictionary) {
                if (!_dictionary.TryGetValue(_list[i], out int value)) {
                    _dictionary.Add(_list[i], cout);
                }
            }
        });

Потом переписал с помощью LINQ. Как итог скорость работы около 100 мс.

 var counts = (from note in WordsList
               group note by note into g
               select new { Note = g.Key, Count = g.Count() }).ToDictionary(key => key.Note, val => val.Count);

Вот собственно вопрос. За счет чего такая большая разница в скорости работы?

Answer 1

Ну у Вас же словарь не используется должным образом, а только служит хранилищем.

Приведённый алгоритм квадратичный, поскольку сравнивает все элементы со всеми

Псевдокод со словарём (почти линейный, если словарь - хэш-таблица):

 for (int i = 0; j < _list.Count; i++) 
     if (_dictionary.TryGetValue(_list[i], out int value)) 
           _dictionary.SetValue(_list[i], value + 1);  
    else
         _dictionary.Add(_list[i], 1);