1. Two SumのRustの解答を読み解く①

LeetCode Rust

今年はRustをじっくりと学びたいと思っていたので、LeetCodeのHello worldとも言うべき問題Two SumをRustで書くとどうなるのだろうか、とふと思った。

当の問題の解法(最適なアルゴリズム)は既に知っているので、では言語の学習に、と全く0の状態からガイドを見ながら解いてみることにした。しかしながら、かなり厳格な言語であるようで、全くコンパイルが通らずエラー地獄となってしまった。

そこで、Discussion Forumで掲載されていた解答コードのリーディングを行うことにした。

1. Two Sum

leetcode.com

数値を含んだ配列とtargetという数値が与えられるので、配列内の2つの数値を足し合わせた値がtargetに等しくなる場合を探る。同じ数値を二度使うことは不可で、こうしたtargetに等しい組み合わせが最低でも1つあることが保証されている。そして、それぞれの足し合わせた数値のインデックスを配列にして返すことが期待される。

Brute Force

いわゆる二重ループを用いて解く方法。おそらくLeetCodeでこの問題を初めて解く場合、大半の人がこのアプローチを取ると思う。ひとときのAC(Accepted)に安堵してしまい、後々この問題の本質の価値に気付く、というのは多くのLeetCoderが経験するお約束のパターン。

時間計算量は言わずもがなO(N^{2})。空間計算量は O(1)。

このトピックで掲載されていたコードをそのまま引用する。

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for ind in (0..nums.len() - 1)
        {
            for comp_ind in (ind+1..nums.len())
            {
                if nums[ind] + nums[comp_ind] == target
                {
                    return vec![ind as i32, comp_ind as i32];
                }
            }
        }
        return vec![0;2];        
    }
}

今回は、ループ、ベクタ、キャストの3つについて取り上げたい。

ループ

Rustのループはloop while forの3つがあるようだが、そのうちの1つforループの処理については、以下のように記述することができる。

for x in 0..10 {
    println!("{}", x);
}

0..nと書けるのが特徴で、Pythonでいうところのrange(0, n)だ。forループといえば、以下のような記述が標準だけど、どうやらRustでは非推奨らしい。Pythonに慣れ親しんだ自分としては少し助かる。

for (x = 0; x < 10; x++) {
    printf( "%d\n", x );
}

理由は以下のとおり。

Rustでは意図的に「Cスタイル」 for ループを持ちません。経験豊富なC開発者でさえ、 ループの各要素を手動制御することは複雑であり、また間違いを犯しやすいのです。

せっかくなので、if文を少し調べつつFizzBuzzを書いてみた。

fn main() {
    for i in 1..101 {
        if i % 3 == 0 && i % 5 == 0 {
            println!("{} : {}",i, "FizzBuzz!")
        } else if i % 3 == 0 {
            println!("{} : {}",i, "Fizz!");
        } else if i % 5 == 0 {
            println!("{} : {}", i, "Buzz!")
        }
    }
}

https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/loops.html

ベクタ

ベクタとは、動的あるいは拡張可能な配列である(PythonのリストやGoのスライスに相当)。vec!というマクロによってベクタの生成が可能。今回は入力で与えられたベクタ、numsのサイズを取得したいので、len()を呼び出している。

以下、サンプルコード。

fn main() {
　　let v = vec![1, 2, 3, 4, 5];
　　println!("{}", v.len()) // 5
}

std::vec::Vec - Rust

型のキャスト

asによって型を安全にキャストすることが可能。今回は出力の形式がVec<i32>で関数内で指定されているので、ベクタ内の要素の型はi32にする必要がある。i32は32ビットの符号付整数型。

以下、サンプルコード(型を呼び出すメソッドについては省略)。

use std::any::type_name;

fn type_of<T>(_: T) -> &'static str {
    type_name::<T>()
}

fn main() {
　　let x: i32 = 5;
　　println!("{}", type_of(x)); // i32

　　let y = x as i64;
　　println!("{}", type_of(y)); // i64
}

as - Rust

次回はもう一つのアプローチ、ハッシュマップを用いたアルゴリズムの場合のコードについて、リーディングを行いたい。

余談

このコードの実行速度は36 msでメモリ使用量は2.2MBだった。

ハッシュマップを用いたO(N)のアルゴリズムアプローチを用いてPythonで提出した結果が履歴に残っており、実行速度は48 msでメモリ使用量は14.1 MBであった。Rustがいかに高速な言語であるということを思い知らされる！(インタプリタ言語とコンパイル言語を比較するのはやや不適切な気もするけど...)

参考

doc.rust-jp.rs