搜索列表<string>表示字符串.StartsWith()

Question

我有一个

List<string>

有1500个字符串.我现在使用以下代码仅提取以字符串prefixText开头的字符串.

foreach(string a in <MYLIST>)
{            
    if(a.StartsWith(prefixText, true, null))
    {
        newlist.Add(a);                   
    }            
}

这很快,但我正在寻找谷歌快速.现在我的问题是,如果我按字母顺序排列List,然后比较char by char我可以加快速度吗？或者其他任何有关加快速度的建议？

Answer 1

因此,1500实际上并不是一个庞大的数字二进制搜索排序列表就足够了.然而,用于前缀搜索的最有效算法基于名为Trie或Prefix Tree的数据结构.见:http://en.wikipedia.org/wiki/Trie

下图简要介绍了这个想法:

对于c#实现,请参阅例如用于前缀字符串搜索的.NET数据结构和子站点(INFIX)搜索实现自动完成和INTELLI-SENSE

Answer 2

1500 通常太少：

• 您可以通过简单的分治问题来并行搜索它。在两个（或分为三个、四个……部分）不同的作业/线程中搜索列表的每一半。

• 或者将字符串存储在（非二叉）树中。将为 O(log n)。

• 按字母顺序排序，您可以进行二分搜索（与前一个相同）