sortプログラムの速度比較 1

2022年3月26日 18:13

概要

ソートするプログラムやAPIは多数あります．
ソート時間を比較しました．
予想通りLinuxのsortプログラムが最速でした．

比較対象

・Linuxのsortコマンド(LC_ALL=空白と LC_ALL=C)
・Rubyの Array.sort() と Array.sort!()
・Pythonの Array.sort() と sorted()関数
・(参考)Linuxのcatプログラム

結果

凡例とプログラム, APIの対応．詳細は後述

python0: Array.sort()
python1: sorted()
ruby0: Array.sort()
ruby1: Array.sort!()
sortcommand0: Linuxのsortコマンド(LC_ALL=)
sortcommand1: Linuxのsortコマンド(LC_ALL=C)
cat: Linuxのcatコマンド

両対数グラフです．各線の左端より左は計測値が0になってしまい，対数グラフに表示できませんでした．
catは，データファイルを読み込んでソートせずにそのまま出力するプログラムです．入出力の時間が測れます．
他のソートプログラムの所要時間は，catの所要時間より圧倒的に長いので，ソートプログラムの消費時間の多くがソートに要した時間と予想します．

解説

Linuxのsortプログラムはマージソートを使っています．
マージソートはo(n * log(n))です．
sort プログラムは，すべてのコア(8コア)を用いてソートしています．
RubyやPythonのプログラムは1コアしか使っていません．
入力データをテキストデータとしてソートせずに，int型に変換してからソートするとRubyやPythonは速くなります．

sortコマンド(LC_ALL=)とPythonがほぼ同じ性能になる理由が分からないです．詳しい方，教えてください．．．
sort(LC_ALL=C)に関して，プロセス優先度を上げる(nice -20)，sortを-O3オプションを付けて自分でコンパイルしたものを使う，などをやってみましたがこれ以上速くはなりませんでした．

測定条件

ソートデータ

以下の様なテキストファイル．
各行に10桁の10進数が1個書いてある．31bit乱数．

テキストデータは以下のプログラムで作成

#include <stdio.h>
void main(int argc, char **argv){
        int i,max=100;
        if( 1<argc ){
                max = atoi(argv[1]);
        }
        for(i=0; i<max; i++){
                printf("%010d\n", rand());
        }
}

ソート方法

各行をテキストデータとしてソート．
入力はファイルからの読み込みで行い，出力は /dev/null へリダイレクトしている．
所要時間は /usr/bin/time コマンドで計測．
ソートデータを作成してすぐに読み込んでソートを実行．よって，データはpageキャッシュから読み込んでいると思います．

プログラム

python0

with open('a.txt') as f:
        lines = f.readlines()
        lines.sort()
        print(lines)

python1

with open('a.txt') as f:
        lines = f.readlines()
        print(sorted(lines))

ruby0

a = open("a.txt")
lines = a.readlines
print lines.sort

ruby1

a = open("a.txt")
lines = a.readlines
print lines.sort!

ベンチマークシェルスクリプト

python0の例

gcc a.c
for((n=1; n<=30000000; n*=2))
do
        echo ${n}
        ./a.out ${n} > a.txt
        rm -f result.${n}.txt
        for i in {0..10}
        do
                echo ${n}.${i}
                /usr/bin/time python3 sort.py > /dev/null 2>> result.${n}.txt
        done
done

python1 は全く同一

ruby0 と ruby1は，10行目が以下の様に変わる．

10c10
<               /usr/bin/time python3 sort.py > /dev/null 2>> result.${n}.txt
---
>               /usr/bin/time ruby sort.rb > /dev/null 2>> result.${n}.txt

sortcommand0 は，10行目が以下の様に変わる．

10c10
<               /usr/bin/time python3 sort.py > /dev/null 2>> result.${n}.txt
---
>               export LC_ALL= ; /usr/bin/time sort a.txt > /dev/null 2>> result.${n}.txt

sortcommand1 は，10行目が以下の様に変わる．
(厳密には，2行目の繰り返し回数も変えている)

10c10
<               /usr/bin/time python3 sort.py > /dev/null 2>> result.${n}.txt
---
>               export LC_ALL=C ; /usr/bin/time sort a.txt > /dev/null 2>> result.${n}.txt

cat は，10行目が以下の様に変わる．

10c10
<               /usr/bin/time python3 sort.py > /dev/null 2>> result.${n}.txt
---
>               /usr/bin/time cat a.txt > /dev/null 2>> result.${n}.txt

環境

CPU: Intel Core i7-3770 CPU @ 3.40GHz, clock rate 3.4 GHz (fixed)
HDD: Hitachi Deskstar 7K1000.C (1TB)
OS: Ubuntu 20.04.3 LTS, desktop, Linux 5.15.25
Memory: 16 GB
Python 3.8.10
ruby 2.7.0p0 (2019-12-25 revision 647ee6f091)
sort (GNU coreutils) 8.30
cat (GNU coreutils) 8.30
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

リンク

良かったら読んでください．
Pythonにおけるソート

記事2: C言語 qsort()関数の結果も紹介しています．

sortプログラムはマージソートを用いている．
実装 sort.c