PHP array_slice 与 Python 的拆分数组

Question

一些背景

我正在参加常见的“MaxProfit”编程挑战。它基本上是这样的:

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.

我对我提出的这个 PHP 算法非常满意，它避免了天真的暴力尝试:

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;
}

但是，在测试我的解决方案后，它似乎在性能方面表现不佳，甚至可能在 O(n²) 时间内。

我围绕这个主题做了一些阅读，发现了一个非常相似的 python 解决方案。 Python 有一些非常方便的数组功能，允许使用 a[s : e] 语法拆分数组，这与我在 PHP 中使用 array_slice 函数不同。我认为这一定是瓶颈，所以我做了一些测试:

测试

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;

结果:

$ 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))

结果:

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

问题

1. 为什么 PHP 的 array_slice() 效率比 Python 低 20 倍左右？
2. 在 PHP 中是否有一种等效的有效方法可以实现上述目标，从而有望使我的 maxProfit 算法在 O(N) 时间内运行？ 编辑 我意识到我上面的实现实际上不是 O(N)，但我的问题仍然是关于切片数组的效率。

Answer 1

1. 我真的不知道，但 PHP 的数组是困惑的混合怪物，也许这就是原因。 Python 的列表实际上只是列表，而不是同时的字典，因此它们可能更简单/更快。
2. 是的，做一个实际的 O(n) 解决方案。您的解决方案不仅慢，因为 PHP 的切片显然很慢，而且很慢，因为您显然有一个 O(n^2) 算法。只需遍历数组一次，跟踪目前找到的最低价格，并与当前价格核对。不是像 max 这样的东西在每个循环迭代中超过数组的一半。