algorithm - すでにサポートされている言語でのデータ構造/アルゴリズムの実装

Question

データ構造とアルゴリズムの独自のバージョンを選択した言語で実装することは、それらが既にサポートされている場合でも、可能な限り最高のパフォーマンスを得るためにチューニングに注意を払っていることを知っていれば、理にかなっていますか?

Answer 1

時々-はい。特定のケースに合わせてデータ構造を最適化するか、特定の追加機能を提供する必要がある場合があります。

Javaの例は、apache Lucene（成熟した、広く使用されている情報検索ライブラリ）です。インターフェイスと実装はすでに存在しますが、パフォーマンスの問題のために、をボックス化するためMap<S,T>、その使用法は十分ではありません。この目的のために、を使用する代わりに、より最適化されたものが開発されました。intIntegerIntToIntMapMap<Integer,Integer>

Answer 2

質問には、「可能な限り最高のパフォーマンス」などがあるという誤った仮定が含まれています。

既存のコードが特定の使用パターンで可能な限り最高のパフォーマンスを発揮するように調整されている場合、パフォーマンスに関して改善することは不可能であり、改善を試みても無駄です。

ただし、特定の使用法で可能な限り最高のパフォーマンスが得られるように調整されていません。まったく調整されていると仮定すると、考えられる多くの使用パターンを考慮して、平均して優れた総合的なパフォーマンスを発揮するように設計されており、そのうちのいくつかはあなたには関係ありません.

したがって、原則として、コードを自分で実装することで、自分に役立つ微調整を適用できます (実装者がその微調整を考慮した場合) 他のユーザーのどこかを妨害する可能性があります。しかし、それは問題ありません。彼らはあなたのコードを使用する必要はありません。あなたはカッコウハッシュが好きで、彼らは線形プロービングが好きかもしれません。

実装者が微調整を考慮しなかった可能性がある理由には、次のようなものがあります。彼らがコードを書いたときに微調整は発明されておらず、その構造/アルゴリズムの最先端に従っていません。彼らは自分たちの時間とより良い関係を築いていますが、あなたはそうではありません。そのような場合、あなたが終わったら、彼らはおそらくあなたからのパッチを受け入れるでしょう.

言語がサポートするものと非常によく似たデータ構造を必要とするパフォーマンス以外の理由もありますが、特定の動作が追加または削除されています。既存の構造の上にそれを実装できない場合は、最初から実装することをお勧めします。明らかに、そうするのは、前もって将来のサポートにかなりのコストがかかりますが、それだけの価値がある場合は、実行してください。

Answer 3

コンパイルされた言語 (C、アセンブリなど) を使用している場合は、意味があるかもしれません。インタープリター型言語を使用すると、おそらくパフォーマンスが低下します。これは、ネイティブ構造パーサーが既にコンパイルされており、新しい構造の「解釈」に時間を無駄にしないためです。ネイティブの構造またはアルゴリズムに必要なものが欠けている場合にのみ、おそらくそれを行います。