From: nobu.nakada@...
Date: 2003-02-03T12:09:07+09:00
Subject: [ruby-dev:19458] Re: Karp-Rabin (Re:  new keyword once)

なかだです。

At Sun, 2 Feb 2003 01:40:48 +0900,
Yukihiro Matsumoto wrote:
> 実際、簡単なベンチマークでは検索文字列が短く、検索する文字列
> があまり長くないケースではKRが一番良い成績を残すことが多いよ
> うです(BM, Quick, Shift-Or, KRで比較しました)。ま、実は似た
> りよったりなんですが。

乗算よりもシフトのほうが速そうな気がするんですが、どうなんでしょ
うか。あまり変わらないかも。


Index: string.c
===================================================================
RCS file: /cvs/ruby/src/ruby/string.c,v
retrieving revision 1.136
diff -u -2 -p -r1.136 string.c
--- string.c	31 Jan 2003 06:48:54 -0000	1.136
+++ string.c	3 Feb 2003 02:53:46 -0000
@@ -841,5 +841,6 @@ rb_str_index(str, sub, offset)
     char *s, *e, *p;
     long len;
-    int d, hx, hy, i;
+    int d, i;
+    unsigned long hx, hy;
 
     if (offset < 0) {
@@ -860,13 +861,13 @@ rb_str_index(str, sub, offset)
     */
 
-#define KR_REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
+#define KR_REHASH(a, b, h) ((((h) ^ ((a)<<d)) << 1) ^ (b))
 
     /* Preprocessing */
     /* computes d = 2^(m-1) with
        the left-shift operator */
-    for (d = i = 1; i < len; ++i)
-	d = (d<<1);
+    d = sizeof(hx) * CHAR_BIT - 1;
+    if (d > len) d = len;
 
-    for (hy = hx = i = 0; i < len; ++i) {
+    for (hy = hx = i = 0; i < d; ++i) {
 	hx = ((hx<<1) + p[i]);
 	hy = ((hy<<1) + s[i]);


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