Какая лучшая структура данных для набора слов?

Question

У меня есть коллекция из 170 000 слов, и я выполняю на них ряд операций. Наиболее распространенными являются: StartsWith, EndsWith и Contains. Я также много проверяю длину.

Первоначально я хранил эту информацию в List<string>, но затем переключился на HashSet<string>, потому что я думал, что это будет быстрее для данных такого типа.

Основываясь на том, что я описал, является ли HashSet лучшим типом коллекции для этих данных?

Answer 1

A trie - очень хорошая структура данных для хранения строк и выполнения операций поиска текста, в которых вы нуждаетесь. Это структура данных, обычно используемая для индексирования строковых значений для использования в поисковых системах, таких как Lucene

Обычно, когда упоминается, trie описывается как дерево префиксов, что позволяет очень эффективно «начинать с» поиска. Изменение структуры данных очень эффективно при «завершении» поиска.

Возможно, одна и та же реализация trie может использоваться как для префикса, так и для суффиксов деревьев путем простого изменения строк при заполнении trie, а также при поиске trie.

Answer 2

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

Важные вещи, которые следует учитывать при выборе типов коллекций, - это то, как вы работаете со всей коллекцией: вы часто вставляете элементы или часто их удаляете? Вы хотите получить доступ к каждому элементу по порядку или хотите получить доступ к определенной части коллекции чаще. Может ли коллекция иметь повторяющиеся элементы? Вам нужно проверить членство? Имеет ли значение, в каком порядке вы их обрабатываете?

Это те вопросы, которые необходимо ответить, чтобы принять обоснованное решение о разных типах сбора.

Answer 3

Лучшее, вероятно, представляет собой массив строк, поскольку он имеет самые низкие служебные данные, если список статичен.

И затем используйте несколько потоков.

Answer 4

Я предполагаю, что вы пытаетесь найти совпадения, которые StartsWith, EndWith или Contains некоторый поисковый запрос. Если это так, то вы правы в том, что List не идеален. Я не верю, что Hashset лучше.

Проверьте trie. Я бы не построил один, но если даёт некоторый контекст проблемного пространства. Алгоритм включает группировку слов по их исходным словам подстрочной группы на основе их первой буквы, затем подгруппы по второй букве и т. Д.

Когда я это делал в прошлом, я использовал класс Lookup, а также реализовал Dictionary<string, List<string>>.

алгоритм я использовал примерно

var dictionary = new Dictionary<int, Lookup<string, string>>(); 
for (int i = 1; i < maxWordLength; i++) 
{ 
    // get all words with i or more letters 
    dictionary.Add(i, words.ToLookup(w => w.Substring(i))); 
} 

, а затем найти такое слово, как

var word = "TestWord"; 
var matches = dictionary[word.Length][word]; 

Если вам также необходимо EndsWith и Contains вы вероятно, потребуется несколько индексных структур для тех, слишком.

Answer 5

Это звучит как работа для Lucene. Однако, если вы решите реализовать свой собственный алгоритм (что бы это ни было), лучше всего воспользоваться преимуществами мощных параллельных циклов C# в Parallel.ForEach и PLINQ.

Data Parallelism (Task Parallel Library)

Parallel LINQ (PLINQ)

т.е.

var source = Enumerable.Range(100, 20000); 

// Result sequence might be out of order. 
var parallelQuery = from num in source.AsParallel() 
        where num % 10 == 0 
        select num; 

Answer 6

Ран тест и не получил ответ, который я ожидал. List и HashSet и AsParallel о том же (но только двухъядерном компьютере). .NET 4.0 и список из 600 000 слов.

Я повторяю первый комментарий. При сомнительном тестировании. l - List и h - HashSet.

Debug.WriteLine("lWords.Count hWords.Count " + lWords.Count.ToString() + " " + hWords.Count.ToString()); 
Stopwatch SW = new Stopwatch(); 
SW.Restart(); 
Debug.WriteLine("H count " + hWords.Where(value => value.StartsWith("s")).Count().ToString()); 
SW.Stop(); 
Debug.WriteLine("H time " + SW.ElapsedMilliseconds.ToString()); 
SW.Restart(); 
SW.Stop(); 
Debug.WriteLine("Start Stop " + SW.ElapsedMilliseconds.ToString()); 
SW.Restart(); 
Debug.WriteLine("L count " + lWords.Where(value => value.StartsWith("s")).Count().ToString()); 
SW.Stop(); 
Debug.WriteLine("L time " + SW.ElapsedMilliseconds.ToString()); 
SW.Restart(); 
Debug.WriteLine("H count " + hWords.Where(value => value.StartsWith("s")).Count().ToString()); 
SW.Stop(); 
Debug.WriteLine("H time " + SW.ElapsedMilliseconds.ToString()); 
SW.Restart(); 
Debug.WriteLine("L count " + lWords.AsParallel().Where(value => value.StartsWith("s")).Count().ToString()); 
SW.Stop(); 
Debug.WriteLine("L time parallel " + SW.ElapsedMilliseconds.ToString()); 
SW.Restart(); 
Debug.WriteLine("H count " + hWords.AsParallel().Where(value => value.StartsWith("s")).Count().ToString()); 
SW.Stop(); 
Debug.WriteLine("H time parallel " + SW.ElapsedMilliseconds.ToString()); 
Debug.WriteLine(""); 

output: 
lWords.Count hWords.Count 667309 667309 
H count 45851 
H time 283 
Start Stop 0 
L count 45851 
L time 285 
H count 45851 
H time 364 
L count 45851 
L time parallel 307 
H count 45851 
H time parallel 344