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

Question

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

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

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

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

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

Поэтому код до сих пор это петля в то время как закончил условие, которое останавливается на сбою (текущий массив не имеет ключа Я ищу) или успех (слово это полное):

// 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 в каждом цикле, это беспокоит меня, поэтому я надеялся услышать, есть ли у кого-то лучшее решение этой проблемы.

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

Answer 1

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

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

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

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

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

$iterator->testForMatches(); 

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

1. Если совпадение найдено: $iterator->matchFound();
2. Если так вы нашли совпадение: $iterator->exactMatchFound();
3. Если есть слова, которые имеют префикс с заданным словом: $iterator->prefixMatchFound();
4. Получите префикс (при обнаружении любого из совпадений префикс будет равен заданному слову): $iterator->getPrefix();
5. Получить окончание с префиксом данного слова: $iterator->getPrefixed().

Адрес working demo.

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

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

Answer 2

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

<?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."); 
}