[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<RARRAY_LEN(ary); i++) {
 	if (rb_equal(RARRAY_PTR(ary)[i], item)) {
 	    return Qtrue;

-- 
Yusuke ENDOH <[e-mail]>