Рекурсивный поиск в массиве php

Рекурсия на PHP — алгоритм, применение

К написанию статьи сподвигли часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах, но в последствии решил реализовать на PHP, дабы снять зависимость от СУБД. На простом примере я покажу как можно пройти от корня иерархии до каждого конечного элемента и обратно, информация скорее для новичков.

Итак, тестовая иерархия, с которой нам предстоит работать:

В базе данных имеется самая простая таблица на самом простом MSSQL сервере, тонкости подключения опустим, наша цель — разобраться с иерархией и рекурсией.

Описание полей есть в комментариях, чуть подробнее о поле access:

По умолчанию в моей системе для каждого нового документа проставляется inherit, то есть наследование от родителя. Для нашего эксперимента для некоторых эелементов пропишем доменные группы. В группе Domain Users моя учётная запись имеется, а вот в AD Group Secret меня нет.

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

Задача №1

Необходимо научиться работать с иерархией как с деревом а не списком. Уровень вложенности заранее не известен и может быть любым, следовательно должно быть универсальное средство, позволяющее выполнять проход по дереву как сверху вниз, так и в обратном направлении.

Задача №2

Необходимо гибко управлять доступами, то есть, давать права на группы, отдельные документы и т.д., по аналогии с файловой системой NTFS, можно закрыть права на всю папку, но для одного документа в этой папке доступ нарезать — тоже самое должно получиться и у нас.

Задача №3

Необходимо скрыть от пользователей ресурсы, к которым у них нет доступа, но самое главное, при наличии прав хотя бы на один документ где то в глубине закрытой для него ветки, делать видимыми элементы ведущие к этому документу (иначе как пользователь до него доберётся?)

Вот собственно базовая функция:

Описание по большей части привёл в комментариях, но если говорить просто — после того как цикл foreach проходит строку и делает что то с данными(в нашем случае просто копирует данные в другой массив, добавляя поле level и точки к имени), он запускает эту же функцию, передав ей uid строки, и поскольку в условии if мы сравниваем его с pid, то следующий запуск однозначно захватит дочерние элементы. Цикл foreach перебирает все строки у которых uid родителя совпадает с переданным значением, поэтому перезапуская саму себя, функция отработает на каждом элементе каждого уровня. Для наглядности, мы так же передаём level увеличивая его на единицу. В итоге мы увидим какой документ какой уровень вложенности имеет.

Выводим массив $array в браузер:

Уже не плохо, не так ли?

А теперь немного усложним нашу функцию:

Разбираем по порядку:

1. Добавлено поле path — для формирования пути, добавляем к значению «/» и имя строки, затем полученное значение передаём в функцию, где история повторяется и на выходе получается путь от корня до элемента.

3. Добавлен индекс $array_idx_lvl = array();. Этот индекс нам так же потребуется позже, смысл таков — результирующий набор складывается не в одну кучу, а с разбивкой на массивы индексируемые по level.

4. Поле Access. Когда функция запускает саму себя, вместе с остальными параметрами она передаёт свою настройку прав $_row[‘access’] дочерям, а далее происходит следующее, проверяются права — если выставлено наследование (inherit), то применяются права родителя, если нет — через in_array проверяем, есть ли указанная в access доменная группа среди групп зашедшего пользователя. Если есть — добавляем в строку allow (разрешить), иначе deny (запрет).

Итоговый результат:

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

Почему здесь нужен проход в обратную сторону? Предположим у пользователя закрыт доступ для всего контента за исключением одного, самого дальнего(на последнем уровне) документа, если подумать, логично было бы брать начало от доступного, и вести его к корню дерева, показывая только нужные элементы.

