Effiziente Teilsuche eines Trie in Python

Question

Dies ist ein Hackerank-Übung, und obwohl das Problem selbst gelöst ist, ist meine Lösung offenbar nicht effizient genug, so dass ich bei den meisten Testfällen Timeouts bekomme. Hier ist das Problem:

Wir werden unsere eigenen Kontakte Anwendung machen! Die Anwendung muss zwei Arten von Operationen durchführen:

1. add name, wo name ist eine Zeichenfolge, einen Kontaktnamen angibt. Dies muss als neuer Kontakt in der Anwendung gespeichert werden.
2. find partial, wobei partial eine Zeichenfolge ist, die einen Teilnamen angibt, nach dem die Anwendung gesucht werden soll. Er muss die Anzahl der Kontakte zählen, die mit partial beginnen, und die Anzahl in einer neuen Zeile ausgeben. Gegeben n sequentielle hinzufügen und finden Operationen, führen Sie jede Operation in Reihenfolge.

ich Tries bin mit ihm, funktioniert hier ist der Code:

import re 

def add_contact(dictionary, contact): 
    _end = '_end_' 
    current_dict = dictionary 
    for letter in contact: 
     current_dict = current_dict.setdefault(letter, {}) 
    current_dict[_end] = _end 
    return(dictionary) 

def find_contact(dictionary, contact): 
    p = re.compile('_end_') 
    current_dict = dictionary 
    for letter in contact: 
     if letter in current_dict: 
      current_dict = current_dict[letter] 
     else: 
      return(0) 
    count = int(len(p.findall(str(current_dict)))/2) 
    re.purge() 
    return(count) 

n = int(input().strip()) 
contacts = {} 
for a0 in range(n): 
    op, contact = input().strip().split(' ') 
    if op == "add": 
     contacts = add_contact(contacts, contact) 
    if op == "find": 
     print(find_contact(contacts, contact)) 

Da das Problem der Rückkehr erfordert nicht, ob partial eine Übereinstimmung vorhanden ist oder nicht, sondern um alle Einträge zu zählen Wenn es dazu passt, kann ich keinen anderen Weg finden, aber die verschachtelten Wörterbücher in einen String umwandeln und dann alle _end_ s zählen, die ich verwende, um gespeicherte Strings zu bezeichnen. Dies scheint der Übeltäter zu sein, aber ich kann keinen besseren Weg finden, die Suche durchzuführen. Wie kann ich das schneller machen? Danke im Voraus.

UPD: Ich habe einen Ergebniszähler hinzugefügt, der den Baum tatsächlich analysiert, aber der Code ist immer noch zu langsam für den Online-Checker. Irgendwelche Gedanken?

def find_contact(dictionary, contact): 
    current_dict = dictionary 
    count = 0 
    for letter in contact: 
     if letter in current_dict: 
      current_dict = current_dict[letter] 
     else: 
      return(0) 
    else: 
     return(words_counter(count, current_dict)) 

def words_counter(count, node): 
    live_count = count 
    live_node = node 
    for value in live_node.values(): 
     if value == '_end_': 
      live_count += 1 
     if type(value) == type(dict()): 
      live_count = words_counter(live_count, value) 
    return(live_count) 

Answer 1

Ok, so, wie es sich herausstellt, verschachtelten dicts verwendet, ist keine gute Idee im Allgemeinen, weil hackerrank 100k Strings in Ihr Programm schieben und dann wird alles zu einem Schleichen verlangsamen. Das Problem lag also nicht im Parsen, sondern im Speichern vor dem Parsing. Schließlich fand ich this blogpost, ihre Lösung besteht die Herausforderung 100%. Hier ist der Code in voller Länge:

class Node: 
    def __init__(self): 
     self.count = 1 
     self.children = {} 

trie = Node() 


def add(node, name): 
    for letter in name: 
     sub = node.children.get(letter) 
     if sub: 
      sub.count += 1 
     else: 
      sub = node.children[letter] = Node() 
     node = sub 


def find(node, data): 
    for letter in data: 
     sub = node.children.get(letter) 
     if not sub: 
      return 0 
     node = sub 
    return node.count 

if __name__ == '__main__': 
    n = int(input().strip()) 
    for _ in range(n): 
     op, param = input().split() 
     if op == 'add': 
      add(trie, param) 
     else: 
      print(find(trie, param))