-1

これが当面の問題です。
私は数万の配列を持っています。各配列の長さは 2 ～ 15 単位です。すべての配列のすべての要素の合計の長さと配列の数は、いくつかの非常に低コストの計算を使用して計算できます。しかし、かなり高価な計算が完了するまで、各配列の正確な数はわかりません。

すべての配列内のすべての要素の合計の長さを知っているので、1 つの new/malloc だけを使用してデータを割り当て、この割り当て内にポインターを設定するだけです。私の現在の実装では、特定のアイテムが挿入された後に memmove を使用してデータを移動し、それに応じてすべてのポインターを更新します。

これを行うより良い方法はありますか？

ありがとう、

  • シド
4

4 に答える 4

2

あなたがより良い方法で何を意味するのかは明らかではありません。より高速に動作し、追加のメモリを確保できるものを探している場合は、2 つの配列を保持できます。1 つはデータを含み、もう 1 つはそれが属する配列のインデックスを含みます。すべてのデータを追加した後、インデックスで並べ替えることができ、すべてのデータを配列で分割し、最後に配列をスイープして、各配列が属する場所へのポインターを取得します。

メモリ消費に関しては、配列の数とデータの大きさに応じて、インデックス データをデータの最後のビットまで絞り込むことができます。このように、数字を並べ替えるだけでよく、各配列の開始位置のポインターを取得するためにスイープするときに、上位ビットを消去できます。

于 2012-12-04T22:19:41.597 に答える
1

すべての配列のすべての要素の合計の長さを知っているので、new/malloc を 1 つだけ使用してデータを割り当て、この割り当て内にポインターを設定するだけです。

1 つの大きなベクトルを使用できます。各サブ配列のオフセットを自分で手動で計算する必要があります。

ベクトルは、データが連続したメモリに格納されることを保証しますが、ベクトルが再割り当てされるような方法で使用される場合は、個々の要素への参照またはポインタを維持するように注意してください。初期サイズを超えて何も追加していないため、問題になることはありません。

int main() {    
    std::vector<T> vec;
    vec.reserve(calc_total_size());
    // now you'll need to manually translate the offset of
    // a given "array" and then add the offset of the element to that 

    T someElem = vec[array_offset + element_offset];
}
于 2012-12-04T22:19:20.127 に答える
0

はい、もっと良い方法があります:

std::vector<std::vector<Item>> array;
array.resize(cheap_calc());
for(int i = 0; i < array.size(); ++i) {
  array[i].resize(expensive_calc(i));
  for(int j = 0; j < array[i].size(); j++) {
    array[i][j] = Item(some_other_calc());
  }
}

ポインターも、面倒なことも、大騒ぎもありません。

于 2012-12-04T22:01:35.677 に答える
0

メモリ効率、速度効率、またはシンプルさをお探しですか?

非常に単純なプール アロケータをいつでも作成またはダウンロードして、それをアロケータとして適切なデータ構造に渡すことができます。合計サイズが事前にわかっており、ベクターのサイズを変更したり、新しいベクターを追加したりする必要がないため、これは典型的なプール アロケーターよりもさらに簡単です。すべてmallocのストレージを 1 つの大きなブロックに格納し、次のブロックへの単一のポインターを保持します。n バイトを割り当てるには、T *ret = nextBlock; nextBlock += n; return ret;. オブジェクトが取るに足らないものであり、破棄する必要がない場合はfree、最後に 1 つの大きな処理を行うことさえできます。

これは、必要なデータ構造を使用したり、異なる構造を比較対照したりできることを意味します。vectorのA vector? vectorセルの巨人に加えてvectorオフセット？クレイジーに聞こえるかもしれませんが、うまくいくかもしれない他の何かを思いつきましたか? メモリ割り当ての側面を気にすることなく、読みやすさ、使いやすさ、およびパフォーマンスを比較できます。

(もちろん、あなたの目標がスピードであるなら、このように詰め込むことは最良の答えではないかもしれません.キャッシュやページの配置を改善するために少しのスペースを無駄にすることで、多くの場合、多くのスピードを得ることができます. 、たとえば、転置された方法でベクトル空間を割り当てて、列優先を行うアルゴリズムのパフォーマンスを向上させますが、その時点では、アロケータよりもアルゴリズムを微調整する方がおそらく簡単です。 )

于 2012-12-05T03:04:02.123 に答える