Suchalgorithmus - IP-Bereiche zu Ländern - VBA/Excel

[Jan K.]

Hallo zusammen,

bis zum 13. Januar muss ich eine VBA/Excel Anwendung fertig haben. Als Projekt habe ich mir etwas ausgesucht das ich schon seit langem machen wollte - Statistiken zu den Logfiles meiner Website erstellen. Insbesondere welcher Besucher aus welchem Land kommt.

Meine Logfiles lese ich mit Excel aus einer MySql Datenbank aus und speichere sie im Array ipd().

Die Tabelle für die IP und Landeszuordnung (GEO-IP) habe ich mir hier besorgt: http://www.maxmind.com/app/csv

Es sind ca 50.000 Datensätze auszuwerten, also hat der Array ipd() ca. 50.000 Elemente.

In der GEO-IP Tabelle gibt es 111.600 IP Bereiche mit Landeszuordnung die in den Array geoip() geladen werden.

Nun klappere ich für jeden einzelnen Logfile Datensatz (50.000) den ganzen Array ipd() (111.600 Datensätze) auf übereinstimmung ab.

Das dauert lange. Sehr lange. Rein vom beobachten des Fortschrittbalkens für das einmalige Abklappern der GEO-IP Datenätze  pi mal daumen 10 Sekunden. 50.000 mal 10 Sekunden - 5,78 Tage - für den Arsch.

Also muss ein effektiverer Suchalgorithmus her. Das Optimieren hat bei mir nur zum vorzeitigen Abbruch der inneren Schleife bei einem Fund gereicht ^^.

Das ganze nochmal bildlich dargestellt:

Aus den IP-Adressen der Logfiles bilde ich einen Rechnwert (mit der Formel oben im Bild), welcher im Array ipd liegt (ipd(i).ipwert). Dieser Rechnwert wird dann mit den Werten aus der GEO-IP Tabelle, bzw. dem Array geoip (geoip(j).low_value; geoip(j).high_value) verglichen um das Herkunftsland zu bestimmen (wenn ipd(i).ipwert zwischen geoip(j).low_value und geoip(j).high_value liegt, wurde das land bestimmt).

Hier noch der, zum besseren Verständniß auf das wesentliche zurechtgekürzte, VBA Code:

  
    For i = 0 To 50000  
        j = 0  
        Do While j <= 111600  
            If (ipd(i).ipwert >= geoip(j).low_value) And (ipd(i).ipwert <= geoip(j).high_value) Then  
                Worksheets("logfiles").Cells(i + 3, 7).Value = geoip(j).country_long  
                Exit Do  
            End If  
            Laender_bestimmen.pb2.Value = j  
            j = j + 1  
        Loop  
    Next i  

Ich hatte mir schon überlegt als Optimierungsmethode die GEO-IP Datensätze anders zu strukturieren, die am häufigsten vorkommenden IP-Bereich am Anfang des Arrays aufzuführen, bin aber noch nicht dazu gekommen.

Wie sieht ein schneller Suchalgorithmus für dieses Problem aus?

Gruß aus Berlin,
Jan

[hotti]

hi Jan,

Wie sieht ein schneller Suchalgorithmus für dieses Problem aus?

Keine Ahnung. Aber Dein Algorithmus zum Umrechnen der IP-Adresse in einen numerischen Wert sieht ein bischen lahm aus. Das gänge mit Bitoperatoren viiieeeeel schneller.

Hotti

[Encoder]

Und danach kannst du die IPs in einer sortierten Liste halten und da dann binär drauf suchen.
Oder du packst das alles in eine Datenbank und lässt die dann die Zuweisung machen. Mit einem gescheiten Index geht da sicher einiges. Also bestimmt keine 5 Tage.
Vielleicht ist auch VBA nicht die performanteste Umgebung um sowas zu machen? Könnte ich mir auch gut vorstellen.