Einfügen oder anhängen bei sortierten Listen?

[carknue]

Hallo,

ich habe eine Liste mit mehren tausend Einträgen. Ich muss sehr häufig vergleichen, ob ein Eintrag schon vorhanden ist oder nicht. Zum Suchen verwende ich die binäre Suche. Aber was ist nun die beste Methode, neue Einträge in diese Liste vorzunehmen?

Bisher habe ich bei einem negativen Ergebnis der binären Suche den neuen Eintrag dann einfach mit list.append(neu) angehangen und danach mit list.sort() neusortiert. Da mir die binäre Suche aber doch eigentlich schon die Stelle sagt, an der das neue Element stehen müsste, kann man es doch eigentlich direkt mit list.insert(index,neu) einfügen und ich könnte mir das sortieren sparen. Die Frage ist jetzt, was performanter ist. insert oder append und anschließendem sort?

Mir steht nur Python 2.2 (auf dem Handy) zur Verfügung.

Code: Alles auswählen

#

def binaere_suche(liste, eingabe):
  maxindex = maxlen = len(liste) - 1
  suche_erfolgreich = False
  index = 0
  while not suche_erfolgreich and index <= maxindex:
    mitte = index + ((maxindex - index)/2)
    if liste[mitte] == eingabe:
      suche_erfolgreich = True
    elif eingabe < liste[mitte]:
      maxindex = mitte - 1
    else:
      index = mitte + 1
  if suche_erfolgreich:
    return (1,mitte)
  else:
    if index > maxlen:
      mitte +=1
    return (0,mitte)

[EyDu]

Ich weiss nicht genau, ob es das Modul schon in 2.2 gab, aber schau dir mal "bisect" an.

EDIT: Muss es unbedingt eine Liste sein, vielleicht ist ein Dictionary (oder eine Menge) in deinem Fall auch möglich? Wie es aussieht, scheint bei dir ja die Reihenfolge der Elemente nicht wichtig zu sein.

[numerix]

Ich weiss nicht genau, ob es das Modul schon in 2.2 gab, aber schau dir mal "bisect" an.

Wurde mit 2.1 eingeführt:

http://docs.python.org/dev/library/bisect.html

Sofern du keine grundsätzliche Änderung deiner Datenstruktur vornehmen willst, dürfte das genau das Richtige sein.

[carknue]

Nein, bisect gibt es noch nicht in Python 2.2.2.

Also, ich lese praktisch eine Tabelle aus einem .csv File ein. Ich habe da anfangs recht viel experimentiert. Ne Datenbank wäre ja nacheliegend ist aber viel zu langsam, da immer auf den Datenträger zugegriffen wird. Hatte auch versucht eine Liste mit Dicts als Elemente oder Listen als Elemente. Das war sehr langsam und hatte einen enormen Speicherverbrauch, was auf dem Handy ja auch entscheident ist. Nun ist jede Zeile meiner csv Datei ein Element dieser Liste und es belegt nicht mehr Speicher, als die csv Datei gross ist. Das Suchkriterium (MAC Adresse steht am Anfang). Wenn ich den passenden Eintrag gefunden habe, splitte ich die Zeile dann auf und verarbeite sie weiter. Die sort() Funktion sortiert das auch wunderbar.

Die Performance Binäre Suche, append und sort() reicht auch momentan, ich befürchte nur, dass bei wachsender Liste die ständige Sortierung nach einem Neueintrag zum Flaschenhals werden könnte und ob da nicht bessser ein gezieltes insert ohne anschliesende Sortierung wäre. Bei insert müssen aber eine Menge Elemente verschoben werden. Ich weiss nicht, wie das in Python ist.

Die Sortierung brauche ich nur für die binäre Suche. Sonst ist die Reihenfolge egal.

[carknue]

Ich weiss nicht genau, ob es das Modul schon in 2.2 gab, aber schau dir mal "bisect" an.

Wurde mit 2.1 eingeführt:

Ist dann aber nicht in Python for S60 drin.

Wobei mir meine binaere_suche ja auch den richtigen Insert point liefert.

[Holzdolph]

und was spricht gegen ein einfaches

Code: Alles auswählen

liste = []

if element not in liste:
    liste.append(element)

?

[carknue]

und was spricht gegen ein einfaches

Code: Alles auswählen

liste = []

if element not in liste:
    liste.append(element)

?

Ja und wie soll die Suche funktionieren? Da nicht sortiert wird, dürfte das eine lineare Suche sein, die viel zu langsam ist.Ich suche ja nur nach den ersten 17 Stellen vom Eintrag. Wenn die MAC Adresse drin ist, muss er mir auch alle anderen Daten anzeigen, ich muss also die position wissen und auch den Eintrag updaten können.

[Holzdolph]

also ich habe gerade eine liste mit 10000 elementen erstellt wobei jedes element aus 12-15 zufälligen kleinbuchstaben besteht.

Danach habe ich 8 elemente aus der liste ausgewählt und geprüft ob sie in der liste enthalten ist, die zahl neben den buchstabenkolonen gibt die zeit an, die differenz zweier zeiten ist also die zeit die für eine abfrage + ausgabe benötigt wird, das spielt sich also im milisekundenbereich ab:

