按联机字数对大量文件的行进行排序(最好并行)

一 幼稚的方法 可以简单地说:

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 此外,最后一种排序(合并排序)效率很高。

进一步改进以提高 N*2+1 使用fifos 再次假设可以有多个输入文件,而不是中间文件:

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 进程接近于零。

甚至更好 ,只读取一次输入文件,并将输入行循环成多个 分类 管:

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]

你应该衡量不同价值观的表现 美元平行 然后选择一个最佳的。

编辑

如其他文章所示,您当然可以使用 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.*

我想知道这会有多快:

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

不过,并没有利用很多核心。

因为您不需要排序,只需复制到bucket中,所以您可以按令牌数量拆分文件,这将是最快的:

perl -ne 'split/\s+/;$t=$#_+1;open $f[$t], sprintf(">%09d",$t) if $f[$t] eq "";$f=$f[$t];print $f $_;'

cat `ls -1r 0*`

顺便说一句,磁盘将是核心和使用的瓶颈。

作为参考,我需要添加到版本8.6(2010)中,gnu coreutils(包括sort)支持多线程排序。默认情况下,我认为(从v8.6开始)它将使用核心数作为线程数,但是您可以使用

sort <file> --parallel=<N>

要创建高效的文件,我应该执行如下操作:对文件进行两次解析:

在第一遍中逐行读取,记录三样东西:行号、文件偏移量和字数。这可以并行化而不太困难(对于在文件中以“随机”行开始的作业,只需在单词后面添加相应的开始编号)。

现在按每行单词数对三个记录的内容进行排序。然后迭代列表,寻找相应的开始偏移量。

从性能的角度来看,所有的搜索可能都很慢,但在内存消耗方面应该相对比较轻,每行只需要3个int。

awk '{print length,$0}' test.txt | sort -nr | cut -d" " -f2-

虽然sort可以绕过内存限制,但不确定它的性能如何。

我不确定自己是否正确理解了这个问题,但我认为类似于快速排序的方法可能会有帮助:

10 split the file into N subfiles, one for each core/cpu
20 sort each partial file using the solutions suggested in some of the answers here
30 once every file is split and sorted, get the first line from each file and put it into a temporary file
40 get the second line from each file, put them in a second temporary file
50 repeat until you have number of temp files == number of cores
60 GOTO 20

根据传递的次数,应该接近完全排序的文件。

注意 这不是一个完美的解决方案 . 然而,即使在几次传递中,它也应该为您提供第一个临时文件中最长行的合理排序列表(我假设原始长文件中行的长度为高斯分布)。

注:如果部分文件仍然大于可用内存,请再次拆分它们,直到它们合适为止(具体取决于对每个文件使用的排序算法,tho)。但在这种情况下,需要将传递次数加倍才能得到合理的近似值

ps2:我还假设您对一个完全排序的文件不感兴趣,而是更感兴趣的是数据的统计意义(即如何 长的 平均排长队等)。