vendredi 29 mai 2015

PHP's array_slice vs Python's splitting arrays

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

  1. Why is PHP's array_slice() around 20x less efficient than Python?
  2. Is there an equivalently efficient method in PHP that achieves the above and thus hopefully makes my maxProfit algorithm run in O(N) time?

Aucun commentaire:

Enregistrer un commentaire