From: Yukihiro Matsumoto <matz@...>
Date: 2008-03-17T16:28:24+09:00
Subject: [ruby-dev:34073] Re: rb_memsearch　optimization

まつもと ゆきひろです

In message "Re: [ruby-dev:34072] rb_memsearch　optimization"
    on Mon, 17 Mar 2008 16:20:33 +0900, "NARUSE, Yui" <naruse@airemix.com> writes:

|現在の rb_memsearch は Karp-Rabin を使っています。
|導入の際に Karp-Rabin についておっしゃっていた通り、
|確かにパターンが短い場合でも長い場合でもそれなりの性能を示しています。
|
|しかし、パターンの長さによってアルゴリズムの向き不向きが変わるのならば、
|長さによってアルゴリズムを変えてはどうでしょう。
|具体的にはパターンが 1 バイトの場合はリニアサーチが最速です。
|逆に、WORD幅 - 1 バイトを超える場合にはどんどん飛ばしていく BM 系の方が速いでしょう。

なるほど。それは考えていませんでした。

|場合分けの手間に見合った速度の向上はあると思うのですが、いかがでしょう。

コミットしてくださいませんか？