PHP的usort真的很慢吗？还是我做错了什么？

Question

我有一个数组（实际上是PHP数组...虽然不是真正的数组，但你懂我的意思），其中包含代表短信的对象。这些对象中的一个字段是DateTime类型，我想按照该字段对数组进行排序。我无法在数据库中对数据进行排序，因为我从无法更改的Web服务中接收到它，所以请不要建议我这样做。我使用以下代码片段对数组进行排序：

usort($smsMessages, function ($a, $b) { 
    if ($a->SendTime == $b->SendTime) {
        return 0;
    }

    return ($a->SendTime < $b->SendTime) ? -1 : 1;
});

这样做可以排序 30,000 个元素，但需要160秒。

我知道 php 慢，但这太离谱了。我写的有什么问题吗？usort是不是已知慢/有缺陷/有bug？应该使用另一种方法吗？还是自己写实现？

- Davor

---

你在抱怨排序三万个元素？ - u_mulder

在第四代 i7 处理器上，针对 3 万个元素，您的代码需要大约 1.3 秒。 - Axalix

@u_mulder - 我在抱怨排序30k个糟糕元素需要160秒的时间。 - Davor

@frz3993 - 不，从服务获取数据不到1秒钟。我专门为这个块测量了时间，诚然，使用了microtime调用，但由于服务器其他方面没有占用，这真的不是问题。排序块是问题所在。 - Davor

@JeremyJackson - 是啊，我可以把它排序。 - Davor

Answer 1

我有同样的问题。我们需要对2-10百万个数组进行排序。每个数组包含约30个字段（字符串、整数和NULL值）。第一个字段是用于排序的唯一整数。

我们使用的是PHP 7.1。

在AWS EC2 r4.large上，对2028830个项目进行排序需要4710秒（=78.5分钟）。

我们的代码如下：

usort($this->rows, function ($item1, $item2) {
        return $item1[0] <=> $item2[0];
});

然后我发现用 $rows 替换 $this->rows 后，速度提高了近4倍：

usort($rows, function ($item1, $item2) {
        return $item1[0] <=> $item2[0];
});

它将执行时间从4710秒降至1195秒。

另一种方法是使用 Min Heap 替代普通的 PHP 数组 [] 来处理 $this->rows。这样可以获得大约相同的性能提升。在这种情况下，您根本不需要使用 usort。

最终结论： 1. 是的，即使进行了上述更改，执行时间仍然惊人地长。 2. 对于已排序数组，usort 比 MinHeap 更快。

- Sergey Rud

Answer 2

你可以尝试加速上面的代码，看看排序是否真的是瓶颈。你可以试着使用全局函数，并缩短代码来加速它（声明：这是大量微小优化，这可能不是你问题所在的地方！）就像这样：

function sort_function($a, $b){
 $a = $a->SendTime;
 $b = $b->SendTime;
 if ($a == $b) return 0;
 return ($a < $b) ? -1 : 1;
}

usort($smsMessages,'sort_function');

假设SendTimes大多数不相等，这实际上应该加速事情的进行。但请理解，以上只是一个非常轻微的加速。如果您实际上看到的是像140秒这样的东西，则可以归咎于usort。然而很可能，上述建议对您的价值在于学习我认为事情的usort部分不是您的问题。在下面更多的输入后添加：
在很可能已经学会这一切都关乎内存（您发布的使用数字是关于系统整体的，我不能推断出这些256MB中有多少实际上被使用，除非对这些对象有更多了解：）），对于您来说，此代码在运行时如何比较？

$dates = array();
foreach ($smsMessages as $key => $obj) {
    $dates[$key] = $obj->SendTime;
}

asort($dates);
$dates = array_keys($dates);
$sorted = array();
foreach ($dates as $key) {
    $sorted[] = &$smsMessages[$key];
}

这段代码需要的内存应该会显著减少，因为它并没有在大数组上使用隐式的foreach循环，而是只在数组键值上进行循环。

- Armin Braun

---

你的代码在i7（第四代）上，处理30k个元素需要约0.5秒。 - Axalix

至少我显然知道如何进行微优化:D 让我们看看这些160会发生什么:P - Armin Braun

是的，它降到了152秒 :) @u_mulder - 是的，这些对象有额外的sms_text、sender和recipient字段。这些字段都不用于排序，并且不应该对排序速度产生影响。在30k个元素上的内存使用也可以忽略不计。 - Davor

这实际上可能意味着缺少RAM。我将添加代码，以便在这种情况下可以更快地运行，大约需要20分钟，稍后回来。 - Armin Braun

@ArminBraun - 我从/proc/meminfo获取了以下统计数据：'MemTotal: 8075928 kB'，'MemFree: 3026172 kB'，'MemAvailable: 6652156 kB'，并从phpinfo()中获取了memory_limit 256M。 - Davor

Answer 3

尝试这个：

首先，将“true”作为第二个参数添加到json_decode中，这样您将获得一个关联数组而不是对象数组。 （我还建议尝试使用此方法加速JSON：https://github.com/RustJason/php-rapidjson - 不过需要PHP7）

然后：

$sentTime = [];
foreach ($smsMessages as $key => $element) {
    $sentTime[$key] = strtotime($element['sent']);
}
array_multisort($sentTime, SORT_DESC, $smsMessages);

（我的电脑上为0.19秒。）

您可以使用(object)$smsMessage或使用自己/定制的方法，在实际需要时将一些$smsMessages转换为对象。

- Axalix

---

我正在按时间戳对日志条目的数组进行排序（范围从20到150000个条目），这种方法（首先从每个条目中提取排序键，然后使用array_multisort）比usort（）快得多！感谢您！ - Tomas Creemers