Та же задачка на Rust

[vak]

Позавчера я показывал решение стандартной задачки Two-Sum на языке Scala. А вот для сравнения то же самое, но на языке Rust. И даже не два варианта решения, а три. Готовые файлы лежат на Гитхабе: two-sum. В отличие от Скалы, тут всего один файл конфигурации Cargo.toml.

Первое решение - самое тривиальное, просто цикл в цикле. Для Scala я его не давал: слишком уж примитивно. Зато не надо много объяснять: из кода всё ясно.

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    for (j, b) in nums.iter().enumerate() {
        for (i, a) in nums[..j].iter().enumerate() {
            if a + b == target {
                return vec![i as i32, j as i32];
            }
        }
    }
    panic!("no solution");
}

Второй вариант, функциональный, я старался сделать максимально близким к решению на Скале. Практически один в один, малость многословнее.

fn two_sum_2(nums: Vec<i32>, target: i32) -> Vec<i32> {
    // Pair each number with it's index.
    // For example: [(2, 0), (7, 1), (11, 2), (15, 3)]
    let with_index: Vec<_> = nums.iter().zip(0..).collect();

    // Compute all the possible combinations of two elements from the array.
    // Like this: [[(2, 0), (7, 1)], [(2, 0), (11, 2)], [(2, 0), (15, 3)],
    //             [(7, 1), (11, 2)], [(7, 1), (15, 3)], [(11, 2), (15, 3)]]
    let comb = combination::combine::from_vec_at(&with_index, 2);

    // Find an item which has a required sum of numbers.
    // The result is Some([(2, 0), (7, 1)]).
    let find = comb.iter().find(|&x| x.iter().map(|&item| item.0).sum::<i32>() == target);

    // We've been told our input has a solution.
    // So extract it from the option.
    // We get something like: [(2, 0), (7, 1)]
    let res = find.unwrap();

    // Get indices from the result.
    // For example: [0, 1]
    let idx: Vec<_> = res.iter().map(|&x| x.1).collect();

    idx
}

Третий вариант, который с линейной сложностью, я переписал бер рекурсии. Так маленько понятнее, мне кажется.

fn two_sum_3(nums: Vec<i32>, target: i32) -> Vec<i32> {
    use std::collections::HashMap;
    let mut complements = HashMap::<i32, i32>::new();

    for (j, num) in nums.iter().enumerate() {
        if let Some(&i) = complements.get(num) {
            return vec![i, j as i32];
        }
        complements.insert(target - num, j as i32);
    }
    panic!("no solution");
}

Тесты ровно такие же. Что хорошо в Rust - можно хранить тесты в том же файле исходников. Мелочь, а приятно.

#[cfg(test)]

// Example 1:
//       Input: nums = [2,7,11,15], target = 9
//      Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
#[test]
fn example_1() {
    let result = two_sum(vec![2, 7, 11, 15], 9);
    assert_eq!(result.len(), 2);
    assert_eq!(result[0], 0);
    assert_eq!(result[1], 1);
}

// Example 2:
//  Input: nums = [3,2,4], target = 6
// Output: [1,2]
#[test]
fn example_2() {
    let result = two_sum(vec![3, 2, 4], 6);
    assert_eq!(result.len(), 2);
    assert_eq!(result[0], 1);
    assert_eq!(result[1], 2);
}

// Example 3:
//  Input: nums = [3,3], target = 6
// Output: [0,1]
#[test]
fn example_3() {
    let result = two_sum(vec![3, 3], 6);
    assert_eq!(result.len(), 2);
    assert_eq!(result[0], 0);
    assert_eq!(result[1], 1);
}

Запускаем:

$ cargo test
   Compiling combination v0.2.2
   Compiling two-sum v0.1.0 (./two-sum)
    Finished test [unoptimized + debuginfo] target(s) in 3.16s
     Running unittests src/main.rs (./two-sum/target/debug/deps/two_sum-c716b7ee0dd71399)

running 3 tests
test example_1 ... ok
test example_2 ... ok
test example_3 ... ok

test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

В целом инструментарий Rust производит более приятное впечатление. Утилита cargo намного шустрее и понятнее.

Это я всё к чему. В комментах juan_gandhi намедни утверждал, что Scala и Rust совсем разные языки, никак друг с другом не конкурирующие. С моей же точки зрения эти языки находятся в одной нише, и годятся для более-менее тех же задач.