Warum die Verarbeitung von Arrays in F # ist schneller als Listen

Question

Ich habe die Leistung von F # Listen und Arrays überprüft. Angesichts der Code:

let list = [ 1.. 100000 ] 
for i in 1 .. 100 do ignore (list|>List.map(fun n -> n)) 

let array = [| 1.. 100000 |] 
for i in 1 .. 100 do ignore (array|>Array.map(fun n -> n)) 

Ich würde beide vermuten sehr ähnliche Zeit laufen in. Tatsächlich stellte sich heraus, dass Arrays über 10 mal schneller sind: Array dauert 28 ms, während die Liste 346 ms dauert! Warum ist das? Ich verstehe das Konzept der Liste in F # und die Tatsache, dass zum Beispiel das Anhängen von Werten zum Auflisten oder Nehmen von Unterfolgen zeitaufwendig ist, aber in diesem Code durchläuft es einfach alle Elemente, so dass ich dachte, dass das Timing sehr vergleichbar sein wird.

Tests im Release-Modus in Visual Studio 2012 (im Debug-Modus Arrays sind etwa 5-mal schneller).

Answer 1

Der Hauptunterschied besteht darin, dass Arrays als fortlaufender Speicherblock zugewiesen werden - die Array.map-Funktion kennt die Größe des Eingangsarrays und kann nur eine einzige Zuweisung durchführen, um den gesamten Speicher für das resultierende Array zu erhalten. Auf der anderen Seite muss die List.map-Funktion eine einzelne "Cons-Zelle" für jedes Element des Eingangsarrays separat zuweisen.

Der Unterschied ist besonders sichtbar für die map Funktion, denn das kann wirklich von der Vor-Zuteilung profitieren. Für größere Datensätze sind Arrays jedoch in der Regel schneller. Wenn Sie den Code zu verwenden, Filterung (wo das Array neu zugewiesen werden, während der Bauphase benötigt) ändern, dann ist die Array-Version ~ 2x schneller:

for i in 1 .. 100 do ignore (list|>List.filter(fun n -> n%5=1)) 
for i in 1 .. 100 do ignore (array|>Array.map(fun n -> n%5=1)) 

Mit Listen andere Vorteile hat - weil sie unveränderlich sind, können Sie sicher teile Verweise auf Listen. Außerdem ist das Klonen einer Liste und das Hinzufügen eines Elements zur Vorderseite sehr effizient (Einzelzellenzuweisung), während das Ausführen einer ähnlichen Operation mit dem Array sehr langsam wäre (das gesamte Array kopieren).