2

単語を格納するために、trys データ構造を使用します。ここで、特定のフレーズが同じ段落に存在する場合、特定の段落を見つける必要があるという要件があります。

これを行うための最も効率的な方法は何でしょうか? フレーズの総数は 100 を超えません。

4

2 に答える 2

1

指定されたトライは、多くの点で最適ではありません。

  • まず、挿入されたアイテムごとに複数のノードを構築します。著者が書いているように、「入力キーのすべての文字は、個別のトライ ノードとして挿入されます。」それは恐ろしく、不必要なペナルティです! ALPHABET_SIZEここで 2 より大きい値を使用すると、傷害に侮辱が加わります。50 バイトのフレーズには 50 ノードが必要であるだけでなく、各ノードのサイズは 100 バイトを超える可能性があります...長さが 50 バイトの各アイテムまたは「フレーズ」は、そのコードを使用して最大約 5KB のストレージを必要とする場合があります! それは最悪のことではありません。
  • 提供されたアルゴリズムはmalloc内部に埋め込まれているため、最適化が非常に困難です。各ノードは独自の割り当てであり、insert非常にmalloc重くなります。割り当ての詳細は、最適化の目的でなくても、使いやすさのために、データ構造の処理から分離する必要があります。このコードを頻繁に使用するプログラムは、メモリの断片化やキャッシュ ミスに関連するパフォーマンスの問題に遭遇する可能性が高く、トライを別のものに置き換える以外に、簡単または重要な最適化は見られません。
  • ここで間違っているのはそれだけではありません...このコードはあまりにも移植性がありません! ASCII ではなく EBCDIC を使用する古い (それほど古いものではなく、まだ存在しています!) メインフレームでこれを実行することになった場合、このコードはバッファ オーバーフローを生成し、プログラマ (あなた) がそれを修正するために呼び出されます。<sarcasm>それはとても最適ですよね？</sarcasm>

私は、アイテムごとに正確に 1 つのノードを使用し、アルファベット サイズが 2 である (各文字ではなく各文字のビットを使用する) パトリシア トライ実装を作成しました。インターフェイスのリファクタリングにはまだ多くの労力を費やしていませんが、最適にかなり近いはずです。その実装はhere にあります。挿入 ( を使用patricia_add)、取得 ( を使用patricia_get)、および削除 ( を使用patricia_remove) の例は、パトリシア_test.cテストケース ファイルで確認できます。

于 2015-08-20T04:59:59.677 に答える