PHP 数组性能 [英] PHP array performance

问题描述

我正在测试一种二维装箱算法，我选择了 PHP 来模拟它，因为它是我现在的基本语言.

I'm testing an algorithm for 2d bin packing and I've chosen PHP to mock it up as it's my bread-and-butter language nowadays.

正如您在 http://themworks.com/pack_v0.2 上看到的/oopack.php?ol=1 它工作得很好，但是您需要等待大约 10-20 秒才能打包 100 个矩形.对于一些难以处理的集合，它会达到 php 的 30 秒运行时限制.

As you can see on http://themworks.com/pack_v0.2/oopack.php?ol=1 it works pretty well, but you need to wait around 10-20 seconds for 100 rectangles to pack. For some hard to handle sets it would hit the php's 30s runtime limit.

我做了一些分析，它表明我的脚本大部分时间都经过一个包含 0 和 1 的小型二维数组的不同部分.它要么检查某个单元格是否等于 0/1，要么将其设置为 0/1.它可以执行数百万次这样的操作，每次只需要几微秒.

I did some profiling and it shows that most of the time my script goes through different parts of a small 2d array with 0's and 1's in it. It either checks if certain cell equals to 0/1 or sets it to 0/1. It can do such operations million times and each times it takes few microseconds.

我想我可以在静态类型语言中使用布尔数组，而且速度会更快.或者甚至制作一个 1 位值的数组.我正在考虑将整个内容转换为某种编译语言.PHP 不适合它吗?

I guess I could use an array of booleans in a statically typed language and things would be faster. Or even make an array of 1 bit values. I'm thinking of converting the whole thing to some compiled language. Is PHP just not good for it?

如果我确实需要将其转换为 C++，那么自动转换器有多好?我的脚本只是很多带有基本数组和对象操作的 for 循环.

If I do need to convert it to let's say C++, how good are the automatic converters? My script is just a lot of for loops with basic arrays and objects manipulations.

编辑.这个函数被调用的次数比任何其他函数都多.它读取一个非常简单的对象的几个属性，并通过一个很小的数组的很小一部分来检查是否有任何不等于 0 的元素.

Edit. This function gets called more than any other. It reads few properties of a very simple object, and goes through a very small part of a smallish array to check if there's any element not equal to 0.

function fits($bin, $w, $h, $x, $y) {

    $w += $x;
    $h += $y;

    for ($i = $x; $i < $w; $i++) {

        for ($j = $y; $j < $h; $j++) {

            if ($bin[$i][$j] !== 0) {
                return false;
            }
        }
    }

    return true;    
}

更新:我尝试使用一维数组而不是二维数组作为建议的答案之一.由于我需要始终可以访问当前的 bin 宽度，因此我决定将所有内容都包装在对象中.此外，现在在每个循环中都需要计算索引.现在脚本需要更多时间来运行.其他技术并没有带来太多的性能提升，反而降低了代码的可读性.我猜是 HipHop 的时间了.

Update: I've tried using 1d array instead of 2d as one of the answers suggested. Since I needed to always have current bin width accessible, I decided to wrap everything in the object. Also, now in every loop the index needs to be calculated. Now the script takes even more time to run. Other techniques didn't bring much performance boost, rather made code less readable. Time for HipHop I guess.

更新:由于 hiphop php 只能在 linux 上运行，而我没有，所以我决定用 C++ 重写整个内容.更新旧技能是很好的.此外，如果我确实找到了一种使用 hiphop 的方法，比较手写的 C++ 代码和 hiphop 生成的代码会很有趣.

Update: since hiphop php only runs on linux, and I don't have one, I've decided to rewrite the whole thing in C++. It's nice to freshen up the old skills. Also, if I do find a way to use hiphop, it'll be interesting to compare hand-written C++ code and the one hiphop would generate.

更新:我用 C++ 重写了这个东西，平均它的运行速度提高了 20 倍，并且使用的内存更少.让我看看我能不能让它更快.

Update: I rewrote this thing in c++, on average it works 20 times faster and uses much less memory. Let me see if I can make it even faster.

推荐答案

PHP 中的数组访问肯定会很慢.PHP 使用哈希表来实现数组，即为了访问数组中的元素，它必须计算哈希并遍历链表.使用带有真实数组的编译语言肯定会提高性能，因为可以直接访问内存.感兴趣的人:带有字符串的哈希访问和带整数.

Array access in PHP can certainly be slow. PHP uses hash tables to implement arrays, i.e. in order to access an element in an array it has to calculate a hash and traverse a linked list. Using a compiled language with real arrays will definitely improve performance, because there a direct memory access is made. For the interested: Code for hash access with string and with integer.

关于你的代码，有几点我会优化:

Concerning your code, there are several points I would optimize:

• return 直接返回，不要break两次.
• 将 $file->get_width() 和 $file->get_height 放入简单变量中.我假设高度或宽度在整个过程中不会改变.请记住:PHP 中的函数很慢.
• 使用一维数组，而不是嵌套数组.这样每次迭代就可以节省一次哈希查找. 实际上一维数组只是稍微快一点，甚至稍微慢一点.几种保存性能和内存使用数据的方法比较.

• return directly, don't break twice.
• put $file->get_width() and $file->get_height into simple variables. I assume that the height or width doesn't change throughout the process. Remember: Functions in PHP are slow.
• Use a one-dimensional array, instead of nested arrays. You save one hash lookup per iteration that way. Actually a one-dimensional array is only marginally faster or even slightly slower. Comparison of several ways of saving the data concerning performance and memory usage.

.

function fits($bin, $x, $y, $w, $h) {
    $w += $x;
    $h += $y;

    for ($i = $x; $i < $w; ++$i) {
        for ($j = $y; $j < $h; ++$j) {
            if ($bin[$i][$j] !== 0) {
                return false;
            }
        } 
    }

    return true;   
}

虽然我不确定，为什么您将 $x 添加到 $width/$y 到 $height.不是要从当前坐标迭代到图像边界吗?

Though I'm not sure, why you add $x to the $width / $y to the $height. Don't you want to iterate from the current coordinates to the image boundaries?

这篇关于PHP 数组性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！