Php реализация префикс дерева по сравнению с массивом ДООС

Question

UPD: я переехал оригинальный вопрос https://codereview.stackexchange.com/questions/127055/building-tree-graph-from-dictionary-performance-issues

Вот короткая версия, без кодов.

Я пытаюсь построить дерево префикса из словаря. Итак, используя следующий словарь: 'and','anna','ape','apple', граф должен выглядеть так: Я пробовал 2 подхода: используя ассоциативный массив и используя самонаписанные классы дерева/узла.

Примечание: оригинал словаря составляет около 8 МБ и содержит> 600000 слов.

Вопрос: есть ли хороший (быстрый/эффективный) способ сделать это?

я пытался до сих пор:

• PHP ассоциативные массивы (они не являются очень гибкими для дальнейшей работы с этим графиком).

• самонаписанные классы дерева/узла (проблемы с производительностью - время выполнения увеличивается до 7x, использование памяти возрастает на 2x, даже не реализуя ничего, кроме функции inserting).

Примеры коды доступны на Просмотр Кода (самый первый ссылка на вопрос)

Answer 1

Пока я переключился на C++ и получил хороший ответ на codereview, я просто ответил на мой собственный вопрос Вот.

Существует еще один способ сделать это намного больше экономии времени за счет увеличения использования памяти (это не очень большой рост, по сравнению с «array в array с в array с ...» подход). Этот подход называется «double array trie», и вы можете прочитать информацию по этой теме here и прочитать вышеупомянутый ответ на codereview, чтобы увидеть пример реализации.

Это более экономичное время, но оно обеспечивает меньшую гибкость/удобство для будущего использования trie (по сравнению с подходом OOP).

Итак, окончательный ответ на этот вопрос для меня: «PHP не лучший инструмент для работы с действительно большими попытками».