iT邦幫忙

2024 iThome 鐵人賽

DAY 28
0

簡介

疊代器(iterators)是遍歷序列中每個元素的一種抽象。

  • 不同於傳統的索引訪問,疊代器通過定義好的疊代器接口逐一訪問序列中的元素,不支援隨機存取而是使用順序存取,因此雖然無法隨機跳到任意位置,優勢在於只在需要的時候才計算下一個元素,而不用擔心記憶體不足的問題。
  • 惰性初始化的特性,代表在我們實際呼叫方法顯式消費疊代器之前(例如在 for 循環中),不會觸發任何操作。

疊代器的定義

在 Rust 中疊代器是透過 Iterator 特徵來實現的,該特徵最低限度要求實作 next 方法,透過這個方法疊代器可以訪問下一個元素。呼叫 next 方法之後可能會有兩種結果:有值與沒有值,對應到 Option<T>Some<T> 以及 None,序列結束時回傳 None

基礎疊代器實作

最基本的疊代器用法如下:

fn main() {
    let v1 = vec![1, 2, 3];

    let v1_iter = v1.iter();

    for val in v1_iter {
        println!("{}", val);
    }
}

因為疊代器惰性初始化的特性,創建疊代器 v1_iter 時還不會有額外的性能消耗或動作,要等到疊代器被使用的時候元素才會被消耗,操作才會被執行。

實際上,即使我們不特別把向量用 iter 方法轉成疊代器, for 迴圈也可以正常運行:

fn main() {
    let v1 = vec![1, 2, 3];

    for val in v1 {
        println!("{}", val);
    }
}

這是因為 Rust 的設計中,許多常見的數據結構,如向量、陣列等,都隱含地實現了 Iterator 特徵,所以編譯器自動幫我們把向量轉換成疊代器再去操作了。

Iterator 特徵

看一下Iterator 特徵,這邊只列出next方法,後面還有很多其他方法是有預設實作的,所以大部分情況只需要實作 next 方法就可以用其他方法的預設實作。

pub trait Iterator {
    /// The type of the elements being iterated over.
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}

要實作 Iterator 特徵的話,還需要定義 Item 關聯型別,它會是被包在 Optionnext 的回傳型別。

因為 Rust 的標準庫已經為包含向量在內的各種集合類型提供了高效的疊代器實作,所以我們甚至也不用實作 next 方法,可以呼叫 next

fn main() {
    let v1 = vec![1, 2, 3];

    let mut v1_iter = v1.iter(); // 這裡要使用 mut,因為後續操作會改變疊代器

    match v1_iter.next() {
        Some(value) => println!("{}", value),
        None => println!("End of iterator"),
    }

    match v1_iter.next() {
        Some(value) => println!("{}", value),
        None => println!("End of iterator"),
    }
}

可以想像成一開始的 v1_iter 是虛擬的頭,要等到第一次呼叫 next 的時候我們才會真正移動到第一個元素的位置,之後每次呼叫 next 都會移往下一個元素。這種寫法要記得在疊代器變數前面加上 mut 告訴編譯器我們後續會改變它,前面 for 迴圈的版本不需要是因為沒有直接呼叫 next方法,而是讓 for 自動管理疊代器,它會在內部隱式地處理了疊代器的可變性,自動獲取疊代器並在每次迴圈迭代中呼叫 next。這些細節由 for自動管理,因此不需要顯式將疊代器標記為可變。

實際上在 Rust for element in collection 這種寫法是一種語法糖,編譯器會把這個語法糖展開成大概是下面這樣,底層其實就是疊代器。:

fn main() {
    let v1 = vec![1, 2, 3];

    // for number in v1 { // 編譯器會展開成呼叫疊代器的方式
    //     println!("{}", number);
    // }

    let mut v1_iter = v1.iter();

    while let Some(number) = v1_iter.next() {
        println!("{}", number);
    }
}

自定義疊代器

我們設計一個簡易版的 Node 結構,有另外一個 LinkedList 會包含多個 Node ,並實作 Iterator 這樣我們就能用疊代器的方式來操作 LinkedList
為了簡化,Node我們只用 Box<T>處理,不考慮共享所有權和內部可變性,然後 LinkedList 增加 Node 的方式限定往前端加,這樣把新增的 Nodenext 指向現有的 LinkedList 前端就好。

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node { value, next: None }
    }
}

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn prepend(&mut self, value: T) {
        let mut new_node = Box::new(Node::new(value));
        // 將新節點的 next 指向當前的 head
        new_node.next = self.head.take();
        // 將 head 指向新的節點
        self.head = Some(new_node);
    }
}

