5

どこにも答えが見つからない、一見単純な質問を投げかけたいと思います。標準準拠のすべての C++ コンパイラでコンパイルでき、外部ライブラリを必要とせずにすべてのオペレーティング システムで動作する、ファイル入力および/または出力用の最新のFASTアルゴリズムはありますか?

  1. 最速の方法はメモリ マップされたファイルを使用することですが、すべてのプラットフォームで同じコードを動作させる必要があるため、そうはなりません。
  2. Win32 API のような API を使用できないため、プラットフォーム固有になります
  3. 私はcを使いたくありません。可能な場合、アルゴリズムをstlを使用した純粋なc ++コードにしたいのですが、asmハック/トリックが混在した醜いcではありません
  4. wxWidgets、Qt、MFC などの標準 C++ に属さないフレームワークまたは外部ライブラリは使用しないでください。
  5. この質問全体の大きな強調点は、アルゴリズムが可能な限り高速であることです。メモリマップされたファイルでそれを実行する速度に沿ったものであり、さらに高速であることは素晴らしいことですが、それは不可能であることを私は知っています

私以外の誰かがこれほどクレイジーな研究をしているのを見たことがありますか? そのようなアルゴリズムは可能ですか?

推奨事項をありがとう

4

7 に答える 7

9

次の制限があります。

標準準拠のすべての C++ コンパイラでコンパイルでき、外部ライブラリを必要とせずにすべてのオペレーティング システムで動作します。

標準ライブラリ ファイルの IO 関数にかなり制限されています。おそらくPOSIX関数（「すべての標準準拠C ++コンパイラ」のどのサブセットを検討しているかによって異なります）。

それらが十分に速くない場合は、いくつかの制限を解除する必要があります。

于 2010-01-26T00:33:46.963 に答える
9

これは「アルゴリズム」とは何の関係もありません。

ファイルへのデータの書き込みに関しては、オペレーティングシステムに翻弄されます.メモリに書き込むだけなので、メモリマップファイルは「高速」であり、OSは独自の時間に同期します。OS がそれをサポートしていない場合、独自のメモリ マッピング レイヤーを実装したい場合を除き、その点では不運です。

ちなみに、POSIX にはmmap.

于 2010-01-26T00:34:48.910 に答える
4

「OS の慈悲」について別の見方をすると、ファイルをコピーする際のオーバーヘッドのほとんどはオペレーティング システムにあります。断片化されたファイルは、最適化されたファイルよりも読み取りに時間がかかります。断片化されたファイルを検出するための汎用または標準の C++ 関数はありません。

C++ で最速の方法:

std::ifstream in_file;
std::ofstream out_file;

out_file << in_file.rdbuf();

詳細については、「 copy file rdbuf 」というキーワードで Web を検索してください。上記のフラグメントは、コピーを OS に任せますが、すべてのプラットフォームで移植可能です。C++ i/o ストリームに読み込むことで、読み込みバッファのサイズを設定したり、独自のバッファを使用したりできます。

より高速なファイル コピーには、DMA 転送などのプラットフォーム固有の機能が必要です。スレッドと複数のバッファリングを使用すると、これを高速化できます。しかし、C++ はスレッドをサポートしていません (スレッドをサポートする事実上の標準である POSIX があります)。あるスレッドがバッファに読み込み、別のスレッドがバッファから書き込みます。

于 2010-01-26T18:04:58.480 に答える
2

いくつかのポイント:

  • これはアルゴリズムとは関係ありません。
  • すべてのオペレーティング システムをターゲットにすることは、あまり生産的な目標ではありません (そして、それは不可能です)。
  • コードは、テストするまで特定のプラットフォームでは機能しません)。代わりに、実行可能なオペレーティング システムのセットに焦点を当てます。たとえば、POSIX + Win32 です。
  • その場合、たとえば Windows 用の mmap() を実装することにより (MapViewOfFile() などの上に -- インスピレーションが必要な場合は、git ソース コードに Windows 用の mmap 実装が含まれています)、メモリ マッピングを行うことができます。
  • メモリ マッピングを使用できない場合、パフォーマンスが重要な場合は、C++ のファイル ストリームではなく、通常の C ファイル API を使用することをお勧めします。C++ のストリームは一部の操作でパフォーマンスが向上する可能性がありますが、実際にはかなり遅くなります。
  • ただし、優れたパフォーマンスを得るには、データを適切に処理していることを確認するだけで「十分」であることがよくあります。データをシーケンシャルに読み取り、再読み取りしないなど。完璧は善の敵です ;)
于 2010-01-26T00:41:41.123 に答える
1

通常、Fast IO は次の 2 つに要約されます。

  1. データのコピーを最小限に抑える
  2. カーネル/ユーザー コンテキストの切り替えを最小限に抑える

ほとんどすべての IO 手法は、どちらか一方に対処しようとします。私が知っている IO の最速のクロスプラットフォーム コードは、Perl IO システムです。ソースを見ることをお勧めします。Perl ハッカーは、可能な限り多くのプラットフォームで IO を可能な限り高速化するために何十年も費やしてきました。

于 2010-01-26T05:46:23.717 に答える
1

ファイル システムのブロック サイズの倍数 (または 2 のべき乗) のブロックを順番に読み取ると、役立つ場合があります。次に、ブロックがメモリに格納されたら、データを分解します。さまざまなブロック サイズのパフォーマンスをテストしたホワイト ペーパーがどこかにあります。また見つけたいです。

また、ファイルからブロックを読み取るための専用スレッドと、メモリ内のデータ操作を行う別のスレッドを用意することもできます (もちろん、適切な同期を使用して)。これにより、ファイルの読み取り呼び出しをブロックしている間に、CPU を使用してデータを処理できます。

とにかく、これらのアイデアを試してみて、違いに気づいたらお知らせください。ベンチマーク テストの実際の結果は興味深いものになるでしょう。

于 2010-01-26T03:36:35.997 に答える
0

他のポスターは、パフォーマンスが常に汎用性 (クロスプラットフォーム) と矛盾するという点で正しいです。

ただし、一般的には、入力を「バッファリング」することによって最良の結果が得られます。fread() を使用して比較的大きなデータのチャンクを読み取り、それらを処理します。

それがかなり基本的で一般的な答えであることは知っていますが、それは、プラットフォーム固有であるか、処理している特定の入力について詳しく知らなくても、得られるのと同じくらい具体的です。

于 2010-01-26T02:07:41.293 に答える