c# - 从列表中选择所有字符串的最快方法

Question

我正在寻找从一组字符开始查找集合中所有字符串的最快方法。我可以为此使用排序的集合，但是我找不到在 .net 中执行此操作的方便方法。基本上我需要在集合中找到满足条件的低索引和高索引。

List 上的 BinarySearch 不保证返回的索引是第一个元素的索引，因此需要向上和向下迭代以找到所有匹配的字符串，如果列表很大，这并不快。

还有 Linq 方法(并行)，但我不确定哪种数据结构会提供最好的结果。

列表示例，~10M 条记录:

aaaaaaaaaaaaaaabb
aaaaaaaaaaaaaaba
aaaaaaaaaaaaabc
...
zzzzzzzzzzzzzxx
zzzzzzzzzzzzzyzzz
zzzzzzzzzzzzzzzzzza

搜索从以下开始的字符串:skk...

结果:记录从x到y的索引。

更新:字符串可以有不同的长度并且是唯一的。

Answer 1

就时间复杂度而言——您应该使用 trie ，而不是排序集或二进制搜索。

Trie 将为您提供 O(|S|) 的时间复杂度 [而排序集和二进制搜索为您提供 O(|S|logn)] 来找到表示该前缀的节点 [让它成为 v]。

trie 中符合前缀的所有字符串 [路径] 将通过 v“传递”。通过向每个节点添加 numberOfLeaves 字段，您可以准确地找出该节点有多少叶子[=strings]。

在单次传递中 - 您还可以找到此 v 的索引 [对于从根到 v 的路径中的每个节点 u > - 对留给 u 的每个 sibling 求和 numberOfLeaves。

与使用现有结构相比，这需要做更多的工作，但如果数据很大 - 它可以使您的算法大大更快，因此如果性能是个问题并且您希望得到巨大的字符串集。