impl<T: Clone> Iterator for LinkedList<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.head.take()?;
        self.head = current.next; // 移到下一個節點
        Some(current.value.clone()) // 回傳當前節點的值
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.prepend(3);
    list.prepend(2);
    list.prepend(1);

    for value in list {
        println!("{}", value);
    }
}

實作 Iterator 可以思考呼叫第一次 next 之後希望取得的值是什麼,不然可能會和預想有落差,例如我中間調整好幾次要嘛只印出 2 和 3 或 1 和 2,要嘛印 3 陷入無限迴圈無法結束。以向量來說第一次呼叫 next 才會取得第一個索引的值,比照辦理的話可能疊代器設計上要有虛擬的頭, next 的邏輯會比較單純 。

取得不同元素版本的疊代器

相對 iter 方法內含的元素是不可變參考,還有 iter_mutinto_iter 分別對應可變參考和取得所有權的版本。

例如我想要修改原本向量上的元素就可以改用 iter_mut 取得可變參考來操作:

fn main() {
    let mut v1 = vec![1, 2, 3];

    let v1_iter = v1.iter_mut();

    for val in v1_iter {
        *val += 1
    }

    println!("{:?}", v1); // [2, 3, 4]
}

Iterator 其他方法

定義在 Iterator 特徵的方法除了 next 還有其他很多好用的方法,可以根據會不會消耗疊代器分為兩類:消費適配器疊代適配器

消費適配器

消費適配器(consuming adaptors)是指會呼叫 next 的方法,例如呼叫 sum:取得疊代器的所有權並重複呼叫 next 來遍歷所有項目把所有項目的數值加到總計,在遍歷結束時回傳總計。

fn main() {
    let v1 = vec![1, 2, 3];
    let v1_iter = v1.iter();

    let total: i32 = v1_iter.sum(); // v1_iter 被消耗,無法再次使用
    println!("{}", total); // 6
}

疊代配接器

疊代配接器(iterator adaptors)則是消費適配器以外的方法,它們不會消耗原有的疊代器,而是在原有的疊代器上加一些屬性,例如 map ,用一個閉包當作參數,每次疊代器被消耗的時候對應的值會傳給這個閉包進行操作。

fn main() {
    let v1 = vec![1, 2, 3];
    let v1_iter = v1.iter();
    let v2_total: i32 = v1_iter.map(|x| x + 1).sum(); // 方法可以串在一起直到把疊代器消耗掉
    println!("v2_total: {}", v2_total); // 9
}

如果是呼叫疊代配接器可以串接多個,因為它們的過程都不會消耗原有的疊代器。而這也呼應到疊代器的惰性初始化,也就是說,在這個過程不會有額外的動作觸發,一直等到疊代器被消耗才會真的執行

v2_total 編譯器會要求加上型別詮釋,原因是 sum 方法不足以判斷我們想要的實際型別是什麼。

collect 是另外一個常見的消費適配器,用來將疊代器中的元素收集到一個新的集合中
我們把疊代配接器(map)和消費適配器(collect)拆成兩行來寫:

use std::slice::Iter;
use std::iter::Map;

fn main() {
    let v1 = vec![1, 2, 3];
    let v1_iter: Iter<'_, i32> = v1.iter();
    let v2_iter: Map<Iter<'_, i32>, _> = v1_iter.map(|x| x + 1); // 可以分開寫
    let v2: Vec<i32> = v2_iter.collect(); // 等到需要時再消耗疊代器
    println!("{:?}", v2); // [2, 3, 4]
}

同樣的這邊呼叫 collect 的那行也必須加上型別詮釋。
為了方便解析,特別把 v1_iterv2_iter 也加上型別詮釋。

Iter 是 Rust 標準庫中的一個具體類型,而 Iterator 是一個特徵。兩者的關係在於 Iter 型別實現了 Iterator 特徵,使得 Iter 能夠作為疊代器來使用。
可以觀察到v2_iterv1_iter的型別是不一樣的,因為呼叫 map 的關係多包了一層邏輯,代表經過 map 轉換的疊代器,它在每次遍歷時會應用轉換邏輯(閉包)並回傳結果。如果再呼叫一次 map或其他疊代配接器就會再多一層。不過原始的疊代器都還是沒有被消耗

