Selecting every nth item from an array

Question

What would be the most efficient way to select every nth item from a large array? Is there a 'smart' way to do it or is looping the only way?

Some points to consider:

• The array is quite large with 130 000 items
• I have to select every 205th item
• The items are not numerically indexed, so for($i = 0; $i <= 130000; $i += 205) won't work

So far, this is the most efficient method I've come up with:

$result = array();
$i = 0;
foreach($source as $value) {

    if($i >= 205) {
        $i = 0;
    }

    if($i == 0) {
        $result[] = $value;
    }

    $i++;
}

Or the same with modulo:

$result = array();
$i = 0;
foreach($source as $value) {
    if($i % 205 == 0) {
        $result[] = $value;
    }
    $i++;
}

These methods can be quite slow, is there any way to improve? Or am I just splitting hairs here?

EDIT

Good answers all around with proper explanations, tried to pick the most fitting as the accepted answer. Thanks!

Answer 1

i recommend to use array_slice

$count = count($array) ;
for($i=205;$i<$count;$i+=205){
    $result[] = array_slice($array,$i,1);
}

Answer 2

You can't move the array pointer, it seems, more than once at a time. I would personally use this:

reset($source);
$next = true;
while($next === true){
    $result[] = current($source);
    for(i=0;i<205;i++){
        $next = next($source);
    }
}

If someone can find a function that can move the array pointer more than just one step at a time, you will have a better answer. I think this is good though.

Answer 3

Try ArrayIterator::seek()

Also, using one the new Spl datastructures might yield better results than using plain arrays.

Answer 4

If this really is a bottleneck, you might want to consider rethinking your design in order to make it numerically indexed.

EDIT: Or create and maintain a seperate array with just the 205th items (which gets updated at insert or something like that).

Answer 5

You could use array_keys to work only on the array keys.

$keys = array_keys($array);
for ($i=0, $n=min(count($keys), 130000); $i<$n; $i += 205) {
    $result[] = $array[$keys[$i]];
}

Answer 6

A foreach loop provides the fastest iteration over your large array based on comparison testing. I'd stick with something similar to what you have unless somebody wishes to solve the problem with loop unrolling.

This answer should run quicker.

$result = array();
$i = 0;
foreach($source as $value) {
    if ($i++ % 205 == 0) {
        $result[] = $value;
    }
}

I don't have time to test, but you might be able to use a variation of @haim's solution if you first numerically index the array. It's worth trying to see if you can receive any gains over my previous solution:

$result = array();
$source = array_values($source);
$count = count($source);
for($i = 0; $i < $count; $i += 205) {
    $result[] = $source[$i];
}

This would largely depend on how optimized the function array_values is. It could very well perform horribly.

Answer 7

I think the solution to this problem doesn't lie in any PHP syntax but in the design of your code.

You could either make the array numerically indexed (might not be plausible for your application), keep track of every 205th item, or only search the array once (cache a list of each 205th item).

In my mind, keeping track of each 205th item would be easier to implement. You'd just keep a count of all the items in a database or something, and every time an item is added, check the modulo of the count. If you have another 205th item, add it to the array. For when items are deleted though, this would be trickier. You might have to re-check the entire array to realign all your 205th items.

Doing this would be simpler if you could start at the deleted item and move forward, but again this would only work for numerically indexed arrays -- and if that were true, you wouldn't have to move forward at all, you would just do a little maths to re-figure it out.

• Numerical indexes -- better long-term solution but harder to implement
• Keeping track -- easier to implement, but you'd have to get dirty again when you delete items
• Caching items -- you should probably do this for the other two solutions as well, but on its own, it would be fast until the array were modified, in which case you would probably have to re-do it.

Answer 8

• Create a two dimentional array [205][N]
• Load data into array
• Access 205th element for every N

May sound silly but by definition it is fastest since you access memory locations directly and do not perform any comparisons.