排序的List <string>是否会更快地执行包含

Question

如果我在已排序的简单字符串标签列表上执行Contains()(而不是复杂的句子),它会比随机排序的标签更快地运行吗？如果没有,那么什么是更好的数据结构.我不一定要先在字典中哈希(出于性能原因),但我愿意接受建议

Answer 1

如果你只是排序List<string>,不是.您可以使用List<T>.BinarySearch,但Contains不会为您执行此操作,因为它并不真正"知道"您的列表已排序.散列它们只是为了性能 - HashSet<T>可能是你最好的选择 - Contains假设你没有遇到哈希冲突,它将具有O(1)性能.

您可以SortedSet<T>在.NET 4中使用,它基本上是一个排序列表 - 您将获得O(log n)性能,但这不需要哈希计算,如果您的字符串非常长,这可能会加快速度.(当然,您需要进行基准测试以确定.)这大致相当于"排序然后使用二进制搜索"方法,但不依赖于您手动执行操作.

SortedList<,>而SortedDictionary<,>如果你只使用.NET 2,但最好你应该使用一组,如果你并不需要一个键/值映射,你不关心顺序也可提供.