即使如此,我們在 v1_iter.map 操作後還是無法再使用 v1_iter,原因不是因為疊代器被消耗,而是因為 map 是會取得所有權的操作,這句代表所有權跑到 v2_iter 上了,如果要保有原有的向量,需要複製一份,不過就會多耗資源,必須看情況斟酌。

map 的源碼,可以看到是少見的用 self 不是 &self

    fn map<B, F>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        F: FnMut(Self::Item) -> B,
    {
        Map::new(self, f)
    }

filter 搭配獲取環境數值的閉包

再舉一個情況是過濾原有的向量元素,只留下限制內的數值:

fn main() {
    let limit = 2;
    let v1 = vec![1, 2, 3];
    let v1_iter = v1.iter();
    let filter_result: Vec<&i32> = v1_iter.filter(|&&x| x <= limit).collect();
    println!("{:?}", filter_result); // [1, 2]
}

如果不用閉包不用疊代器和 for語法糖,大概要寫成下面這樣:

fn filter(v: &[i32], limit: i32) -> Vec<&i32> {
    let mut result: Vec<&i32> = Vec::new();
    for i in 0..v.len() {
        if v[i] <= limit {
            result.push(&v[i]);
        }
    }
    result
}

fn main() {
    let limit = 2;
    let v1 = vec![1, 2, 3];

    let filtered_result = filter(&v1, limit);
    println!("{:?}", filtered_result); // [1, 2]
}

要建立新的向量、要用索引操作 for 迴圈,而整個 filter 函數用疊代器和閉包只要一行。

從這個例子就可以看出閉包和疊代器搭配之後精簡又清晰表達意圖的優勢。

總結來說疊代配接器的好處:

  • 函數式風格:疊代配接器讓我們可以以一種更為聲明式的方式來處理數據。
  • 可讀性高:疊代配接器使得程式碼更好讀、易理解。
  • 靈活性高:疊代配接器可以與其他 Rust 特性結合使用,實現高度定制化的數據處理。

和索引迴圈效能比較:

結論是,疊代器雖然是高階抽象,但經過編譯器優化之後編譯出來的程式碼和用索引迴圈效能相比也毫不遜色,甚至有些情況效能是更好的。

可以試著執行以下的程式碼看看,就算把順序調換結果也差不多,這個情況幾乎都是疊代器比較快,除了編譯器有針對疊代器做優化外,還有一個主要原因是疊代器版本不用檢查界限。

use std::time::Instant;

fn main() {
    let numbers: Vec<i64> = (0..100000000).collect();

    // 手寫迴圈版本
    let start = Instant::now();
    let mut sum_for = 0;
    for i in 0..numbers.len() {
        sum_for += numbers[i];
    }
    let duration = start.elapsed();

    println!("Sum using for loop: {}, took: {:?}", sum_for, duration);

    // 疊代器版本
    let start = Instant::now();
    let sum_iter: i64 = numbers.iter().sum();
    let duration = start.elapsed();

    println!("Sum using iterator: {}, took: {:?}", sum_iter, duration);
}

另外可以比較看看用 cargo runcargo run --release 的差別,--release 如以前提到的,是正式的編譯,才會做完整優化,差異十分巨大。

cargo run
Sum using for loop: 4999999950000000, took: 1.054879417s
Sum using iterator: 4999999950000000, took: 339.45675ms
cargo run --release
Sum using for loop: 4999999950000000, took: 30.10825ms
Sum using iterator: 4999999950000000, took: 13.721792ms

不過這邊不是完整的測試,不同電腦、不同次的執行結果可能會不太一樣,上面結果也只是我自己電腦執行幾次的結果而已,僅供參考,只能說疊代器至少效能不劣於手寫迴圈的版本。

結語

和閉包一樣,疊代器也是 Rust 其中一種零成本抽象。這代表的是我們可以用高階概念來撰寫程式碼但又同時享有低階程式碼的效能,這是 Rust 的核心精神。
既具有可讀性、彈性等優勢,效能又不會打折,這讓疊代器成為 Rust 裡面十分重要而且最常使用的工具,在各種處理資料的場合可以讓我們用高階的概念寫出精簡易懂的程式碼。疊代器還有許多沒有介紹到的方法,未來值得花時間自己另外探索!


上一篇
Day27 - 閉包
下一篇
Day29 - 巨集
系列文
螃蟹幼幼班:Rust 入門指南30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言