PHP's array_slice vs Python's splitting arrays

Question

Some background

I was having a go at the common "MaxProfit" programming challenge. It basically goes like this:

Given a zero-indexed array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period.

I was quite pleased with this PHP algorithm I came up, having avoided the naive brute-force attempt:

public function maxProfit($prices)
{
    $maxProfit = 0;
    $key = 0;
    $n = count($prices);

    while ($key < $n - 1) {
        $buyPrice = $prices[$key];
        $maxFuturePrice = max( array_slice($prices, $key+1) );          
        $profit = $maxFuturePrice - $buyPrice;
        
        if ($profit > $maxProfit) $maxProfit = $profit;
        $key++;
    }
    return $maxProfit;
}

However, having tested my solution it seems to perform badly performance-wise, perhaps even in O(n²) time.

I did a bit of reading around the subject and discovered a very similar python solution. Python has some quite handy array abilities which allow splitting an array with a a[s : e] syntax, unlike in PHP where I used the array_slice function. I decided this must be the bottleneck so I did some tests:

Tests

PHP array_slice()

$n = 10000;    
$a = range(0,$n);

$start = microtime(1);
foreach ($a as $key => $elem) {
    $subArray = array_slice($a, $key);
}
$end = microtime(1);

echo sprintf("Time taken: %sms", round(1000 * ($end - $start), 4)) . PHP_EOL;

Results:

$ php phpSlice.php
Time taken: 4473.9199ms
Time taken: 4474.633ms
Time taken: 4499.434ms

Python a[s : e]

import time

n = 10000
a = range(0, n)

start = time.time()
for key, elem in enumerate(a):
    subArray = a[key : ]
end = time.time()

print "Time taken: {0}ms".format(round(1000 * (end - start), 4))

Results:

$ python pySlice.py 
Time taken: 213.202ms
Time taken: 212.198ms
Time taken: 215.7381ms
Time taken: 213.8121ms

Question

Why is PHP's array_slice() around 20x less efficient than Python?
Is there an equivalently efficient method in PHP that achieves the above and thus hopefully makes my maxProfit algorithm run in O(N) time? Edit I realise my implementation above is not actually O(N), but my question still stands regarding the efficiency of slicing arrays.

According to this: http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions it would be faster if you specify a length. (Python does it implicitly for you [key:-1]) — Maresh, May 29 '15 at 12:34
Big-O notation doesn't have anything to do with implementation specifics. It says how long the output takes to compute relative to the size of the input. It doesn't say how many milliseconds your concrete implementation is running. Your algorithm will still be O(n²) regardless of how fast the language you write it in is. — deceze, May 29 '15 at 12:49
I agree completely, however my original question arose as it seemed to me that the `array_slice()` function itself runs in O(N) time (which causes my implementation to be O(N²)) whilst Python's `a[s:e]` runs in O(1) time. But this may well be wrong and I'd have to do further testing to check this/someone more knowledgable than me can enlighten. — harryg, May 29 '15 at 14:32
Python's `a[s:e]` is O(N) as well (N being the size of the slice), as it creates a copy of that slice. Do your test again with n=100000 (that's 10 times your old n) and you'll see it takes about 100 times longer, not 10 times. — Stefan Pochmann, May 29 '15 at 15:53
Fast `O(N)` Python solution: `from itertools import accumulate; from operator import sub; max(map(sub, stocks, accumulate(stocks, min)))`. — Veedrac, May 29 '15 at 17:06

score 4 · Answer 1 · answered May 29 '15 at 12:30

I don't really know, but PHP's arrays are messed up hybrid monsters, maybe that's why. Python's lists are really just lists, not at the same time dictionaries, so they might be simpler/faster because of that.
Yes, do an actual O(n) solution. Your solution isn't just slow because PHP's slicing is apparently slow, it's slow because you obviously have an O(n^2) algorithm. Just walk over the array once, keep track of the minimum price found so far, and check it with the current price. Not something like max over half the array in every single loop iteration.

Ah, yes. The proper dynamic programming method is clearly the best and doesn't involve slicing the array each time. — harryg, May 29 '15 at 12:32

PHP's array_slice vs Python's splitting arrays

Some background

Tests

Question

1 Answers1