Quick Way to Find the Largest Array in a Multidimensional Array?

Question

Situation: I have a multidimensional array with a variable number of elements. e.g.

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

And I would like to find the maximum number of elements in this sub-array (in the example above, it would be 12). A straightforward solution would be an O(N) linear search.

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

However, I can't help but wonder if there's some clever trick to optimize this lookup. So my question is a two-parter (though an answer to either part would solve it):

Is there an algorithm that performs this search faster than O(N) without requiring special requirements (pre-sorted, etc)?
Is there an obscure PHP function somewhere that will perform this search in native code rather than my userland PHP script?

Ravi B · Accepted Answer · 2019-09-16 12:23:56Z

7

You can use this : https://www.php.net/manual/ro/function.max.php

$test = array(
           array('G', 'M', 2, 2),
           array(1, 2222, 3)
         );
 $arr = max($test);

// output ->

array(4) {
  [0]=>
  string(1) "G"
  [1]=>
  string(1) "M"
  [2]=>
  int(2)
  [3]=>
  int(2)
}

edited Sep 16, 2019 at 12:23

Ravi B

1,5922 gold badges16 silver badges32 bronze badges

answered Sep 16, 2019 at 11:20

Marian

861 silver badge2 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Scott Arciszewski Over a year ago

That's a neat, unexpected, yet documented behavior for max().

Amal · Accepted Answer · 2014-02-18 18:04:10Z

4

Not sure about the performance, but I think the following should work:

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

Or even:

$counts = array_map('count', $input_arr);
$key = array_flip($counts)[max($counts)];
$largest_arr = $input_arr[$key];

answered Feb 18, 2014 at 18:04

Amal

76.8k18 gold badges133 silver badges154 bronze badges

5 Comments

Amal Over a year ago

@Scott: Did you see the second solution? (the first part of the answer)

Scott Arciszewski Over a year ago

gist.github.com/sarciszewski/9076834 I saw it, hadn't benchmarked it until just now.

Amal Over a year ago

@Scott: Those are the same. The only difference between both the gists are in the line $key = array_flip($counts)[max($counts)];. I just shortened it to include in a single line. The one I'm talking about is this one: $min = array_keys($count , max($count))[0];

Amal Over a year ago

@Scott: Well, you have to do it for more than 1000 to get some stable results. Here's my version (with 100000 iterations): gist.github.com/amalmurali47/9077238

Amal Over a year ago

let us continue this discussion in chat

runDOSrun · Accepted Answer · 2014-02-18 18:15:33Z

2

1) Sort the multi-dim array by the element sizes:
Choose an algorithm that runs in O(n logn) worst case, e.g. Heap Sort (comparison of sorting algorithms).

2) Choose the last element.
This runs in O(1)

So if you implement the sorting algorithm yourself and assuming that fetching the array length is O(1) and not linear (no counting every time you ask for the length), you can do it in O(n logn)

I can't comment on any PHP methods which do this for you since I'm not using it.

answered Feb 18, 2014 at 18:15

runDOSrun

11.1k7 gold badges50 silver badges60 bronze badges

3 Comments

Scott Arciszewski Over a year ago

Strictly speaking, N log N is worse than N: 1000 * lg(1000) is just below 10,000. I appreciate the effort though

runDOSrun Over a year ago

If there is a sorting algorithm that performs better than O(n), then that's your solution. I posted this answer with O(n logn) since this is currently the best bound known for comparing sorting algorithms. So it can't be faster than this unless you find a way to sort it non-comparingly without reencoding the array into a numeric representation (which seems impossible to me).

Scott Arciszewski Over a year ago

Well, if the data is sorted, getting O(1) is trivial; that's why I specified "without requiring special requirements (pre-sorted, etc)". Sorting is expensive. Thanks for your answer, though; if I had a requirement to sort the data shortest-to-longest, heap-sort would probably help significantly ;)

AbraCadaver · Accepted Answer · 2014-02-18 19:17:10Z

1

Just for fun:

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

edited Feb 18, 2014 at 19:17

answered Feb 18, 2014 at 18:24

AbraCadaver

79.2k7 gold badges75 silver badges91 bronze badges

5 Comments

Scott Arciszewski Over a year ago

Heh. Naive solution: Result 44 calculated in 0.049926996231079 seconds. Stack Overflow: Result 44 calculated in 0.13289713859558 seconds.

AbraCadaver Over a year ago

@Scott: I don't know what that means. Also, array_multisort returns boolean so no array_shift.

Scott Arciszewski Over a year ago

I was benchmarking it. It took ~3x as long as the naive approach. You could use return array_shift($result); in a function call context.

AbraCadaver Over a year ago

Yes, mine is "Just for fun" approach :0

Scott Arciszewski Over a year ago

Yeah, it was a fun solution to the problem. But for the sake of fairness, I benchmarked it. ;)

Community · Accepted Answer · 2017-05-23 11:54:37Z

0

$max = 0;
foreach($array as $obj)
{
    if($obj->dnum > $max)
    {
        $max = $obj->dnum;
    }
}

or

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

or ...

Read more in that article - Get the maximum value from an element in a multidimensional array? or How to find the largest array from a multi dimensional array

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Feb 18, 2014 at 18:07

TN888

7,7499 gold badges52 silver badges85 bronze badges

1 Comment

Scott Arciszewski Over a year ago

Sadly, we don't have a $obj->dnum to compare, so this solution wouldn't work.

Scott Chu · Accepted Answer · 2016-10-20 13:02:16Z

0

How about this:

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))

Just sort array-element in arraylist in ascending order of count(array-element) and take last element.

answered Oct 20, 2016 at 13:02

Scott Chu

1,00015 silver badges28 bronze badges

Collectives™ on Stack Overflow

Quick Way to Find the Largest Array in a Multidimensional Array?

6 Answers 6

1 Comment

5 Comments

3 Comments

5 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

5 Comments

3 Comments

5 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related