Что делает эта функция — принимает в качестве параметра uid строки, с которой нужно начать действовать, обращается к этой строке и проверяет видимость. Если в поле view не show(т.е. показывать), а что то другое, проверяет что находится в безопасности, и если там стоит allow(доступ открыт), делает элемент видимым, в противном случае скрытым(hide), затем запускает себя же, передавая свой pid и настройку видимости, а так же переменную $ident увеличенную на 1, тем самым блокируя последующие самозапуски. При втором проходе, по переданному pid находится родительский элемент, выполняется та же проверка, за исключением одного, если от дочернего в переменной $view передано ‘show‘, то не смотря ни на что, текущему элементу так же присвоится show, то есть видимый.

На мой взгляд, работа с ограничителем — самый оптимальный вариант, ибо представьте ситуацию, на 10 уровне у нас 100 документов, для полного обхода всего дерева, нам нужно запускать эту функцию на каждом элементе, т.к. если на последнем уровне мы запустим функцию 100 раз, то выполняя самозапуски, перебор 100 раз дойдёт до корня. Если умножить на 10 уровней — уже получится 1000 циклов, что не есть хорошо, поэтому подъём нужно осуществлять равномерно, уровень за уровнем.

Запускает эту функцию следующий код:

Вот тут как раз и потребовался индекс по уровню. Здесь мы движемся от самого дальнего уровня, заходя в каждый, обрабатывая в нём каждый элемент.

Перед запуском, я намеренно прописал разрешающую группу для пункта «Отчет для налоговой», чтобы наглядно показать что код отрабатывает корректно. Несмотря на то, что доступ к разделу «Бухгалтерская отчетность» закрыт, он видимый.

Вот и собственно всё, думаю с задачей мы справились, основа получена, алгоритм работает, можно применить в реальной системе.

Источник

рекурсивный поиск и создание нового массива

Есть массив, нужно обойти рекурсивно и создать новый, например при выборе ключа 254362, получаем значения 254370, 254363 ищем полученные значения, как ключи вновь и т.д. Новый массив должен иметь структуру, как в примере, но без незатронутых ключей при поиске.

В настоящий момент есть код:

При его исполнении возникает ошибка ERR_CONNECTION_RESET

1 ответ 1

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

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками php или задайте свой вопрос.

Похожие

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2021 Stack Exchange Inc; материалы пользователей предоставляются на условиях лицензии cc by-sa. rev 2021.9.17.40238

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Источник

PHP: array_search — быстрый поиск по массиву

Я уже достаточно долго использую функцию array_search() для поиска значений в массиве, так как неоднократно слышал и читал о том, что она работает заметно быстрее, чем поиск по массиву в цикле, но насколько она быстрее — не знал. Наконец-то дошли руки самому проверить и посчитать.

Сравнил скорость поиска в массиве с помощью этой функции с обычным перебором массива в циклах foreach и while. На 10-100 элементах массива разница незаметна да и время столь мало, что им можно принебречь. А вот для больших массивов разница оказалась весьма существенной. С увеличением размера массива на порядок, значительно увеличивалось и время поиска. При ста тысячах элементов скорость foreach падала до 0,013 секунды, а while — до 0,017, при том что array_search() тоже замедлился, но все-таки остался на порядок быстрее — 0.004 секунды. Для большого скрипта, работающего с большими массивами замена поиска в цикле на поиск с помощью array_search() будет вовсе не «блошиной оптимизацией».

UPD: добавил в циклы break и менял искомое значение так, чтобы оно было в середине массива — 5-50-500 и т.д. Данные в таблице обновленные.

В связи с этим вспомнил недавнюю дискуссию с одним из коллег на работе — насчет того, нужно ли программисту знать все эти встроенные функции языка, или достаточно «программистского склада ума» и общих познаний. Не вдаваясь с рассуждения об этом самом складе ума, думаю, что все-таки знать функции надо, может быть не весь синтаксис в деталях, а хотя-бы какие функции есть и что они в общих чертах могут.

