☰

有效地 grep 排序文件的间隔

tag-icon • tag-icon shell-script text-processing performance
有效地 grep 排序文件的间隔

我的文件有数百万行，驻留在内存中/dev/shm/tmp.file，由多个线程访问，看起来像这样

831092,25a1bd66f2eec71aa2f0a8bb3d,/path/to/a/file
4324,8d83c29e4d8c71bd66f1bd66fs,/path/to/another/file
...

,并按第二个之后的部分排序sort -t , -k3。一般来说，每行都有形状[0-9]*,[0-9a-z]*,.*，文件路径可以包含除\0或之外的任何字符\n。

我需要尽快提取驻留在给定目录中的所有文件的行，并且无需制作额外的副本。由于文件是以这种方式排序的，因此我正在查找的行是文件的不间断块。

目前我使用，grep -F ',<directory>' /dev/shm/tmp.file但我知道对第一个命中进行二分搜索，然后逐行扩展块或使用另一个二分搜索，而不需要读取每个新行的整个文件，会快得多。然而，这必须集成到 bash 脚本中，而且我发现没有办法在 bash 中执行类似 lseek 的操作。

有sgrep但它需要对完整的行进行排序。

如何以',<directory>'比 更快的速度提取所有匹配项grep -F？

编辑：输入/dev/shm/tmp.file仅用于进行这种提取。因此，以某种方式对其进行预处理以使工作变得更容易是一种选择。

编辑： a.ba和之间的排序a/b不是问题，因为所有子目录都应包含在块中。

答案1

如果你831092,25a1bd66f2eec71aa2f0a8bb3d,/path/to/a/file改为 /path/to/a/file,831092,25a1bd66f2eec71aa2f0a8bb3d

你可以这样做：

look /path/to/ /dev/shm/tmp.file

look是 70 年代的传统 Unix 实用程序，未被 POSIX 指定，但相当常见。在 Debian 及其衍生版本上，您会在软件包中找到一个bsdmainutils，在 util-linux 中也有一个（也是从 BSD 复制的，不在 Debian 软件包中同名）。

look mmap()s 文件并进行二分搜索。

但请注意，Debian 实现将恢复为基本的线性搜索，grep除非您传递该-b选项（叹气）。因此，在 Debian 或衍生版本上，您需要：

look -b /path/to/ /dev/shm/tmp.file

另请注意，某些实现对其可以处理的文件大小有限制（查看 Debian 的相应错误及其补丁）

相关内容