PowerShell: Wie schnell sind Arrays?

Die Herausforderung

Neulich im TechNet Forum: Jemand hat eine Liste, die sehr viele Einträge enthält, die sich oft wiederholen. In diesem Fall ging es um IP-Adressen. Wenn er versucht, die eindeutigen Werte mit

zu generieren, dauert das sehr lange. Da er das normale PowerShell-Array verwendet hat, war es wenig überraschend. Im Forum-Thread kam natürlich sofort der (berechtigte) Hinweis auf den ArrayList-Typ, aber auch ein paar ausgefallenere Sachen. Da wollte ich natürlich genau wissen, wie sich das tatsächlich auswirkt.

Die Testmethodik

Da ich auf die Schnelle keine Quelle mit vielen IP-Adressen zur Hand hatte, habe ich beschlossen, einfach mit Strings zu arbeiten. Um die ursprüngliche Herausforderung zu simulieren, generieren wir einige (viele) Male eine Zufallszahl. Wenn der Bereich der Zufallszahlen deutlich kürzer ist als die Anzahl der Versuche, werden garantiert viele Dubletten auftreten.

Für die Generierung der Listen verwenden wir die folgende Logik:

Bei den Methoden, wo von vornherein nur eindeutige Elemente auf die Liste kommen, entfällt natürlich der Teil mit Select und die „Zwischenzeit“. Diese Methodik führt zu den folgenden Skripten:

Methode 0: PowerShell-Array mit Select

Das ist die primitivste Methode. Das komplette Skript dieht wie folgt aus:

Methode 1: ArrayList mit Select

Wie wir alle wissen, kann man die Bestückung von Arrays deutlich beschleunigen, wenn man statt des PowerShell-Array den .Net-Typ System.Collections.ArrayList verwendet. Nicht nur erweitert sich solch ein Array dynamisch, sondern man kann Elemente auch nachträglich löschen. Und schneller ist es obendrein. Das folgende Skript wird uns zeigen, wie sehr:

Methode 2: ArrayList mit -notcontains

Ich nehme ein Ergebnis schon mal vorweg: der Teil mit Select dauert eine Weile. Das war auch das, was den ursprünglichen Thread ausgelöst hat. Es liegt daher natürlich nahe, vor dem Hinzufügen von Elementen zu checken, ob sie nicht schon drin sind, statt hinterher zu filtern. PowerShell hatt dafür den Operator -notcontains im Angebot:

Methode 3: ArrayList mit .Contains()

Wir haben schon oft gehört, dass .Net-Methoden von Klassen schneller sein können als PowerShell-Äquivalente. Und da wir mit ArrayList arbeiten, können wir zur Prüfung auch auf die .Contains()-Methode zurückgreifen:

Methode 4: Hashtable

Schon bald im Thread kam der Einwurf, man könnte doch eine Hashtable verwenden, wenn die Werte eindeutig sein sollen. Das wäre ein Stück weit „mißbräuchliche Nutzung“, da wir nur den Key verwenden würden, aber nicht den Value. Aber sei’s drum, wenn es ans Ziel führt, ist jedes Mittel recht. Beim Versuch, einen bereits vorhandenen Key-Wert einzufügen, generiert die Hashtable eine Ausnahme. Diese fangen wir ab und… machen nichts weiter:

Methode 5: Hashtable mit Prüfung

Ausnahmen sind natürlich häßlich und in ordentlicher Programmierung zu vermeiden. Zum Glück kann man in einer Hashtable bestimmen, ob ein Key bereits vorhanden ist, nämlich mit der Methode .ContainsKey(). Ob es schneller ist als Ausnahme, wird der Test zeigen:

Methode 6: Hashset

Zum Schluss hatte Denniver Reining noch das Hashset ins Gespräch gebracht. Das ist eine eindimensionale Liste, deren Mitglieder stets eindeutig sind, ohne das Ausnahmen generiert werden – vorhandene Werte werden einfach nicht hinzugefügt:

Die Ergebnisse

Die obigen Skripte könnt ihr euch hier herunterladen und selbst Messungen vornehmen. Bei $passes = 100000 und $maxval = 10000 (also im Schnitt 10 Dubletten pro Eintrag) erhalten wir folgende Ergebnisse:

MethodeZeit gesamt (sek.)davon sortieren (sek.)
Baseline (Schleife und Generierung der Zufallszahlen)6,5-
PowerShell Array und select -unique51590
ArrayList und select -unique9590
ArrayList mit -notcontains58-
ArrayList mit .Contains()11-
Hashtable mit Exception21-
Hashtable mit .ContainsKey()7,5-
Hashset6,8-

Erhöhen wir die Werte auf $passes = 400000 und $maxval = 20000 (damit verdoppelt sich sowohl die Länge der eindeutigen Liste als auch die durchschnittliche Anzahl der Dubletten), ändern sich die Ergebnisse wie folgt:

MethodeZeit gesamt (sek.)davon sortieren (sek.)
Baseline (Schleife und Generierung der Zufallszahlen)27,8-
PowerShell Array und select -unique6280768
ArrayList und select -unique762734
ArrayList mit -notcontains520-
ArrayList mit .Contains()57-
Hashtable mit Exception86-
Hashtable mit .ContainsKey()32-
Hashset28,6-

Man sieht also sehr deutlich, dass die Bestückung eines Hashset auch bei einer größeren Menge an Ergebnissen kaum Zeit in Anspruch nimmt!

Das Fazit

Die „Ausbeute“ aus diesen Zahlen ist wie folgt:

  1. Das Erweitern eines PowerShell-Array mit $array += $item ist extrem langsam
  2. Die .Contains()-Methode ist viel schneller als der Operator -contains
  3. Beim Hinzufügen zu einer Hashtable ist es deutlisch schneller, vorher die Existenz des Key abzuprüfen als eine Ausnahme zu generieren.
  4. Will man von vorhnherein eindeutige Werte auf der Liste haben, ist ein Hashset optimal. Der Geschwindigkeitsgewinn gegenüber Hashtable mit Prüfung ist zwar nicht mehr weltbewegend, aber er ist da, man benutzt die Typen richtig und mißbraucht den Key nicht als Datenspeicher…

Also: Wenn lange Listen generiert und verarbeitet werden müssen, lohnt es sich auf jeden Fall, das bequeme Konstrukt des PowerShell-Arrays zu verlassen und sich fortgeschritteneren Typen von Sammlungen zuzuwenden.

Happy listing!

1 Kommentar

  1. Danke für diesen Vergleich, bin gerade zufällig darauf gestossen. Eine interessante Hintergrundinfo, die Laufzeitunterschiede sind schon bemerkenswert.

1 Trackback / Pingback

  1. PowerShell: Zeig mir, wie du mit Arrays umgehst, und ich sage dir, aus welcher Sprache du kommst – Evgenij Smirnov – IT Pro aus Berlin

Antworten

Deine E-Mail-Adresse wird nicht veröffentlicht.


*


Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.