Comment effectuer une recherche par clé=>valeur dans un tableau multidimensionnel en PHP

Question

Existe-t-il un moyen rapide d'obtenir tous les sous-réseaux où une paire clé-valeur a été trouvée dans un tableau multidimensionnel ? Je ne peux pas dire quelle sera la profondeur du tableau.

Tableau d'exemples simples :

$arr = array(0 => array(id=>1,name=>"cat 1"),
             1 => array(id=>2,name=>"cat 2"),
             2 => array(id=>3,name=>"cat 1")
);

Lorsque je recherche key=name et value="cat 1", la fonction doit retourner :

array(0 => array(id=>1,name=>"cat 1"),
      1 => array(id=>3,name=>"cat 1")
);

Je suppose que la fonction doit être récursive pour descendre au niveau le plus profond.

Answer 1

Faites attention aux algorithmes de recherche linéaire (les algorithmes ci-dessus sont linéaires) dans les tableaux multidimensionnels, car leur complexité augmente avec la profondeur et le nombre d'itérations nécessaires pour parcourir l'ensemble du tableau. Par exemple

array(
    [0] => array ([0] => something, [1] => something_else))
    ...
    [100] => array ([0] => something100, [1] => something_else100))
)

prendrait au maximum 200 itérations pour trouver ce que vous cherchez (si l'aiguille était à [100][1]), avec un algorithme approprié.

Dans ce cas, les algorithmes linéaires ont une performance de O(n) (ordre du nombre total d'éléments dans le tableau entier), ce qui est médiocre, un million d'entrées (par exemple un tableau de 1000x100x10) nécessiterait en moyenne 500 000 itérations pour trouver l'aiguille. De plus, que se passerait-il si vous décidiez de changer la structure de votre tableau multidimensionnel ? Et PHP rejetterait un algorithme récursif si votre profondeur était supérieure à 100. L'informatique peut faire mieux :

Dans la mesure du possible, utilisez toujours des objets plutôt que des tableaux multidimensionnels :

ArrayObject(
   MyObject(something, something_else))
   ...
   MyObject(something100, something_else100))
)

et appliquer une interface et une fonction de comparateur personnalisées pour les trier et les retrouver :

interface Comparable {
   public function compareTo(Comparable $o);
}

class MyObject implements Comparable {
   public function compareTo(Comparable $o){
      ...
   }
}

function myComp(Comparable $a, Comparable $b){
    return $a->compareTo($b);
}

Vous pouvez utiliser uasort() pour utiliser un comparateur personnalisé, si vous vous sentez aventureux vous devriez implémenter vos propres collections pour vos objets qui peuvent les trier et les gérer (j'étend toujours ArrayObject pour inclure une fonction de recherche au minimum).

$arrayObj->uasort("myComp");

Une fois qu'ils sont triés (uasort est O(n log n), ce qui est aussi bon que possible sur des données arbitraires), la recherche binaire peut faire l'opération en O(log n) temps, c'est à dire qu'un million d'entrées prend seulement ~20 itérations pour la recherche. Pour autant que je sache, la recherche binaire de comparateurs personnalisés n'est pas implémentée en PHP ( array_search() utilise l'ordre naturel qui fonctionne sur les références des objets et non sur leurs propriétés), vous devrez l'implémenter vous-même comme je le fais.

Cette approche est plus efficace (il n'y a plus de profondeur) et surtout universelle (en supposant que vous fassiez respecter la comparabilité à l'aide d'interfaces) puisque les objets définissent la manière dont ils sont triés, ce qui permet de recycler le code à l'infini. Beaucoup mieux =)

Answer 2

$result = array_filter($arr, function ($var) {   
  $found = false;
  array_walk_recursive($var, function ($item, $key) use (&$found) {  
    $found = $found || $key == "name" && $item == "cat 1";
  });
  return $found;
});

Answer 3

http://snipplr.com/view/51108/nested-array-search-by-value-or-key/

<?php

//PHP 5.3

function searchNestedArray(array $array, $search, $mode = 'value') {

    foreach (new RecursiveIteratorIterator(new RecursiveArrayIterator($array)) as $key => $value) {
        if ($search === ${${"mode"}})
            return true;
    }
    return false;
}

$data = array(
    array('abc', 'ddd'),
    'ccc',
    'bbb',
    array('aaa', array('yyy', 'mp' => 555))
);

var_dump(searchNestedArray($data, 555));

Answer 4

function in_multi_array($needle, $key, $haystack) 
{
    $in_multi_array = false;
    if (in_array($needle, $haystack))
    {
        $in_multi_array = true; 
    }else 
    {
       foreach( $haystack as $key1 => $val )
       {
           if(is_array($val)) 
           {
               if($this->in_multi_array($needle, $key, $val)) 
               {
                   $in_multi_array = true;
                   break;
               }
           }
        }
    }

    return $in_multi_array;
}

Answer 5

J'avais besoin de quelque chose de similaire, mais pour rechercher un tableau multidimensionnel par valeur... J'ai pris l'exemple de John et j'ai écrit

function _search_array_by_value($array, $value) {
        $results = array();
        if (is_array($array)) {
            $found = array_search($value,$array);
            if ($found) {
                $results[] = $found;
            }
            foreach ($array as $subarray)
                $results = array_merge($results, $this->_search_array_by_value($subarray, $value));
        }
        return $results;
    }

J'espère que cela aidera quelqu'un :)