最快的搜索算法

我想实现一个算法来搜索某个记录的多个XML文件。已知记录没有排序（我没有索引编号）。搜索该记录的最快算法是什么？
请让我知道如果有什么是提前最快的搜索算法

来源

2010-07-13 Moayyad Yaghi

当然，它听起来像你应该预处理XML文件，并建立一个索引，以促进快速搜索。 – polygenelubricants 2010-07-13 10:29:16

是的，如果你想搜索一次或多次，这很重要。因为那你可能需要建立一个索引。但是，如果你只搜索一次，这将是无用的。 – galambalazs 2010-07-13 10:32:25

有趣的问题。我想知道我们何时会看到来自Moayyad的一些反馈，特别是关于一次或多次访问的问题？ – 2010-07-13 13:17:23

galambalazs是正确的：未排序的数据意味着你必须要经历这一切寻找你所需要的。但这只是解决问题的一小部分。

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

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

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

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

所需的内存量与文件大小成正比，所以一个大文件可能会让你运行内存不足。
必须从文件内容构建大型数据结构。一次搜索后，它会立即被丢弃。计算和内存资源将最终被浪费。

因此，最推荐的方法是使用SAX解析器。谷歌搜索会找到你一个最喜欢的语言。 SAX解析器扫描您的输入文件一次，在您可以（并且必须）以适当方式处理的每个元素上生成事件。数据是按顺序处理的，除了您决定对所找到的数据做什么以外，没有其他存储空间。 SAX解析器通常比DOM解析器快得多，但需要对如何处理事件进行一些规划。

来源

2010-07-13 10:38:18

另外，可以使用XPath。虽然，实施细节很重要。例如。据我所知，默认的Java XPath实现基于DOM解析器，因此继承了其所有的性能影响。但XPath的表现力如此强烈以至于有时候会超出性能=） – Rorick 2010-07-13 12:29:28

现在您已经提到它了，一种合理且非常“XML-y”的方式可能是使用XSLT将XML输入文档转换为任意输出文档，其中包含只是搜索字符串。这里的吸引力在于，很有可能将Transformer挂接到SAX源，从而确保（可能？）输入只能按顺序处理。这可以让您将用于定义搜索的XPath表达式的表达性与SAX解析的速度结合起来。 – 2010-07-13 13:15:47