Rust 迭代scan - 條件累加並回傳迭代器

Rust 迭代scan - 條件累加並回傳迭代器

  11月 20, 2023    LaGee

---

Scan 

Scan和Fold[1]很像

都是有一個累加器

可以累加執行閉包後的數值

差別在於Scan回傳的是一個迭代器

Fold則是回傳一個值

Scan被分類在iter

文件[2]這樣解釋Scan

    fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>

    where

        Self: Sized,

        F: FnMut(&mut St, Self::Item) -> Option<B>,

self 為一個迭代器

需要有一個初始值以及閉包，閉包內需要兩個元素

一個為內部狀態，另一個為迭代器的值

最後回傳一個迭代器

而所謂的狀態與fold的累加器很像

只是累加器最後只會有一個值，狀態則最後則是疊加器

例子

舉一個簡單的例子

假設有一個數組1, 2, 3, 4...., 10

希望呈現 1、1 + 2、1 + 2 + 3、1 + 2 + 3 + 4 、 ... 、1 + 2 + 3 + 4 + 5 + ... + 10的迭代器

可以使用scan實現

    let res = (1..=10)

        .into_iter()

        .scan(0, |state, x| {

            *state = *state + x;

            Some(*state)

        })

        .collect::<Vec<_>>();

    println!("{:?}", res);

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

第一行為創建1..10的數組

第二行放入蝶愛器

第三行使用scan，包括初始值0、狀態state以及元素值x

第四行，因為state是&mut，必須解引用成i32才可以使用他

第五行則是回傳，因為scan閉包回傳值為Option，因此使用Some判斷裡面的值

最後則是輸出

可以看到滿足要求

應用

費波那契數(Successione di Fibonacci)[3]，又稱為黃金分割、費式數列

黃金分割指的是，一個整體會被切成兩塊

較大的那塊會是較小那塊的0.618

被公認為最能引起美感的比例

特別在文藝復興前後受到各地的歡迎[4]

不知道有沒有看過這張圖

圖片來源: Wikipedia 費波那契數[3]

這個數列滿足這個公式

• 
• ${\displaystyle {�}_1=1}$
• ${\displaystyle {�}_{�}={�}_{�-1}+{�}_{�-2}}$（${\displaystyle �\geqq 2}$）

也就是會呈現0, 1, 1, 2, 3, 5, 8, 13, 21...

假設題目希望算出n = 20內的所有黃金比例數值

就很適合用scan

解答

    let res = (1..=20)

        .into_iter()

        .scan((0, 1), |state, _| {

            let next = state.0 + state.1;

            *state = (state.1, next);

            Some(next)

        })

        .collect::<Vec<_>>();

    println!("{:?}", res);

[1, 2, 3, 5, 8, 13, 21, 34, 55, 89,

144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]

一樣先將數組放入迭代器中

但這次scan初始值要放兩個

初始值為0和1，因此輸入(0, 1)

state具有兩個值，第一個元素表示F(n-2)，第二個則是F(n-1)

以一開始來說，第一個元素為0，第二個元素為1

next 表示 F(n)，F(n)為F(n-2)+F(n-1)

算出現在的值後，需更新state

state放入F(n-1)，也就是state.1，與next

詳細可以看這張表

表1，透過scan實現費式數列詳細資料

參考資料

[1] https://lageeblog.blogspot.com/2023/10/rust-fold.html

[2] https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.scan

[3] https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0

[4] https://baike.baidu.hk/item/%E9%BB%83%E9%87%91%E5%88%86%E5%89%B2/115896