рекурсивный поиск в массиве php
рекурсивный поиск и создание нового массива
Есть массив, нужно обойти рекурсивно и создать новый, например при выборе ключа 254362, получаем значения 254370, 254363 ищем полученные значения, как ключи вновь и т.д. Новый массив должен иметь структуру, как в примере, но без незатронутых ключей при поиске.
В настоящий момент есть код:
При его исполнении возникает ошибка ERR_CONNECTION_RESET
1 ответ 1
Ваша процедура может зацикливаться на данных в которых 2 id будут указывать друг на друга. В вашем примере таких не видно, но надо учитывать, что в вашем массиве присутствует элемент, отсутствие номера у которого может вводить в заблуждение:
А процедура с защитой от циклов и исключением других ошибок, типа отсутствующих элементов массива и не объявленной переменной childs должна выглядеть примерно так:
Всё ещё ищете ответ? Посмотрите другие вопросы с метками php или задайте свой вопрос.
Похожие
Подписаться на ленту
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
дизайн сайта / логотип © 2021 Stack Exchange Inc; материалы пользователей предоставляются на условиях лицензии cc by-sa. rev 2021.9.27.40309
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Search for a key in an array, recursively
Hey, this method searches for a specific key in an associative array and returns the value associated with it. There’s some problem with the recursion. Any clue?
7 Answers 7
Maybe it’s overkill, but it’s funny to use RecursiveIterators 🙂
UPDATE: Maybe it was overkill with old versions of PHP, but with >=5.6 (specially with 7.0) I would totally use this without doubt.
UPDATE: Also, as of PHP 5.6, with generators you can easily iterate over all elements which pass the filter, not only the first one:
you need to stop the recursive deep search, by return false and then check it in the function.
you can find more examples of functions (like using RecursiveArrayIterator and more) in this link : http://php.net/manual/en/function.array-search.php
The answer provided by xPheRe was extremely helpful, but didn’t quite solve the problem in my implementation. There are multiple nested associative arrays in our data structure, and there may be multiple occurrences of any given key.
In order to suit our purposes, I needed to implement a holder array that was updated while traversing the entire structure, instead of returning on the first match. The real work was provided by another poster, but I wanted to say thanks and share the final step that I had to cover.
The best solution above misses the case if the key is repeated and only returns the first value, here I get all the values in an array instead:
I just been through a similar issue and here’s what worked for me:
This is going to return an array containing the value of all the matching keys it found in the multidimensional array. I tested this with arrays dinamically generated by an e-mail API. In the case of multiple matches, you just need to create a simple foreach loop to sort the array however you want.
I noticed the main mistake I was making was using if-ifelse conditions when I should be using if-if conditions. Any questions or criticism are very welcome, cheers!
I recently came across the same issue, when dealing with Yii2 query object.
The reason your function didn’t work is that the return action doesn’t work here. Just pass a reference parameter to store the value, and do whatever you want afterwards.
As you can see, this is a simple PHP function doesn’t rely on any library. So I think its worth to mention with all the answer listed above.
Linked
Related
Hot Network Questions
Subscribe to RSS
To subscribe to this RSS feed, copy and paste this URL into your RSS reader.
site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2021.9.27.40309
By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.
Рекурсия на PHP
В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.
PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.
Перевод Google из официальной документации по PHP
Понятие рекурсии
Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.
Существует два варианта реализации рекурсивных функций: простой и сложный. В простом случае рекурсивная функция вызывает саму себя. В сложном — функция вызывает другую функцию, которая вызывает исходную функцию, с которой всё начиналось.
Рассмотрим пример из жизни. Если взять два больших зеркала и поставить их друг напротив друга, то можно увидеть бесконечный коридор из изображений зеркал. Каждое зеркало несёт в себе функцию отражения пространства расположенного перед ним. Поэтому здесь мы имеем пример сложной рекурсии (функция вызывает другую функцию, которая вызывает исходную).
Другим примером можно взять всем хорошо известное детское стихотворение:
…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).
Глубина рекурсии
В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.
Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.
Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.
Опасности и подводные камни рекурсии
Рассмотрим простой пример.
Здесь функция foo() должна вызывать самое себя до бесконечности. В реальных условиях запуск программы приведёт к Segmentation fault, так как произойдёт переполнение стека вызова в силу ограничений на выделенную под него память. Понимая это следует избегать таких конструкций при разработке.
То же самое касается и примера со сложной рекурсией.
В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.
Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.
Здесь рекурсивный вызов должен завершиться по достижении степени вложенности n.
На практике при запуске этой программы для больших значений n произойдёт та же самая ошибка переполнения стека. Это так же следует учитывать при обработке больших списков и других структур данных, в которых глубина рекурсии зависит от их размера.
Рекурсивные алгоритмы на PHP
Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.
Существует множество таких алгоритмов:
Рассмотрим некоторые из них.
Вычисление последовательности Фибоначчи
Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…
В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения: 
Эта последовательность обладает одним замечательным свойством, а именно: 
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…
Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:
С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:
Дело в том, что реализация рекурсивного алгоритма “в лоб” обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.
Повторные вызовы функции с одинаковыми аргументами занимает дополнительное время. Чтобы избежать этого, используют подход восходящего динамического программирования, который состоит в том, что задача разбивается на подзадачи и каждая подзадача решается только один раз. В нашем примере это можно реализовать в виде :
Таким образом вызов функций над одним и тем же аргументом производится лишь однажды, в случае повторных вызовов производится обращение к памяти к уже вычисленным значениям. Такой алгоритм выполняется гораздо быстрее, чем его простая реализация. Но всё же при этом он значительно уступает итеративной версии. Вы спросите в чём же дело?
Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.
Чтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:
Время выполнения этой программы уже приближается к времени выполнения программы основанной на итерациях. Но всё же для достаточно больших значений n мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?
Предлагаю вам пока самостоятельно поразмышлять на эту тему.