Как верно использовать ссылку для запоминания родителя?

Question

[Сергей]

Доброго времени суток. Пытаюсь реализовать алгоритм Ахо-Корасик, сделал бор, все прекрасно работает, реализовал удаление значений из бора. После попытки загрузить тестовые значения ~56к слов, интерпретатор выдал мне сообщение о том, что превышен лимит памяти, доступный для одного скрипта (128 мб). После недолгих раздумий я пришел к выводу, что я неверно использую ссылки. Вместо того, чтобы сохранить в массиве адрес на значение, туда записывается само значение (читай массив), находящееся по этой ссылке. Приведу пример кода, чтобы было нагляднее:

public function insert($key, $value) {
        $current_node = &$this->root;

        for ($i = 0; $i < mb_strlen($key, 'UTF-8'); $i++) {
            $char = mb_substr($key, $i, 1, 'UTF-8');

            $parent = &$current_node; // по идее должен указывать на родителя

            if (isset($current_node['children'][(string)$char])) { // если существует переход по букве
                $current_node = &$current_node['children'][(string)$char]; // обновляем текущее состояние (тут проблема)
                if (isset($current_node['isLeaf']))
                    unset($current_node['isLeaf']);
            } else {
                $current_node['children'][(string)$char] = []; // если нет перехода, то создаем его
                $current_node = &$current_node['children'][(string)$char]; // обновляем текущее состояние (и здесь проблема)
            }

            $current_node['parent'] = &$parent; // устанавливаем родителя данного узла

            if ($i == (mb_strlen($key, 'UTF-8') - 1)) { // обработка последнего символа в ключе
                $current_node['value'] = $value;
                if (!isset($current_node['children'])) {
                    $current_node['isLeaf'] = true;
                }
            }
        }
    }

При таком создании бора возникает перерасход памяти, как я уже описал в самом начале. Как быть?

Answer 1

[Антон Шаманов]

Как минимум нужно избавиться от лишнего кода:
Заменить

for ($i = 0; $i < mb_strlen($key, 'UTF-8'); $i++) {
            $char = mb_substr($key, $i, 1, 'UTF-8');

на разбитие строки на массив символов (mb_split) и обход его циклом (foreach).
Заменить

if (isset($current_node['isLeaf']))
                    unset($current_node['isLeaf']);

на
unset($current_node['isLeaf']);
Ну и

$current_node = &$current_node['children'][(string)$char];

явно не лучшее решение.

Comments

[Сергей]

а по теме есть что-нибудь?

[Антон Шаманов]

Pjeroo: по теме и написано, главное не использовать ссылки там где это не требуется: реализуй как объект с вспомогательными методами или добавь замыкания в функцию. Из-за таких кривых ссылок переменная сама на себя ссылается и начинается рекурсия бесконечная.