Was ist eine schnellere Möglichkeit, einen Wert in einer Liste von Tupeln nachzuschlagen?

8

Ich suche Land nach IP-Bereich für mehrere Millionen Zeilen. Ich bin auf der Suche nach einem schnelleren Weg zum Nachschlagen.

Ich habe 180K Tupel in dieser Form:

%Vor%

(Die Ganzzahlen sind IP-Adressen, die in einfache Zahlen umgewandelt werden.)

Das macht den Job richtig, aber dauert nur zu lange:

%Vor%

Kann mir irgendjemand in die richtige Richtung zeigen, um diese Suche schneller durchzuführen? Bei Verwendung der obigen Methode benötigen 100 Suchvorgänge 3 Sekunden. Das heißt, ich denke, 10 Millionen Zeilen werden mehrere Tage dauern.

    
exzackley 17.03.2012, 17:47
quelle

2 Antworten

8

Sie können das Modul bisect verwenden, um nach dem Sortieren des Datasets eine binäre Suche durchzuführen:

%Vor%

Die algorithmische Komplexität der Suche ist hier O(log n) anstelle von O(n) für eine vollständige Liste walk.

    
Niklas B. 17.03.2012, 18:01
quelle
1

Unter der Annahme, dass Ihre Situation einige Anforderungen erfüllt, gibt es eine Möglichkeit, die Laufzeitkomplexität im Durchschnitt auf O(1) zu reduzieren, aber die Platzkomplexität leidet.

  1. Die Daten müssen statisch sein; Alle Daten müssen vor jeder Suche verarbeitet werden.
  2. Bei einer beliebigen IP-Adresse muss es möglich sein, die signifikanten Oktette zu bestimmen.
  3. Es muss genug Platz sein, um für jeden signifikanten Wert für jedes Land einen Schlüssel hinzuzufügen.

Unten ist eine sehr naive Implementierung. Es wählt die ersten zwei Oktette der IP als signifikant aus, egal was passiert, verkettet dann die signifikanten Oktette als ganze Zahlen und fügt schrittweise einen Schlüssel für jeden Wert zwischen Minimum und Maximum hinzu. Wie Sie wahrscheinlich feststellen können, gibt es viel Raum für Verbesserungen.

%Vor%     
Matt Eckert 17.03.2012 20:59
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset localStorage Datenpersistenz