近一個月開始學習Rust，體感上覺得離能夠實戰還是差了很遠。因此計畫接下來用寫文章的方式，強迫自己每天寫一點Rust Code，再積極一點的學習這個語言。

Intro

這次的主題用簡單的插入排序算法，比較了Rust跟Python之間的效能差異。
Insertion Sort是個O(n2)的演算法，將排序後的元素維持在低位的子序列，然後將新的元素根據大小逐步插入子序列中，重複的比較過程。

先看Python Code：

import random
import time
from typing import List

def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        execution_time = (end_time - start_time) * 1000  # Convert to milliseconds
        print(f"Execution time: {execution_time:.4f} ms")
        return result
    return wrapper

def generate_random_array(size: int, lower_bound: int = 0, upper_bound: int = 100) -> List[int]:
    return [random.randint(lower_bound, upper_bound) for _ in range(size)]

@timer
def insertion_sort(arr: List[int]) -> List[int]:
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

if __name__ == "__main__":
    array_size = 10000
    array = generate_random_array(array_size, 0, 9999)
    sorted_array = insertion_sort(array)

使用10,000個元素作為排序的對象。時間的紀錄方式用簡易的Timer裝飾器實現。

Rust Code:

use rand::Rng;

fn time_it<F, T>(func: F) -> T
where
    F: FnOnce() -> T,
{
    let start = std::time::Instant::now();
    let result = func();
    let elapsed = start.elapsed();
    println!("Elapsed time: {:?}", elapsed);
    result
}

fn insertion_sort(array: &mut [usize]) {
    let n = array.len();

    for i in 1..n {
        let mut j = i;
        let key = array[i];
        while j > 0 && key < array[j - 1] {
            array.swap(j, j - 1);
            j -= 1;
        }
    }
}

fn main() {
    // Create a random array with 1000000 elements
    let random_array = generate_dyn_random_array(10000);

    // Clone the random array to use it in both bubble sort and insertion sort
    let mut insertion_array = random_array.clone();

    // Insertion sort
    time_it(|| insertion_sort(&mut insertion_array));
}

fn generate_dyn_random_array(len: usize) -> Vec<usize> {
    let mut rng = rand::thread_rng();
    let mut array = Vec::with_capacity(len);

    for _ in 0..len {
        array.push(rng.gen_range(1..len));
    }

    array
}

這裏利用了Rust的FnOnce Closure，去實現Timer Decorator的功能。
另外利用了rand::Rng實現了隨機產生亂數陣列的函數。
最後實作Insertion Sort的演算法，雙方的執行結果如下：

> python insertion_sort.py
Execution time: 2009.5739 ms

> Cargo build --release
> ./target/release/insertion_sort
Elapsed time: 18.484417 ms

接近了快100倍的效能差距。