Implementieren Sie ein Doppelarray in Python und messen Sie dessen Speichernutzung und Suchzeit. Als ich die Leistung bewertet habe, habe ich verschiedene Suchanfragen durchgeführt, aber ich konnte keine überzeugende Implementierung finden. Deshalb habe ich beschlossen, sie selbst zu erstellen. Ursprünglich sollten wir die Effizienz des Prozesses zum Erstellen eines doppelten Arrays berücksichtigen, aber diesmal werden wir uns nicht darauf konzentrieren. Der Zweck besteht darin, die Leistung des fertigen Doppelarrays zu bewerten. (Daher ist auch eine dynamische Addition ausgeschlossen.) Auch die Operation mit Dateien wird nicht berücksichtigt. Erstellen Sie es im Speicher und messen Sie dort seine Leistung.
Es ist eine der Methoden zum Verwalten von Zeichenkettendaten und kann die Suche mit einer effektiven Geschwindigkeit durchführen. Obwohl es theoretisch eine einfache Struktur hat, ist es abhängig von der Implementierungsmethode möglicherweise nicht sehr effektiv.
"Double Array" ist eine der Implementierungsmethoden der TRIE-Struktur und kann eine Hochgeschwindigkeitssuche realisieren.
Bitte beachten Sie die leicht verständlichen Erklärungen für das Doppelarray an verschiedenen Stellen.
Ich habe zuvor "Double Arrays" in anderen Programmiersprachen (C, C ++, Java usw.) implementiert, aber dies ist das erste Mal, dass ich es in Python implementiert habe. Ich denke, es gibt eine Python-spezifische Methode zur Effizienzsteigerung, aber ich werde sie gemäß dem grundlegenden Algorithmus implementieren. Die grundlegende Datenstruktur (Liste, Array usw.) verwendet die Sprache, aber die Algorithmusimplementierung wurde vollständig erstellt.
Wenn Sie nicht das gesamte Bild des Links in einem Knoten sehen können, können Sie nicht überprüfen, wo es im Array gespeichert werden kann. Führen Sie daher zunächst eine einfache (geschwindigkeitsfreie) TRIE-Implementierung durch, damit Sie den gesamten Link sehen können. Versuchen Sie, in einem doppelten Array zu speichern.
Bei dieser Double-Array-Implementierung wird Tail berücksichtigt. Es ist möglich, alle Zeichenfolgen in einer TRIE-Struktur darzustellen. Dies vereinfacht den Algorithmus. Gegen Ende gibt es jedoch keine Verzweigung in der Zeichenfolge, und es wird eine Verknüpfung mit einem verbundenen Knoten erstellt, wodurch sich die Kosten für Speicher und Zeit erhöhen. Daher können wir dies verbessern, indem wir die Terminalzeichenfolge ohne Verzweigungen als Tail verwalten. Mit anderen Worten, wir haben mit Tail ein Doppelarray implementiert, um eine bessere Leistung bei der Leistungsbewertung zu erzielen.
Leistungsmessmethode
Messen Sie die genaue Übereinstimmungssuche Versuchen Sie es 100 Mal und erhalten Sie den Durchschnittswert
Ausführungsumgebung
--Suchbegriff --87.379 englische Wörter aus wordnet