Wie zu zählen, die in einer rekursiven Funktion? [python]

Ihre rekursive Funktion hat O(n^2) Leistung, da es kopiert den restlichen Inhalt der Zeichenfolge jedes mal, wenn es eine übereinstimmung findet. Diese ist langsamer als die iterative Lösung O(n) und so unnötig.

Können Sie leicht umschreiben, dass es schneller zu sein, und gleichzeitig den code vereinfachen und erweitern seine Funktionalität, indem eine start-index für die Suche als optionaler parameter der Funktion:

def countSubStringMatchRecursive(target, key, start_index = 0):
    index = target.find(key, start_index)
    if index >= 0:
        return countSubStringMatchRecursive(target, key, index + len(key)) + 1
    return 0

target_string = 'an apple and a banana'
key = 'an'
count = countSubStringMatchRecursive(target_string,  key)
print "Number of instances of %r in %r is %d" % (key, target_string, count)

Ausgabe:

Number of instances of 'an' in 'an apple and a banana' is 4

Update: Wenn Sie wirklich wollen, verwenden Sie die string-Modul suchen-Funktion, Sie können dies tun, einfach durch änderung einer Zeile:

index = find(target, key, start_index)

InformationsquelleAutor der Antwort Mark Byers

Nur eine Randnotiz: alle Lösungen präsentiert werden (von der original-Q alle) sind, ein problem zu lösen, die anders als die ausdrücklich sagte, man (ich vorstellen, das ist ein Fehler in der spezifischen Problemstellung, aber Wert Festsetzung, wenn so;-). Bedenken Sie:

>>> 'banana'.count('ana')
1
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana')))
2

der erste Ausdruck zählt die nicht-überlappende vorkommen von 'ana' in 'Banane'; das zweite ist, zählen alle vorkommen -- es gibt zwei Ereignisse in allen, bei Indizes 1 und 3 in "Banane", und Sie überlappen. Also da das problem Erklärung, und ich zitiere:

finden die keine. Instanzen eines
substring in die übergeordnete Zeichenfolge.

ohne jede Erwähnung von "nicht-überlappend", es scheint, dass überschneidungen vorkommen sollte gezählt werden. Natürlich, das ist leicht zu beheben, sobald bemerkt-Sie müssen nur vorher 1 jedes mal, anstelle der Förderung von len(key) was führt Sie zu überspringen, einander überschneidende vorkommen.

So, zum Beispiel:

import string

def countit(target, key, startfrom=0):
    where = string.find(target, key, startfrom)
    if where < 0: return 0
    return 1 + countit(target, key, where+1)

print countit('banana', 'ana')

Drucke 2zählen beide (sich überlappende) Ereignisse.

InformationsquelleAutor der Antwort Alex Martelli

Unter Berücksichtigung überlappender Ereignisse und die Erhaltung der ursprünglichen definition von MIT dies ist die einfacher und kompakter code, den ich bekommen kann.

code:

from string import *
def countSubStringMatchRecursive(target, key):
    index = find(target, key)
    if index > -1:
        return countSubStringMatchRecursive(target[index + 1:], key) + 1
    return 0


def test(target, key):
    instances = countSubStringMatchRecursive(target, key)
    if instances == 0:
        print "No instance of %r in %r" % (key, target)
    else:
        print "Number of instances of %r in %r: %d" % (key, target, instances)

test("atgacatgcacaagtatgcat","ggcc")
test("atgacatgcacaagtatgcat","atgc")
test("banana", "ana")

Ausgabe:

Keine Instanz von 'ggcc' in 'atgacatgcacaagtatgcat'

Anzahl der Instanzen von "atgc' in 'atgacatgcacaagtatgcat': 2

Anzahl der Instanzen von 'ana' in 'Banane': 2

InformationsquelleAutor der Antwort Ari Bj Rvnn

Wie über dieses?

def count_it(target, key):
    index = target.find(key)
    if index >= 0:
        return 1 + count_it(target[index+len(key):], key)
    else:
        return 0


print count_it("aaa bbb aaa ccc aaa", "aaa")

Ausgabe:

3

InformationsquelleAutor der Antwort Ryan Ginstrom

Anderen Weg sein könnte, um einen Dritten optionalen parameter auf der countSubStringMatchRecursive Funktion namens count, die ursprünglich zu 0. So könnte man verfolgen, zählen. Dies würde aussetzen, die count-variable, um die Außenwelt, die vielleicht nicht wünschenswert, aber da es nicht schlimmer als deine Globale variable, die ich nicht glaube, es wäre ein problem in Ihrem Fall.

Würden Sie auch haben um den code zu ändern, um die Letzte rekursive Aufruf der Aufruf, gibt der return-Anweisung an die Außenwelt. Siehe dieses Beispiel (ungetestet):

def countSubStringMatchRecursive(target, key, count = 0):
    index = find(target, key)
    targetstring = target
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        countSubStringMatchRecursive(target, key, count)
    else:
        return "No. of instances of", key, 'in', targetstring, 'is', count

Edit: ich erkannte, dass, würden Sie brauchen einen vierten parameter, um der Lage sein, um die ursprüngliche Zeichenfolge Reisen entlang der Rekursion. Dies ist wahrscheinlich eine weniger als optimale Lösung und ich würde empfehlen, mit Greg Hewgill Lösung. Es hat eine saubere Trennung zwischen den Interaktionen mit der Außenwelt und die "business-Logik", so dass der code besser wiederverwendbar!

InformationsquelleAutor der Antwort adamse