배열을 반복 할 때 사이클을 어떻게 찾을 수 있습니까?

Question

$arr = array(
    'a'   => 1, 
    'b'   => 15, 
    'c'   => 0, 
); 

$arr['c'] = &$arr; 

print_r($arr); // <-- CYCLE 

어떻게하면 기존 요소를 가리키는 배열 값이 있는지 또는 무한 루프가 발생하는지 감지 할 수 있습니까?

Answer 1

메모리 , 루크을 사용하십시오. 반복자가 다른 하나의 요소로 배열을 가로 지르는 경우 set 또는 list (또는 다른 적절한 컨테이너, 예 : 배열)와 같은 참조 또는 ID를 저장하십시오. 그래서 당신은 당신이 이미 처리 한 어레이를 암기하고 다음에 만날 때 그것을 무시하거나 루프를 멈춘다.

<?php 
function get_id(&$array) { 
    return crc32(serialize($array)); 
} 

# This will not work as expected. I leave it here just for future versions. 
function get_id_alt(&$array) { 
    $obj = (object) $array; 
    return spl_object_hash($obj); 
} 

function iterate(array $input, &$reached=array(), $id_func='get_id') { 
    // this is an unseen array, memorize it 
    array_push($reached, $id_func($input)); 

    foreach($input as $key=>$item) { 
    if (is_array($item)) {  // This is an array 
     if (in_array($id_func($item), $reached)) { 
     // We found an array that have been processed before. What will you do? 
     } else { 
     // Recurse! 
     iterate($item, $reached); 
     } 
    } else { 
     // It is not traversable value, do what you want here 
    } 
    } 
} 

PS : 나는 ID-함수로 spl_object_hash를 사용하고, 다른 하나를 사용할 수 있습니다, 선호 (하지만이 하나처럼 내가 같은 물체를 식별 할 수있는 다른 사람을 모르는)합니다.

UPD :spl_object_hash을 사용하면 PHP 5.3.10부터 올바른 결과를 얻을 수 없습니다. 내용에 관계없이 모든 배열을 동일한 객체로 취급합니다. 그러나 %hash_fn%(serialize($array))과 같은 smth를 사용하면 성능이 저하 될 수 있습니다.

Answer 2

print_r에서 재귀를 알려주는 이유는 무엇입니까? :)

// Set up bad array 
$arr = array(
    'a'   => 1, 
    'b'   => 15, 
    'c'   => 0, 
); 
$arr['c'] = &$arr; 

// Check print_r 
if(strpos(print_r($a,1),'*RECURSION*') !== false) { 
    echo "Houston, we got a problem!\n"; 
} 

편집 : @Vyktor에서 설명한 것처럼, 이것은 모든 경우에 작동하지 않고 거짓 positves을 생산할 수 있지만, serialize() 또한 재귀의 지표를 제공합니다. 재귀를 위해 R을 제공합니다. serialize()의 출력 문자열의 R 외부가 있다면 그래서 우리는 확인 :

<?php 
// Set up bad array 
$arr = array(
    'a'   => 1, 
    'b'   => 15, 
    'c'   => 0, 
); 
$arr['c'] = &$arr; 

$str = serialize($arr); // Serialize it 
$len = strlen($str);  // Get the length 

// Simple serialize "parser" 
$state = 0; 
$recursion_found = false; 
for($i=0;$i<$len;$i++) { 
    $byte = $str[$i]; 
    if($byte == "\"" && $state == 0) { 
    $state = 1; // in string! 
    } else if($byte == "\"" && $state == 1) { 
    // Check if the " is escaped 
    if($str[$i-1] != "\\") { 
     $state = 0; // not in string 
    } 
    } else if($byte == "R" && $state == 0) { // any R that is not in a string 
    $recursion_found = true; 
    } 
} 

if($recursion_found) { 
    echo "There is recursion!\n"; 
} 

Answer 3

(난 그냥 @Cheery 언급하는 Is there a way to detect circular arrays in pure PHP? 질문에 대한 답변으로 이것을 게시,하지만 난 그 답을 업데이트 할 수있다

아래의 isRecursiveArray (array) 메서드는 순환/재귀 배열을 감지합니다. 배열의 끝에 알려진 객체 참조를 포함하는 요소를 임시로 추가하여 방문한 배열을 추적합니다. 배열과 객체에 대한

function removeLastElementIfSame(array & $array, $reference) { 
    if(end($array) === $reference) { 
     unset($array[key($array)]); 
    } 
} 

function isRecursiveArrayIteration(array & $array, $reference) { 
    $last_element = end($array); 
    if($reference === $last_element) { 
     return true; 
    } 
    $array[] = $reference; 

    foreach($array as &$element) { 
     if(is_array($element)) { 
      if(isRecursiveArrayIteration($element, $reference)) { 
       removeLastElementIfSame($array, $reference); 
       return true; 
      } 
     } 
    } 

    removeLastElementIfSame($array, $reference); 

    return false; 
} 

function isRecursiveArray(array $array) { 
    $some_reference = new stdclass(); 
    return isRecursiveArrayIteration($array, $some_reference); 
} 



$array  = array('a','b','c'); 
var_dump(isRecursiveArray($array)); 
print_r($array); 



$array  = array('a','b','c'); 
$array[] = $array; 
var_dump(isRecursiveArray($array)); 
print_r($array); 



$array  = array('a','b','c'); 
$array[] = &$array; 
var_dump(isRecursiveArray($array)); 
print_r($array); 



$array  = array('a','b','c'); 
$array[] = &$array; 
$array  = array($array); 
var_dump(isRecursiveArray($array)); 
print_r($array); 

Answer 4

파생 작업 (모두) :

function isRecursiveArrayObjectTest(&$object, $marker) 
{ 
    if (is_array($object)) { 
     // Move the array pointer to the end and test if we encounter the marker (if so, its recursive) 
     $last = end($object); 
     if ($marker === $last) { 
      return true; 
     } 
     // Add a marker to the end of the array to test for recursion (removed upon exit) 
     $object[] = $marker; 
    } elseif (is_object($object)) { 
     // Treat objects differently 
     if ($marker === $object->__testRecursion) { 
      return true; 
     } 
     // Add a marker using a member that is unlikely to be defined (removed upon exit) 
     $object->__testRecursion = $marker; 
    } else { 
     return false; 
    } 

    $isRecur = false; 

    // Loop over the elements of the array, recursively testing each one (if it is an array|object) 
    foreach($object as &$element) { 
     if(is_array($element) || (is_object($element) && $element !== $marker)) { 
      if(isRecursiveArrayObjectTest($element, $marker)) { 
       $isRecur = true; 
       break; 
      } 
     } 
    } 

    // remove marker before we leave 
    if (is_array($object) && end($object) === $marker) { 
     unset($object[key($object)]); 
    } elseif (is_object($object) && isset($object->__testRecursion)) { 
     unset($object->__testRecursion); 
    } 

    return $isRecur; 
} 

function isRecursiveArrayObject($object) 
{ 
    // Create a 'marker' to detect where we have visited to determine recursion 
    $marker = new stdClass(); 
    return isRecursiveArrayObjectTest($object, $marker); 
}