UPD: Ich zog ursprüngliche Frage zu https://codereview.stackexchange.com/questions/127055/building-tree-graph-from-dictionary-performance-issuesPhp Präfixbaums Implementierung im Vergleich zu Assoc Array
Hier ist eine kurze Version, ohne Codes.
Ich versuche, einen Präfixbaum aus dem Wörterbuch zu erstellen. Also, mit dem folgenden Wörterbuch 'and','anna','ape','apple'
, sollte das Diagramm so aussehen: Ich habe versucht 2 Ansätze: mit assoziativen Array und mit selbst geschriebenen Baum/Knoten-Klassen.
Hinweis: Originalwörterbuch ist etwas über 8 MB und enthält> 600000 Wörter.
Frage: Gibt es einen guten (schnellen/effizienten) Weg, es zu tun?
Ich habe bisher versucht:
php assoziative Arrays (sie sind nicht sehr flexibel für die zukünftige Arbeit mit dieser Grafik).
selbstgeschriebene Tree/Node-Klassen (Performance-Probleme - Ausführungszeit steigt um bis zu 7x, Speicherbelegung steigt um 2x, ohne dass etwas implementiert wurde außer
inserting
).
Beispielcodes auf Codereview (das erste Glied in Frage) verfügbar
Sie haben beide die gleiche Code-/Ausführungskomplexität, nicht den gleichen Speicherbedarf und die gleiche Ausführungsgeschwindigkeit. Abhängig von der PHP-Version, die Sie ausführen, verwenden Sie unter Klassen auch mehr oder weniger Speicher. Wenn Sie nach einer besseren Leistung suchen und nicht nur Dinge lernen, würde ich vorschlagen, in verschachtelte Sets zu schauen. Sie finden auch bereit, PHP-Implementierungen zu verwenden: http://stackoverflow.com/questions/272010/searching-for-the-best-php-nested-sets-class-pear-class-excluded –
Diese Frage ist besser geeignet for [code review] (http://codereview.stackexchange.com) – nickb
@Sergiu Paraschiv - Ich werde es mir ansehen – haldagan