sortプログラムの速度比較 2 (C言語qsort())

May

2022年4月1日 23:25

概要

過去の記事でソートするプログラムやAPIのソート時間を比較しました．
C言語のqsort()関数の速度も比較しました．
ただし，公平な比較ではないので，参考程度にとどめてください．

比較対象

・Linuxのsortコマンド(LC_ALL=C)
・Rubyの Array.sort()
・Pythonの sorted()関数
・C言語のqsort()関数

結果

python0: Array.sort()
ruby0: Array.sort()
sortcommand1: Linuxのsortコマンド(LC_ALL=C)
qsort0: C言語 qsort()関数下記注意点参照
qsort1: C言語 qsort()関数下記注意点参照
qsort2: C言語 qsort()関数下記注意点参照

qsort()が速いですが，公平な比較ではないです．
以下の点に注意してください．詳細は，ソースコード参照．
注意点：
(1) qsortプログラムは，各データサイズが11バイト(改行コードを含む)固定であることを前提とし，それ利用している．
(2) qsortプログラムは，データ個数が既知であることを前提とし，それ利用している．

解説

C言語のqsort()関数はクイックソートを使っています．通常時は o(n * log(n))です．最悪時はo(n^2)です．
Linuxのsortプログラムはマージソートを使っています．マージソートはo(n * log(n))です．
sort プログラムは，すべてのコア(8コア)を用いてソートしています．
C言語qsort()やRubyやPythonのプログラムは1コアしか使っていません．
入力データをテキストデータとしてソートせずに，int型に変換してからソートするとRubyやPythonは速くなります．

測定条件

ソートデータ

以下の様なテキストファイル．
各行に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)

ruby0

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

qsort0

#define NUM 33554432
#define BLK 11

#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>

char buf[NUM+1][BLK];
void main(int argc, char ** argv){
        int fd, num;
        num = atoi(argv[1]);
        fd = open("a.txt",O_RDONLY);
        read(fd, buf, num*BLK);
        buf[num][0] = '\0';
        close(fd);
        qsort(buf,num,BLK, strcmp);
        write(1, buf, num*BLK);
}

比較関数にstrcmp()を指定しています．
各データ(改行を含めて11バイト)はNULL終端していないので，比較対象データが同一内容だと，改行コード以降の次のデータまで読み進めてしまいます．ただし，内容が同一なので比較結果がどのようになっても問題ありません．最後のデータは，次のデータがなく，読み進めてはならないので，NULL終端しています．

qsort1

#define NUM 33554432
#define BLK 11

#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>

int cmp(void *a, void *b){
        strncmp(a,b,BLK-1);
}

char buf[NUM+1][BLK];
void main(int argc, char ** argv){
        int fd, num;
        num = atoi(argv[1]);
        fd = open("a.txt",O_RDONLY);
        read(fd, buf, num*BLK);
        close(fd);
        qsort(buf,num,BLK, cmp);
        write(1, buf, num*BLK);
}

比較関数に自作関数cmp()を指定しています．中身はstrnmp()を呼んでいるだけです．

qsort2

#define NUM 33554432
#define BLK 11

#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>

int cmp(char *a, char *b){
        while( *a != '\n' ){
                char ch = *a - *b;
                if( ch ){ return ch; }
                a++;
                b++;
        }
        return 0;
}

char buf[NUM+1][BLK];
void main(int argc, char ** argv){
        int fd, num;
        num = atoi(argv[1]);
        fd = open("a.txt",O_RDONLY);
        read(fd, buf, num*BLK);
        close(fd);
        qsort(buf,num,BLK, cmp);
        write(1, buf, num*BLK);
}

比較関数に自作関数cmp()を指定しています．中身は教科書的なstrcmp()を真似して作ったつもりです．

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

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

ruby0 は，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

qsort0, qsort1, qsort2 は以下の通り

gcc q.c -o q
gcc ../a.c
for((n=1; n<=60000000; 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 ./q ${n}> /dev/null 2>> result.${n}.txt
        done
done

環境

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

リンク

良かったら読んでください．
過去の記事: sortプログラムの速度比較 1
Pythonにおけるソート

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