如何使用 GNU Parallel 编写多核排序
How to write multicore sorting using GNU Parallel
GNU parallel is a shell tool for executing jobs in parallel using one or more computers
例如,如果我想编写 wc
的多核版本,我可以这样做:
cat XXX | parallel --block 10M --pipe wc -l | awk 'BEGIN{count=0;}{count = count+ ;} END{print count;}'
我的问题是如何使用并行排序?我知道我应该做的是将并行结果通过管道传输到 "merge sorted files" 命令(就像合并排序中的最终合并一样),但我不知道该怎么做。
有几种方法可以做到这一点。
让我们来玩一个简单的文本文件:
$ curl http://www.gutenberg.org/cache/epub/2701/pg2701.txt 2>/dev/null |
tr " " "\n" | tr "[A-Z]" "[a-z]" |
sed -e 's/[[:punct:]]*//g' -e '/^[[:space:]]*$/d' > moby-dick-words.txt
$ wc moby-dick-words.txt
215117 moby-dick-words.txt
$ time sort moby-dick-words.txt > moby-dick-words-sorted.txt
real 0m0.260s
user 0m0.462s
sys 0m0.004s
我们可以对文本块进行排序,一次说 10000 个单词,并将一些困难的串行工作推迟到合并 (sort -m
) 部分:
$ mkdir tmp
$ time (
cd tmp;
split -l 1000 ../moby-dick-words.txt;
parallel sort {} -o {}.sorted ::: x*;
sort -m *.sorted > ../moby-dick-words-sorted-merge.txt;
rm x* )
real 0m0.787s
user 0m0.495s
sys 0m0.103s
$ diff moby-dick-words-sorted.txt moby-dick-words-sorted-merge.txt
$ uniq -c moby-dick-sorted-merge.txt | tail
1 zeuglodon
1 zigzag
5 zodiac
1 zogranda
4 zone
1 zone
2 zoned
3 zones
2 zoology
1 zoroaster
所以这会将文本拆分为连续的 10000 行块,使用并行对每个块进行排序,然后使用 sort -m
将排序后的块合并为一个完整的排序。
下一个方法是在拆分阶段而不是合并阶段进行艰苦的工作,以便可以通过简单的 cat 将部分结果合并在一起:
$ rm tmp/*
$ letters="a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9"
$ time (
cd tmp;
parallel sed -e "/^{}/w{}.txt" ../moby-dick-words.txt ::: $letters >& /dev/null;
parallel sort {}.txt -o {}.sorted.txt ::: $letters;
cat *.sorted.txt > ../moby-dick-words-sorted-split.txt;
rm *.txt )
real 0m1.015s
user 0m2.355s
sys 0m0.510s
$ diff moby-dick-words-sorted-split.txt moby-dick-words-sorted.txt
$ uniq -c moby-dick-words-sorted-split.txt | tail
1 zeuglodon
1 zigzag
5 zodiac
1 zogranda
4 zone
1 zone
2 zoned
3 zones
2 zoology
1 zoroaster
这里我们(并行)按行的第一个字符拆分文件;分别对这些文件进行排序;然后合并是一个简单的连接。
请注意,这仅用于 entertainment/educational 目的;更高版本的 gnu sort 具有内置的并行性(查看 --parallel option) which will do a much better job than this. And a slicker version of the of the merge approach can be seen in this answer.
GNU parallel is a shell tool for executing jobs in parallel using one or more computers
例如,如果我想编写 wc
的多核版本,我可以这样做:
cat XXX | parallel --block 10M --pipe wc -l | awk 'BEGIN{count=0;}{count = count+ ;} END{print count;}'
我的问题是如何使用并行排序?我知道我应该做的是将并行结果通过管道传输到 "merge sorted files" 命令(就像合并排序中的最终合并一样),但我不知道该怎么做。
有几种方法可以做到这一点。
让我们来玩一个简单的文本文件:
$ curl http://www.gutenberg.org/cache/epub/2701/pg2701.txt 2>/dev/null |
tr " " "\n" | tr "[A-Z]" "[a-z]" |
sed -e 's/[[:punct:]]*//g' -e '/^[[:space:]]*$/d' > moby-dick-words.txt
$ wc moby-dick-words.txt
215117 moby-dick-words.txt
$ time sort moby-dick-words.txt > moby-dick-words-sorted.txt
real 0m0.260s
user 0m0.462s
sys 0m0.004s
我们可以对文本块进行排序,一次说 10000 个单词,并将一些困难的串行工作推迟到合并 (sort -m
) 部分:
$ mkdir tmp
$ time (
cd tmp;
split -l 1000 ../moby-dick-words.txt;
parallel sort {} -o {}.sorted ::: x*;
sort -m *.sorted > ../moby-dick-words-sorted-merge.txt;
rm x* )
real 0m0.787s
user 0m0.495s
sys 0m0.103s
$ diff moby-dick-words-sorted.txt moby-dick-words-sorted-merge.txt
$ uniq -c moby-dick-sorted-merge.txt | tail
1 zeuglodon
1 zigzag
5 zodiac
1 zogranda
4 zone
1 zone
2 zoned
3 zones
2 zoology
1 zoroaster
所以这会将文本拆分为连续的 10000 行块,使用并行对每个块进行排序,然后使用 sort -m
将排序后的块合并为一个完整的排序。
下一个方法是在拆分阶段而不是合并阶段进行艰苦的工作,以便可以通过简单的 cat 将部分结果合并在一起:
$ rm tmp/*
$ letters="a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9"
$ time (
cd tmp;
parallel sed -e "/^{}/w{}.txt" ../moby-dick-words.txt ::: $letters >& /dev/null;
parallel sort {}.txt -o {}.sorted.txt ::: $letters;
cat *.sorted.txt > ../moby-dick-words-sorted-split.txt;
rm *.txt )
real 0m1.015s
user 0m2.355s
sys 0m0.510s
$ diff moby-dick-words-sorted-split.txt moby-dick-words-sorted.txt
$ uniq -c moby-dick-words-sorted-split.txt | tail
1 zeuglodon
1 zigzag
5 zodiac
1 zogranda
4 zone
1 zone
2 zoned
3 zones
2 zoology
1 zoroaster
这里我们(并行)按行的第一个字符拆分文件;分别对这些文件进行排序;然后合并是一个简单的连接。
请注意,这仅用于 entertainment/educational 目的;更高版本的 gnu sort 具有内置的并行性(查看 --parallel option) which will do a much better job than this. And a slicker version of the of the merge approach can be seen in this answer.