Gor*_*yle 6 c linux binary-search
这个问题经常在StackOverflow上重复出现,但我已经阅读了所有以前的相关答案,并对问题略有不同.
我有一个包含4.75亿行相同大小的23Gb文件,每行包含一个40个字符的哈希码,后跟一个标识符(一个整数).
我有一个传入的哈希码流 - 总共有数十亿个 - 对于每个传入的哈希码,我需要找到它并打印出相应的标识符.这项工作虽然很大,但只需要完成一次.
该文件太大,我无法读入内存,因此我一直尝试以下列方式使用map:
codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0);
然后我只是根据代码中的地址使用地址算法进行二进制搜索.
这似乎开始工作得很漂亮,并在几秒内产生几百万个标识符,使用100%的cpu,但是经过一些看似随机的时间,它会减慢到爬行的速度.当我使用ps查看进程时,它已使用100%的cpu从状态"R"更改为使用1%cpu的状态"D"(磁盘绑定).
这是不可重复的 - 我可以在相同的数据上再次启动该过程,并且可能在"慢速爬行"发生之前运行5秒或10秒.昨晚一次,在此之前我差不多花了一分钟.
一切都是只读的,我没有尝试任何写入文件,我已经停止了机器上的所有其他进程(我控制).它是一台现代的Red Hat Enterprise Linux 64位机器.
有谁知道为什么这个过程变得磁盘受限以及如何阻止它？
更新:
感谢大家的回答,以及您的想法; 之前我没有尝试过所有各种改进,因为我想知道我是否以某种方式错误地使用了mmap.但答案的要点似乎是,除非我能将所有东西都挤进记忆中,否则我将不可避免地遇到问题.所以我将哈希码的大小压缩到没有创建任何重复项的前导前缀的大小 - 前15个字符就足够了.然后我将生成的文件拉入内存,并分别运行大约20亿个传入的哈希码.
小智 3
首先要做的就是分割文件。
使用散列码创建一个文件，使用整数 ID 创建另一个文件。由于行是相同的，因此在找到结果后它会很好地排列。您还可以尝试一种方法，将每个第 n 个哈希放入另一个文件中，然后存储索引。
例如，将每第 1000 个哈希键放入带有索引的新文件中，然后将其加载到内存中。然后进行二进制扫描。这将告诉您文件中需要进一步扫描的 1000 个条目的范围。是的，这样就可以了！但可能远不止于此。如果我觉得不错的话，大概每 20 条记录左右就会将该文件大小除以 20+。
换句话说，扫描后您只需要接触磁盘上文件的几千字节。
另一种选择是拆分文件并将其放入多台计算机的内存中。然后对每个文件进行二进制扫描。这将在零磁盘访问的情况下产生绝对最快的搜索......