PHP에서 순환 배열 감지 - 새로운 접근 방식

이 시리즈에서 순환 배열을 감지하는 문제와 왜 순수 PHP에서 감지하는지 설명했습니다. 또한 가능한 모든 어레이에 대해 간단하고 올바른 솔루션을 제시하겠다고 약속했는데, 이것이 바로 이 게시물에 관한 것입니다. 그러나 그 전에 이전 게시물에서 순환 배열의 정의를 다시 설명하겠습니다. 모든 항목 및 하위 항목 반복이 종료되지 않으면 배열은 순환입니다.

다음은 순환 배열의 예입니다.

$array = [1, [2, 3]];
$array[1][1] = &$array;

알고 계셨나요?

PHP 표준 라이브러리는 무한 재귀를 피하기 위해 배열이 순환하는지 확인하기 위해 이미 검사를 수행합니다. 그러한 예 중 하나는 json_encode ( run code )입니다.

$array = [1, [2, 3]];
$array[1][1] = &$array;
json_encode($array);
echo json_last_error_msg() . ', ' . json_last_error ();

Recursion detected, 6

이것은 이미 쉽고 정확한 솔루션을 제공합니다( run code )?

function is_cyclic(array &$array) {
    json_encode($array);
    return json_last_error() === JSON_ERROR_RECURSION;
}

Wendelin Jacober에서 Pexels 님의 사진

우리는 더 잘할 수 있습니다

기술적으로는 정확하지만 순환적인 소리인지 아닌지 확인하기 위해 어레이를 JSON으로 직렬화하는 것은 낭비적인 소리입니다. 고맙게도 우리가 사용할 수 있는 다른 기능이 있습니다. 오버헤드가 가장 적다고 생각되는 것은 good ol'count입니다. $mode 라는 잘 알려지지 않은 두 번째 매개 변수를 사용하며 값은 COUNT_NORMAL 또는 COUNT_RECURSIVE 입니다. 다음은 순환 배열( run code )을 재귀적으로 계산할 때 발생합니다.

$array = [1, [2, 3]];
$array[1][1] = &$array;
count($array, COUNT_RECURSIVE);

Warning: count(): Recursion detected

documentation for count은 순환 배열에서 E_WARNING로 호출될 때 COUNT_RECURSIVE를 방출한다고 말합니다. 이 정보를 사용하여 사용자 지정 오류 처리기를 설정하여 경고를 트랩하고 실제로 순환 배열( run code )로 인해 발생한 것인지 확인할 수 있습니다.

function is_cyclic(&$array) {
    $isRecursive = false;
    set_error_handler(function ($errno, $errstr) use (&$isRecursive) {
        $isRecursive = $errno === E_WARNING && mb_stripos($errstr, 'recursion');
    });
    try {
        count($array, COUNT_RECURSIVE);    
    } finally {
        restore_error_handler();
    }
    return $isRecursive;
}

이것은 이미 우리의 완벽한 솔루션입니다. 꽤 깔끔한.

이것이 정말 효과가 있습니까?

네, 그렇습니다. 그러나 고려해야 할 한 가지 중요한 사항이 있습니다. PHP는 새 버전에서 경고를 예외로 변경하는 것으로 알려져 있으며 실제로 PHP 7에서 PHP 8로 업그레이드할 때 발생한 일입니다. 내가 편안하게 약간 조정해야합니다. 더 중요한 것은 이 솔루션이 에서 설명한 극단적인 경우에도 작동한다는 것입니다.
count 함수가 오버헤드( see count source code )를 거의 추가하지 않기 때문에 성능도 우수합니다. my benchmarks에서는 정확할 뿐만 아니라 순수한 PHP 솔루션보다 훨씬 빠릅니다.

객체에도 적용되나요?

안타깝게도 재귀 객체를 효율적으로 감지하는 count와 같은 기능이 없습니다. json_encode 와 var_dump 가 있는데 이미 지적했듯이 불필요한 작업을 많이 한다. 표준 라이브러리가 배열과 객체 모두에서 순환을 감지하는 함수를 노출한다면 좋을 것입니다.

즉, 일반 PHP에서 작동하는 알고리즘을 구현하는 것이 가능하기 때문에 개체에서 주기를 감지하는 라이브러리 함수가 없는 것은 중요하지 않습니다.

마무리

해결책을 제시하는 동안 PHP 소스 코드를 많이 살펴보았습니다. 런타임이 주기를 감지할 수 있는 방법과 이것이 표준 라이브러리의 어디에 표시되는지 알고 싶었습니다. count 함수의 두 번째 매개변수에 대해서도 알 수 있었다. 나는 또한 모든 사람이 조금 더 깊이 파고들어 소시지가 어떻게 만들어지는지 직접 확인하도록 권장합니다. C 코드를 한 줄도 작성해 본 적이 없더라도 요지를 이해하고 흥미로운 것을 찾을 수 있을 것입니다.

I wish people were more fearless. There is too many people who don’t understand that it’s just code. It may not be the code that you wrote, but it’s just code. It follows the same rules. It may be in language that you are not particularly familiar with. But it’s still code running on a von Neumann architecture. There is nothing magic here.

Larry Osterman, https://channel9.msdn.com/Shows/Checking-In-with-Erik-Meijer/Checking-In-Larry-Osterman-26-Years-of-Programming-at-Microsoft

암호

GitHub에서 기능에 대한 테스트 및 벤치마크를 찾을 수 있습니다. 비교를 위해 json_encode 변형뿐만 아니라 깨진 구현도 포함했습니다.

게시물 Detecting cyclic arrays in PHP – A new approach이 hbgl에 처음 나타났습니다.