From: Yusuke ENDOH Date: 2009-05-26T22:58:16+09:00 Subject: [ruby-dev:38545] [suggestion] sorted flag for Array 遠藤です。 思い付きですが、Array に「ソート済み」を表すフラグを持たせるのはどう でしょうか。 「ソート済み」の配列に対しては、 - Array#index や include? で二分探索を使う - Array#uniq や - 、& 、| では、一時ハッシュを作らず、1 パスで処理する という最適化ができます。特に前者は O(n) から O(log n) になります。 前者はテーブルを配列で実装しているプログラムで使えそうで、後者は集合を 配列で代替表現しているプログラムで使えそうです。 フラグの管理は - ブロックなし Array#sort や Array#sort! の返り値のフラグを立てる - 破壊的変更を行ったらフラグを消す とするだけなので、オーバーヘッドは無視できる量だと思います (未検証) 。 試験的に Array#include? だけ実装しました。 非常に極端な例で実測したところ、オリジナルで 30 秒、パッチ後で 0.04 秒 でした (オーダの改善なので数値にあまり意味はないですが) 。 a = ([0] * 100000 + [1]).sort; 1000.times { a.include?(1) } 自分でもこの提案がどのくらい便利なのか (または便利でないのか、もしくは まずいのか) 読みきれていません。みなさんどう思われますか。 以下、自分で考え付いた議論: - sort が返した配列だけ速いというのがわかりにくい (ブロックつき sort や sort_by ではダメというのもわかりにくいか) - ソートすべきでない配列 (<=> が全順序になっていない配列) をソートした 配列では、最適化で結果が変わることがあるが、現実的にまずい例はあるか - <=> と == が矛盾するような要素を含む配列でも結果が変わるが、現実的に まずい例はあるか Index: array.c =================================================================== --- array.c (revision 23590) +++ array.c (working copy) @@ -140,6 +140,14 @@ FL_SET(ary, RARRAY_SHARED_ROOT_FLAG); \ } while (0) +#define RARRAY_SORTED_FLAG FL_USER6 +#define ARY_SORTED_P(ary) (FL_TEST(ary, RARRAY_SORTED_FLAG)) +#define FL_SET_SORTED(ary) do { \ + assert(!ARY_SORTED_P(ary)); \ + FL_SET(ary, RARRAY_SORTED_FLAG); \ +} while (0) +#define FL_UNSET_SORTED(ary) FL_UNSET(ary, RARRAY_SORTED_FLAG) + static void ary_resize_capa(VALUE ary, long capacity) { @@ -268,6 +276,9 @@ ARY_SET_PTR(ary, ptr); } } + if (ARY_SORTED_P(ary)) { + FL_UNSET_SORTED(ary); + } } VALUE @@ -1863,6 +1874,7 @@ } /* tmp will be GC'ed. */ RBASIC(tmp)->klass = rb_cArray; + if (!rb_block_given_p()) FL_SET_SORTED(ary); } return ary; } @@ -2856,6 +2868,25 @@ { long i; + if (ARY_SORTED_P(ary)) { + long j; + struct ary_sort_data data; + volatile VALUE tmp = rb_ary_tmp_new(0); + data.ary = tmp; + data.opt_methods = 0; + data.opt_inited = 0; + i = 0; j = RARRAY_LEN(ary) - 1; + if (j == -1) return Qfalse; + while (i <= j) { + long m = i + (j - i) / 2; + long r = sort_2(&RARRAY_PTR(ary)[m], &item, &data); + if (!ARY_SORTED_P(ary)) goto unsorted; + if (r == 0) return Qtrue; + if (r > 0) j = m - 1; else i = m + 1; + } + return Qfalse; + } + unsorted: for (i=0; i