分類: 未分類

我還以為 PHP SPL 的類別應該實作上應該有比較嚴謹，但 … 我錯了 QQ

先來看一下 SplPriorityQueue 的官方文件定義：
public void insert ( mixed $value , mixed $priority )
priority 和我預期的不一樣，原本以為只能放數字 (numbers) 但這邊的 priority type hint 卻標示為「mixed」，表示 priority 可以是任何資料型態 …？

先從最一般的 case 來測試吧：

$q = new SplPriorityQueue();

$q->insert(1, 'A');
$q->insert(2, 'B');
$q->insert(3, 'C');
$q->insert(4, 'D');
$q->insert(5, 'E');

while ($q->count() > 0) {
    echo $q->extract() . PHP_EOL;
}

output:

5
4
3
2
1

看起來會用 ASCII 數值來比較，數值大的優先 dequeue。看起來沒問題。

再來看一下遇到相同 priority 中有多個數值時，到底會發生什麼事：

$q = new SplPriorityQueue();

$q->insert(1, 1);
$q->insert(2, 1);
$q->insert(3, 1);
$q->insert(4, 1);
$q->insert(5, 1);

while ($q->count() > 0) {
    echo $q->extract() . PHP_EOL;
}

output:

1
5
4
3
2

「5, 4, 3, 2」還算正常，但是為什麼「1」會突然跑到最前面！？

最後，priority 真的可以放其他資料型態嗎？為了更清楚的看到執行結果，我這邊改使用 psysh 來操作：

Psy Shell v0.8.18 (PHP 7.1.18 — cli) by Justin Hileman
Unable to check for updates
>>> $q = new SplPriorityQueue();
=> SplPriorityQueue {#201
     heap: [],
   }
>>> $q->insert(1, [1, 2, 3]);
=> true
>>> $q->insert(2, []);
=> true
>>> $q->insert(3, new Exception())
=> true

靠北啊，Exception 也可以當作 priority 使用 ….

>>> while ($q->count() > 0) {
... echo $q->extract() . PHP_EOL;
... }
3
1
2

…. 我不想講了。

總之，若你要使用 SplPriorityQueue，請注意 undefined behavior。

Reference:

• php – Why SplPriorityQueue keys are reversed? – Stack Overflowhttps://stackoverflow.com/questions/21446898/why-splpriorityqueue-keys-are-reversed
• php – How SplPriorityQueue works when priority is not an integer? – Stack Overflowhttps://stackoverflow.com/questions/15851726/how-splpriorityqueue-works-when-priority-is-not-an-integer
• 有人重新實作了自己的 priority queue –  ezimuel/FastPriorityQueue
  https://github.com/ezimuel/FastPriorityQueue