9

ある種の2次元配列を使用する必要がある場所に取り組んでいる問題があります。配列は固定幅 (4 列) ですが、その場で余分な行を作成する必要があります。

これを行うために、私はベクトルのベクトルを使用しており、これを含むいくつかのネストされたループを使用しています。

array.push_back(vector<float>(4));
array[n][0] = a;
array[n][1] = b;
array[n][2] = c;
array[n][3] = d;
n++

行とその内容を追加します。問題は、作成しようとしていた要素の数でメモリが不足しているように見えることです。そのため、使用していた要素の数を減らしました。しかし、その後、deque について読み始め、連続している必要がないため、より多くのメモリを使用できるようになると考えました。このループでは、すべての宣言と同様に、「vector」のすべての言及を「deque」に変更しました。しかし、今度は行数を減らしても、再びメモリが不足しているように見えました。

コードが使用しているメモリの量を調べたところ、deque を使用している場合、メモリは 2GB を超えて着実に増加し、使用する行数が少ない場合でもプログラムはすぐに終了します。このループのどこがメモリ不足になるのか正確にはわかりません。

ベクトルを使用すると、ループが終了してもメモリ使用量 (同じ行数の場合) は 1GB 未満です。その後、さらに行が追加される同様のループに進みますが、まだ約 1.4GB にしか達していません。

だから私の質問はです。deque が vector の 2 倍以上のメモリを使用するのは普通のことですか、それとも、宣言/初期化と上記のコードで "vector" という単語を "deque" に置き換えるだけでよいという誤った仮定をしているのですか?

前もって感謝します。

使用しています: MS Visual C++ 2010 (32 ビット) Windows 7 (64 ビット)

4

5 に答える 5

5

それはすべて の内部実装に依存します(比較的簡単なので説明しdequeません)。vector

実際には、(最も重要なのは、両端でO(1) 挿入をサポートし、後ろで O(1) 挿入のみをサポートすることです) とdequeは完全に異なる保証があります。これは、 によって管理される内部構造がよりも複雑でなければならないことを意味します。vectorvectordequevector

これを可能にするために、典型的なdeque実装では、メモリをいくつかの連続しないブロックに分割します。しかし、個々のメモリブロックには、メモリ管理が機能するように固定のオーバーヘッドがあります (たとえば、ブロックのサイズに関係なく、システムは簿記のためにさらに 16 バイトまたは 32 バイトなどを必要とする場合があります)。a とは対照的にvector、 adequeは多くの小さな独立したブロックを必要とするため、オーバーヘッドが積み重なり、目に見える違いを説明できます。また、これらの個々のメモリ ブロックは (おそらく別の構造体で) 管理する必要があることに注意してください。これは、おそらく追加のオーバーヘッドもいくらか (または多く) することを意味します。

問題を解決する方法については、コメントで@BasileStarynkevitchが提案したことを試すことができます。これにより、実際にメモリ使用量が削減されますが、ある時点でまだメモリが不足するため、これまでのところしか取得できません。そして、256MB の RAM しかないマシンでプログラムを実行しようとするとどうなるでしょうか? すべてのデータをメモリに保持しようとしながら、メモリフットプリントを削減することを目標とする他のソリューションは、同じ問題に悩まされます。

あなたのような大規模なデータセットを処理するときの適切な解決策は、アルゴリズムとデータ構造を調整して、データセット全体の小さなパーティションを一度に処理できるようにし、必要に応じてそれらのパーティションをロード/保存して、他のパーティション。残念ながら、おそらくディスクアクセスを意味するため、パフォーマンスが大幅に低下することも意味しますが、ケーキを食べて食べることはできません.

于 2013-04-27T12:52:09.353 に答える
5

仮説

両端キューを効率的に実装する一般的な方法は 2 つあります。変更された動的配列を使用する方法と、二重にリンクされたリストを使用する方法です。

変更された動的配列の使用は、基本的に、両端から拡張できる動的配列であり、配列 dequesと呼ばれることもあります。これらの配列両端キューには、動的配列のすべてのプロパティがあります。たとえば、一定時間のランダム アクセス、適切な参照の局所性、途中での非効率的な挿入/削除、代わりに両端で償却された一定時間の挿入/削除が追加されています。片端だけ。

変更された動的配列にはいくつかの実装があります。

  1. 基になる配列の中心から両端キューの内容を割り当て、いずれかの端に達したときに基になる配列のサイズを変更します。このアプローチでは、特に要素が一方の端にのみ挿入される場合に、サイズ変更を頻繁に行う必要があり、より多くのスペースを浪費する可能性があります。

  2. deque の内容を循環バッファーに格納し、バッファーがいっぱいになったときにのみサイズを変更します。これにより、サイズ変更の頻度が減少します。

  3. コンテンツを複数の小さな配列に格納し、必要に応じて先頭または末尾に追加の配列を割り当てます。小さい配列のそれぞれへのポインターを含む動的配列を保持することによって、インデックス付けが実装されます。

