从列表中选择所有字符串的最快方式

本文关键字：方式 字符串 列表 选择 | 更新日期: 2023-09-27 18:25:23

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

BinarySearch on List<T>不能保证返回的索引是第一个元素的索引，因此需要上下迭代才能找到所有匹配的字符串，如果列表很大，这就不快了。

还有Linq方法（具有并行），但我不确定哪种数据结构将提供最佳结果。

列表示例，约1000万条记录：

aaaaaaaaaaaaaaabb
aaaaaaaaaaaaaaba
aaaaaaaaaaaaabc
...
zzzzzzzzzzzzzxx
zzzzzzzzzzzzzyzzz
zzzzzzzzzzzzzzzzzza

搜索从以下位置开始的字符串：skk。。。

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

UPDATE：字符串可以有不同的长度并且是唯一的。

从列表中选择所有字符串的最快方式

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

Trie会给你一个O(|S|)时间复杂度[而排序集和二进制搜索会给你O(|S|logn)]来找到代表该前缀的节点[让它是v]。

trie中符合前缀的所有字符串[paths]都将通过v"传递"。通过向每个节点添加numberOfLeaves字段，您可以准确地了解该节点有多少剩余[=string]。

在一次遍历中，您还可以找到该v的索引[对于从根到v的路径中的每个节点u-对于留给u的每个同级节点求和numberOfLeaves]。

与使用现有结构相比，这需要做更多的工作，但如果数据量很大，它可以使您的算法更快，因此，如果性能是一个问题，并且需要大量字符串，则应该对其进行协调。

你可以用手写的二进制搜索来完成这项工作——当找到匹配项时，它不会停止；它一直持续到找到一个索引为止。

事实上，你甚至不必自己编写二进制搜索位——你可以创建一个自定义比较器，永远不会返回0，即如果你在寻找"abc"，它会将"abb"视为低于目标值，而将"abc"视为高于目标值。这样，BinarySearch将始终返回一个负数，然后您可以对其进行位翻转，以找到"abb和abc之间的字符串"的理论插入点。

您可以反向执行相同的操作（将"abc"视为低于目标值）以找到最高界限。

如果你知道这些字符串的格式，并且它不会像Unicode NULL字符那样有边缘大小写，并且所有字符串的长度都相同，你甚至可以在不编写自己的比较器的情况下完成它：

// This could be done more efficiently :)
string stringJustBelow = target.Substring(0, target.Length - 1) +
                         target[target.Length - 1] + "X";
string stringJustAbove = target + "X"; // Or any character
int lowerBoundInclusive = ~list.BinarySearch(stringJustBelow);
int upperBoundExclusive = ~list.BinarySearch(stringJustAbove);

所以，如果字符串的长度都是3，并且你在搜索"abc"，你实际上会寻找"abbX"answers"abcX"的插入位置。

将它们放入SortedSet并使用GetViewBetween。

这个答案说明了搜索前缀和后缀，我相信如果这确实是你想要的，你会很容易将其调整为只搜索前缀。

如果您只想搜索一个范围（而不是前缀），那么直接使用GetViewBetween就足够了。

相关文章：