大量のデータをディスク上に約1,000ブロックで保存する必要があります。予測するのは難しい方法でこれらのオブジェクトにアクセスしますが、パターンがおそらく存在する場所です。
アクセスパターンに基づいてディスク上のオブジェクトを再配置し、シーケンシャルアクセスを最大化して、ディスクシーク時間を最小化するアルゴリズムまたはヒューリスティックはありますか？
1123 次
5 に答える
5
最新の OS (Windows、Linux など) では、シーク時間を最適化するためにできることはまったくありません。理由は次のとおりです。
- あなたはプリエンプティブなマルチタスキング システムにいます。アプリケーションとそのすべてのデータは、いつでもディスクにフラッシュできます - ユーザーがタスクを切り替えたり、スクリーンセーバーが起動したり、バッテリーが切れたりするなど.
- ファイルがディスク上で連続していることは保証できません。Aaron の最初の箇条書きを実行しても、ファイルが断片化されていないことは保証されません。ファイルの書き込みを開始すると、OS はファイルがどれだけ大きくなるかを認識していないため、小さなスペースにファイルを配置し、より多くのデータを書き込むにつれてファイルを断片化する可能性があります。
- ファイルのメモリ マッピングは、ファイル サイズがアプリケーションで使用可能なアドレス範囲よりも小さい場合にのみ機能します。Win32 では、使用可能なアドレス空間の量は約 2Gb (アプリケーションが使用するメモリ) です。通常、より大きなファイルをマッピングするには、ファイルの一部をマッピング解除して再マッピングする必要がありますが、これは最善の方法ではありません。
- データをファイルの中央に配置しても、ファイルの中央部分が最も断片化されたビットになる可能性があるため、役に立ちません。
Raymond Chenを言い換えると、OS の制限について質問する必要がある場合は、おそらく何か間違ったことをしている可能性があります。ファイルシステムを不変のブラックボックスとして扱ってください。
最初に実行する必要がある (最適化を行っている場合は常に実行する必要がある) 手順は、現在の状態を測定することです。何も仮定しないでください。ハードデータですべてを検証します。
あなたの投稿から、実際にはまだコードを書いていないか、書いていたとしても現時点でパフォーマンスの問題はないようです。
唯一の本当の解決策は、全体像を見て、アプリケーションを停止させずにディスクからデータを取得する方法を開発することです。これは通常、非同期アクセスと投機的読み込みによって行われます。アプリケーションが常にディスクにアクセスし、データの小さなサブセットを操作している場合は、データを再編成して、すべての有用なものを 1 つの場所に配置し、その他のデータを別の場所に配置することを検討してください。完全な問題領域を知らなければ、本当に役に立つことはできません。
于 2008-12-08T11:13:02.717 に答える
2
通常のオープン シーク読み取り/書き込みパターンではなく、メモリ マップド ファイル アクセスを使用します。この手法は、Windows および Unix プラットフォームで機能します。
このようにして、オペレーティング システムの仮想メモリ システムがキャッシュを処理します。すでにメモリ内にあるブロックへのアクセスでは、ディスクのシーク時間や読み取り時間は発生しません。メモリからディスクへの書き込みは、アプリケーションをブロックすることなく、自動的かつ効率的に処理されます。
メモリ内にないチャンクの初期ロード時間に影響するため、Aaron のメモも適切です。それをメモリマップ手法と組み合わせてmemcpy()ください。結局のところ、ディスクからの読み取り/書き込みやスワップアウトなどを試みるよりも、を使用してチャンクを並べ替える方が簡単です.
于 2008-12-05T15:12:41.423 に答える
2
「予測が難しい」の意味に応じて、いくつかのオプションを考えることができます。
常に同じブロック フィールド/プロパティに基づいてシークする場合は、そのフィールドでソートされたディスクにレコードを保存します。これにより、バイナリ検索を使用して O(log n) の効率を得ることができます。
異なるブロック フィールドをシークする場合は、フィールドごとに外部インデックスを格納することを検討してください。Bツリーは O(log n) 効率を提供します。シークするときは、適切なインデックスを取得し、ブロックのデータ ファイル アドレスを検索してそこにジャンプします。
さらに良いことに、ブロックが同種の場合は、ブロックをデータベース レコードに分割することを検討してください。データベースは、最適化されたストレージ、インデックス作成、および高度なクエリを無料で実行する機能を提供します。
于 2008-12-05T16:16:29.190 に答える
1
これを解決する最も簡単な方法は、Linux のように内部で解決してくれる OS を使用することです。オブジェクトの 10% を RAM に保持するのに十分な RAM を与えると、可能な限り多くのオブジェクトをキャッシュに保持して、ロード時間を 0 に短縮しようとします。Windowsの最近のサーバーバージョンも動作する可能性があります (一部のオブジェクトは動作しませんでした)。私にとってはそうではありません、それが私がこれに言及している理由です）。
これがうまくいかない場合は、次のアルゴリズムを試してください。
ハードディスク上に非常に大きなファイルを作成します。OS がディスク上に連続したスペースを割り当てるように、これを一度に書き込むことが非常に重要です。
すべてのオブジェクトをそのファイルに書き込みます。各オブジェクトが同じサイズであることを確認してください (または、ファイル内の各オブジェクトに同じスペースを与え、各チャンクの最初の数バイトの長さに注意してください)。空のハードディスクまたは最適化したばかりのディスクを使用してください。
データ構造では、各データ チャンクのオフセットとアクセス頻度を保持します。頻繁にアクセスされる場合は、ファイルの先頭に近く、アクセス回数が少ないチャンクとファイル内の位置を入れ替えます。
[編集] OS のメモリ マップ API を使用してこのファイルにアクセスし、OS が最もよく使用される部分を効果的にキャッシュして、次回ファイル レイアウトを最適化できるまで最高のパフォーマンスを実現できるようにします。
時間の経過とともに、頻繁にアクセスされたチャンクが一番上にバブルします。アクセス パターンをしばらく収集して分析し、マシンにほとんど負荷がかからない夜間に並べ替えを行うことができることに注意してください。または、完全に別のマシンで並べ替えを行い、それが完了したらファイル (およびオフセット テーブル) を交換することもできます。
そうは言っても、多くの賢い人々がこれらの問題を解決するために長い間懸命に考えてきた最新のOSに本当に頼るべきです.
于 2008-12-05T15:08:00.340 に答える
-1
それは興味深い挑戦です。残念ながら、これをすぐに解決する方法もわかりません。コービンのアプローチは、私には理にかなっているように思えます。
少なくとも、最適化に関するちょっとした提案があります。最もアクセスの多い項目を、ディスク (または断片化されていないファイル) の中央に配置します。末尾の先頭には配置しません。そうすれば、使用頻度の低いデータを探すことが平均的に近くなります。ええと、それはかなり明白です。
ご自身で解決策を見つけた場合はお知らせください。
于 2008-12-08T09:54:11.877 に答える