Как повысить производительность этого алгоритма?

Ответ 1

• Замените словарь на List<KeyValuePair<string, decimal>>, отсортированный по клавише.

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

  int startIndex = dictionary.BinarySearch(searchWord, comparer);
  if(startIndex < 0)
      startIndex = ~startIndex;
  
  var adviceWords = dictionary
              .Skip(startIndex)
              .TakeWhile(p => p.Key.StartsWith(searchWord, StringComparison.Ordinal))
              .OrderByDescending(ks => ks.Value)
              .ThenBy(ks => ks.Key)
              .Select(s => s.Key)
              .Take(10).ToList();
  

• Обязательно используйте порядковое сравнение для всех операций, включая начальную сортировку, двоичный поиск и проверку StartsWith.

• Я бы назвал Console.ReadLine вне параллельного цикла. Вероятно, используя AsParallel().Select(...) в наборе слов поиска вместо Parallel.For.

Ответ 2

Вы совсем не используете какую-либо алгоритмическую силу словаря. В идеале вы должны использовать древовидную структуру, чтобы вы могли выполнять поиск в префиксах. С другой стороны, вы в пределах 3.7x от своей производительности. Я думаю, вы можете достичь этого, просто оптимизируя постоянный коэффициент в вашем алгоритме.

• Не используйте LINQ в первичном критическом коде. Ручная петля по всем коллекциям и сбор результатов в List<T>. Это, оказывается, дает значительное ускорение на практике.
• Не используйте словарь вообще. Просто используйте KeyValuePair<T1, T2>[] и пропустите его, используя цикл foreach. Это самый быстрый способ пересечения набора пар.

Может выглядеть так:

KeyValuePair<T1, T2>[] items;
List<KeyValuePair<T1, T2>> matches = new ...(); //Consider pre-sizing this.

//This could be a parallel loop as well.
//Make sure to not synchronize too much on matches.
//If there tend to be few matches a lock will be fine.
foreach (var item in items) {
 if (IsMatch(item)) {
  matches.Add(item);
 }
}

matches.Sort(...); //Sort in-place

return matches.Take(10); //Maybe matches.RemoveRange(10, matches.Count - 10) is better

Это должно превысить ускорение 3,7 раза.

Если вам нужно больше, попробуйте наполнить элементы в словарь, введенный в первый char из Key. Таким образом, вы можете найти все элементы, соответствующие tempInputWord[0]. Это должно сократить время поиска за счет селективности, которая находится в первом char of tempInputWord. Для текста на английском языке это будет порядка 26 или 52. Это примитивная форма поиска в префиксе, которая имеет один уровень поиска. Не очень, но, возможно, этого достаточно.

Ответ 3

Я думаю, что лучшим способом было бы использовать структуру данных Trie вместо словаря. Структура данных Trie сохраняет все слова в древовидной структуре. A node может представлять все слова, начинающиеся с одних и тех же букв. Итак, если вы ищете поисковое слово tempInputWord в Trie, вы получите node, который представляет все слова, начинающиеся с tempInputWord, и вам просто нужно пройти через все дочерние узлы. Таким образом, у вас есть только одна операция поиска. Ссылка на статью в Википедии также упоминает некоторые другие преимущества по сравнению с хэш-таблицами (что в основном словарь):

• Поиск данных в trie быстрее в худшем случае, O (m) время (где m - длина строки поиска), по сравнению с несовершенной хеш-таблица. У несовершенной хеш-таблицы могут быть ключевые коллизии. Ключ collision - это хеш-функция, отображающая различные ключи для одного и того же положение в хеш-таблице. Наихудшая скорость поиска в несовершенном хэш-таблица - это время O (N), но более типично O (1), с O (m) время, потраченное на оценку хэша.
• В trie нет столкновений разных ключей.
• Ведра в trie, которые аналогичны хэш-табличным ковшим, которые хранят ключевые коллизии, необходимы только в том случае, если один ключ связанных с более чем одним значением.
• Нет необходимости предоставлять хеш-функцию или изменять хеш-функции, так как в trie добавлено больше ключей.
• Trie может обеспечить алфавитное упорядочение записей с помощью ключа.

И здесь есть некоторые идеи для создания trie в С#.

Это должно, по крайней мере, ускорить поиск, однако создание Trie может быть медленнее.

Update: Хорошо, я сам тестировал его, используя файл с частотами английских слов, который использует тот же формат, что и ваш. Это мой код, который использует класс Trie, который вы также пытались использовать.

    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();

        sw.Start();
        var trie = new Trie<KeyValuePair<string,int>>();

        //build trie with your value pairs
        var lines = File.ReadLines("en.txt");
        foreach(var line in lines.Take(100000))
        {
            var split = line.Split(' ');
            trie.Add(split[0], new KeyValuePair<string,int>(split[0], int.Parse(split[1])));
        }

        Console.WriteLine("Time needed to read file and build Trie with 100000 words: " + sw.Elapsed);

        sw.Reset();

        //test with 10000 search words
        sw.Start();
        foreach (string line in lines.Take(10000))
        {
            var searchWord = line.Split(' ')[0];
            var allPairs = trie.Retrieve(searchWord);
            var bestWords = allPairs.OrderByDescending(kv => kv.Value).ThenBy(kv => kv.Key).Select(kv => kv.Key).Take(10);

            var output = bestWords.Aggregate("", (s1, s2) => s1 + ", " + s2);
            Console.WriteLine(output);

        }

        Console.WriteLine("Time to process 10000 different searchWords: " + sw.Elapsed);
    }

Мои результаты на довольно похожей машине:

Время, необходимое для чтения файла и сборки Trie с 100000 словами: 00: 00: 00.7397839
Время обработки 10000 различных поисковых слов: 00: 00: 03.0181700

Итак, я думаю, что вы делаете что-то неправильно, чего мы не можем видеть. Например, как вы измеряете время или способ чтения файла. Как показывают мои результаты, этот материал должен быть очень быстрым. 3 секунды в основном связаны с выходом Консоли в цикле, который мне нужен, чтобы использовать переменную bestWords. В противном случае переменная была бы оптимизирована.

Ответ 4

Если вы хотите профилировать, отделите чтение файла и посмотрите, сколько времени потребуется. Также вычисление, сбор, представление могут быть разными.

Если вы хотите совпадение И словарь, посмотрите на ConcurrentDictionary, возможно, даже больше на надежность, чем на производительность, но, вероятно, для обоих:

http://msdn.microsoft.com/en-us/library/dd287191(v=vs.110).aspx

Ответ 5

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

Этот метод лучше всего подходит для небольших значений. Если вам нужно было взять первые 5000 объектов, рассмотрите возможность использования двоичной кучи вместо списка.