1

私は最近、次の投稿を書きました:
c++ で VERY large 2D list of floats を保存するにはどうすればよいですか? エラー処理？

float の 2D リストのような構造をベクトルとして実装することを提案する人もいれば、deque と言う人もいました。

私が収集したものから、ベクトルは連続メモリを必要としますが、したがってより効率的です。明らかに、可能であればこれが望ましいでしょう。

したがって、私の質問は、基本構造がどのくらいの長さになるかについての良いルールは何ですか...

1. float
2. int

...メモリの問題を回避するためにベクトルから両端キューに切り替える前に?

たとえば、「約 400 万の float または 800 万の int で、切り替える必要があります...」などの回答を探しています ...可能であれば。

4

7 に答える 7

4

さて、ここで2つの意見があります。C++ 標準は次のように述べています (23.1.1/2):

vectorデフォルトで使用されるシーケンスのタイプです。

list配列の途中からの挿入と削除が頻繁にある場合に使用する必要があります。

dequeほとんどの挿入と削除がシーケンスの先頭または末尾で行われる場合に選択されるデータ構造です。

Herb Sutter は次のように主張しています(この記事には、彼の理論的根拠とパフォーマンス分析が含まれています)。

親しみを込めて反対意見を述べたいと思います: 特に含まれる型が組み込み型ではなくクラスまたは構造体である場合は、ベクターではなくデフォルトで deque を優先することを検討することをお勧めします。連続する。

于 2010-09-17T19:36:07.197 に答える
2

最初に挿入が必要な場合は、dequeを使用してください。

それ以外の場合は、 （ここでJames McNellisによってリンクされているものに加えて）vectorvs.dequeに関するこの記事を常に指摘したいと思います。ページベースの割り当てを使用するdequeの実装を想定して、この記事では、reserve（）がある場合とない場合のベクトルとdequeの割り当て時間（および割り当て解除時間）を適切に比較しています。基本的に、reserve（）を使用すると、ベクトルの割り当て時間がdequeと非常に似たものになります。有益であり、事前に予約する適切な値を推測できる場合に役立ちます。

于 2010-09-17T19:52:15.590 に答える
2

繰り返しになりますが、deque が vector よりも優れている、または優れていないサイズの制限はありません。メモリの断片化の影響は、どちらの場合でもほとんど同じですが、割り当て/割り当て解除の膨大な負荷を既に実行しており、大きなベクトル用に十分な連続スペースが残っていない場合を除きます。しかし、このケースは非常にまれです。メモリスペースはプロセスごとにあることに注意してください（仮想メモリのグーグル）。reserveまた、クラッタリングが発生する前に(メソッドによって) ベクターにメモリを割り当てることで、問題を解決できます。

トレードオフは、それで何をしたいかという点です。構造体が基本的に不変であり、インデックス アクセスによってアクセス/上書きするだけの場合は、ベクターを使用します。

Deque は、最後、最初、または途中で挿入を行う必要がある場合で、ベクターでは自然に処理できないものです (最後の挿入を除く)。

Herb Sutter の記事は概して質が高いですが、C++ で「数値計算」を行う場合、「一般的な C++」の本で教えられていることのほとんどは、特別な注意を払って行う必要があることに気付くでしょう。deques で発生するインデックス作成のパフォーマンスの低下は、アプリケーションにとっておそらく重要です。この場合、deque を使用しないでください。

于 2010-09-17T19:46:26.070 に答える
1

考慮すべき要素が非常に多いため、明確な答えを出すことは不可能です。マシン上のメモリの量、断片化の程度、断片化の程度など。私の提案は、1つを選択して使用することです。問題が発生した場合は切り替えてください。とにかく、これらのエッジケースにぶつかる可能性はありません。

本当に心配している場合は、おそらく一種の疑似PIMPLを実装できます。

template<typename T>
class VectorDeque
{
private:
  enum TYPE { NONE, DEQUE, VECTOR };
  std::deque<T> m_d;
  std::vector<T> m_v;
  TYPE m_type;
  ...
public:
  void resize(size_t n)
  {
    switch(m_type)
    {
      case NONE:
      try
      {
        m_v.resize(n);
        m_type = VECTOR;
      }
      catch(std::bad_alloc &ba)
      {
        m_d.resize(n);
        m_type = DEQUE;
      }
      break;
    }
  }
};

しかし、これは完全にやり過ぎのようです。ベンチマークやテストを行いましたか？メモリの割り当てが失敗する、または両端キューが遅すぎると信じる理由はありますか？

于 2010-09-17T20:00:21.827 に答える
1

テストとプロファイリングにより、アプリケーションにとって一方が他方よりも悪いことが示されたら、切り替えます。「N float または M int 前後」の普遍的な答えはありません。

于 2010-09-17T20:23:32.360 に答える
0

メモリに関しては、連続したメモリ ブロック (malloc または std::vector) がいつ大きくなりすぎるかを判断するのに役立ついくつかの経験を共有できます。

私が使用しているアプリケーションは、ほとんどが 4byte の測定データを記録floatします。このために、データを保存するために内部バッファーを割り当てます。これらのバッファーのサイズは大きく異なりますが、典型的な範囲は、1 ～ 10 MB の数十個と 100 MB を超えるごく少数です。callocバッファは常に、つまり 1 つの大きなメモリ チャンクで割り当てられます。バッファ割り当てが失敗した場合、エラーがログに記録され、ユーザーは再試行を選択できます。

バッファサイズ: 100Hz で 10 分間 1000 チャネルを記録したいとします: 4 バイト x 1000 x 100 x 60x10 == 228 MB (概算) ... または 10Hz で 12 時間 100 チャネル == 41 MB

40MB のバッファ (約 1000 万個の浮動小数点数) の割り当てに (ほぼ) 問題が発生したことはなく、200 ～ 300 MB のバッファは時々失敗します。これはすべて、4GB RAM を搭載した通常の WinXP/32 ビット ボックスで発生します。

于 2010-09-17T20:17:24.063 に答える
0

作成後に挿入しないことを考えると、通常の old を使用するか、断片化が本当に問題になる場合は、ベクトルまたは固定サイズ配列へのポインタの配列として実装されstd::vectorたカスタム ベクトルのようなSequenceを使用する必要があります。

于 2010-09-17T20:20:32.300 に答える