schnelle Suche in Liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
template
User
Beiträge: 29
Registriert: Mittwoch 21. November 2007, 09:44

schnelle Suche in Liste

Beitragvon template » Donnerstag 29. November 2007, 08:15

Hi,

ich habe eine Liste mit vielen (ca. 40000) strings in der ich nun effizient suchen möchte. Das Problem ist, das ich nicht nur exakt gleiche finden will, sondern eine Liste all derer, die mit dem suchstring anfangen. Nun bin ich zu dem Ansatz Liste sortieren und dann manuelle Binäre suche gekommen, aber irgendwie habe ich gehofft, das es da in der Python Trickkiste irgendwas für mich gibt und ich es nicht selber programmieren muss;)

Vielen dank im voraus
template
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Beitragvon veers » Donnerstag 29. November 2007, 08:24

Interessanter hack: http://aspn.activestate.com/ASPN/Cookbo ... ipe/389169 :wink:

Ansonsten hat es im O'Reilly Cookbook dazu afaik was. Ich kann das heute Abend mal nachschauen. :wink:
My Website - 29a.ch
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Re: schnelle Suche in Liste

Beitragvon gerold » Donnerstag 29. November 2007, 12:48

template hat geschrieben:Nun bin ich zu dem Ansatz Liste sortieren und dann manuelle Binäre suche gekommen

Hallo template!

Ich habe da mal ein wenig getestet. Unten stehendes Programm sucht aus 1.000.000 Einträgen alle Einträge raus, die mit "Toten" beginnen. Dafür verbraucht mein Computer, während im Hintergrund ein Backup läuft, zwischen 1,1 und 1,2 Sekunden.

[code=]76711 1.20300006866
76711 1.10899996758
76711 1.20399999619[/code]

Wenn man Psyco aktiviert, dann geht es noch ein bischen schneller. :-) Die erste Zahl ist die Anzahl an gefundenen Einträgen.

[code=]77045 0.25
77045 0.233999967575
77045 0.25[/code]

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: iso-8859-15 -*-

import time
import random
#import psyco; psyco.full()


def main():
   
    items = "wir sind gekommen um zu bleiben das ist nicht von den Toten Hosen".split()
   
    my_list = []
   
    for i in xrange(1000000):
        random.shuffle(items)
        my_list.append(" ".join(items))
   
    for i in xrange(3):
        old_time = time.time()
        counted = 0
        for item in my_list:
            if item.startswith("Toten"):
                counted += 1
       
        print counted, time.time() - old_time
   
    # Sortieren
    old_time = time.time()
    my_list.sort()
    print "sortieren:", time.time() - old_time

if __name__ == "__main__":
    main()

Sortieren braucht länger als das reine Durchlaufen der Liste:
2.64 Sekunden ohne Psyco und 2.62 mit Psyco. Psyco hat also auf den Sortiervorgang keinen Einfluss. Sortieren bringt also erst dann etwas, wenn man oft auf die Liste filternd zugreifen muss und dafür einen guten Algorithmus hat.

mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
template
User
Beiträge: 29
Registriert: Mittwoch 21. November 2007, 09:44

Beitragvon template » Freitag 30. November 2007, 08:35

Danke für die Antworten.

@veers
Danke für den Tip, ganz verstanden hab ichs noch nicht, aber das muss ich mir nochmal genauer anschauen.

@gerold
Da hast du natürlich recht. Ich hätte vielleicht dazu sagen sollen, das ich mehrmals in der Liste suchen muss;) (so um die 7000 mal)

Der naive Ansatz mit Linearer Suche hat hierfür ca. 8 Minuten gebraucht. Deswegen habe ich überhaupt angefangen über die Code Stelle nach zu denken. Jetzt hab ichs auf ne binäre Suche in einer Sortierten Liste umgestellt und das ganze dauert nur noch 1 Sekunde.

Falls es jemanden interessiert, hier der Code für die Binäre suche mehrerer passender Elemente (ich musste den Code abtippen, deswegen könnten Tipfehler reingekommen sein). Ist sicher nicht der Weisheit letzter Schluss, nachdem ich auch noch nicht besonders lange mit Python arbeite aber vielleicht hilft er ja irgend jemand. Kommentare erwünscht;)

Code: Alles auswählen

# parameter list: the list must be sorted ascending
# parameter item: the item that must be matched
# parameter compareFunc: a callback function that got two list items and must return:
# < 0 -> item1 less than item2
# > 0 -> item1 greater than item2
# = 0 -> items are equal
# return value: a list that contains all matching items
def SearchItemsInList(list, item, compareFunc):
  matches = []
  min = 0
  max = len(list)
  while min < max:
    idx = min + ((max - min) / 2)
    result = compareFunc(list[idx], item)
    if result < 0:
      min = idx + 1
    elif result > 0:
      max = idx
    else:
      while idx > 1 and compareFunc(list[idx - 1], item) == 0:
        idx -= 1
      while idx < len(list) and compareFunc(list[idx], item) == 0:
        matches.append(list[idx])
        idx += 1
      break
  return matches
BlackJack

Beitragvon BlackJack » Freitag 30. November 2007, 09:40

Etwas in Richtung Cookbook, allerdings ungetestet:

Code: Alles auswählen

from bisect import bisect_left
from itertools import count


class PrefixSequence(object):
    def __init__(self, data, prefix_length):
        self.data = data
        self.prefix_length = prefix_length

    def __len__(self):
        return len(self.data)

    def __getitem__(self, index):
        return self.data[index][:prefix_length]


def iter_same_prefix(sorted_sequence, prefix):
    indices = count(bisect_left(PrefixSequence(sorted_sequence, len(prefix)),
                                prefix))
    try:
        for i in indices:
            result = sorted_sequence[i]
            if not result.startswith(prefix):
                break
            yield result
    except IndexError:
        pass


Ansonsten wäre die passende Datenstruktur ein Trie. Bleibt die Frage ob das aufbauen des Baums nicht mehr Zeit auffrist als man beim Suchen hinterher spart.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder