複雑な多次元配列を反復する（PHPのTrieデータ構造、改善コード）

Question

最近、私はphpで簡単なトライを構築しなければならないコーディングの課題に直面していました。私はPHPのイテレータを使って実装しようとしているので、コード自体に満足していません。

だから、私は例えば、複雑な配列（トライ）を持つ：

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

そして私は「ベーコン」は、それがこのトライに保存されているWordのかどうかを確認したい、プロセスは、それがあるべき見つけるために配列を反復し、各ノードがネストされて存在するかどうかをチェックします。例えば、ルートにキー '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を作成しているので、誰かがこの問題を解決できるかどうかを知りたいと思っていました。

ありがとうございます。ここ

Answer 1

これは、イテレータを使用してこの問題を解決するのがよい課題です。反復子は素晴らしいと思うが、反復的なアプローチの考え方を強いられる。いくつかの問題については問題はありませんが、あなたのようなタスクについては、は再帰の方が意味があります。

@cjohanssonの回答を受け入れるべきだと思います。それは読みやすく分かりやすいです。

しかし、コンセプトの証明と同じように、私の解決方法はRecursiveIteratorIteratorです。私たちは、私たちのニーズに合うようにしても、不必要な反復回数を減らすためにビットを、このクラスを拡張し、それを変更する必要があります。

その後、我々は以下のことが可能です。その後

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

$iterator->testForMatches(); 

を、我々はできます一致が見つかった場合

1. ：次のような私たちの$iterator異なるものを、頼む$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."); 
} 

は、任意の数のレベルを反復し、メモリやCPUであるべきである反復アルゴリズムするためのコードであります効率：

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