Effizienz des Anhängens an Vektoren

Question

Das Anhängen eines Elements an ein Millionenelement ArrayList kostet jetzt eine Referenz und das Kopieren einer Referenz in der Zukunft, wenn die Größe der ArrayList geändert werden muss.

Wie ich es verstehe, muss das Anhängen eines Elements an ein Millionenelement einen neuen Pfad erstellen, der aus 4 Arrays der Größe 32 besteht. Das bedeutet, dass mehr als 120 Referenzen berührt werden müssen.

Wie schafft es Clojure, den Vektor-Overhead auf "2,5-mal schlechter" oder "4-mal schlechter" zu halten (im Gegensatz zu "60-mal schlechter"), was in mehreren Clojure-Videos behauptet wurde? Hat es etwas mit Caching oder Fundort zu tun oder etwas, das mir nicht bekannt ist?

Oder ist es irgendwie möglich, einen Vektor intern mit Mutation zu bauen und ihn dann unveränderlich zu machen, bevor er ihn der Außenwelt offenbart?

Ich habe die Frage scala auch markiert, seit scala.collection.immutable.vector ist im Grunde die gleiche Sache, richtig?

Answer 1

Clojures PersistentVectors haben einen speziellen Tail-Buffer, um einen effizienten Betrieb am Ende des Vektors zu ermöglichen. Erst nachdem dieses 32-Elemente-Array gefüllt ist, wird es dem Rest des Baums hinzugefügt. Dies hält die fortgeführten Anschaffungskosten niedrig. Here ist ein Artikel über die Implementierung. Die source ist auch eine Lektüre wert.

In Bezug auf "ist es irgendwie möglich, einen Vektor intern mit Mutation zu bauen und ihn dann unveränderlich zu machen, bevor er es der Außenwelt offenbart?", Ja! Diese sind in Clojure als transients bekannt und werden für effiziente Chargenwechsel verwendet.

Answer 2

Kann nicht über Clojure erzählen, aber ich kann einige Kommentare über Scala Vectors geben.

Persistente Scala Vektoren (scala.collection.immutable.Vector s) sind viel langsamer als ein Array-Puffer, wenn es zum Anhängen kommt. Tatsächlich sind sie 10x langsamer als die List Vorlaufoperation. Sie sind 2x langsamer als das Anhängen an Conc-Bäume, die wir in parallelen Sammlungen verwenden.

Aber Scala hat auch veränderbare Vektoren - sie sind in der Klasse VectorBuilder versteckt. Das Anfügen an veränderbare Vektoren behält die vorherige Version des Vektors nicht bei, sondern mutiert sie an Ort und Stelle, indem der Zeiger auf das Blatt ganz rechts im Vektor gehalten wird. Also, ja - den Vektor intern änderbar zu halten und eine unveränderliche Referenz zurückzugeben, ist genau das, was in Scala Sammlungen gemacht wird.

Die VectorBuilder ist etwas schneller als die ArrayBuffer, weil sie ihre Arrays nur einmal zuweisen muss, während ArrayBuffer es zweimal im Durchschnitt tun muss (wegen des Wachsens). Conc.Buffer s, die wir als Parallel Array Combiner verwenden, sind doppelt so schnell verglichen mit VectorBuilder s.

Benchmarks sind hier. Keiner der Benchmarks alle Boxen beinhalten, sie arbeiten mit Referenzobjekten jegliche Verzerrungen zu vermeiden:

• comparison of Scala List, Vector and Conc
• comparison of Scala ArrayBuffer, VectorBuilder and Conc.Buffer

Weitere Sammlungen Benchmarks here.

Diese Tests wurden unter Verwendung von ScalaMeter ausgeführt.