时间戳

首页 > 解决方案 > 当忽略某些值时，如何在迭代器实现中避免不必要的昂贵操作？

rust - 当忽略某些值时，如何在迭代器实现中避免不必要的昂贵操作？

问题描述

我有一个Iterator看起来像这样的实现：

struct MyType {
    // stuff
}

struct Snapshot {
    // stuff
}

impl MyType {
    pub fn iter(&mut self) -> MyIterator {
        MyIterator {
            foo: self
        }
    }
}

struct MyIterator<'a> {
    foo: &'a mut MyType
}

impl<'a> Iterator for MyIterator<'a> {
    type Item = Snapshot;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cheap_condition() {
           self.cheap_mutation();  // Inexpensive
           let s: Snapshot = self.snapshot();  // Expensive copying
           Some(s)
        } else {
           None
        }
    }
}

如果我想使用 generate 的每个实例，这很好用Snapshot，但是如果我想使用Iterator::step_byor之类的东西Iterator::last，我不关心中间Snapshots，生成那些未使用的值所产生的成本是一个巨大的性能损失。

我可以重写每一个方法，Iterator这样昂贵的操作只在必要时发生，但我觉得必须有一种更简单、更惯用的方法来做到这一点，或者一种懒惰地Snapshot从中间类型生成与迭代对应的方法因为Item如果Iterator::next没有再次被调用。

我不想返回对 的引用MyType，因为我希望我生成的sSnapshot具有独立的生命周期，例如，使 的结果比 的实例寿命更长。Iterator::collect()MyType

标签： rustiteratortraitslazy-evaluationiterator-traits

解决方案

您不必重写每个Iterator方法。唯一相关的是nth, last, count,step_by和skip。所有其他方法都需要Self::Item以某种方式进行检查，因此您无法避免Snapshot为这些方法生成 s。幸运step_by的是，在内部skip使用nth，所以我们只剩下nth, count, 并且last我们必须覆盖它：

use core::marker::PhantomData;

struct Snapshot;

struct MyType<'a> {
    item: PhantomData<&'a ()>,
}

impl<'a> MyType<'a> {
    fn cheap_condition(&self) -> bool {
        todo!()
    }
    fn cheap_mutation(&mut self) {
        todo!()
    }
    fn snapshot(&self) -> Snapshot {
        Snapshot
    }
}

impl<'a> Iterator for MyType<'a> {
    type Item = Snapshot;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cheap_condition() {
            self.cheap_mutation(); // Inexpensive
            Some(self.snapshot()) // Expensive
        } else {
            None
        }
    }

    // also covers skip & step_by methods
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        for _ in 0..n {
            if self.cheap_condition() {
                self.cheap_mutation();
            } else {
                return None;
            }
        }
        self.next()
    }

    fn count(mut self) -> usize
    where
        Self: Sized,
    {
        let mut count: usize = 0;
        while self.cheap_condition() {
            self.cheap_mutation();
            count += 1;
        }
        count
    }

    fn last(mut self) -> Option<Self::Item>
    where
        Self: Sized,
    {
        while self.cheap_condition() {
            self.cheap_mutation();
            if !self.cheap_condition() {
                return Some(self.snapshot());
            }
        }
        None
    }
}

操场

如果您想通过检查谓词来使其他Iterator方法（例如惰性），而不是您必须为此定义自己的-like 特征，因为所有其他方法仅适用于.filterMyType<'a>SnapshotIteratorSelf::Item

推荐阅读