在C/C++中查找大数据文件

通过只在哈希表中存储哈希值和文件偏移量,可以减小哈希表的大小。如果属性只有一个固定的、相对较少的值,那么您更有可能在内存中容纳整个哈希表。为属性的每个可能值分配一个ID,然后为每个ID值存储一个文件偏移量的大列表。

当然,只有在程序的同一个运行过程中,您执行几个不同的搜索时,哈希表才有帮助。

显而易见的解决方案是将数据填充到数据库中,但我假设OP足够聪明,已经意识到这一点,并且有其他原因专门请求非数据库解决方案来解决该问题。

如果你只搜索一次,你就不能做得比O(N)更好。

如果散列索引太大,无法放入内存,请使用类似磁盘上散列的 dbm 或 gdbm .

编辑 :我想指出的是,Keithb建议的伯克利数据库工具在磁盘哈希表上属于这个类别。伯克利数据库不是使用关系数据库的SQL。

您可以使用Berkley数据库为这个文件编制索引。基本上,检查整个文件一次,对于找到的每个属性,存储属性的文件位置。BerkleyDB使用一个高效的B树实现,不需要将整个索引存储在内存中,只需要存储所需的部分。 我以前做过,而且很成功。

听起来像是数据库系统的工作。

如何在不同属性上索引整个文件?

您真的不需要在引擎盖下实现一个DB解决方案。您最好的选择可能是一些离线搜索算法和维护索引文件。

你也可以找到 Map-Reduce 感兴趣的

对于直接搜索可变长度行的文本文件,没有有效的方法。最有效的方法需要一个开销来将数据转换成更适合于更有效搜索方法的形式。对于不经常进行的搜索,这种开销可能不值得。

不经常搜索

如果文件只被搜索一次或不是很频繁,我建议一个强力逐行搜索。其他方法可能会浪费时间设置数据以便更快地进行搜索。例如,使用程序查找包含一个或多个属性的第一行。

频繁搜索

该程序需要多次搜索该文件。在这种情况下,您可能希望设置一些数据结构以更好地进行搜索。一种技术是创建索引文件。这些文件包含属性的文件位置,按属性排序。像[属性][第一次发生][第二次发生]等。

另一种选择是让程序将文件转换为更好的工具可以使用的格式,例如电子表格或数据库。一个例子是逗号分隔的值,或者一些工具喜欢用“”分隔值。

更换发电机

然而,生成日志文件的程序可以更改为生成电子表格或数据库友好的日志文件。我用一个嵌入式系统做了这个。我将数据输入电子表格,并使用电子表格功能分析数据。写一个程序来搜索(和分析)日志文件要容易得多。

在一个单独的线程中进行搜索,可能需要一段时间,但我认为在这种情况下,先构建哈希表,然后再搜索哈希表是不值得的。

如果用户反复搜索不同的属性, 可以 值得一段时间,但我怀疑。

对于搜索尝试 boost::regex 或 QRegExp .

对于只搜索日志文件,我认为您可能用数据库或哈希表过度工程了这一点。

我将使用B树或哈希表构建索引。我将把索引存储在磁盘上。如果您控制此文件的更新,则也可以在文件更新时更新索引。如果您不控制更新,则使用文件的哈希来确定是否需要重新生成该文件。

考虑到这一点,我意识到我通常在命令行上使用grep搜索600K+行(100M)的日志文件。它相当快。所以,我不认为100K是一个问题,除非你的文件有更多的数据。

如果日志文件越来越大,您可能还需要研究使用日志旋转。

您可以尝试对文件进行直接的线性搜索,但启动一个工作线程来进行搜索。这样,您就可以生成多个工作线程,并在文件中的不同点启动它们。在具有多个处理器/内核的机器上,这种并行性应该能够在简单的单线程线性搜索上提高性能。

执行搜索后,您可能希望将输入参数和搜索结果存储在数据文件中。这样,如果以后重复搜索,则可以使用此缓存数据,并且只需搜索自上次搜索以来修改的文件部分。

别担心。只需扫描一下。

说真的。你说这个文件有100k行,实际上几乎和我输入这个文件的计算机上的/var/log/messages大小完全相同。好吧,这是一个上网本,也就是说,按现代标准来说,速度非常慢——然而,我的/var/log/messages的一个直接grep速度非常快,与将结果打印到屏幕上所花费的时间相比,就显得相形见绌了。

所以我真的不认为你有什么需要担心的——特别是如果这是一个只在人类需要的时候运行搜索的交互进程,而不是一些守护进程,它们可能会不断地在后台搜索东西。您可能已经浪费了更多的时间来担心这个问题,这比实现一个索引所能节省的时间还多!

来吧,说真的。日志文件的数据库?

日志文件随时或至少每天都在更改。所以你真正想要的可能是做一些日志文件旋转,其中有很多预谋和失败,可以在几个小时内完成,如果你知道一点Perl的话。你可能也不需要C++。它只会使开发时间变慢,最终结果更糟。