PHP Lang
  1. PHP Lang
  3. Быстрый способ найти самый большой массив в многомерном массиве?
Intereting Posts
AWS PHP SDK Promise не работает Ползунок Nivo + php datatables и ошибка форматирования json с php Symfony2 + Необходимо использовать регулярное выражение в ODM доктрины mongodb для проверки регистра без учета регистра Как разместить массив с использованием AJAX для PHP? PHP-файлы cookie для нескольких доменов получение значения Message-ID из gmail imap с помощью php Отправка электронной почты с помощью PHP mail () Вставить арабский текст MySQL Вы не выбрали файл для загрузки. PHP-код воспламенителя Установка PHP на Windows с помощью IIS Автозагрузка с пространствами имен в PHP 5.3? Задайте задание PHP cron на сервере Windows 2003 php mysql_connect Предупреждение отключено Отдельный процесс php останавливает весь сайт

Быстрый способ найти самый большой массив в многомерном массиве?

Ситуация: У меня многомерный массив с переменным числом элементов. например 

array(N) { 0 => array(3) { ... }, 1 => array(8) { ... }, 2 => array(1) { ... }, ... M => array(12) { ... }, ... N-1 => array(7) { ... } }

И я хотел бы найти максимальное количество элементов в этом под-массиве (в приведенном выше примере это будет 12). Прямым решением будет линейный поиск O (N). 

 <?php function max_length($2d_array) { $max = 0; foreach($2d_array as $child) { if(count($child) > $max) { $max = count($child); } } return $max; }

Тем не менее, я не могу не задаться вопросом, есть ли какой-то умный трюк, чтобы оптимизировать этот поиск. Таким образом, мой вопрос – двухпартийный (хотя ответ на любую из частей решал бы его):

  • Существует ли алгоритм, который выполняет этот поиск быстрее, чем O (N), не требуя особых требований (предварительно отсортированный и т. Д.)?
  • Есть ли где-то скрытая функция PHP, которая будет выполнять этот поиск в собственном коде, а не в PHP-скрипте userland?

Не уверен в производительности, но я думаю, что следующее должно работать: 

 $count = array_map('count', $input_arr); $min = array_keys($count , max($count))[0]; $largest_arr = $input_arr[$min];

Или даже: 

 $counts = array_map('count', $input_arr); $key = array_flip($counts)[max($counts)]; $largest_arr = $input_arr[$key]; 
 $max = 0; foreach($array as $obj) { if($obj->dnum > $max) { $max = $obj->dnum; } }

или 

 $numbers = array(); foreach($array as $obj) { $numbers[] = $obj->dnum; } $max = max($numbers);

или …

Подробнее в этой статье. Получить максимальное значение из элемента в многомерном массиве? или Как найти самый большой массив из многомерного массива

1) Сортируйте многодисковый массив по размерам элементов:
Выберите алгоритм, который выполняется в O (n logn) в худшем случае, например Heap Sort ( сравнение алгоритмов сортировки ).

2) Выберите последний элемент.
Это выполняется в O (1)

Поэтому, если вы сами реализуете алгоритм сортировки и считаете, что выборка длины массива равна O (1), а не линейной (без подсчета каждый раз, когда вы запрашиваете длину), вы можете сделать это в O (n logn)

Я не могу комментировать какие-либо PHP-методы, которые делают это для вас, так как я не использую его.

Просто для удовольствия: 

 array_multisort($result = array_map('count', $array), SORT_DESC); echo $result[0];

Как насчет этого: 

 function accmp(&$a, &$b) { return count($a)<count($b)?-1:1; } $arraylist=array(array(1,2),array(1,2,3),array(1),array(1,2,3,4,5,6),array(1,2,3,4),array(2,3,4)); echo 'original arraylist:<br>'; print_r($arraylist); echo '<br>'; usort($arraylist,'accmp'); echo 'largest array::<br>'; print_r(end($arraylist)); echo '<br>'; echo 'largest size = '.count(end($arraylist))

Просто отсортируйте массив-элемент в arraylist в порядке возрастания count (array-element) и возьмите последний элемент.

Хорошо, @DefuseSec в Twitter сказал следующее:

https://twitter.com/DefuseSec/status/435842054195671040

Я склонен полагать, что это ответ на этот вопрос.