none
Array und -unique seeeehr langsam

    Frage

  • Hallo,


    ich muss diverse Logs á ca. 500 MB durchsuchen. Ich suche eine bestimmte Zeile mit IP und lasse mir die IP später aus dem String extrahieren.

    Dafür habe ich eine Abfrage mit Regex erstellt, funktioniert wunderbar.

    RegEx: $var_pattern = "Incoming SMTP call from [0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3} at [0-9:]+\."

    Befehl: $var_PatternLines = Select-String -path $var_Path"*.LOG" -pattern $var_pattern

    Es sind ca. 2 Mio Treffer. Darüber lasse ich ein Foreach laufen und mit einer Funktion die IP in ein Array schreiben.

    foreach ($var_treffer in $var_PatternLines)
    	{
    	$var_tmp_ip = ExtractValidIPAddress ($var_treffer)
    	$var_iparray += $var_tmp_ip
    	}

    Funktioniert auch wunderbar.

    Gefolgt von zwei Zeilen und ich glaube, dafür braucht es sehr lange. Ich möchte jede IP ja nur 1x haben und lasse es so "filtern" und in eine Datei schreiben.

    $var_iparray = $var_iparray | Select-Object -uniq
    $var_iparray | Out-File -filepath $var_OutPath

    Das Script läuft jetzt schon 2 Tage...

    Meine Frage, wie kann ich das beschleunigen....? Kann ich Regex womöglich so anpassen, das man auf das unique verzichten kann?

    Ich bin nicht so der Profi und über Tipps dankbar.


    Gruss,

    Matthias



    Dienstag, 22. August 2017 08:10

Antworten

  • Moin,

    habe es noch mal schnell getestet. Hier was zum Spielen:

    $passes = 100000
    $maxval = 10000
    
    $a = New-Object System.Collections.ArrayList
    
    $s1 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            $a.Add($r)
        }
    }).TotalSeconds
    $s2 = (Measure-Command {
        $a = $a | select -Unique
    }).TotalSeconds
    $a.Count
    $a = New-Object System.Collections.ArrayList
    $s3 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            if ($a -notcontains $r) { $a.Add($r) }
        }
    }).TotalSeconds
    $a.Count
    
    $h = @{}
    $s4 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            try {$h.Add($r,"")} catch {}
        }
    }).TotalSeconds
    
    "$s1 | to add $passes random numbers to array"
    "$s2 | to uniquify that array"
    "$($s1 + $s2) | total method 1"
    "$($s3) | total method 2"
    "$s4 | total hashtable method"
    

    (nun auch inklusive des Hashtable-Einwurfs von bfuerchau unten)

    Hier kann man schön sehen, wie sich das Verhältnis verschiebt, je nachdem, a. wieviele unterschiedliche Werte es insgesamt gibt, und b. wie hoch die Wiederholungsrate der einzelnen Werte (also das Verhältnis von Gesamtanzahl zur Anzahl unterschiedliche) ausfällt.

    Aber select -Unique IST langsam, daran gibt's nichts zu drehen.


    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com



    Dienstag, 22. August 2017 09:08
  • Eigentlich ist hier alles beschrieben, mit Beispielen:

    https://technet.microsoft.com/en-us/library/ee692803.aspx

    Dienstag, 22. August 2017 10:48
  •   

    Ein Hashset könnte die schnellste Variante sein:

    $Data = New-Object System.Collections.Generic.HashSet[object]
    $maxval = 50000
    for ($i = 1; $i -le $maxval; $i++) {
    	[Void]$Data.add((Get-Random -Minimum 1 -Maximum $maxval))
    }

     

      

    Geschwindigkeit wie eine Arraylist, Doubletten werden automatisch gefiltert, also keine Überprüfung notwendig.

    @Kiezkicker
    Für dich sähe das so aus:

    $var_iparray  = New-Object System.Collections.Generic.HashSet[object]
    
    Foreach ($var_treffer in $var_PatternLines)	{
    	$var_tmp_ip = ExtractValidIPAddress ($var_treffer)
    	[Void]$var_iparray.add($var_tmp_ip)
    }
    
    $var_iparray | Out-File -filepath $var_OutPath
     
     Kleine Anmerkung noch: Unterstriche in den Variablennamen machen den Code unnötig schwer zu lesen. D.h. es rutschen schnell vertipper und andere Fehler durch. Würde ich nicht machen.





    Blog: http://bytecookie.wordpress.com

    Kostenloser Powershell Code Manager v5: Link
    (u.a. Codesnippets verwalten + komplexe Scripte graphisch darstellen)

    Hilf mit und markiere hilfreiche Beiträge mit dem "Abstimmen"-Button (links) und Beiträge die eine Frage von dir beantwortet haben, als "Antwort" (unten).
    Warum das Ganze? Hier gibts die Antwort.


    Dienstag, 22. August 2017 13:05
    Moderator

