1
0
お題は不問!Qiita Engineer Festa 2024で記事投稿!
Qiita Engineer Festa20242024年7月17日まで開催中!

Rust 100 Ex 🏃【19/37】 配列・動的配列 ~スタックが使われる配列と、ヒープに保存できる動的配列~

Last updated at Posted at 2024-07-17

前の記事

全記事一覧

100 Exercise To Learn Rust 演習第19回になります、今回から6章に入ります!

今回の関連ページ

[06_ticket_management/01_arrays] 配列 (静的配列)

問題はこちらです。

lib.rs
// TODO: Flesh out the `WeekTemperatures` struct and its method implementations to pass the tests.

pub struct WeekTemperatures {
    // TODO
}

pub enum Weekday {
    Monday,
    Tuesday,
    Wednesday,
    Thursday,
    Friday,
    Saturday,
    Sunday,
}

impl WeekTemperatures {
    pub fn new() -> Self {
        todo!()
    }

    pub fn get_temperature(&self, day: Weekday) -> Option<i32> {
        todo!()
    }

    pub fn set_temperature(&mut self, day: Weekday, temperature: i32) {
        todo!()
    }
}
テストを含めた全体
lib.rs
// TODO: Flesh out the `WeekTemperatures` struct and its method implementations to pass the tests.

pub struct WeekTemperatures {
    // TODO
}

pub enum Weekday {
    Monday,
    Tuesday,
    Wednesday,
    Thursday,
    Friday,
    Saturday,
    Sunday,
}

impl WeekTemperatures {
    pub fn new() -> Self {
        todo!()
    }

    pub fn get_temperature(&self, day: Weekday) -> Option<i32> {
        todo!()
    }

    pub fn set_temperature(&mut self, day: Weekday, temperature: i32) {
        todo!()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_get_temperature() {
        let mut week_temperatures = WeekTemperatures::new();

        assert_eq!(week_temperatures.get_temperature(Weekday::Monday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Tuesday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Wednesday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Thursday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Friday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Saturday), None);
        assert_eq!(week_temperatures.get_temperature(Weekday::Sunday), None);

        week_temperatures.set_temperature(Weekday::Monday, 20);
        assert_eq!(week_temperatures.get_temperature(Weekday::Monday), Some(20));

        week_temperatures.set_temperature(Weekday::Monday, 25);
        assert_eq!(week_temperatures.get_temperature(Weekday::Monday), Some(25));

        week_temperatures.set_temperature(Weekday::Tuesday, 30);
        week_temperatures.set_temperature(Weekday::Wednesday, 35);
        week_temperatures.set_temperature(Weekday::Thursday, 40);
        week_temperatures.set_temperature(Weekday::Friday, 45);
        week_temperatures.set_temperature(Weekday::Saturday, 50);
        week_temperatures.set_temperature(Weekday::Sunday, 55);

        assert_eq!(week_temperatures.get_temperature(Weekday::Monday), Some(25));
        assert_eq!(
            week_temperatures.get_temperature(Weekday::Tuesday),
            Some(30)
        );
        assert_eq!(
            week_temperatures.get_temperature(Weekday::Wednesday),
            Some(35)
        );
        assert_eq!(
            week_temperatures.get_temperature(Weekday::Thursday),
            Some(40)
        );
        assert_eq!(week_temperatures.get_temperature(Weekday::Friday), Some(45));
        assert_eq!(
            week_temperatures.get_temperature(Weekday::Saturday),
            Some(50)
        );
        assert_eq!(week_temperatures.get_temperature(Weekday::Sunday), Some(55));
    }
}

解説

(配列を使わなくてもここまでの応用で普通に記述可能ですが、)一週間の気温を保存する配列を構造体に定義し、コンストラクタとその配列へのゲッター・セッターを記述すればACです。

lib.rs
pub struct WeekTemperatures {
    temperatures: [Option<i32>; 7],
}

pub enum Weekday {
    Monday,
    Tuesday,
    Wednesday,
    Thursday,
    Friday,
    Saturday,
    Sunday,
}

impl WeekTemperatures {
    pub fn new() -> Self {
        Self {
            temperatures: [None; 7],
        }
    }

    pub fn get_temperature(&self, day: Weekday) -> Option<i32> {
        self.temperatures[day as usize]
    }

    pub fn set_temperature(&mut self, day: Weekday, temperature: i32) {
        self.temperatures[day as usize] = Some(temperature);
    }
}

ところで想定回答だと match 式を使うように書いていますし、実際このように書いたほうが "Rustっぽい" です。

lib.rs (該当箇所抜粋)
impl From<Weekday> for usize {
    fn from(value: Weekday) -> Self {
        use Weekday::*;

        match value {
            Monday => 0,
            Tuesday => 1,
            Wednesday => 2,
            Thursday => 3,
            Friday => 4,
            Saturday => 5,
            Sunday => 6,
        }
    }
}

// ...

impl WeekTemperatures {
    pub fn new() -> Self {
        Self {
            temperatures: [None; 7],
        }
    }

    pub fn get_temperature(&self, day: Weekday) -> Option<i32> {
-        self.temperatures[day as usize]
+        self.temperatures[usize::from(day)]
    }