UPD: нужен программистский склад ума, тоже нужен! И внимательность с памятью не помешают (навеяно break и range 🙂

Под хабракатом код скрипта, которым подсчитывал время:

$mass=100000; // число значений в массиве в котором будем искать
$search=50000; // в массиве будем искать это значение
$first_result=array(); // массив результатов, для вычисления среднего значения первого варианта
$second_result=array(); // массив результатов, для вычисления среднего значения второго варианта
$third_result=array(); // массив результатов, для вычисления среднего значения третьего варианта

Источник

array_search

(PHP 4 >= 4.0.5, PHP 5, PHP 7, PHP 8)

array_search — Осуществляет поиск данного значения в массиве и возвращает ключ первого найденного элемента в случае успешного выполнения

Описание

Список параметров

Если needle является строкой, сравнение происходит с учётом регистра.

Возвращаемые значения

Примеры

Пример #1 Пример использования array_search()

Смотрите также

User Contributed Notes 44 notes

in (PHP 5 >= 5.5.0) you don’t have to write your own function to search through a multi dimensional array

$userdb=Array
(
(0) => Array
(
(uid) => ‘100’,
(name) => ‘Sandra Shush’,
(url) => ‘urlof100’
),

(1) => Array
(
(uid) => ‘5465’,
(name) => ‘Stefanie Mcmohn’,
(pic_square) => ‘urlof100’
),

(2) => Array
(
(uid) => ‘40489’,
(name) => ‘Michael’,
(pic_square) => ‘urlof40489’
)
);

simply u can use this

$key = array_search(40489, array_column($userdb, ‘uid’));

About searcing in multi-dimentional arrays; two notes on «xfoxawy at gmail dot com»;

It perfectly searches through multi-dimentional arrays combined with array_column() (min php 5.5.0) but it may not return the values you’d expect.

Secondly, if your array is big, I would recommend you to first assign a new variable so that it wouldn’t call array_column() for each element it searches. For a better performance, you could do;

It’s what the document stated «may also return a non-Boolean value which evaluates to FALSE.»

the recursive function by tony have a small bug. it failes when a key is 0

here is the corrected version of this helpful function:

If you are using the result of array_search in a condition statement, make sure you use the === operator instead of == to test whether or not it found a match. Otherwise, searching through an array with numeric indicies will result in index 0 always getting evaluated as false/null. This nuance cost me a lot of time and sanity, so I hope this helps someone. In case you don’t know what I’m talking about, here’s an example:

hallo every body This function matches two arrays like
search an array like another or not array_match which can match

for searching case insensitive better this:

About searcing in multi-dimentional arrays;
note on «xfoxawy at gmail dot com» and turabgarip at gmail dot com;

$xx = array_column($array, ‘NAME’, ‘ID’);
will produce an array like :
$xx = [
[ID_val] => NAME_val
[ID_val] => NAME_val
]

$yy = array_search(‘tesxt’, array_column($array, ‘NAME’, ‘ID’));
will output expected ID;

To expand on previous comments, here are some examples of
where using array_search within an IF statement can go
wrong when you want to use the array key thats returned.

Take the following two arrays you wish to search:

I was going to complain bitterly about array_search() using zero-based indexes, but then I realized I should be using in_array() instead.

The essence is this: if you really want to know the location of an element in an array, then use array_search, else if you only want to know whether that element exists, then use in_array()

Be careful when search for indexes from array_keys() if you have a mixed associative array it will return both strings and integers resulting in comparison errors

/* The above prints this, as you can see we have mixed keys
array(3) <
[0]=>
int(0)
[1]=>
string(3) «car»
[2]=>
int(1)
>
*/

hey i have a easy multidimensional array search function

Despite PHP’s amazing assortment of array functions and juggling maneuvers, I found myself needing a way to get the FULL array key mapping to a specific value. This function does that, and returns an array of the appropriate keys to get to said (first) value occurrence.

But again, with the above solution, PHP again falls short on how to dynamically access a specific element’s value within the nested array. For that, I wrote a 2nd function to pull the value that was mapped above.

I needed a way to return the value of a single specific key, thus:

Better solution of multidimensional searching.

FYI, remember that strict mode is something that might save you hours.

one thing to be very aware of is that array_search() will fail if the needle is a string and the array itself contains values that are mixture of numbers and strings. (or even a string that looks like a number)

The problem is that unless you specify «strict» the match is done using == and in that case any string will match a numeric value of zero which is not what you want.

also, php can lookup an index pretty darn fast. for many scenarios, it is practical to maintain multiple arrays, one in which the index of the array is the search key and the normal array that contains the data.

//very fast lookup, this beats any other kind of search

I had an array of arrays and needed to find the key of an element by comparing actual reference.
Beware that even with strict equality (===) php will equate arrays via their elements recursively, not by a simple internal pointer check as with class objects. The === can be slow for massive arrays and also crash if they contain circular references.

This function performs reference sniffing in order to return the key for an element that is exactly a reference of needle.

A simple recursive array_search function :

A variation of previous searches that returns an array of keys that match the given value:

I needed a function, that returns a value by specifying a keymap to the searched value in a multidimensional array and came up with this.

My function get_key_in_array() needed some improvement:

An implementation of a search function that uses a callback, to allow searching for objects of arbitrary complexity:

For instance, if you have an array of objects with an id property, you could search for the object with a specific id like this:

For a more complex example, this function takes an array of key/value pairs and returns the key for the first item in the array that has all those properties with the same values.

The final step is a function that returns the item, rather than its key, or null if no match found:

Источник

array_walk_recursive

array_walk_recursive — Рекурсивно применяет пользовательскую функцию к каждому элементу массива

Описание

Список параметров

Если требуется, чтобы функция callback изменила значения в массиве, определите первый параметр callback как ссылку. Тогда все изменения будут применены к элементам массива.

Возвращаемые значения

Возвращает true в случае успешного выполнения или false в случае возникновения ошибки.

Примеры

Пример #1 Пример использования array_walk_recursive()

Результат выполнения данного примера:

Смотрите также

User Contributed Notes 27 notes

Since this is only mentioned in the footnote of the output of one of the examples, I feel it should be spelled out:

* THIS FUNCTION ONLY VISITS LEAF NODES *

That is to say that if you have a tree of arrays with subarrays of subarrays, only the plain values at the leaves of the tree will be visited by the callback function. The callback function isn’t ever called for a nodes in the tree that subnodes (i.e., a subarray). This has the effect as to make this function unusable for most practical situations.

How to modify external variable from inside recursive function using userdata argument.

// result
// 11 : 1
// 12 : 1
// 2 : 1
// counter: 0

// result
// 11 : 1
// 12 : 2
// 2 : 1
// counter : 0

// result
// 11 : 1
// 12 : 2
// 2 : 3
// counter : 3

Unfortunately the PHP example given doesn’t do this. It actually took me a while to figure out why my function wasn’t changing the original array, even though I was passing by reference.

One other silly thing you might try first is something like this:

I use RecursiveIteratorIterator with parameter CATCH_GET_CHILD to iterate on leafs AND nodes instead of array_walk_recursive function :

The description says «If funcname needs to be working with the actual values of the array, specify the first parameter of funcname as a reference.» This isn’t necessarily helpful as the function you’re calling might be built in (e.g. trim or strip_tags). One option would be to create a version of these like so.

multidimensional array to single array

Array ( [0] => 2 [1] => 4 [2] => 2 [3] => 7 [4] => 3 [5] => 6 [6] => 5 [7] => 4 )

array_walk_recursive itself cannot unset values. Even though you can pass array by reference, unsetting the value in the callback will only unset the variable in that scope.

A simple solution for walking a nested array to obtain the last set value of a specified key:

I needed to add or modify values in an array with unknown structure. I was hoping to use array_walk_recursive for the task, but because I was also adding new nodes I came up with an alternate solution.

I decided to add to the previous PHP 4 compatible version of array_walk_recursive() so that it would work within a class and as a standalone function. Both instances are handled by the following function which I modified from omega13a at sbcglobal dot net.

The following example is for usage within a class. To use as a standalone function take it out of the class and rename it. (Example: array_walk_recursive_2)

Источник