Tag-Archiv für » array «

23 | 08 | 2017

PowerShell: Wie schnell sind Arrays?

Geschrieben von um 11:13 Uhr

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

$list | select -Unique

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:

$passes = 100000 # Anzahl der Durchläufe
$maxval = 10000 # Länge des Zufallszahlen-Bereiches
$a = <Initialisierung des jeweiligen Listentyps>
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    <$r wird an $a angefügt, evtl. mit Prüfung>
}
$s1 = $timer.Elapsed.TotalMilliseconds # das ist die Zeit der Listen-Erstellung
$a = $a | select -Unique
$s2 = $timer.Elapsed.TotalMilliseconds # das ist die Gesamtzeit

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:

$passes = 100000
$maxval = 10000
$a = @()
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    $a += $r
}
$s1 = $timer.Elapsed.TotalMilliseconds
$a = $a | select -Unique
$s2 = $timer.Elapsed.TotalMilliseconds
"Zeit zum erstellen: $s1, Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = New-Object System.Collections.ArrayList
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    $a.Add($r) > $null
}
$s1 = $timer.Elapsed.TotalMilliseconds 
$a = $a | select -Unique 
$s2 = $timer.Elapsed.TotalMilliseconds 
"Zeit zum erstellen: $s1, Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = New-Object System.Collections.ArrayList
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    if ($a -notcontains $r) { $a.Add($r) > $null }
}
$s2 = $timer.Elapsed.TotalMilliseconds 
"Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = New-Object System.Collections.ArrayList
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    if (!($a.Contains($r))) { $a.Add($r) > $null }
}
$s2 = $timer.Elapsed.TotalMilliseconds 
"Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = @{}
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    try {$a.Add($r,"") > $null} catch {}
}
$s2 = $timer.Elapsed.TotalMilliseconds 
"Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = @{}
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    if (!($a.ContainsKey($r))) { $a.Add($r,"") > $null }
}
$s2 = $timer.Elapsed.TotalMilliseconds 
"Gesamtzeit: $s2"

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:

$passes = 100000
$maxval = 10000
$a = New-Object System.Collections.Generic.HashSet[object]
$timer = [System.Diagnostics.Stopwatch]::StartNew()
(1..$passes) | foreach {
    $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString().PadLeft(15,'0')
    $a.Add($r) > $null
}
$s2 = $timer.Elapsed.TotalMilliseconds 
"Gesamtzeit: $s2"

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!

Tags » , , , , , , «

+

07 | 12 | 2016

PowerShell Quirks: String-Array als verbindliches Argument

Geschrieben von um 18:04 Uhr

Nicht wirklich schwierig, aber gut zu wissen: Nehmen wir mal eine Funktion, die irgendwas mit einem Array aus Strings machen soll. Und weil wir sie nicht umsonst aufrufen wollen, deklarieren wir diesen Parameter als verbindlich:

function Do-Something {
    [CmdletBinding()]
    Param(
        [Parameter (Mandatory=$true)][string[]]$in_content
    )
    foreach ($x in $in_content) {
        $col = Get-Random @('Red','Yellow','Green')
        Write-Host $x -ForegroundColor $col
    }
}

Wenn wir also Do-Something ‚blahblahblah‘ oder Do-Something @(‚blah‘,’suelz‘,’foo‘,’bar‘) aufrufen, bekommen wir das erwartete Ergebnis. Die Funktion sollte aber in meinem Fall Inhalte von Textdateien verarbeiten:

Do-Something (Get-Content 'c:\temp\textfile01.txt')

Und siehe da, prompt bekam man den Fehler „Do-Something : Cannot bind argument to parameter ‚in_content‘ because it is an empty string.„. Offensichtlich enthält die Textdatei eine leere Zeile, und diese wird durch den Mandatory-Dekorator geblockt.

Um dies zu umgehen, kann man den Parameter wie folgt definieren:

[Parameter (Mandatory=$true)][AllowEmptyString()][string[]]$in_content

Ganz ohne Argument kann man die Funktion danach immer noch nicht aufrufen. Happy scripting!

Tags » , , , , «

+