[ruby-dev:19464] Re: Karp-Rabin (Re: new keyword once)

なかだです。

At Mon, 3 Feb 2003 13:11:55 +0900,
Yukihiro Matsumoto wrote:
> |乗算よりもシフトのほうが速そうな気がするんですが、どうなんでしょ
> |うか。あまり変わらないかも。
> 
> 手元でテストしたらなんかマッチしないケースがあるみたい。

たしかに。

しかしせいぜい2,3%くらい。


Index: re.c
===================================================================
RCS file: /cvs/ruby/src/ruby/re.c,v
retrieving revision 1.93
diff -u -2 -p -r1.93 re.c
--- re.c	3 Feb 2003 05:34:15 -0000	1.93
+++ re.c	3 Feb 2003 07:04:56 -0000
@@ -104,8 +104,9 @@ rb_memsearch(x0, m, y0, n)
     unsigned char *x = x0, *y = y0;
     unsigned char *s, *e;
-    long d, i;
+    long i;
+    int d;
     unsigned long hx, hy;
 
-#define KR_REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
+#define KR_REHASH(a, b, h) (((h) << 1) - ((a)<<d) + (b))
 
     s = y; e = s + n - m + 1;
@@ -114,12 +115,12 @@ rb_memsearch(x0, m, y0, n)
     /* computes d = 2^(m-1) with
        the left-shift operator */
-    for (d = i = 1; i < m; ++i)
-	d = (d<<1);
+    d = sizeof(hx) * CHAR_BIT - 1;
+    if (d > m) d = m;
 
     if (ruby_ignorecase) {
 	/* Prepare hash value */
-	for (hy = hx = i = 0; i < m; ++i) {
-	    hx = ((hx<<1) + casetable[x[i]]);
-	    hy = ((hy<<1) + casetable[s[i]]);
+	for (hy = hx = i = 0; i < d; ++i) {
+	    hx = KR_REHASH(0, casetable[x[i]], hx);
+	    hy = KR_REHASH(0, casetable[s[i]], hy);
 	}
 	/* Searching */
@@ -128,5 +129,5 @@ rb_memsearch(x0, m, y0, n)
 		return s-y;
 	    }
-	    hy = KR_REHASH(casetable[*s], casetable[*(s+m)], hy);
+	    hy = KR_REHASH(casetable[*s], casetable[*(s+d)], hy);
 	    s++;
 	}
@@ -134,7 +135,7 @@ rb_memsearch(x0, m, y0, n)
     else {
 	/* Prepare hash value */
-	for (hy = hx = i = 0; i < m; ++i) {
-	    hx = ((hx<<1) + x[i]);
-	    hy = ((hy<<1) + s[i]);
+	for (hy = hx = i = 0; i < d; ++i) {
+	    hx = KR_REHASH(0, x[i], hx);
+	    hy = KR_REHASH(0, s[i], hy);
 	}
 	/* Searching */
@@ -143,5 +144,5 @@ rb_memsearch(x0, m, y0, n)
 		return s-y;
 	    }
-	    hy = KR_REHASH(*s, *(s+m), hy);
+	    hy = KR_REHASH(*s, *(s+d), hy);
 	    s++;
 	}


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