[ruby-dev:12239] String#index and Shift-Or algorithm

http://www.ruby-lang.org/~eban/diary/200102a.html#200102055
にある話をうけて, Namazu の高林くんに String#index を
Shift-Or とかにしたらいいんじゃない? と言われました. 

わたし自身は今だ Shift-Or ってなに? という状態なのですが
http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060
にコードが載っていたので, それをそのまま使って
実装することができました. 

結果としてはこんな感じです. 

  $ ./miniruby.orig /tmp/t.rb
	       user     system      total        real
  *1(o)       5.580000   0.000000   5.580000 (  5.587018)
  *1(x)       6.390000   0.000000   6.390000 (  7.202354)
  *100(o)     0.560000   0.000000   0.560000 (  0.693866)
  *100(x)    26.660000   0.020000  26.680000 ( 27.953883)
  *1000(o)    0.060000   0.000000   0.060000 (  0.057596)
  *1000(x)   26.410000   0.010000  26.420000 ( 27.743034)
  *50000(o)   0.000000   0.000000   0.000000 (  0.000288)
  *50000(x)   6.600000   0.000000   6.600000 (  7.313645)
	       user     system      total        real
  >total:    47.850000   0.010000  47.860000 ( 52.587569)
  >avg:       0.398750   0.000083   0.398833 (  0.438230)

  $ ./miniruby /tmp/t.rb
	       user     system      total        real
  *1(o)       5.510000   0.010000   5.520000 (  5.862235)
  *1(x)       5.690000   0.080000   5.770000 (  6.513963)
  *100(o)     0.530000   0.020000   0.550000 (  0.586939)
  *100(x)     2.340000   0.020000   2.360000 (  3.456867)
  *1000(o)    0.070000   0.000000   0.070000 (  0.079166)
  *1000(x)    1.870000   0.000000   1.870000 (  1.894066)
  *50000(o)   0.000000   0.000000   0.000000 (  0.000298)
  *50000(x)   0.700000   0.000000   0.700000 (  0.695278)
	       user     system      total        real
  >total:     1.020000   0.010000   1.030000 (  1.155083)
  >avg:       0.008500   0.000083   0.008583 (  0.009626)

miniruby.orig が 1.6.2 の CVS 版で, 
miniruby がそれに添付した diff のように手を入れたものです. 

t.rb も添付しておきます. 

# t.rb に書いた内容が正しい実験かどうかって話が
# まずあるんですが(^_^;;), 正しい実験だったとして
両者を比べると, Shift-Or を使った方(miniruby.orig ではなく
miniruby の方)が良い結果が出ていると言えるのではないかと思います. 

わたしが行った実装は場当り的ですし, 
http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060
のコードをそのまま使ってよいものかどうかも確認していませんが, 
もしもこのようなやり方を入れることが有効であるなら
ちょっと検討してもらえるとうれしいです. 

-- 

 やまだ あきら <URL:http://arika.org/>
 ([e-mail], [e-mail] or [e-mail])

Index: string.c
===================================================================
RCS file: /home/akira/cvs/ruby-src/cvs/ruby/string.c,v
retrieving revision 1.50.2.4
diff -u -u -r1.50.2.4 string.c
--- string.c	2001/02/08 09:17:57	1.50.2.4
+++ string.c	2001/02/14 04:05:43
@@ -617,11 +617,82 @@
     return rb_reg_match2(rb_reg_regcomp(str));
 }
 
+#define ASIZE 256
 static long