結論

さまざまなライブラリがさまざまな方法で両端キューを実装する場合がありますが、通常は変更された動的配列として実装されます。ほとんどの場合、標準ライブラリは #1 のアプローチを使用して を実装しstd::dequeます。一方の端からのみ要素を追加するため、最終的に多くのスペースを無駄にします。そのため、std::deque通常よりも多くのスペースを占有する錯覚を起こしますstd::vector。

さらに、std::deque二重にリンクされたリストとして実装される場合、各要素はカスタム データに加えて 2 つのポインターを収容する必要があるため、スペースの浪費にもなります。

アプローチ 3 (変更された動的配列アプローチも) で実装すると、これらすべての小さな配列へのポインターなどの追加のメタデータを収容するためにスペースが無駄になります。

いずれにせよ、std::dequeは単純な古いものよりもストレージの面で効率が悪いstd::vectorです。何を達成したいのかわからない場合、必要なデータ構造を自信を持って提案することはできません。ただし、deques が何のためにあるのかさえ知らないようです。したがって、状況で本当に必要なのはstd::vector. 一般に、deques にはさまざまな用途があります。

于 2013-04-27T12:52:29.167 に答える
3

Deque は、連続したブロックではなくいくつかのブロックで構成されているため、vector よりも追加のメモリ オーバーヘッドが発生する可能性があります。

en.cppreference.com/w/cpp/container/dequeから:

とは対照的にstd::vector、 a の要素はdeque連続して格納されません。典型的な実装では、個別に割り当てられた固定サイズの配列のシーケンスを使用します。

于 2013-04-27T12:50:16.890 に答える
1

主な問題はメモリ不足です。

では、一度にメモリ内のすべてのデータが必要ですか?
これを達成することは決してできないかもしれません。

部分処理

データを「チャンク」またはより小さなサブマトリックスに処理することを検討することをお勧めします。たとえば、標準の長方形グリッドを使用すると、次のようになります。

  • 第 1 象限のデータを読み取ります。
  • 第 1 象限のプロセス データ。
  • 第 1 象限の結果を (ファイルに) 保存します。
  • 残りの象限について繰り返します。

検索中

粒子または一連のデータムを検索する場合、データ セット全体をメモリに読み込まなくても検索できます。

  1. メモリのブロック (配列) を割り当てます。
  2. データの一部をこのメモリ ブロックに読み込みます。
  3. データのブロックを検索します。
  4. データが見つかるまで、手順 2 と 3 を繰り返します。

ストリーミング データ

アプリケーションが入力ソース (ファイル以外) から生データを受け取る場合、後で処理するためにデータを保存する必要があります。

これには複数のバッファが必要であり、少なくとも 2 つの実行スレッドを使用するとより効率的です。

読み取りスレッドは、バッファがいっぱいになるまでデータをバッファに読み込みます。バッファがいっぱいになると、別の空のバッファにデータが読み込まれます。

書き込みスレッドは、最初の読み取りバッファーがいっぱいになるか、読み取り操作が完了するまで待機します。次に、書き込みスレッドが読み取りバッファーからデータを取り出し、ファイルに書き込みます。その後、書き込みスレッドは次の読み取りバッファーから書き込みを開始します。

この手法は、ダブル バッファリングまたはマルチプル バッファリングと呼ばれます。

スパース データ

行列にゼロまたは未使用のデータが多数ある場合は、スパース行列を使用してみてください。基本的に、これはデータの座標と値を保持する構造体のリストです。これは、ほとんどのデータがゼロ以外の共通値である場合にも機能します。これにより、多くのメモリ スペースが節約されます。ただし、実行時間が少し長くなります。

データ圧縮

データ圧縮を使用するようにアルゴリズムを変更することもできます。ここでの考え方は、データの場所、値、および数または連続した等しい値 (別名ラン) を格納することです。したがって、同じ値の 100 個の連続したデータ ポイントを格納する代わりに、(実行の) 開始位置、値、および数量として 100 を格納します。これにより、多くのスペースが節約されますが、データにアクセスする際により多くの処理時間が必要になります。

メモリマップファイル

ファイルをメモリとして扱えるライブラリがあります。基本的に、ファイルの「ページ」をメモリに読み込みます。リクエストが「ページ」から出ると、別のページを読み込みます。これはすべて「舞台裏」で実行されます。ファイルをメモリのように扱うだけです。

概要

配列と両端キューは主な問題ではなく、データの量です。主な問題は、一度に小さなデータを処理するか、データ ストレージを圧縮するか、ファイル内のデータをメモリとして扱うことで解決できます。ストリーミング データを処理しようとしている場合は、処理しないでください。理想的には、ストリーミング データをファイルに配置し、後で処理する必要があります。ファイルの歴史的な目的は、メモリに収まらないデータを含めることです。

于 2013-04-27T16:59:02.910 に答える