什么是一组单词的最佳数据结构？

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