Will foreach become inefficient when number of array elements grow big?

Question

Currently I'm using foreach to search key when use array_replace:

$grades = array(
               0 =>array('id'=>1, 'grade'=>4),
               1 =>array('id'=>5, 'grade'=>2), 
               2 =>array('id'=>17,'grade'=>1),
             )
$replacement = array('id'=>17,'grade'=>3);

foreach($grades as $key=>$grade){
    if($grade->id ==$replacement['id'] )
       $found = $key;
}
$new_grades = array_replace($grades, array($found_key=>$replacement));

I wonder if this will become inefficient when the number of elements grow too much in $grades array. Is there any better way to do the search and replace job?

...you never do anything with `$found`? – Matt Aug 16 '12 at 14:58 — Matt, Aug 16 '12 at 14:58
no, I don't need to do anything with $found – Jenny Aug 16 '12 at 14:58 — Jenny, Aug 16 '12 at 14:58
What does the `foreach` do then? – Matt Aug 16 '12 at 14:59 — Matt, Aug 16 '12 at 14:59
if without foreach, how can I find which key to replace? – Jenny Aug 16 '12 at 14:59 — Jenny, Aug 16 '12 at 14:59
The answers below are what you're looking for. – Matt Aug 16 '12 at 15:00 — Matt, Aug 16 '12 at 15:00

score 5 · Accepted Answer · edited May 23 '17 at 12:04

5

The execution time grows linearly with the number of elements in the array (O(N)). Use a better data structure, i.e. use the array in an associative way with the ID as index:

$grades = array(
    1 => array('grade'=>4),
    5 => array('grade'=>2), 
    17 => array('grade'=>1)
);

Then the lookup cost is constant (O(1)). You can do:

$grades[$replacement['id']] = array('grade' => $replacement['grade']);

or something similar, depending on your data.

edited May 23 '17 at 12:04

Community

1
1

answered Aug 16 '12 at 14:59

Felix Kling

795,719
175
1,089
1,143

Thanks! The id is not just array index, each id is an unique identity of one assignment. it is wildly called whenever anything need to work with this assignment. Is it ok to use the id as array key? – Jenny Aug 16 '12 at 15:13
Yes of course. Everything that can uniquely identify something is usable as index/key. – Felix Kling Aug 16 '12 at 15:22
Thanks! I will re-prepare my data. – Jenny Aug 16 '12 at 15:25

score 4 · Answer 2 · answered Aug 16 '12 at 14:59

4

Yeah, that can be done vastly more efficiently.

$grades = array(
    1   => 4,
    5   => 2,
    17  => 1,
);
$replacement = array(
    17  => 3,
);
$grades = array_merge($grades, $replacement);

If you need more information associated with the ID than just the grade, then you'll still need a more involved data structure like Felix Kling has. But no such requirement is present in your question so I'm not assuming it.

answered Aug 16 '12 at 14:59

chaos

122,029
33
303
309

Thanks! I just commented on Felix's answer--I do have many other things associated with the ID. I'm not sure if it is a good idea to use it as array key? – Jenny Aug 16 '12 at 15:15
@Jenny: Okay, then you'll want something like he wrote. As long as the ID is unique and can be represented as a string, it's fine to use as an array key. – chaos Aug 16 '12 at 17:51

Will foreach become inefficient when number of array elements grow big?

2 Answers2