Speichereffiziente Umwandlung zwischen einer HashMap und einem Vec

Question

Ich versuche, eine große HashMap<K, V> zu Vec<(K, V)> zu konvertieren. Der üblicher Weg, es zu tun wie folgt aussieht:

// 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)>>(); 

Dieser Code funktioniert nicht gut, wenn HashMap groß genug ist - am Anfang des Anrufs collect(), wird die ursprünglichen HashMap noch in Erinnerung sein und Vec wird zugeordnet mit der Kapazität der unteren Größe Hinweis aus der Iterator entnommen. Dies verursacht eine nicht genügend Speicher-Panik für wirklich große HashMap s, obwohl ich in der Lage sein sollte zwischen diesen beiden Typen mit sehr wenig zusätzlichen Speicheraufwand zu konvertieren. Bisher habe ich kam mit der folgenden Lösung:

// 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); 
    } 
} 

Gibt es einen besseren (effizientere oder idiomatischen) Ansatz für dieses Problem? Ich bin bereit, unsafe Code zu verwenden, wenn es Leistung verbessern würde.

bearbeiten Wie bereits into_iter aus während der Iteration nicht freigeben, so dass die vorgeschlagene Lösung nicht wie vorgesehen. Gibt es eine andere Möglichkeit, diese Sammlungen zu konvertieren von HashMap in die Datei und dann lesen Sie diese Datei in Vec?

Answer 1

Es scheint, dass Sie nicht mit Vec Implementierung von FromIterator Eigenschaft zufrieden sind. Ich weiß nicht, ob es vernünftig ist, es in Std zu ändern. Sie können jedoch einen Wrapper für Vec einzuführen und umzusetzen FromIterator, wie Sie wollen:

#[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(); 

Der Vec Wert zugänglich als vec.0 sein wird.

Answer 2

Die genaue Menge, die im Voraus benötigt wird ist die speicher- und zeiteffiziente Lösung.

Angenommen, Sie möchten einen Vektor mit 100 Elementen erstellen. Wenn Sie Platz für 50 Artikel zuweisen möchten, gibt es zwei Möglichkeiten:

Die Zuordnung kann an Ort und Stelle erweitert werden und Sie auf Ihrem fröhlichen Weg fortsetzen.

Die Zuweisung kann nicht an Ort und Stelle erweitert werden, sodass eine neue, größere Zuweisung vorgenommen wird. Alle Daten müssen aus der vorherigen Zuordnung kopiert werden; wahrscheinlich eine O (n) -Operation. Während dieser Kopie sind beide Zuordnungen live und belegen 50 + 100 Steckplätze, mehr Speicherplatz, als wenn die ursprüngliche Zuordnung richtig bemessen wäre.

Es ist nicht möglich zu wissen, welcher Fall passieren wird.

Dies ist einer der Gründe, dass Iterator hat die size_hint Methode: zu wissen, wie viele Elemente für effizienter zu reservieren ist.

Auf der anderen Seite speichert die HashMap wahrscheinlich die Daten in einer großen Zuordnung, da es effizienter ist. Dies bedeutet, dass es nicht möglich (oder vielleicht nicht einfach/effektiv) ist, ein Element zu verschieben und dann die Zuweisung zu verringern.Selbst wenn Sie dies tun könnten, hätten Sie am Anfang der Kopie sowohl die gesamten HashMap als auch Vec zugewiesen.

Es gibt zwei Möglichkeiten, die ich daran denken kann, könnte die Situation verbessern:

1. Wenn HashMap speichert die Daten intern in einem Vec, dann möglicherweise ein Verfahren zu HashMap hinzugefügt werden könnten, dass Vec nach einiger zuletzt zurückkehrt -minute Sanitisierung.
2. Lagern Sie die HashMap und/oder Vec überhaupt nicht. Wenn Sie zum Beispiel über die Daten iterieren müssen, müssen Sie nicht zuerst collect zu einem Vec; Iterieren Sie einfach darüber.