きっかけ
https://leetcode.com/problems/linked-list-cycle/
内容
PHP の比較は緩やかな比較(==)と厳密な比較(===)があるが、オブジェクトの比較の場合は下記のようになる
- 緩やかな比較(==)
- 同じクラスのインスタンスであり、かつ全てのプロパティが(緩やかな比較において)等しいならに2つのオブジェクトは等しい
- 厳密な比較(===)
- 同じクラスの同じインスタンスを参照しているなら2つのオブジェクトは等しい
なのでオブジェクト構造が単純でない場合にうっかり緩やかな比較を使うと時間がかかる
// 例えばこういう Linked List の要素を表すクラスがあったとする
class Node
{
public __construct(int $value, ?Node $next) {
$this->value = $value;
$this->next = $next;
}
/** @var int */
private $value;
/** @var Node */
private $next;
}
// ループがあるかどうか判定する
function hasCycle($head) {
/** @var Node[] $nodes */
$nodes = [];
/** @var Node $cur */
$cur = $head;
while (true) {
// こうするとやる必要のない比較が走って時間がかかる
//if (in_array($cur, $nodes)) {
// こうするのが正しい
if (in_array($cur, $nodes, true)) {
return true;
}
if ($cur === null) {
return false;
}
$nodes[] = $cur;
$cur = $cur->next;
}
}
感想
緩やかな比較でも普通に動いてしまうので最初 in_array に true 渡してないの気づかなかった。
やたら時間がかかってたので見直してみたら…な感じ。
個人的には緩やかな比較はなくなればいいのに…って思う