    pub fn set_temperature(&mut self, day: Weekday, temperature: i32) {
-        self.temperatures[day as usize] = Some(temperature);
+        self.temperatures[usize::from(day)] = Some(temperature);
    }
}

ところが今回演習に取り組んでみたところ、 フィールドを持たない列挙体については as usize で整数型へのキャストが可能 みたいなんですよね...意外な仕様を知ったので折角の機会ということで載せてみました!

配列それ自体に対してはあまり解説することがない...Rustの配列はスタック領域に保存される静的配列を指すため、サイズの変更ができないので動的配列と比べるとあまり使われないですね、ぐらいでしょうか...?使用頻度は少ないですが、存在や仕組みは知っておいて損がないと思います。

[06_ticket_management/02_vec] 動的配列

問題はこちらです。

lib.rs
// Given a number `n`, return the `n+1`th number in the Fibonacci sequence.
//
// The Fibonacci sequence is defined as follows:
//
// - The first number of the sequence is 0.
// - The second number of the sequence is 1.
// - Every subsequent number is the sum of the two preceding numbers.
//
// So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.
//
// We expect `fibonacci(0)` to return `0`, `fibonacci(1)` to return `1`,
// `fibonacci(2)` to return `1`, and so on.
pub fn fibonacci(n: u32) -> u32 {
    // TODO: implement the `fibonacci` function
    //
    // Hint: use a `Vec` to memoize the results you have already calculated
    // so that you don't have to recalculate them several times.
    todo!()
}
テストを含めた全体
lib.rs
// Given a number `n`, return the `n+1`th number in the Fibonacci sequence.
//
// The Fibonacci sequence is defined as follows:
//
// - The first number of the sequence is 0.
// - The second number of the sequence is 1.
// - Every subsequent number is the sum of the two preceding numbers.
//
// So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.
//
// We expect `fibonacci(0)` to return `0`, `fibonacci(1)` to return `1`,
// `fibonacci(2)` to return `1`, and so on.
pub fn fibonacci(n: u32) -> u32 {
    // TODO: implement the `fibonacci` function
    //
    // Hint: use a `Vec` to memoize the results you have already calculated
    // so that you don't have to recalculate them several times.
    todo!()
}

#[cfg(test)]
mod tests {
    use crate::fibonacci;

    #[test]
    fn first() {
        assert_eq!(fibonacci(0), 0);
    }

    #[test]
    fn second() {
        assert_eq!(fibonacci(1), 1);
    }

    #[test]
    fn third() {
        assert_eq!(fibonacci(2), 1);
    }

    #[test]
    fn tenth() {
        assert_eq!(fibonacci(10), 55);
    }

    #[test]
    fn thirtieth() {
        assert_eq!(fibonacci(30), 832040);
    }
}

解説

フィボナッチ数列を返す関数を定義せよという問題です。30程度なら要らない気もしますが、プログラミングでの実装練習において「フィボナッチ数列」は「メモ化」の枕詞であり、この問題でもメモとして動的配列を使用してほしいようです。

lib.rs
pub fn fibonacci(n: u32) -> u32 {
    let n = n as usize;

    // 1.
    if n == 0 {
        return 0;
    }

    if n == 1 {
        return 1;
    }

    // 2.
    let mut memo = vec![0; n + 1];
    memo[0] = 0;
    memo[1] = 1;

    // 3.
    for i in 2..=n {
        memo[i] = memo[i - 2] + memo[i - 1];
    }

    memo[n]
}

処理の詳細になります。

  1. 計算不可能な特定の値に対するガード節
    • 再帰で書く場合は再帰を終わらせるために必須のもので、再帰実装も試していたのでその名残です
  2. 必要分のサイズを持つ動的配列 memovec! マクロにより作成
    • 計算に必要な初期値も代入
  3. for 文で答えを計算

また本エクササイズでは解説することがあまりない... vec![0; n + 1] だと n の値がコンパイル時にわからないから、静的配列ではなく動的配列を使う必要がある、ということがわかればとりあえず良しです!

C言語のVLA

あんまり他言語に苦言を呈するのはよろしくないですが、母国語C言語に対して色々ある不満の一つに、C99から追加されたVLA (Variable Length Array) という機能があります。このVLAを使用すると、静的配列と同じ記法で可変長配列を宣言できます。

https://qiita.com/raccy/items/bfcb62086c5f027d57b6

下記コードはC11等ではコンパイルが通りちゃんと動作します。え??

C
#include <stdio.h>

int main(void) {
    int lngth;
    scanf("%d", &lngth);

    // コンパイル時サイズ不定なのに静的配列みたいに書けちゃうの...??
    int array[lngth];

    for (int i = 0; i < lngth; i++) {
        array[i] = i;
        printf("%d\n", array[i]);
    }

    return 0;
}

本来可変長配列は malloc 関数を使ってヒープ上に動的に確保されるべきです(過激派)。この機能が実装された後にC言語を学んだ初学者は「 malloc 関数ってなんですか?」となること請け合いです!こんなお節介改良のせいで、スタックとヒープというコンピュータサイエンスで必要な知識の説明機会が後延ばしになってしまっているのです1。後から長さを変えるなどはできないらしい(可変長という和訳はミスリードでは...?)のがまだ救いでしょうか。

言語はアップデートされていくものではありますが、正直自分はC言語には「教育用言語」としての役割を期待しているので、この改良はやめてほしいなぁとか思ってしまいました...古き良きC言語で転んでRustを始めるのです...(強い思想)

では次の問題に行きましょう!

次の記事: 【20】 動的配列のリサイズ・イテレータ ~またまたトレイト登場!~

  1. VLAのせい(おかげ?)でmallocに気づかずに課題を終えていた友人が実際にいました。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0