最快搜索算法

Question

我正在尝试实现一个算法来搜索多个XML文件中的某个记录。知道记录没有排序(我没有索引的id)。搜索该记录的最快算法是什么？

如果有什么不清楚的地方，请告诉我

提前感谢

Answer 1

galambalazs是正确的:未排序的数据意味着你必须遍历所有这些数据来搜索你需要的东西。但这只解决了问题的一小部分。

在处理多个文件时，您的大部分处理时间可能会被文件I/O占用。按照计算机标准，在目录中找到一个文件并打开它需要很长时间。但这是一个成本，您将招致基本上无论您最终使用哪个程序。

性能等式的另一部分是您使用的解析器的类型。根据XML的结构，您可以选择使用手工编写的解析器、DOM XML解析器或Sax解析器。

如果搜索数据周围的标记始终出现在与该数据相同的行上，并且不可能有歧义，那么逐行读取文件并通过字符串搜索或regexp进行搜索是一种有效的可能性。因此，许多人会抗议正则表达式匹配是一种可怕的处理XML的方法，这通常是正确的；它是在非常特定和有限的情况下执行搜索的一种快速而肮脏的方法，并且对于您最终要使用的XML结构来说非常脆弱。

DOM解析器将整个XML文档“吸入”到一个内存结构中，然后您的应用程序就可以按顺序搜索它。当您想要在XML树上执行许多复杂操作时，DOM是很好的；对于顺序搜索，它们是一个可怕的想法，因为

• 所需的内存量与文件大小成正比，因此大型文件可能会耗尽内存。
• 必须从文件内容构建大型数据结构。搜索一次后，它将立即被丢弃。计算和内存资源最终将被浪费。

因此，最推荐的方法是使用SAX解析器。谷歌会为你找到你最喜欢的语言。SAX解析器只扫描一次您的输入文件，在您可以(也必须)的每个元素上生成事件。以适当的方式进行处理。数据是按顺序处理的，除了您决定要对找到的数据执行的操作之外，没有其他存储。SAX解析器通常比DOM解析器快得多，但是需要对如何处理事件稍加规划。

Answer 2

你需要决定的一切都在这里，Sorting Algorithms

Answer 3

在没有排序的情况下，线性搜索是你最好的选择。想想看。

正如我在评论中所说:如果你想搜索一次或多次，这很重要。因为你可能需要建立一个索引。但如果你只搜索一次，这将是无用的。