zwwauevptabekcu, 11.284510
dkfvlnlsyqdyq, 11.293067
stnogylgwfurj, 11.307193
yuczhozbjmodgie, 11.314435
qugzxkwjsnle, 11.321398
xrlltpegedvmlw, 11.330232
ursovpbhfowk, 11.341175
cozmauplwrjmw, 11.347923

es sollte doch möglich sein deine liste an diese einfache suche anzupassen, mir ist der aufbau nicht ganz klar da deine beschreibung etwas wirr ist:

Das Suchkriterium (MAC Adresse steht am Anfang).

ja was ist es denn ? irgendwie ist da der Satz aus

[carknue]

So sieht meine csv Datei aus. Der Header wird natürlich nicht mit in die Liste übernommen. Jede komplette Zeile ist also ein Element der Liste. Das Einlesen geht über readlines() ja blitzschnell.

BSSID;LAT;LON;SSID;Crypt;Beacon Interval;Connection Mode;Channel;RXL;Date;Time
00:01:36:08:22:32;52.284208;7.470292;atiwlan;Open;100;Infra;6;-74;2007/12/25;13:56:25
00:01:36:0B:01:C3;52.283867;7.462213;Geri;Wep;100;Infra;6;-75;2007/12/25;13:57:38

Das Suchkritierum ist nur die MAC Adresse, also nur die ersten 17 Stellen. Es reicht nicht, nur zu wissen, ob die MAC drin ist. Wenn sie drin ist, muss ich auch die gesamte zeile auslesen und updaten können.

Und nochmal , eine lineare Suche ist zu langsam. Ab 7000 Einträgen bricht das zusammen. Das Programm muss die Suche ca. 26 mal innerhalb von 10 Sekunden ausführen können dazu kommen noch Berechnungen und Updates der Einträge. Das geht nur mit einer binären Suche.

Also, da ich keinen Benchmark auf dem Handy ausführen kann und ich nicht weiß, wie die Funktionen sort(), append und insert in Python aufgebaut sind, würde mich einfach nur interessieren, was bei grossen Listen schneller ist.

1. Suche, dann anhängen mit append und dann sort()
2. Suche, dann insert an der richtigen Stelle

[EyDu]

Na dann ist, ein Dictionary doch gerade zu die perfekte Wahl. Als Schlüssel verwendest du die MAC und der Wert wird einfach ein Tupel aus den verbleibenden Daten:

Code: Alles auswählen

{
00:01:36:08:22:32: (52.284208, 7.470292, atiwlan, Open, 100, Infra, 6, -74;2007/12/25, 13:56:25) ,
00:01:36:0B:01:C3: (52.283867,  7.462213, Geri, Wep, 100, Infra, 6, -75, 2007/12/25, 13:57:38)
}

Hab' jetzt mal die Anführungszeichen weggelassen.

[carknue]

Na dann ist, ein Dictionary doch gerade zu die perfekte Wahl.

Und wie soll ich das aus der csv einlesen? Als Liste geht es am einfachsten und mit Abstand am schnellsten.

Code: Alles auswählen

wlan_list = file.readlines()

Und Dicts brauchen zuviel Speicher.

Aber was würde das Dict denn vereinfachen? An die einzelnen Felder komme ich ja bei mir über die splitt function, wenn ich den Eintrag gefunden habe, vorher und nach her brauche ich die Trennung nicht, die wohl sehr viel Speicher braucht. Damals hatte ne 2MB Datei ca. 20 MB im Handyspeicherbelegt, wo ich mit dicts probiert hatte und das einlesen hatte mehrere Minuten gedauert.

[EyDu]

Code: Alles auswählen

import csv

fp = open("test.csv")
wlan_list = {}
for line in csv.reader(fp, delimiter=";"):
    wlan_list[line[0]] = tuple(line[1:])
fp.close()

print wlan_list

Ich sehe nicht, wo ein Dictionary hier viel mehr Speicher verbrauchen sollte als in einer Liste.

[carknue]

Abgesehen davon, das mir das Modul csv leider auch nicht zur Verfügung steht, scheidet das zeilenweise Einlesen schon aus Performancegründen aus. Dann muss ich 5 Minuten beim Programmstart warten. Nur die schnelle readlines() Funktion schafft das in wenigen Sekunden. Man beachte das s in readlines() . Das habe ich alles schon probiert.

Klar ist ein Dict schöner und vielleicht aus passender, aber auf dem Handy zählt nur Performance, sonst gibt es unerträgliche Wartezeiten.

Bei dem Dict komme ich aber auch um eine binäre Suche und der dafür nötigen Sortierung nicht herum. Ich hatte eigentlich auf eine Einschätzung und vielleicht Begründung gehofft, was aus Geschwindigkeitsgründen vorteilhafter ist bei neuen Elementen:

1. Binäre Suche, dann anhängen mit append und dann sort()
2. Binäre Suche, dann insert an der richtigen Stelle

[EyDu]

Das Parsen der csv-Datei wäre auch mit "readline" gegangen, aber da dies offensichtlich viel zu langsam ist, fällt die Variante wohl auch weg.

Welche der beiden Varianten nun in deinem Fall schneller ist, musst du wohl wieder auf der Zielplatform testen. Ich würde jedoch zunächst Variante 1 verwenden, da sie leicht zu implementieren ist. Und wenn die Geschwindigkeit nicht ausreichen sollte, probierst du es eben mit der zweiten.