+rb_shift_or(str, sub, offset, return_last)
+     VALUE str, sub;
+     long offset;
+     int return_last;
+{
+  unsigned long j, state, lim, first, initial;
+  unsigned int T[ASIZE];
+  long i;
+  char *s, *e, *p;
+  long len, r = -1;
+   
+  if (offset < 0) {
+    offset += RSTRING(str)->len;
+    if (offset < 0) {
+      return -1;
+    }
+  }
+  /*p = RSTRING(sub)->ptr;*/
+  len = RSTRING(sub)->len;
+  if (!return_last) {
+    if (RSTRING(str)->len - offset < RSTRING(sub)->len) {
+      return -1;
+    }
+    s = RSTRING(str)->ptr + offset;
+    e = RSTRING(str)->ptr + RSTRING(str)->len - len + 1;
+  } else {
+    if (offset > RSTRING(str)->len) {
+      offset = RSTRING(str)->len;
+    }
+    s = RSTRING(str)->ptr + RSTRING(str)->len - offset;
+    e = RSTRING(str)->ptr + RSTRING(str)->len - len;
+  }
+  if (len == 0) {
+    return offset;
+  }
+
+  /* Preprocessing */
+  for (i = 0; i < ASIZE; i++) {
+    T[i] = ~0;
+  }
+  lim = 0;
+  for (i = 0, j = 1; i < len; i++, j <<= 1) {
+    T[*(RSTRING(sub)->ptr + i)] &= ~j;
+    lim |= j;
+  }
+  lim = ~(lim>>1);
+   
+  /* Searching */
+  state = ~0;
+  if (!return_last) {
+    for (p = s; p <= e; p++) {
+      state = (state << 1)|T[*p];
+      if (state < lim) {
+	r = p - s - len + 1 + offset;
+	return r;
+      }
+    }
+  } else {
+    for (p = s; p <= e; p++) {
+      state = (state << 1)|T[*p];
+      if (state < lim) {
+	r = p - s - len + 1;
+      }
+    }      
+  }
+  return r;
+}
+
+static long
 rb_str_index(str, sub, offset)
     VALUE str, sub;
     long offset;
 {
+#if 0
     char *s, *e, *p;
     long len;
 
@@ -642,6 +713,9 @@
 	s++;
     }
     return -1;
+#else
+    return rb_shift_or(str, sub, offset, 0);
+#endif
 }
 
 static VALUE
@@ -672,7 +746,11 @@
 	break;
 
       case T_STRING:
+#if 0
 	pos = rb_str_index(str, sub, pos);
+#else
+	pos = rb_shift_or(str, sub, pos, 0);
+#endif
 	break;
 
       case T_FIXNUM:
@@ -729,6 +807,7 @@
 	break;
 
       case T_STRING:
+#if 0
 	len = RSTRING(sub)->len;
 	/* substring longer than string */
 	if (RSTRING(str)->len < len) return Qnil;
@@ -749,6 +828,9 @@
 	else {
 	    return INT2NUM(pos);
 	}
+#else
+	return INT2NUM(rb_shift_or(str, sub, pos, 1));
+#endif
 	break;
 
       case T_FIXNUM:


require "/tmp/benchmark"
include Benchmark

benchmark(" "*7 + CAPTION, 10, FMTSTR) do |x|
  str = "abcdefgABCDEFG"
  x.report("*1(o)") {
    1.upto(1000000) {
      str.index("C")
    }
  }
  x.report("*1(x)") {
    1.upto(1000000) {
      str.index("X")
    }
  }

  str = "abcdefgABCDEFG"*100
  x.report("*100(o)") {
    1.upto(100000) {
      str.index("C")
    }
  }
  x.report("*100(x)") {
    1.upto(100000) {
      str.index("X")
    }
  }

  str = "abcdefgABCDEFG"*1000
  x.report("*1000(o)") {
    1.upto(10000) {
      str.index("C")
    }
  }
  x.report("*1000(x)") {
    1.upto(10000) {
      str.index("X")
    }
  }

  str = "abcdefgABCDEFG"*50000
  x.report("*50000(o)") {
    1.upto(50) {
      str.index("C")
    }
  }
  x.report("*50000(x)") {
    1.upto(50) {
      str.index("X")
    }
  }
end

s = []
Dir.foreach(".") do |f|
  next unless FileTest.file?(f)
  s << open(f, "r").readlines.join()
end

benchmark(" "*7 + CAPTION, 10, FMTSTR, ">total:", ">avg:") do |x|
  r = []
  s.each do |l|
    r << measure{1.upto(100){l.index("oo")}}
  end
  avg = nil
  total = nil
  r.each do |b|
    if avg
      avg += b
    else
      avg = b
    end
    if total
      total += b
    else
      total = b
    end
  end

  [total, avg/r.size]
end