更快速搜索 C# List<String> 中的子字符串方法

Question

我目前有一个名为regkey的列表和一个名为line_to_delete的字符串，我显然想从列表中删除它。目前，我正在逐个搜索列表的一个元素，创建子字符串，因为line_to_delete仅表示我要删除的行的一部分，但在列表中是唯一可识别的。

无论如何，我真正需要做的是使这更有效率，使用更少的资源并更快速，那么有没有办法做到这一点呢？

- manemawanna

Answer 1

如果是List<string>，请使用lambda表达式：

list.RemoveAll(x => x.Contains(line_to_delete));

- Jamie Ide

---

是的，但由于 OP 在子字符串上进行匹配，我认为 SortedList 不会有帮助。 - Jamie Ide

真的，但你需要在其中使用二叉树，并且可以在现有树上自己实现二分查找。这并不难，这样你就可以获得O(log(n))的时间复杂度。 - mfeingold

我没有完全考虑清楚这件事，但也许你甚至可以捏造一个比较器来与标准的BinarySearch方法一起使用，这样就不必自己实现了。 - mfeingold

据我所知，大多数排序算法通常需要O(n*log(n))的时间复杂度，而二分查找则需要一个已排序的列表。 - Chansik Im

@Chansik 这是正确的，但你只需要对它进行一次排序。 - mfeingold

Answer 2

您最好对列表进行排序并使用二分搜索。SortedList可以为您完成这项工作。这样，您可以获得O(log(n))的性能。

- mfeingold

---

List<T> 还有一个 BinarySearch 方法：http://msdn.microsoft.com/zh-cn/library/3f90y839.aspx - Powerlord

不，这完全没有帮助，因为OP正在寻找匹配的子字符串。 - Konrad Rudolph

排列列表的成本如何？ - Chansik Im

Answer 3

        List<String> regKey = new List<String> { "test1", "test2" };
        var toDelete = regKey.Where(u => u.Contains(line_to_delete)).SingleOrDefault();
        if (toDelete != null)
            regKey.Remove(toDelete);

或者

regkey.RemoveAll(k => k.Contains(line_to_delete));

这将使您的删除操作更易读，但我不确定与您当前方法相比性能如何。

- Michael G

Answer 4

最简单的方法是使用：

var result = list.Where(x => !x.Contains(line_to_delete))

首先，请确保这种方式并不高效。如果不是，您需要采用高级数据结构来表示字符串，例如trie。在C#中没有原生支持这样的数据结构。

- Konrad Rudolph

Answer 5

我认为使用indexOf比使用contains更好，因为它可以加快搜索速度。

所以应该使用：

regkey.RemoveAll(k => k.IndexOf(line_to_delete) >=0);

- Rohit Gupta