2

我收集了大约 170,000 个单词，并对它们执行了许多操作。最常见的是：StartsWith、EndsWith和Contains。我也做了很多长度检查。

我最初将这些信息存储在 a 中，List<string>但后来切换到 a HashSet<string>，因为我认为这种类型的数据会更快。

根据我所描述的，HashSet 是该数据的最佳集合类型吗？

4

6 回答 6

5

trie是一种非常好的数据结构，用于存储字符串和执行所需的文本搜索操作。它是常用于索引字符串值的数据结构，用于搜索引擎，例如 Lucene

通常在提到时，trie 被描述为允许非常有效的“开始于”搜索的前缀树。数据结构的后缀树变体在“结束于”搜索时非常有效。

可以想象，相同的 trie 实现可以用于前缀树和后缀树，只需在填充 trie 以及搜索 trie 时反转字符串即可。

于 2012-07-02T03:14:18.773 回答
2

您提到的操作都是在集合的各个元素上完成的，因此他们完全不知道您的元素实际上来自什么类型的集合。

集合类型要考虑的重要事项是您以何种方式处理整个集合：您是插入很多项目还是经常删除它们？您想按顺序获取每个元素，还是想更频繁地访问集合的特定部分。集合可以有重复的元素吗？您需要检查会员资格吗？你处理它们的顺序有关系吗？

这些是您需要回答的问题类型，以便对不同的馆藏类型做出明智的决定。

于 2012-07-02T02:42:28.970 回答
2

我假设您正在尝试查找匹配 whichStartsWith或EndWith某些Contains搜索词。如果是这种情况，那么您是正确的，因为这List并不理想。我不相信Hashset会更好。

检查特里。我不会建立一个，但如果给出有关问题空间的一些上下文。该算法涉及按单词的初始子字符串对单词进行分组——根据单词的第一个字母对单词进行分组，然后按第二个字母对单词进行分组，依此类推。

当我过去这样做时，我既使用了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您可能也需要一些索引结构。

于 2012-07-02T03:17:14.410 回答
1

这听起来像是Lucene的工作。但是，如果您决定实现自己的算法（无论是什么算法），那么最好的办法是利用 C# 在 Parallel.ForEach 和 PLINQ 中强大的并行循环结构。

数据并行（任务并行库）

并行 LINQ (PLINQ)

IE

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;
于 2012-07-02T03:42:28.700 回答
0

最好的可能是字符串数组，因为如果列表是静态的，它的开销最低。

然后使用多个线程。

于 2012-07-02T02:48:30.503 回答
0

跑了一个测试，并没有得到我期望的答案。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
于 2012-07-03T17:31:09.093 回答