strcmp für Python oder wie Substrings effizient sortieren (ohne Kopie), wenn ein Suffix Array Aufbau

Question

Hier ist eine sehr einfache Art und Weise eine suffix array aus einer Zeichenfolge in Python zu bauen:

def sort_offsets(a, b): 
    return cmp(content[a:], content[b:]) 

content = "foobar baz foo" 
suffix_array.sort(cmp=sort_offsets) 
print suffix_array 
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9] 

jedoch „Inhalt [a: ] "erstellt eine Kopie des Inhalts, die sehr ineffizient wird, wenn der Inhalt groß wird. Also frage ich mich, ob es eine Möglichkeit gibt, die beiden Teilstrings zu vergleichen, ohne sie kopieren zu müssen. Ich habe versucht, den eingebauten Puffer zu verwenden, aber es hat nicht funktioniert.

Answer 1

Ich weiß nicht, ob es eine schnelle Art und Weise ist Strings zu vergleichen, aber Sie können Ihren Code viel schneller (und einfacher) machen, indem key anstelle von cmp:

suffix_array.sort(key=lambda a: content[a:]) 

Diese den Teil schaffen nur einmal für jeden Wert von a.

Edit: Ein möglicher Nachteil ist, dass es O (n^2) Speicher für die Teilketten erfordern.

Answer 2

Die buffer Funktion kopiert nicht die gesamte Zeichenfolge, sondern erzeugt ein Objekt, das nur die Quellzeichenfolge verweist. Mit dem Vorschlag von interjay wäre das:

suffix_array.sort(key=lambda a: buffer(content, a)) 

Answer 3

+1 für ein sehr interessantes Problem! Ich kann keine offensichtliche Art und Weise sehe dies direkt zu tun, aber ich konnte eine signifikante Beschleunigung (für 100000 Zeichenkette eine Größenordnung) erhalten, indem die folgende Vergleichsfunktion anstelle von Ihnen mit:

def compare_offsets2(a, b): 
    return (cmp(content[a:a+10], content[b:b+10]) or 
      cmp(content[a:], content[b:])) 

Mit anderen Worten, beginnen Sie mit dem Vergleich der ersten 10 Zeichen jedes Suffixes; nur wenn das Ergebnis dieses Vergleichs 0 ist, was anzeigt, dass Sie eine Übereinstimmung für die ersten 10 Zeichen haben, fahren Sie fort, die gesamten suffices zu vergleichen. Experiment mit dem besten Preis zu finden:

Offensichtlich 10 könnte alles sein.

Diese Vergleichsfunktion ist auch ein schönes Beispiel für etwas, das nicht leicht mit einer Schlüsselfunktion ersetzt wird.

Answer 4

könnten Sie die blist extension type verwenden, die ich geschrieben habe. Ein blist funktioniert wie die eingebaute in list, sondern (unter anderem) verwendet copy-on-write, so dass eine Scheibe unter O braucht Zeit und Speicher (n log).

from blist import blist 

content = "foobar baz foo" 
content = blist(content) 
suffix_array = range(len(content)) 
suffix_array.sort(key = lambda a: content[a:]) 
print suffix_array 
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9] 

Ich konnte eine suffix_array aus einer zufällig erzeugten 100.000-Zeichenkette in weniger als 5 Sekunden erzeugen, und das schließt die Zeichenkette zu erzeugen.