HashMap和Vec之間的內存高效轉換

我試圖將大HashMap<K, V>轉換爲Vec<(K, V)>。這樣做的通常的方式是這樣的：HashMap和Vec之間的內存高效轉換

// 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中分配了較小尺寸提示的容量。這會導致內存不足，造成真正大的HashMap s，儘管我應該可以在這兩種類型之間進行轉換，而只需很少的額外內存開銷。

// 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之外，是否還有其他方式來轉換這些集合？

來源

2016-08-22 Fuine

你確定你的第二個代碼有更少的內存開銷嗎？我認爲迭代過程中'IntoIter'迭代器不會釋放內存。實際上它不容易做這種對話，只需很少的額外內存...... –

如果沒有足夠的內存同時存儲'HashMap'和'Vec'，則可能需要切換計算機，或者重新調整程序以便能夠處理較小的工作（例如MapReduce）。事實上，你的空間非常小：如果問題的規模增加了50％，那麼你可能很可能是帶有* HashMap的OOM，那麼你打算怎麼做？ –

看來你不滿意Vec的FromIterator特性的實現。我不知道在std中改變它是否合理。但是，你可以引入一個包裝爲Vec和實施FromIterator如你所願：

#[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。

來源

2016-08-22 10:50:23

除非我完全誤解了某些東西，否則將它修改爲'std'絕對不合理。內存優化實施將遠遠低於現在的做法。我也懷疑OP自己的實現可以幫助... –

我打算將該代碼封裝在自定義結構中，但爲了簡化問題，我沒有發佈它。我明白，std的實現不應該改變，因爲這會產生大量的時間影響。我的用例很少，我想知道是否有更好的方法比連續的'reserve_exact'調用。 – Fuine

這個想法是，你保留一個相對較小的項目，這樣推動就不必重新分配。我將編輯問題以避免錯誤信息（我認爲into_iter在遍歷迭代器時釋放內存）。 – Fuine

預先分配需要的確切數量是內存和時間有效的解決方案。

假設您想創建一個包含100個項目的向量。如果您要爲50個項目分配空間，則當您添加項目51時，存在兩種可能性：

分配可以在適當的位置進行擴展，並繼續您的快樂方式。
分配不能在原地進行，因此會產生新的更大的分配。所有的數據需要從以前的分配中複製;可能是O（n）操作。在此副本中，兩個分配都是實時的，佔用50 + 100個插槽，如果原始分配的大小適當，則可以使用多個空間。

不可能知道會發生什麼情況，所以你必須假設最壞的情況。

這是Iterator擁有size_hint方法的原因之一：知道要分配的項目數量更有效。

另一方面，HashMap可能將數據存儲在一個大的分配中，因爲它更高效。這意味着將一個項目移出然後減少分配是不可能的（或者可能不容易/有效）。即使你可以做到這一點，在副本的開始，你會分配整個HashMap和Vec。

有兩種可能性，我能想到的，可以改善這種情況：

如果HashMap內部存儲在Vec數據，那麼可能的方法可以被添加到HashMap，經過一些最後返回Vec - 清潔衛生。
根本不要儲存HashMap和/或Vec。例如，如果您需要迭代數據，則首先不需要collect至Vec;只是迭代它。

來源

2016-08-22 13:50:08 Shepmaster

我想我記得'HashMap'使用了3個向量，如下所示：（哈希值，鍵值）。因此，從HashMap '到'Vec <（usize，usize）>'沒有小的轉換。 –

HashMap和Vec之間的內存高效轉換

回答

相關問題