schnelle Suche in Liste

[template]

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

[veers]

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

Ansonsten hat es im O'Reilly Cookbook dazu afaik was. Ich kann das heute Abend mal nachschauen.

[gerold]

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: Alles auswählen

76711 1.20300006866
76711 1.10899996758
76711 1.20399999619

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

Code: Alles auswählen

77045 0.25
77045 0.233999967575
77045 0.25

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

[template]

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]

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.