Итерация по сложному многомерному массиву (структура данных Trie на PHP, улучшение кода)

Question

Итерация по сложному многомерному массиву (структура данных Trie на PHP, улучшение кода)

Недавно я столкнулся с проблемой кодирования, когда мне пришлось создать простое дерево в php, мне удалось сделать это с помощью циклов php и foreach, но я не доволен самим кодом (кажется, не совсем корректным), поэтому я Я пытаюсь реализовать это с помощью итераторов PHP.

Итак, у меня есть сложный массив (Trie), например:

array(
'a' => array(),
'b' => array(
'a' => array(
'c' => array(
'o' => array(
'n' => array()
)
)
)
),
'x' => array(
'x' => array(
'x' => array()
)
)
);

И я хочу проверить, является ли ‘бекон’ словом, хранящимся в этом дереве, процесс, чтобы найти его, должен проходить по массиву и проверять, существует ли каждый узел, к которому он относится и существует, например: мне нужен в корне элемент с ключ ‘b’, затем внутри массива [‘b’], мне нужно проверить, есть ли у меня массив [‘b’] [‘a’], затем [‘b’] [‘a’] [‘c ‘] и так далее.

С помощью цикла foreach я смог сделать это, передав новый массив по ссылке и проверив ключи. Теперь, используя итератор, кажется, я немного забиваю код (и тот факт, что при выполнении foreachs php копирует массив, заставляет меня думать, что это решение может использовать намного больше памяти, чем использование итераторов).

Таким образом, код до сих пор является циклом while, в котором завершено условие, которое останавливается при сбое (в текущем массиве нет ключа, который я ищу) или об успешном завершении (слово, которое завершено):

// OUTSIDE THE LOOP
$finished = false;
$string = 'bacon';
$string = str_split($string);
$queue = new SplQueue();
// Enqueue all the letters to the queue -> skipping this because it's boring

// FIRST WHILE LOOP
$iterator = new ArrayIterator($array);
$iterator->key(); // No match with queue -> check next key

// SECOND WHILELOOP
$iterator->next();
$iterator->key(); // Matches with the key I want do dequeue (B),
$next =  new ArrayIterator($array[$iterator->key()]);
$queue->dequeue();

// THIRD WHILE LOOP
$next->key();  // Match [A] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 4TH WHILE LOOP
$next->key();  // Match [C] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 5TH WHILE LOOP
$next->key();  // Match [O] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 5TH WHILE LOOP
$next->key();  // Match [N]
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue(); // queue empty, throw success

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

Заранее спасибо.

1

arrays data-structures iterator php trie

Решение

Другие решения

Вот код для рекурсивный алгоритм который будет повторять любое количество уровней:

<?php
$trie = array(
'a' => array(),
'b' => array(
'a' => array(
'c' => array(
'o' => array(
'n' => array()
)
)
)
),
'x' => array(
'x' => array(
'x' => array()
)
)
);

/**
* @param string $word
* @param array $array
* @param int [$i = 0]
*/
function findWord($word, $array, $i = 0)
{
$letter = substr($word, $i, 1);
if (isset($array[$letter])) {
if ($i == strlen($word) - 1) {
return true;
} else if ($i < strlen($word)) {
return findWord($word, $array[$letter], $i + 1);
}
}
return false;
}

if (findWord('bacon', $trie)) {
die("Did find word.");
} else {
die("Didn't find word.");
}

Вот код для итерационный алгоритм который будет перебирать любое количество уровней и должен эффективно использовать память и процессор:

<?php

$trie = array(
'a' => array(),
'b' => array(
'a' => array(
'c' => array(
'o' => array(
'n' => array()
)
)
)
),
'x' => array(
'x' => array(
'x' => array()
)
)
);

/**
* @param string $word
* @param array $array
*/
function findWord($word, $array)
{
$tmpArray = $array;
for ($i = 0; $i < strlen($word); $i++)
{
$letter = substr($word, $i, 1);
if (isset($tmpArray[$letter])) {
if ($i == strlen($word) - 1) {
return true;
} else {
$tmpArray = $tmpArray[$letter];
}
} else {
break;
}
}
return false;
}

if (findWord('bacon', $trie)) {
die("Did find word.");
} else {
die("Didn't find word.");
}

2

Источник

Accepted Answer

Это хорошая задача для решения этой проблемы с использованием итераторов. Хотя я думаю, что итераторы хороши, но они заставляют вас думать с точки зрения итеративного подхода. Хотя для некоторых проблем это нормально, но для задач, которые вы описали имеет больше смысла использовать рекурсию.

Итак, я думаю, что вы должны принять ответ @cjohansson. Как это читабельно и понятно.

Но в качестве доказательства концепции вот мое решение, использующее RecursiveIteratorIterator. Мы должны расширить этот класс и немного изменить его в соответствии с нашими потребностями, а также сократить количество ненужных итераций:

class TrieRecursiveIteratorIterator extends RecursiveIteratorIterator
{
protected $word;

public function __construct(
$word,
Traversable $iterator,
$mode = RecursiveIteratorIterator::LEAVES_ONLY,
$flags = 0
) {
$this->word = str_split($word);

parent::__construct($iterator, $mode, $flags);
}

public function next()
{
if ($this->currentLetterMatched()) {
$this->updatePrefix();
$this->setPrefixed();
}

parent::next();
}

protected $prefix = [];
protected function updatePrefix()
{
$this->prefix[$this->getDepth()] = $this->key();
}

protected $prefixed = [];
protected function setPrefixed()
{
$this->prefixed = $this->current();
}

public function valid()
{
if (
$this->getDepth() < count($this->prefix)
|| count($this->word) === count($this->prefix)
) {
return false;
}

return parent::valid();
}

public function callHasChildren()
{
if ($this->currentLetterMatched()) {
return parent::callHasChildren();
}

return false;
}

protected function currentLetterMatched()
{
return isset($this->word[$this->getDepth()])
&& $this->key() === $this->word[$this->getDepth()];
}

public function testForMatches()
{
foreach ($this as $_) {
}

return $this;
}

public function getPrefix()
{
return implode('', $this->prefix);
}

public function getPrefixed()
{
return $this->prefixed;
}

public function matchFound()
{
return ($this->word === $this->prefix);
}

public function exactMatchFound()
{
return ($this->word === $this->prefix) && empty($this->prefixed);
}

public function prefixMatchFound()
{
return ($this->word === $this->prefix) && !empty($this->prefixed);
}
}

Тогда мы можем сделать следующее:

$iterator = new TrieRecursiveIteratorIterator(
$word,
new RecursiveArrayIterator($trie),
RecursiveIteratorIterator::SELF_FIRST
);

$iterator->testForMatches();

После этого мы можем спросить наших $iterator разные вещи, такие как:

Если совпадение найдено: $iterator->matchFound();
Если точное совпадение было найдено: $iterator->exactMatchFound();
Если есть слова с префиксом данного слова: $iterator->prefixMatchFound();
Получить сам префикс (когда совпадение найдено, префикс будет равен заданному слову): $iterator->getPrefix();
Получить окончания с префиксом данного слова: $iterator->getPrefixed(),

Вот рабочая демо.

Итак, как вы можете видеть, эта реализация не так прямолинейна, как рекурсия. И пока я большой поклонник итераторов и SPL использование, но это не серебряная пуля, и вы должны выбрать инструменты, которые лучше соответствуют вашим текущим потребностям.

Кроме того, это за пределами домена, но мой класс нарушает Принцип единой ответственности. Это было сделано намеренно ради простоты. В реальной жизни был бы другой класс, который будет использовать наш итератор в качестве зависимости.

1