Alle Antworten

  • Hallo,

    schon beim befüllen des Arrays liegt ein Problem vor. Kannst ja mal folgenden Code ansehen, dann siehst du den Unterschied schon.

    https://msdn.microsoft.com/de-de/library/system.collections.arraylist(v=vs.110).aspx

    # Langsam Array
    Measure-Command {
    	$Array = @()
    	$i = 0
    	do {
    		$Array += "$i" 
    		$i++
    	} until ($i -gt 100000)
    }
    
    # Schnell ArrayList
    Measure-Command {
    	$ArrayList = New-Object System.Collections.ArrayList
    	$i = 0
    	do {
    		$Null = $ArrayList.Add("$i")
    		$i++
    	} until ($i -gt 100000)
    }

    Beste Gruesse
    brima


    • Bearbeitet brima Dienstag, 22. August 2017 08:44
    Dienstag, 22. August 2017 08:33
  • Moin,

    ich bin mir nicht sicher, welchen Impact das haben wird, aber Du könntest ja vor dem Adden prüfen, ob der Wert nicht bereits enthalten ist:

    foreach ($var_treffer in $var_PatternLines){
        $var_tmp_ip = ExtractValidIPAddress ($var_treffer)
        if ($var_iparray -notcontains $var_tmp_ip) {
            $var_iparray += $var_tmp_ip
        }
    }

    Dadurch, dass das Array nie unnötig wächst, kann ich mir vorstellen, dass es etwas performanter sein dürfte. Und, je nach der zu erwartenden Menge an eindeutigen Ergebnissen, kombiniert mit dem ArrayList-Typ und der Add-Methode.


    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com

    Dienstag, 22. August 2017 08:43
  • Moin,

    habe es noch mal schnell getestet. Hier was zum Spielen:

    $passes = 100000
    $maxval = 10000
    
    $a = New-Object System.Collections.ArrayList
    
    $s1 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            $a.Add($r)
        }
    }).TotalSeconds
    $s2 = (Measure-Command {
        $a = $a | select -Unique
    }).TotalSeconds
    $a.Count
    $a = New-Object System.Collections.ArrayList
    $s3 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            if ($a -notcontains $r) { $a.Add($r) }
        }
    }).TotalSeconds
    $a.Count
    
    $h = @{}
    $s4 = (Measure-Command {
        (1..$passes) | foreach {
            $r = (Get-Random -Minimum 1 -Maximum $maxval).ToString()
            try {$h.Add($r,"")} catch {}
        }
    }).TotalSeconds
    
    "$s1 | to add $passes random numbers to array"
    "$s2 | to uniquify that array"
    "$($s1 + $s2) | total method 1"
    "$($s3) | total method 2"
    "$s4 | total hashtable method"
    

    (nun auch inklusive des Hashtable-Einwurfs von bfuerchau unten)

    Hier kann man schön sehen, wie sich das Verhältnis verschiebt, je nachdem, a. wieviele unterschiedliche Werte es insgesamt gibt, und b. wie hoch die Wiederholungsrate der einzelnen Werte (also das Verhältnis von Gesamtanzahl zur Anzahl unterschiedliche) ausfällt.

    Aber select -Unique IST langsam, daran gibt's nichts zu drehen.


    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com



    Dienstag, 22. August 2017 09:08
  • Da du ja von Anfang an nur eindeutige Werte haben willst, bietet sich eher der Einsatz einer Hashtable statt eines Arrays an.
    Dienstag, 22. August 2017 09:14
  • Da du ja von Anfang an nur eindeutige Werte haben willst, bietet sich eher der Einsatz einer Hashtable statt eines Arrays an.
    Ja, ist nach der obigen Testmethode in der Tat deutlich schneller. Man muss halt Ausnahmen abfangen (und ignorieren), aber dagegen ist ja grundsätzlich erst mal nichts zu sagen...

    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com

    Dienstag, 22. August 2017 09:24
  • Eigentlich ist hier alles beschrieben, mit Beispielen:

    https://technet.microsoft.com/en-us/library/ee692803.aspx

    Dienstag, 22. August 2017 10:48
  • Vielen Dank für eure Antworten!

    Ich muss das testen und melde mich wieder.

    Gruss,

    Matthias

    Dienstag, 22. August 2017 11:47
  • Eigentlich ist hier alles beschrieben, mit Beispielen:

    https://technet.microsoft.com/en-us/library/ee692803.aspx

    Naja,

    es ist dort nicht beschrieben, warum das schneller sein sollte als ArrayList. Es ist auch nicht beschrieben, wie groß der Impact auf den Speicherverbrauch durch die "mißbräuchliche" Nutzung der Hashtable ist. Wir nutzen ja quasi nur den Key, für die Values wird aber auch noch Speicher allokiert. Vermutlich wird der Impact um so geringer, je länger die tatsächlichen Keys sind, aber er ist auf jeden Fall meßbar.

    Noch eine Erkenntnis, die aus dem verlinkten TechNet-Artikel nicht direkt hervorgeht: NOCH um Faktor 2x-4x schneller als Hashtable mit Ausnahmen-(nicht)-Behandlung ist Hashtable mit expliziter Prüfung:

    if (!($h.ContainsKey($r))) { $h.Add($r,"") > $null }


    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com

    Dienstag, 22. August 2017 12:10
  •   

    Ein Hashset könnte die schnellste Variante sein:

    $Data = New-Object System.Collections.Generic.HashSet[object]
    $maxval = 50000
    for ($i = 1; $i -le $maxval; $i++) {
    	[Void]$Data.add((Get-Random -Minimum 1 -Maximum $maxval))
    }

     

      

    Geschwindigkeit wie eine Arraylist, Doubletten werden automatisch gefiltert, also keine Überprüfung notwendig.

    @Kiezkicker
    Für dich sähe das so aus:

    $var_iparray  = New-Object System.Collections.Generic.HashSet[object]
    
    Foreach ($var_treffer in $var_PatternLines)	{
    	$var_tmp_ip = ExtractValidIPAddress ($var_treffer)
    	[Void]$var_iparray.add($var_tmp_ip)
    }
    
    $var_iparray | Out-File -filepath $var_OutPath
     
     Kleine Anmerkung noch: Unterstriche in den Variablennamen machen den Code unnötig schwer zu lesen. D.h. es rutschen schnell vertipper und andere Fehler durch. Würde ich nicht machen.





    Blog: http://bytecookie.wordpress.com

    Kostenloser Powershell Code Manager v5: Link
    (u.a. Codesnippets verwalten + komplexe Scripte graphisch darstellen)

    Hilf mit und markiere hilfreiche Beiträge mit dem "Abstimmen"-Button (links) und Beiträge die eine Frage von dir beantwortet haben, als "Antwort" (unten).
    Warum das Ganze? Hier gibts die Antwort.


    Dienstag, 22. August 2017 13:05
    Moderator
  •   

    Ein Hashset könnte die schnellste Variante sein:

    Jawohl, wenn auch nicht mehr wesentlich schneller als Hashtable mit Check.

    Meine Zahlen sehen so aus:

    100.000 Versuche

    Zahlen von 1 bis 10.000

    EDIT: Und der absolute Hammer, bestätigt das, was der TO geschrieben hat: Alle zum PS Array hinzufügen und dann filtern: 491 Sekunden, davon 86s fürs Filtern.

    Alle zum ArrayList hinzufügen, dann filtern: 93s, davon 86s fürs Filtern

    Zum ArrayList hinzufügen,  vorher mit -notcontains prüfen: 59s

    Zum ArrayList hinzufügen,  vorher mit .Contains() prüfen: 11s

    Zur Hashtable mit try-catch hinzufügen: 21s

    Zur Hashtable hinzufügen, vorher mit .containsKey prüfen: 7,5s

    Zum Hashset hinzufügen: 6,9s

    Sind also schon bei Faktor 13x EDIT: 70x gegenüber dem ursprünglichen Vorschlag :-)


    Evgenij Smirnov

    I work @ msg services ag, Berlin -> http://www.msg-services.de
    I blog (in German) @ http://it-pro-berlin.de
    my stuff in PSGallery --> https://www.powershellgallery.com/profiles/it-pro-berlin.de/
    Exchange User Group, Berlin -> http://exusg.de
    Windows Server User Group, Berlin -> http://www.winsvr-berlin.de
    Mark Minasi Technical Forum, reloaded -> http://newforum.minasi.com


    • Bearbeitet Evgenij Smirnov Dienstag, 22. August 2017 13:35 EDIT: PS Array hinzugefügt
    Dienstag, 22. August 2017 13:18
  • Und es werden keine Fehler erzeugt, beim hinzufügen von bereits vorhandenen Werten.
    Es wird aber True oder False zurückgeliefert, d.h. man kann auch z.b. die Anzahl der doubletten einfach zählen.


    Blog: http://bytecookie.wordpress.com

    Kostenloser Powershell Code Manager v5: Link
    (u.a. Codesnippets verwalten + komplexe Scripte graphisch darstellen)

    Hilf mit und markiere hilfreiche Beiträge mit dem "Abstimmen"-Button (links) und Beiträge die eine Frage von dir beantwortet haben, als "Antwort" (unten).
    Warum das Ganze? Hier gibts die Antwort.

    Dienstag, 22. August 2017 13:30
    Moderator
  • Moin,

    ich hatte leider bislang keine Zeit eure Vorschläge zu prüfen- bis eben.

    Weil es einfach für mich war, vielen Dank an Denniver für den vorgekauten Code, habe ich die Zeilen mit dem Hashset getestet.

    $var_iparray  = New-Object System.Collections.Generic.HashSet[object]
    
    Foreach ($var_treffer in $var_PatternLines)	{
    	$var_tmp_ip = ExtractValidIPAddress ($var_treffer)
    	[Void]$var_iparray.add($var_tmp_ip)
    }
    
    $var_iparray | Out-File -filepath $var_OutPath

    Gleiche Bedingungen, wie mit meinem Code:

    Gleicher Server mit 128 GB RAM, 16 Log-Dateien á ca. 500 MB.

    Mein Code lief 6 Tage.

    Dein Code läuft 10 Minuten (!!!).

    Ich bin begeistert, vielen Dank. Jetzt versuche ich es nur noch zu verstehen...

    Die Unterstriche in den Variablen habe ich extra genutzt, ich dachte so kann ich das besser lesen :)

    Danke, bin immer für Tipps dankbar!

    Gruss,

    Matthias

    Montag, 28. August 2017 12:46
  • Zum Verständnis:
    Mit der doppelten Schleife machst du statistisch im Zweifel ca. N * M/2 Zugriffe bzw. Vergleiche.
    Im ungünstigsten Fall, kein Satz gefunden, machst du N * M vergebliche Suchen.
    Nun ist nicht klar, wieviele 1000de Zeilen beide Dateien haben.

    Nun die Hashtable:
    Die 1. Schleife lädt die Informationen per Hashwert in die Tabelle.
    Der Hashwert ist je nach Implementation ein 32/64-Bitwert.
    Die Tabelle wird mit Primzahl-Sätzen initialisiert und der "integer(Hashwert / Primzahl)" ergibt die Speicherposition.
    Bei Kollisionen (identische Position) wird an dieser Position eine Liste von elementen angelegt.
    Wenn die Tabelle einen entsprechenden Füllungsgrad hat, wird sie automatisch vergrößert und die enthaltenen Suchbegriffe neu verteilt.
    Eine günstige Verteilung ergibt keine Kollision, so dass genau 1 Zugriff genügt, per Hashwert den zum Schlüssel gehörenden Wert zu finden. Selbst bei einer etwas höheren Kollisionsrate von z.B. 5 ergibt dies in der Liste dann max. 5 Vergleiche je Suche.

    Es gibt halt verschiedene Implementierungen zur Berechnung eines Hashwertes, Erweiterung der Tabelle und Vermeidung von Kollisionen.
    Und sie sind gerade sehr schön, um beliebige Informationen in einer Tabelle (Array) abzulegen und schnellstens wiederzufinden.

    Montag, 28. August 2017 14:07
  • Es ist auch in meiner generellen Erfahrung leider so, dass man die meisten Cmdlets und PowerShell-typischen Elemente nicht verwenden sollte, wenn es wirklich auf Performance ankommt. Wenn man also große Datenmengen oder sehr viele Durchläufe hat, sollte man immer auf .NET-Klassen zurückgreifen. Cmdlets und das @()-Array sind nur sinnvoll, wenn die Aufgabe so klein ist, dass es auf Performance nicht ankommt - dafür sind sie leichter zu lesen und zu programmieren.
    Dienstag, 29. August 2017 06:02