什麼是一組單詞的最佳數據結構？

Question

我收集了大約170,000個單詞，並對它們執行了一些操作。最常見的是：StartsWith,EndsWith和Contains。我也做了很多長度檢查。

我原本保存在List<string>這個信息，但後來切換到HashSet<string>，因爲我認爲這種類型的數據會更快。

基於我所描述的那樣，是一個HashSet收集這些數據的最佳類型？

Answer 1

一個trie是用於存儲字符串和執行你所需要的文本搜索操作的很好的數據結構。通常用於索引字符串值的數據結構用於搜索引擎，例如Lucene

通常當提到時，trie被描述爲允許非常高效的'開始'搜索的前綴樹。數據結構的變化在搜索結束時非常有效。

可以想象，同特里的實現可以通過填充線索時，以及搜索線索時，簡單地顛倒字符串用於前綴和後綴樹。

Answer 2

您提到的操作都是在個別元素上完成的，因此他們完全不知道您的元素實際來自何種類型的集合。

考慮與集合類型的重要的事情是在你與整個收集工作什麼方式：你插入的項目很多，或經常清理？您是否想要按順序查看每個元素，還是希望更頻繁地訪問集合中的特定部分？該集合可以重複元素嗎？你需要檢查會員資格嗎？你處理它們的順序有關係嗎？

這些類型的，你需要回答做出不同的集合類型做出明智的決策問題。

Answer 3

最好的可能是一個字符串數組，因爲它具有最低的開銷，如果列表是靜態的。

然後使用多個線程。

Answer 4

我假設您正在嘗試查找StartsWith,EndWith或Contains某些搜索字詞的匹配項。如果是這種情況，那麼你是正確的，List是不理想的。我不相信​​是更好的。

時退房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的工作。但是，如果您決定實現自己的算法（不管可能如何），那麼最好的辦法就是利用Parallel.ForEach和PLINQ中C＃的強大並行循環結構。

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約相同（但只有2個核心機器）。 .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