以前の質問python の効率的な部分文字列検索を拡張しています。
部分文字列検索の実装のパフォーマンスを改善することに興味があります。
私の以前の質問からの回答のいくつかは、BM アルゴリズムに触発された fastsearch を使用して部分文字列検索が実装されていることを指摘していました。ソース コードは次のとおりです。
より多くの回答により、Boyer-Moore Algorithm、Rabin-Karp アルゴリズムの Python 実装が示されました。
will it be efficient to embed c code as a good implementation of substring search using those algorithms (B-M,Rabin-Karp)?
「効率的」とはどういう意味かを指定していません。どのようなトレードオフを行いますか? 新しい文字列を初期化するときに、パフォーマンスの低下という代償を払う覚悟はありますか? 検索を開始するときは？より多くのメモリを交換して速度を向上させますか?
Python 開発者は、Python 文字列ライブラリを開発したときに明確な目標を設定しました。
- Jim Hugunin の最悪のケースのテストを含む、すべてのテスト ケース (実際のコードに基づく) で現在のブルート フォース アルゴリズムよりも高速である必要があります。
- セットアップのオーバーヘッドが小さい。高速パスでの動的割り当てなし (速度は O(m)、ストレージは O(1))
- 良い場合の準線形検索動作 (O(n/m))
- 最悪の場合でも現在のアルゴリズムより悪くない (O(nm))
- 8 ビットの文字列と 16 ビットまたは 32 ビットの Unicode 文字列の両方でうまく機能するはずです (O(σ) の依存関係はありません)。
- 多くの実際の検索は良好であり、最悪の場合はほとんどありません
- かなり単純な実装
そのため、開発者は、検索ケースとセットアップ ケースのパフォーマンス、ストレージ要件、およびメンテナンス効率にいくつかの制限を設定しました。これらの境界は、Boyer-Moore を除外しました (検索対象の文字列の前処理、起動コスト、およびストレージ コストが必要になるため)。根拠（ハッシュを作成して保存する必要があります）。
境界は、多くの Python 内部と使用経験に基づいて設定されました。上記の要約は何もないところから引き出されたものではなく、単にその経験の要約です。
ここで、トレードオフを別の方法で設定できる特定のケースがある場合、確かに、別のアルゴリズムの C 実装は、標準の Python 実装よりも優れている可能性があります。ただし、別の一連の基準に従って、より効率的になります。
いずれにせよ、Python 検索アルゴリズムは小さな文字列のケースを扱います。大量のテキストに適用しようとすると、アルゴリズムは、大きなテキストに適したさまざまな選択を行うアルゴリズムほどには機能しません。また、10,000,000 のドキュメントからテキストを検索する必要がある場合は、小さな Python 文字列検索の代わりに、何らかのインデックス ソリューションを使用する必要があります。
これを、10,000,000,000 個の整数の並べ替えに対して、既定の並べ替えの実装で 100 項目のリストを並べ替える場合と比較してください。後者の場合、デフォルトの Python の提供を簡単に打ち負かすことができる並べ替えの実装があります。
また、Python にはアルゴリズムの革新の歴史があることにも注意してください。Python の標準的な並べ替えアルゴリズムはTimSortです。これは、Python インタープリターが対処しなければならない実用的な現実の状況に合わせて、Tim Peters によって発明された新しいアルゴリズムです。その後、このアルゴリズムは Java および Android プラットフォームでもデフォルトになりました。したがって、私は Python コア開発者の決定を信頼する傾向があります。
私の知る限り、Python C コードにパッチを適用しないとデフォルトを置き換えることはできないため、別の実装を組み込んだ人はいません。もちろん、別の検索アルゴリズムを実装する特殊な文字列型を簡単に作成できます。Boyer-Moore、Rabin-Karp、またはその他のアルゴリズムを使用する特殊な検索アルゴリズムに C を使用するライブラリが存在する可能性があります。これは、特定の問題領域に対してより適切な選択である可能性があるためです。