алгоритм — масштабируемая реализация Trie в переполнении стека

Следующий этот учебник я встретил Trie структура данных. С недавнего времени я программировал на PHP, я пытался решить лекцию проблема с этим. Мне удалось получить правильные ответы, но только для небольших входных данных (вход № 10 — файл размером 2,82 МБ). Очевидно, мой алгоритм плохо масштабируется. Это также превышает ограничение по умолчанию 128 МБ памяти PHP.

Мой алгоритм

В Trie хранится корневой узел. Каждый узел имеет дочерний элемент. Я использую стандартный массив PHP для хранения детей. Дочерний ключ представляет символ (в настоящее время я создаю новый узел для каждого символа, a-z в нижнем регистре, сопоставляя с 0-25), дочернее значение является ссылкой на другой узел.

Член «веса», который есть у каждого узла, существует из-за проблема.
Я хотел бы оптимизировать свой код (или даже переписать его с нуля, используя другой подход), чтобы он мог пройти тесты для больших входных данных.

Я заинтересован в решении, чтобы эта структура данных работала в PHP с большими входными данными, если это возможно.

Мой код

TrieNode Класс хранит древовидную иерархию.

class TrieNode {
// weight is needed for the given problem
public $weight;
/* TrieNode children,
* e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
* where 0 stands for 'a', 1 for 'c'
* and TrieNode objects are references to other TrieNodes.
*/
private $children;

function __construct($weight, $children) {
$this->weight = $weight;
$this->children = $children;
}

/** map lower case english letters to 0-25 */
static function getAsciiValue($char) {
return intval(ord($char)) - intval(ord('a'));
}

function addChild($char, $node) {
if (!isset($this->children)) {
$this->children = [];
}
$this->children[self::getAsciiValue($char)] = $node;
}

function isChild($char) {
return isset($this->children[self::getAsciiValue($char)]);
}

function getChild($char) {
return $this->children[self::getAsciiValue($char)];
}

function isLeaf() {
return empty($this->children);
}
}

Trie Класс хранит корневой TrieNode. Он может вставлять и запрашивать узлы.

class Trie {
/* root TrieNode stores the first characters */
private $root;

function __construct() {
$this->root = new TrieNode(-1, []);
}

function insert($string, $weight) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if(!$currentNode->isChild($char)) {
$n = new TrieNode($weight, null);
$currentNode->addChild($char, $n);
}
$currentNode->weight = max($weight, $currentNode->weight);
$currentNode = $currentNode->getChild($char);
}
}

function getNode($string) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if ($currentNode->isLeaf() || !$currentNode->isChild($char)) {
return null;
}
$currentNode = $currentNode->getChild($char);
}
return $currentNode;
}

function getWeight($string) {
$node = $this->getNode($string);
return is_null($node) ? -1 : $node->weight;
}
}

Тестовый код. Анализирует ввод и вызывает объект Trie.

//MAIN / TEST

/*
In case the problem page is down:

e.g.
INPUT
2 1
hackerearth 10
hackerrank 9
hacker

OUTPUT
10

where 2 is the number of inserts, 1 is the number of queries
"string number" is the string to insert and its "weight""hacker" is the string to query
10 is maximum the weight of the queried string (hacker -> 10)
*/

$trie = new Trie();
$handle = fopen('test.txt', 'r');
//$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
list($s, $weight) = fscanf($handle, "%s %d");
$trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
$query = trim(strval(fgets($handle)));
echo $trie->getWeight($query) . PHP_EOL;
}
fclose($handle);

Потерпеть поражение