병합 정렬을 사용한 역전 계산 - 예기치 않은 결과

이 코드는 작은 요소 집합에 대해 올바른 결과를 산출하지만 큰 숫자 집합 (100,000 개 요소)에 대한 결과가 잘못된 이유를 알지 못합니다. 예를 들어 the 100,000 integers text file from coursera입니다. 이미 파이썬 코드에서 올바른 결과를 얻었습니다. 하지만이 PHP 코드가 정확합니다 출력이되지 않는 이유 파악하려는 2,397,819,672 2407905288.병합 정렬을 사용한 역전 계산 - 예기치 않은 결과

$raw_input = file_get_contents($argv[1]); 

$arr_input = explode("\n",trim($raw_input)); 

$count = 0.0; 

function merge_sort($a) 
{ 
    if(count($a) <2) return $a; 
    $hl = count($a)/2; 
    return merge(merge_sort(array_slice($a, 0, $hl)), merge_sort(array_slice($a, $hl))); 

} 

function merge($l, $r) 
{ 
    global $count; 
    $result = array(); 
    $i = $j = 0; 

    while($i < sizeof($l) && $j < sizeof($r)) 
    { 
     if($l[$i] < $r[$j]) 
     { 
      $result[] =$l[$i]; 
      $i++; 
     } 
     else 
     { 
      $result[] =$r[$j]; 
      $count+= (sizeof($l) - $i); 
      $j++; 
     } 
    } 

    while($i <sizeof($l)) 
    { 
     $result[] = $l[$i]; 
     $i++; 
    } 

    while($j <sizeof($r)) 
    { 
     $result[] = $r[$j]; 
     $j++; 
    } 
    return $result; 
} 

$sorted = merge_sort($arr_input); 

print $count . "\n";

출처

2013-07-06 hungneox

파이썬에서이 문제가 발생했기 때문에 최대 정수 값 관련 문제라고 생각하지 않습니다. 나는 내 코드의 마지막 부분은

f = open('IntegerArray.txt') 
unsorted = list() 
for line in f: 
    unsorted.append(line) 
merge_sort(unsorted)

경우 내 코드의 마지막 부분 인 경우이 번호는 : 나는 정답 2,407,905,288를 얻을 사실 나는 구글이 페이지에 도착 (오답 2,397,819,672를 얻을 수

f = open('IntegerArray.txt') 
unsorted = list() 
for line in f: 
    unsorted.append(int(line)) 
merge_sort(unsorted)

차이점을 찾을 수 있습니까? 그것이 바로 답이있는 곳입니다.

출처

2013-07-07 08:42:14 kkzxak47

정말 고마워요 !! 마술의 하나 일 뿐이야 :-? – hungneox

의 intead 난 당신이 PHP의 최대 정수 값을 명중 내기 것입니다. 공식 문서에 따르면

http://php.net/manual/en/language.types.integer.php

The size of an integer is platform-dependent, although a maximum value of about two billion is the usual value (that's 32 bits signed). 64-bit platforms usually have a maximum value of about 9E18. PHP does not support unsigned integers. Integer size can be determined using the constant PHP_INT_SIZE, and maximum value using the constant PHP_INT_MAX since PHP 4.4.0 and PHP 5.0.5.

그래서 당신은 INT_MAX 일정을 변경할 수 있습니다.

테스트되지 않은 것 : 문자열로 사용하십시오.

출처

2013-07-06 10:04:17

PHP_INT_SIZE가 2397819672보다 적습니다. 그래서 혼란 스럽습니다. – hungneox

'PHP_INT_MAX'이 상수를 확인해야한다고 생각합니다. –

제 컴퓨터에서 2147483647입니다 : -? 그러나 그것은 거짓 결과보다 작습니다 – hungneox

위 대답 중 하나와 비슷하게 파이썬을 사용하고있었습니다. 오류는 코드가 int 비교 대신 문자열 비교를 수행하고있는 것입니다. 예를 들어, 파이썬에서 '33'< '4'는 참입니다.

출처

2015-06-02 06:09:58 user3150434

병합 정렬을 사용한 역전 계산 - 예기치 않은 결과

답변

관련 문제