読者です 読者をやめる 読者になる 読者になる

テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(rust report) DAG生成コードをCで書き直した結果

HeiankyoViewのPython実装において, 利用している二次元配列をPythonの配列からnumpyのものにしたら大幅に性能が改善したことがある.

http://akiradeveloper.hatenadiary.com/entry/2013/06/22/170950

配列操作をC言語に委譲すると高速になるケースがある. 私は, 何でもかんでもC/アセンブラで書くと速くなる厨は糞だと思うが, 妥当な場合にはC言語を部分的に使うこともアリだと思う. メモリ操作だとか, そういう部分についてはPythonは遅いことがある.

DAG生成コードがN=5万ごときがいつまで経っても終わらないので, イライラしてきてCで書き直した. 結果, 10倍以上高速化した. Pythonならば5時間かかるものが30分で終わるということだから, こういう高性能化は本当に意味がある. N=10万で実験しようと思う.

ちなみにアルゴリズムがO(N2)であり, そもそもここが糞である. 天才の方, もう少しマシなアルゴリズムがあったら教えてください.

akira@Hercules:~/rust-tsort$ time ./a.out 1000 > tmp.txt

real    0m0.166s
user    0m0.040s
sys     0m0.110s

akira@Hercules:~/rust-tsort$ time python gen-rand-dag.py 1000 > tmp.txt

real    0m2.018s
user    0m0.840s
sys     0m0.510s
#include <stdio.h>
#include <stdlib.h>

struct edge_t {
        int src;
        int dest;
};

int main(int argc, char **argv){
        int i, j;
        int n = atoi(argv[1]);
        int *perms = malloc(sizeof(int) * n);
        for (i = 0; i < n; i++) {
                *(perms + i) = i;
        }
        for (i = 0; i < n; i++) {
                int j = rand() % n;
                int t = perms[i];
                perms[i] = perms[j];
                perms[j] = t;
        }
        int num_edges = n * (n-1) / 2;
        struct edge_t *edges = malloc(sizeof(struct edge_t) * num_edges);
        unsigned long long k = 0;
        for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {                        
                        if (i < j) {
                                struct edge_t *e = edges + k;
                                e->src  = perms[i];
                                e->dest = perms[j];
                                k++;
                        }
                }
        }
        unsigned long long l;
        for (l = 0; l < k; l++) {
                struct edge_t *e = edges + l;
                printf("%d %d\n", e->src, e->dest);
        }

        return 0;
}