Та же задачка на 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 совсем разные языки, никак друг с другом не конкурирующие. С моей же точки зрения эти языки находятся в одной нише, и годятся для более-менее тех же задач.

Comments

[chabapok]

скала с растом?

Ну если задача факнуть мозг...

как вообще можно сравнивать ниши языков с gc и без.

[juan_gandhi]

cargo - поразительно осмысленная тулза.

Спасибо за примерчики. Раст я разлюбил; и, мне кажется, хотя вот здесь тебе удалось забацать решение, мне еще не верится, что projecteuler можно вот так вот задачу за задачей щелкать на расте. В смысле, у меня не получилось.

[dedekha]

Ну на фортране это такие задачки тоже беспроблемно решаются и когда-то пришлось на фортране-2 управлять масс-спектрометром и тоже никто от этого не умер.

[vak]

Почему-то большинство программировавших на Фортране либо умерли, либо переключились на другие языки. 😀

[vak]

А нет никакой особой разницы. Golang с gc, Rust без, D с gc, C++ без. Всё одна и та же ниша. Писал я компиляторы на Go и на C++. Разница в удобстве есть, но определяется она не сборкой мусора.

[dedekha]

Ну и почему это случилось? Одни вещи удобнее делать на одних языках, а другие вещи на других + мода + ресурсы.

Скала замечательна тем что она очень удобна для любого применения и если бы не ресурсы (и наличие знающих людей) была бы она универсальным языком - это персональное мнение на правильности которого я не настаиваю.

[vak]

Да просто то поколение ушло, а у нового свои игрушки.

Скала как язык мне очень нравится. Но насчет удобства для любого применения... Пока для меня Rust и Golang перевешивают.

[dedekha]

Хочется надеятся что у меня еще есть время :). Поколения языков менялись гораздо быстрее чем поколения инженеров у многих из нас в начале пути были фортран и кобол.

[vak]

Я в студенчестве писал файловую систему на Фортране для БЭСМ-6. Самые тёплые воспоминания. :)
Тогда других подходящих языков не имелось.

Если к Скале привинтить cargo да завести общий репозиторий пакетов типа crates.io - цены бы не было.

[vak]

Я конечно не настоящий сварщик, в функциональном подходе не мастак. Но почему бы и не щёлкать на Расте? Там всё для этого присутствует, хоть и в менее элегантном виде, чем в Скале.

[juan_gandhi]

Вот я и занялся. И не пошло совершенно.

[dedekha]

позади скалы стоят все библиотеки java и их очень много. Как-то я пытался портануть умеренную java аппликацию на с++ - уперлось в библиотеки. Если по выходу на пенсию мир будет стоять и я все еще смогу печатать планирую заполнять свободное время переписывание java библиотек на с++

[ivanrubilo]

Я, конечно, с Фортраном имел дело только с -66 и -77м, не знаю совершенно современного, но вот на -77 хрена с два, даже убогой хэш-мапы не наблюдается из коробки.

Попробуйте Advent of Code где-нить начиная с дня 15го порешать без мапов да сетов.

[vak]

Поэтому Rust и опередит: там всё уже переписано.