PHP array_slice vs python for splitting arrays

Question

Some background

I had a general call to "MaxProfit". This basically happens as follows:

For the zero index of array A, consisting of N integers containing daily stock prices for a period of N consecutive days, the maximum possible profit from one transaction for this period is returned.

I was very pleased with this PHP algorithm that I came up with, avoiding 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, after testing my solution, it seems to work poorly in performance, perhaps even in O (n ² ).

I read the topic a bit and found a very similar python solution. Python has some fairly convenient array capabilities that allow you to split an array with a[s : e] syntax, unlike PHP, where I used the array_slice function. I decided that this should be a bottleneck, so I did some tests:

Test

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 array_slice() about 20 times less efficient than Python?
• Is there an equivalent efficient method in PHP that achieves the above and hopefully makes my maxProfit algorithm run in O (N) time? Change I understand that my implementation above is not really O (N), but my question is still about the efficiency of section arrays.

Answer 1

• I really don't know, but PHP arrays are mixed up with hybrid monsters, maybe that's why. Python is really lists, not dictionaries, so they can be simpler and faster because of this.
• Yes, make the actual decision O (n). Your solution is not just slow because the PHP slice is apparently slow, it is slow because you obviously have an O (n ^ 2) algorithm. Just go through the array once, track the minimum price found so far, and check it with the current price. Not something like max over half the array in each individual iteration of the loop.