HashMapとVecの間のメモリ効率的な変換

Question

大きなHashMap<K, V>をVec<(K, V)>に変換しようとしています。それを行うための通常の方法は次のようになります。

// initialize HashMap 
let cap = 50000000; 
let mut hm: HashMap<usize, usize> = HashMap::new(); 
for i in 0..cap { 
    hm.insert(i, i); 
} 
// convert HashMap to Vec 
let vec = hm.into_iter().collect::<Vec<(usize, usize)>>(); 

HashMapが十分に大きい場合には、このコードがうまく動作しない

- 通話の開始にcollect()に、元HashMapはまだメモリになり、Vecは次のようになりますIteratorから取られたより小さいサイズのヒントの容量で割り当てられます。これにより、メモリオーバーヘッドがほとんどなく、これらの2つのタイプ間で変換できるはずですが、実際には大きなメモリ不足が発生します（HashMap）。これまでのところ私は、次の解決策を考え出したています

// create small vector 
let mut vec: Vec<(usize, usize)> = Vec::with_capacity(100); 
for i in hm.into_iter() { 
    vec.push(i); 
    // reserve few megabytes 
    if vec.capacity() - vec.len() < 10 { 
     vec.reserve_exact(1000000); 
    } 
} 

この問題へのより良い（より効率的な以上の慣用）アプローチはありますか？パフォーマンスを向上させる場合は、unsafeコードを使用します。

編集 としてはinto_iterが反復中に解放していません指摘し、その意図したとおりに提案された解決策は動作しません。これらのコレクションを別の方法で変換してHashMapをファイルにダンプし、そのファイルをVecに読み込む方法はありますか？

Answer 1

Vecの実装では、FromIteratorの特性に満足していないようです。私はstdでそれを変更するのが妥当かどうかわかりません。

#[derive(Debug)] 
struct OptimizedVec<T>(Vec<T>); 

impl<T> std::iter::FromIterator<T> for OptimizedVec<T> { 
    #[inline] 
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> OptimizedVec<T> { 
     let mut vec = Vec::with_capacity(100); 
     for i in iter { 
      vec.push(i); 
      // reserve few megabytes 
      if vec.capacity() - vec.len() < 10 { 
       vec.reserve_exact(1000000); 
      } 
     } 
     OptimizedVec(vec) 
    } 
} 

//... 
let vec: OptimizedVec<_> = hm.into_iter().collect(); 

Vec値はvec.0としてアクセスできるようになります。しかし、あなたが望むようにVecのラッパーを導入し、FromIteratorを実装することができます。

Answer 2

正面に必要な量を正確に割り当てるは、のメモリと時間効率の高いソリューションです。

100アイテムのベクトルを作成したいとします。 50個のアイテムのスペースを割り当てる場合、アイテム51を追加すると、2つの可能性があります。

1. 割り振りを拡張してメリー・ウェイを続けることができます。
2. 割り振りを拡張することはできません。そのため、新しいより大きな割り当てが行われます。前の割り当てからすべてのデータをコピーする必要があります。おそらくO（n）操作です。このコピーでは、両方の割り当てがライブであり、元の割り当てが適切なサイズよりも小さい場合は、以上、スペースを使用します。

どのようなケースが起こるかわからないので、最悪の場合を想定する必要があります。

Iteratorにはsize_hintという方法がある理由の1つは、割り当てるアイテム数を知る方が効率的です。

HashMapは、より効率的であるため、データを1つの大きな割り当てに格納する可能性があります。つまり、1つのアイテムを移動して割り当てを減らすことは不可能（または簡単/効果的ではない）であることを意味します。これを行うことができたとしても、コピーの冒頭にはHashMapとVecの両方が割り当てられます。内部Vec内のデータは、その後、潜在的方法はHashMapに追加することができ

1. HashMapもし店いくつかの最後の後にそのVecを返します。

   状況を改善することができ、私はそのことを考えることができる2つの可能性があります - 丁寧な衛生化。

2. HashMapおよび/またはVecを保管しないでください。たとえば、データを反復処理する必要がある場合は、最初にVecにcollectを設定する必要はありません。それを繰り返すだけです。