Поиск по многомерному массиву PHP

387

31 декабря 2016, 17:03

Здравствуйте. Есть массив такой структуры:

Array(
    'category1'=>Array(
        0=>"some long string";
        1=>"another long string";
        'text'=>"one more str";
    ),
    'category2'=>Array(
        0=>"test1";
        'text'=>"test3";
    ),
    ...
);

Мне нужно, чтобы по значению, например, "test1" я находил категорию элемента, в данном случае - category2. Как это можно реализовать максимально производительно (такой поиск используется у меня в скрипте довольно часто) ?

UPD: Код моей реализации:

function search($needle, $haystack){
    foreach($haystack as $key=>$item){
        if(in_array($needle, $item))
            return $key;
    }
    return false;
}

Он, конечно, работает, но хотелось бы найти какое-нибудь сверхбыстрое решение.

Answer 1

Если структуру не менять и предполагать универсальное решение, то полный перебор в худшем случае - единственный путь. Какой-то существенный бонус может дать явное или неявное изменение самой структуры.

Если искать надо по одному массиву и часто, то можно затратить больше памяти, некоторое время на обработку первого вызова, но получить очень существенный бонус по скорости для последующих вызовов до уровня O(1) - реализовать hashmap. В PHP, где ассоциативный массив уже hash, достаточно создать вспомогательный массив вида item => category

$search = function($needle) use($rg) {
    static $hashmap = null;
    if (! $hashmap) {
        // первый запуск, заполняем индекс
        foreach ($rg as $cat => $elements) {
            foreach ($elements as $item) {
                $hashmap[ $item ] = $cat;
            }
        }
    }
    return isset($hashmap[ $needle ])
        ? $hashmap[ $needle ]
        : null;
};

Я намеренно воспользовался реализацией через замыкание чтобы показать привязку работы метода к определённому массиву.

Напомню про проблему с необходимостью инвалидации сохранённого в функции списка значений при изменении исходного массива.

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