按行数(理想情况下并行)对大量文件行进行排序

我正在研究社区检测算法,用于分析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

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

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

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

请注意,此解决方案的用户时间为1分21秒,比第一个解决方案26分钟好得多.

一种天真的方法可能很简单:

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*2CPU; 而且,最后一种排序(merge-sort)非常高效.

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(即剥离第一列)以获得更高的效率.:)

EDIT2

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

此外,使用新的文件名约定,如果I/O不是瓶颈,那么/ 或解决方案的一个非常小的变化daveniry应该更有效:

   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.*

我想知道这会有多快:

#!/bin/sh
rm -rf /tmp/fb
mkdir /tmp/fb
cd /tmp/fb
awk '{ print $0 > NF }'
ls | sort -nr | xargs cat

但是,没有利用很多核心.