- 929 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 18:35:38.20 ]
- 上で紹介されている配列回転アルゴリズムはコピーにコストがかかるデータの場合に有利ですね。
テンポラリ配列や２回逆転方法の約半分のコピー回数で済むので
例えば、私の環境では以下のようになりました。
typedef struct {
long id;
long data[1000];
} data_t;
こんなデータの配列 data_t arr[1000] を回転操作( 0〜999 )
$ gcc -O3 -o rotate_temporaly rotate_temporaly.c
$ time ./rotate_temporaly
rreal 0m3.172s
user 0m3.158s
sys 0m0.012s
$ gcc -O3 -o rotate_reverse rotate_reverse.c
$ time ./rotate_reverse
real 0m1.915s
user 0m1.910s
sys 0m0.004s
$ gcc -O3 -o rotate_dolphin rotate_dolphin.c
$ time ./rotate_dolphin
real 0m0.703s
user 0m0.699s
sys 0m0.003s
おそらく細かい実装の違いではカバーしきれないほどの差が出ます。
まあ、この種のアルゴリズムが必要になる前にデータ構造の見直しをしたほうがいいとは思います。
リスト構造なら一部の配線付け替えで一瞬です
|
 |
