Ruby＃indexメソッドVSバイナリ検索

与えられた要素と配列で、Ruby＃indexメソッドは配列内の要素の位置を返します。バイナリ検索を使用して私自身のインデックスメソッドを実装しました。私の予想は組み込みのものよりも優れていました。私の驚いたことに、ビルトインのものは実験の約3倍の速さで走った。Ruby＃indexメソッドVSバイナリ検索

どのRubyistがその理由を知っていますか？

出典

2011-09-15 Terry Li

Rubyの '＃index'メソッドは、バイナリ検索ではまだ実装されていませんでしたか？さらに、そのメソッドはRubyで実装されていると誰が言いましたか？ :-) –

@Platinum Azureああ、バイナリ検索でCで実装されるかもしれない。どうもありがとう！ –

あなたはそれを持っています！ :-) –

組み込みの#index is not a binary searchは単なる反復検索です。しかしRubyではなくC言語で実装されているので、自然に数桁速くなります。

出典

2011-09-15 19:30:55 harbichidian

ありがとうございます。それは本当に変だ。彼らがバイナリサーチアプローチを採用しなかった理由はありましたか？ –

バイナリ検索では、2つの要素が等しいかどうかを確認できるだけでなく、2つの要素を比較できます。また、引数に等しい* first *オブジェクトを返すと文書に記載されていることにも注意してください。バイナリ検索は必ずしもその要素を返すわけではありません。 #bsearch（配列がソートされていると仮定）のバージョンは#indexよりも遅く見えません。https://gist.github.com/1220440 –

#bsearch実装ではRubyとCとバイナリ検索とシーケンシャル検索の違いは？ –

Ruby＃indexメソッドVSバイナリ検索

答えて

関連する問題