快速关键字查找

这是正确的答案。他坚持认为数据实际上是不相关的。正确的问题是用于快速查找的最佳内存数据结构是什么？如果数组被排序以便可以使用二分搜索（现在我们是'O（log n）'，其中'n'是关键字的数量），那么数组就很好。如果这个速度不够快（在分析后！）可以考虑一个线索。 – jason 2009-11-25 02:07:46

是的，这是迂腐的...但是，不是一组字符串的二进制搜索真的O（log（N）* log（K））其中N是单词的数量，K是中位数字长度？ – 2009-11-25 04:00:05

最糟糕的情况是'O（m log n）'，其中'm'是最大字长，'n'是关键字的数量。 – jason 2009-11-25 14:32:52

硬编码列表速度更快。数据库命中检索列表无疑比从内存中抽取列表要慢。

至于哪个数据类型存储的值，一个数组可能会更快，并占用较少的内存比列表，但平凡如此。

来源

2009-11-25 01:57:35

如果在从数据库初始检索（启动时）后进行本地高速缓存，则不适用。 – jason 2009-11-25 02:00:28

@Jason - 对于后续匹配为真。不过，第一次击中会更慢。 – 2009-11-25 02:01:37

@凯文庞：第一击是无关紧要的。 – jason 2009-11-25 02:04:13

如果列表大部分是静态的，并且您可以花费一些时间准备（即在应用程序启动时），那么您最好将关键字列表存储在文本文件中，然后使用说B *树在内部存储关键字（假设你只关心精确匹配而不是部分匹配或Levenshtein距离）。

来源

2009-11-25 01:57:37

如果他正在进行即时插入和删除操作，那么B * -tree很好，但对于静态列表来说，已排序的数组很好。 B *树的复杂性与已排序数组相比没有什么优势。 – jason 2009-11-25 02:05:32

一棵B *树不一定是正确的答案，但是我在一个排序的数组上提出了一个树结构的原因是搜索的速度。搜索树是O（log N），而搜索一个数组（甚至是一个排序的）是O（N）。 – 2009-11-25 02:09:58

我在哪里可以阅读更多关于部分匹配或Levenshtein距离的内容？可能需要稍后使用 – program10 2009-11-25 02:11:46

IMO，如果列表没有经常更新，请将其存储在文件（text/xml）中，然后将其缓存到应用程序中，以便下一次请求更快。

来源

2009-11-25 02:01:59 jerjer

+1 - 这是使用缓存的理想情况。看看http://stackoverflow.com/questions/1308354/asp-net-caching-vs-static-variable-for-storing-a-dictionary – CoderHawk 2009-11-25 04:00:02

好，响应你的编辑（基本上解除我的评论到一个答案）：

事先指定你期望的性能。
将您的应用程序编码为排序后的数组，并使用二进制搜索在数组中搜索关键字。这是非常简单的实施，并提供体面的表现。然后通过配置文件查看它是否符合您的要求。如果这种表现可以接受，继续前进。这里最糟糕的表现是，其中n是关键字的数量，m是关键字的最大长度。
如果步骤2中的性能不可接受，请使用trie（也称为前缀树）。这里预期的性能是m，其中m是您的关键字的最大长度。配置文件以查看这是否符合您的预期性能。如果没有，请重新审视您的绩效标准;他们可能是不合理的。如果你仍然不符合你的性能规范，考虑使用散列表（在.NET中你会使用HashSet<string>。虽然散列表会有更差的最差情况下的性能，但它可以有更好的平均情况下的性能（如果有的话）没有冲突的哈希表查找是O(1)而散列计算功能O(m)其中m是关键字的最大长度），这可能会更快（平均），但可能不会显着如此。

你甚至可能考虑直接跳到最后一步（因为它比前者简单），这一切都取决于哟你的需求。例如，尝试可以轻松地吐出最接近的匹配关键字。

这里重要的是要有你的性能要求和配置文件的规范！使用最简单的实现来满足你的性能要求（为了可维护性，可读性和可执行性（如果不是这样，现在这是一个词））

来源

2009-11-25 02:30:27 jason

感谢您的详细回复。 Im新的c＃和我只是写了一个reg exp“wordA | wordB | word \ sC这个用2000个单词就足够快了吗？你介意为你提到的方法提供一些示例代码吗？我仍然在学习。谢谢 – program10 2009-11-25 08:41:40

不要使用这样的正则表达式，它不是正确的工具，并且维护一个硬编码的正则表达式字符串就像是一场噩梦。 – jason 2009-11-25 13:36:57

快速关键字查找

回答

相关问题