使用合併排序計數倒置 - 意外的結果

此代碼爲一小組元素生成正確的結果，但我不知道爲什麼結果對於大數字集（100,000個元素）不正確。例如，這是the 100,000 integers text file from coursera。我已經從我的Python代碼中得到了正確的結果。但是，我想弄清楚爲什麼這個PHP代碼是不是correct.The輸出爲2397819672這一翻譯的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

我不認爲這是一個最大的整數值相關的問題，因爲我在Python中遇到了這個問題。我得到錯誤的答案2397819672（其實我通過谷歌訪問此頁面這個數字:)如果我的代碼的最後一部分是

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

我找到正確答案，如果2407905288我的代碼的最後一部分是

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

我敢打賭，你打在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

與上面的答案類似，我使用的是Python。錯誤的是你的代碼可能是做字符串比較而不是int比較。例如，在Python中，'33'<'4'爲真。

來源

2015-06-02 06:09:58 user3150434

使用合併排序計數倒置 - 意外的結果

回答

相關問題