shell - 按行上的字数对海量文件的行进行排序(最好是并行的)

Question

我正在研究用于分析来自 Facebook 的社交网络数据的社区检测算法。第一个任务，检测图中的所有派系，可以并行高效地完成，并给我留下这样的输出:

17118 17136 17392
17064 17093 17376
17118 17136 17356 17318 12345
17118 17136 17356 17283
17007 17059 17116

这些行中的每一行都代表一个独特的集团(节点 id 的集合)，我想按照每行 id 的数量降序对这些行进行排序。在上面的例子中，输出应该是这样的:

17118 17136 17356 17318 12345
17118 17136 17356 17283
17118 17136 17392
17064 17093 17376
17007 17059 17116

(关系---即具有相同 id 数量的行---可以任意排序。)

对这些行进行排序的最有效方法是什么。

请记住以下几点:

我要排序的文件可能大于机器的物理内存

我运行它的大多数机器都有多个处理器，所以 并行解决方案将是理想的

一个理想的解决方案就是一个 shell 脚本 (可能使用 sort )，但我对 Python 或 perl(或任何语言，只要它使任务简单)的简单解决方案持开放态度

从某种意义上说，这项任务非常简单---我不只是在寻找任何旧的解决方案，而是寻找一个简单且最重要的高效解决方案

更新 2:最佳解决方案

基于对提出的解决方案进行基准测试(见下文)，这里是最佳解决方案(取自 Vlad，他又从此处提出的其他解决方案中进行了调整)。它非常聪明，甚至不使用排序

for FILE in infile.* ; do
  awk '{ print >sprintf("tmpfile.%05d.%s", NF, FILE) }' \
    FILE=`basename $FILE` $FILE&
done
wait
ls -1r tmpfile.* | xargs cat >outfile
rm -f tmpfile.*

更新 1:建议解决方案的基准测试结果

对于基准测试，我采用了在俄克拉荷马州 Facebook 网络中发现的 Cliques。包含这些派系的未排序文件看起来就像我上面展示的第一个示例，包含 46,362,546 行，这使文件大小高达 6.4 GB。这些派系几乎均匀分布在 8 个文件中。我正在测试的系统包含 4 个物理处理器，每个处理器有 6 个内核和一个 12MB 二级缓存，总共有 24 个内核。它还包含 128 GB 物理内存。由于要排序的行被拆分为 8 个文件，因此这些解决方案中的大多数都使用了 8 个(或 16 个)并发进程。

忽略第一个幼稚的方法，我对 Vlad Romascanu 的最后 5 条建议(我选择的解决方案)进行了基准测试。

第一个解决方案效率不高:

real    6m35.973s
user    26m49.810s
sys     2m14.080s

我尝试使用使用 FIFO 文件的解决方案 2、3 和 4，但它们每个只使用一种排序过程，因此需要很长时间(因此我在它们完成之前杀死了它们)/

最后一个解决方案是最快的:

real    1m3.272s
user    1m21.540s
sys     1m22.550s

请注意，此解决方案的用户时间为 1m21s，比第一个解决方案的 26 分钟要好得多。

Answer 1

A 天真的方法可能很简单:

awk '{ print NF " " $0 }' infile| sort -k1,1nr |
 awk '{ $1=""; print $0 }' >outfile

这将使最多 3 个 CPU 保持忙碌。 sort不受可用物理内存量的限制，使用 -S和 -T切换到配置要使用多少内存( -S )，然后再诉诸临时目录( -T )中足够大(理想情况下是快速)分区上的临时文件。

如果可以生成多个输入文件 通过分割导致排序阶段的工作，您将能够执行以下操作:

for FILE in infile.* ; do
  awk '{ print NF " " $0 }' $FILE | sort -k1,1nr >$FILE.tmp&
done
wait
sort -k1,1nr -m infile.*.tmp | awk '{ $1=""; print $0 }' >outfile
rm -f infile.*.tmp

这将使用最多 N*2 CPU；此外，最后一种排序(合并排序)非常高效。

进一步细化以提高与 N*2+1 的并行性通过使用 FIFO 而不是中间文件，再次假设多个输入文件是可能的:

for FILE in infile.* ; do
  mkfifo $FILE.fifo
  awk '{ print NF " " $0 }' $FILE | sort -k1,1nr >$FILE.fifo&
done
sort -k1,1nr -m infile.*.fifo | awk '{ $1=""; print $0 }' >outfile
rm -f infile.*.fifo

如果多个输入文件不可用 ，您可以 模拟它们 (添加 I/O 开销，这有望通过可用进程的数量进行摊销):

PARALLELISM=5 # I want 5 parallel instances
for N in `seq $PARALLELISM` ; do
  mkfifo infile.$N.fifo
  awk 'NR % '$PARALLELISM'=='$N' { print NF " " $0 }' infile |
    sort -k1,1nr >infile.$N.fifo&
done
sort -k1,1nr -m infile.*.fifo | awk '{ $1=""; print $0 }' >outfile
rm -f infile.*.fifo

因为我们使用模行数，所以我们有很好的局部性，理想情况下，文件系统缓存应该带来在 $PARALLELISM 中一遍又一遍地读取输入文件的成本。过程接近于零。

更好 , 只读取输入文件一次，并将输入行循环成几行 sort管道:

PARALLELISM=5 # I want 5 parallel instances
for N in `seq $PARALLELISM` ; do
  mkfifo infile.$N.fifo1
  mkfifo infile.$N.fifo2
  sort -k1,1nr infile.$N.fifo1 >infile.$N.fifo2&
done
awk '{ print NF " " $0 >("infile." NR % '$PARALLELISM' ".fifo1") }' infile&
sort -k1,1nr -m infile.*.fifo2 | awk '{ $1=""; print $0 }' >outfile
rm -f infile.$N.fifo[12]

您应该测量 $PARALLELISM 的各种值的性能然后选择最佳的。

编辑

如其他帖子所示，您当然可以使用 cut而不是最后的 awk (即剥离第一列)以提高效率。 :)

编辑2

更新了您提供的文件名约定的所有脚本，并修复了上一版本中的错误。

此外，使用新的文件名约定，如果 I/O 不是瓶颈，那么 dave 上的细微变化/niry的解决方案可能应该更有效:

   for FILE in infile.* ; do
     awk '{ print >sprintf("tmpfile.%05d.%s", NF, FILE) }' \
       FILE=`basename $FILE` $FILE&
   done
   wait
   ls -1r tmpfile.* | xargs cat >outfile
   rm -f tmpfile.*