11

パフォーマンスを向上させるために、実行時にデータ構造の表現を変更するプログラム/アルゴリズムはどれですか?

コンテキスト: データ構造は、実世界の概念がどのように構造化され、コンピューター メモリ内で表現されるかを「定義」します。さまざまな種類の計算では、許容できるパフォーマンスを達成するために、さまざまなデータ構造を使用する必要があります (たとえば、リンク リストと配列の実装)。

自己適応型 (自己更新を参照) データ構造は、具体的な使用パターン (自己平衡ツリーなど) に従って内部状態を変更するデータ構造です。これらの変更は内部的なものであり、データに依存します。さらに、これらの変更は設計上想定されています。

他のアルゴリズムは、表現の外部変更から恩恵を受けることができます。たとえば、行列乗算では、「2 番目の行列」を転置する (キャッシュがより効率的に使用されるようにする) ことはよく知られているパフォーマンス トリックです。これは実際には行列表現を行優先から列優先に変更しています。"A" は "Transposed(A)" と同じではないため、プログラムの意味を正しく保つために、乗算の後に 2 番目の行列が再び転置されます。

2 番目の例は、プログラムの起動時にリンク リストを使用して「データ構造」にデータを入力し、リストの内容が「安定」したら配列ベースの実装に変更することです。

パフォーマンスを向上させるために、アプリケーションで表現の外部変更が実行される他のサンプル プログラムで同様の経験を持つプログラマーを探しています。したがって、データ構造の表現 (選択された実装) は、実行時にプログラムの明示的な部分として変更されます。

4

1 に答える 1

4

より効率的なアルゴリズムを有効にするために入力表現を変換するパターンは、多くの状況で出てきます。これは、一般的に効率的なアルゴリズムの設計を考える上で重要な方法であると言えます。頭に浮かぶいくつかの例：

  • ヒープソート。これは、元の入力リストをバイナリ ヒープ (おそらく最小ヒープ) に変換し、remove-min 関数を繰り返し呼び出してリスト要素を並べ替えた順序で取得することによって機能します。漸近的には、比較に基づく最速の並べ替えアルゴリズムに結び付けられています。

  • リスト内の重複を見つける。入力リストを変更しないと、O(n^2) 時間かかります。しかし、リストを並べ替えたり、要素をハッシュ テーブルまたはブルーム フィルターに格納したりできる場合は、O(n log n) 時間またはそれ以上ですべての重複を見つけることができます。

  • 線形計画法を解く。線形計画法 (LP) は、経済学やその他の分野で多くの用途があるある種の最適化問題です。LP を解く上で最も重要なテクニックの 1 つは双対性です。これは、元の LP を「双対」と呼ばれるものに変換し、双対を解くことを意味します。状況によっては、二重の問題を解決する方が、元の (「主要な」) LP を解決するよりもはるかに簡単な場合があります。この本の章は、プライマル/デュアル LP の良い例から始まります。

  • 非常に大きな整数または多項式の乗算。最速の既知の方法は、FFT を使用することです。いくつかの素晴らしい説明については、ここまたはここを参照してください。アイデアの要点は、多項式の通常の表現 (係数のリスト) を評価基準 (慎重に選択された特定の点でのその多項式の評価のリスト) に変換することです。評価基準により、乗算は自明になります。評価の各ペアを乗算するだけです。これで、評価ベースの積多項式が得られ、補間します（評価の反対）必要に応じて係数を取得します。高速フーリエ変換 (FFT) は、評価と補間のステップを実行する非常に効率的な方法であり、係数を直接操作するよりも全体がはるかに高速になります。

  • 最長共通部分文字列。一連のテキスト ドキュメントに表示される最長の部分文字列を見つけたい場合、最速の方法の 1 つは、それぞれからサフィックス ツリーを作成し、それらをマージして、最も深い共通ノードを見つけることです。

  • 線形代数。さまざまな行列計算は、元の行列をHermite 正規形などの正規形に変換するか、QR 分解を計算することによって最も効率的に実行されます。行列のこれらの代替表現により、逆行列、行列式、または固有値を見つけるなどの標準的な処理がはるかに高速に計算されます。

これら以外にも確かにたくさんの例がありますが、私はいくつかの種類を考え出そうとしていました.

于 2014-07-09T22:11:34.140 に答える