提高CPU密集型PHP脚本的性能

Question

我有一个PHP脚本,需要几个小时(可能是几天)才能执行.它非常简单,但是CPU密集型,大部分执行时间花在了(我可以在分析脚本后告诉):

1. $array = explode(',', $a[$i]); where $a[$i]是一个非常长的字符串,表示由逗号分隔的30k元素的向量

2. foreach($array as $key => $value)循环; 对于每个循环,执行一些in_array()以及比较和赋值操作

$a实际上是一个非常大的稀疏矩阵(30k*30k),但我无法将其保留在内存中(8GB似乎没有足够的RAM)所以我只保留一个"稀疏表示"(基本上每行都是一个字符串)并使用explode()任何时候我需要连续工作.

我知道用C(或其他语言)重写所有内容会提高性能(多少？)但是,在这之前我想知道我是否可以做任何事情来改善PHP的执行时间.

编辑后回答.

我尝试了几条你的建议,这是我的报告:

1)str_getcsv在大多数情况下比爆炸慢

2)SPLFixedArray减少了存储矩阵所需的内存,但是对于30k x 30k的矩阵来说,8GB是不够的,所以我认为它不会有多大帮助; 这里真正的问题是我认为PHP中缺少矩阵的稀疏表示

3)我无法存储爆炸操作的所有结果,因为这仍然意味着将整个矩阵保留在内存中(没有足够的RAM)

4)我已经尝试过数据库方法,即使我确定它会更慢:我已经存储了三元组(i,j,value)来表示每个矩阵元素; 甚至删除不太重要的值(我可以牺牲小于阈值的值并获得不太精确的结果,但仍然有用)并且只存储了1800万个元组,使用mysql myisam的方法比我在内存中的数组方法慢得多.

5)我尝试了使用MEMORY引擎(RAM中的mysql表)的数据库方法并存储除零值为零的所有矩阵元素; 这次有4200万条记录...它更快,不是一个数量级,但快2-4倍......我想我可以在5天而不是15-20完成工作......它仍然太多了(我想在24小时内完成),如果您有任何其他建议,欢迎您

编辑2:我解释了这个问题

我会提供一些关于这个问题的细节,我真的需要简化一切,否则解释起来会太长,但我认为这足以让他们更好地了解情况.

我有一个矩阵表示节点之间的距离; 整数中的距离也可以是无限的.

我有一个内存表,用三元组表示每个距离:node_1,node_2,distance(仅表示非无限距离).

我有这种贪婪的算法,我没有写,我应该优化在具有8GB RAM的笔记本电脑上在可行的时间(比如说不到一天)执行它.

算法基本上进入输入两个节点,并根据必须在每个步骤验证的以下两个属性逐步设计起始节点和结束节点之间的路径:

• 必须在相对于当前节点更靠近结束节点的节点集中选择新的中间节点
• 在这些节点中,选择更接近当前节点的节点

请考虑1)不满足三角不等式.2)这不是最短的路径问题

这是我多次调用的函数的伪代码,直到我足够接近结束节点:

get_next_node($node_1, $node_2){

    $dist = select distance from distances_table where node_2 = $node_2 and node_1 = $node_1

    $candidates_ar = select node_1 from distances_table where node_2 = $node_2 and distance < $dist

    $distances_ar = select distance from distances_table where node_1 = $node_1 and node_2 in ($candidates_ar) // e.g. $distances_ar[12] contains distance between node 12 and $node_1

    $min = 1000;
    foreach ($candidates_ar as $value){
        if ($distances_ar[$value] < $min){
            $min = $distances_ar[$value]
            $next_node = $value
        }
    }

}

我省略了很多检查和额外的复杂性,但这是基本的,这是算法花费大部分时间的地方.

我想它可以通过A*的实现来解决,但我想避免它,如果有可能提高性能,以便我可以在几小时(而不是几天)执行它.

谢谢.

Answer 1

好的,你有性能问题.现在有趣的部分开始了.

第一步,是不要猜测.不要在C中开始重写.不要切换PHP编译器.这是吸盘的.相反,首先尝试找到实际的瓶颈.

获取XDEBUG并生成应用程序的cachegrind概要分析.这将显示大部分时间花在哪里.

您也可以使用xhprof.

关键是,不要猜测,但是配置文件.找到算法的慢速部分,然后进行优化.

问题可能不是代码,而是您正在使用的算法.我建议尝试将算法形式化,以便您可以尝试针对特定约束优化和调整部件.

例如.现在,您正在解析大型CSV字符串.为什么？为什么不把它放在数据库中让数据库为你做繁重的工作呢？显然,对于您的特定用例可能无法实现,但每当我看到人们在PHP中使用30k元素的数组操作时,通常是因为他们正在做一些他们不应该首先做的事情.

如果所有其他方法都失败了,请尝试将算法分块,以便您可以部分运行它.这样你就可以尝试使用map-reduce或类似技术来调整运行时.

简而言之,这实际上取决于你究竟在做什么.但重新编码或切换运行时将是我的最后手段,而不是第一步......