爲什麼我的Rust實現InsertionSort比我的C版本慢？

我決定開始學習編程語言來重寫我的程序。第一個是大學第二年的簡單課程。但是...看看測試！爲什麼簡單的插入排序很慢？爲什麼我的Rust實現InsertionSort比我的C版本慢？

測試在C：

ARRAY SIZE: 100000 
< counting_sort: 0.003602 
< insertion_sort: 8.273647 
< heap_sort:  0.017918

測試生鏽：

ARRAY SIZE: 100000 
< counting_sort: PT0.039530982S 
< insertion_sort: PT276.529915469S 
< heap_sort:  PT0.117946209S

我怎樣才能提高我的轉換後的代碼？

C-版本：

void insertion_sort(int a[], int length) { 
    int i, j, value; 
    for (i = 1; i < length; i++) { 
     value = a[i]; 
     for (j = i - 1; j >= 0 && a[j] > value; j--) { 
      a[j + 1] = a[j]; 
     } 
     a[j + 1] = value; 
    } 
}

防鏽版本：

pub fn insertion_sort(array: &mut [i32]) { 
    let mut value; 
    for i in 1..array.len() { 
     value = array[i]; 
     let mut flag = true; 
     for j in (0..i).rev() { 
      if array[j] > value { 
       array[j + 1] = array[j]; 
      } else { 
       flag = false; 
       array[j + 1] = value; 
       break; 
      } 
     } 
     if flag { 
      array[0] = value; 
     } 
    } 
}

我並沒有建立在釋放模式。

C-版本（gcc -O3）：

ARRAY SIZE: 100000 
< counting_sort: 0.001252 
< insertion_sort: 1.672351 
< heap_sort:  0.008694

防鏽版本（cargo build --release）：

ARRAY SIZE: 100000 
< counting_sort: PT0.001556914S 
< insertion_sort: PT3.291146043S 
< heap_sort:  PT0.008269021S

來源

2015-06-21 Vladislav Orlov

您可以使用'get_unchecked'，這是一個'unsafe'方法，而不是'[]'來繞過邊界檢查。這可能會有很大的幫助。 –

爲什麼一個簡單的插入排序很慢，即使編譯在釋放模式後？

我願意打賭這是對數組訪問的邊界檢查。你正在做很多。

如果您使用迭代器而不是直接訪問，則不支付該懲罰。不幸的是，我現在還沒有一個適合你的迭代器版本。也許別人可以貢獻一個。 :)

來源

2015-06-21 20:58:20

我不確定使用迭代器構建一個版本會很容易，借用規則將很難滿足。 –

爲什麼我的Rust實現InsertionSort比我的C版本慢？

回答

相關問題