Running time of Vec<T>.iter().enumerate().map(...).skip(n) -- O(1) or O(n)?

Suppose we do a :slight_smile:

Vec.iter().filter(...).skip(n)

then it needs to be atleast O(n) time as we need to run the predicate function to filter the list before we even skip.

However, suppowe we do:

Vec.iter().enumerate().map(...).skip(n)

is this O(1) or O(n) time?

First: map() is lazy. Unless we call something like .collect() on a map() it is not evaluated.

Because skip() is called after map(), the map will execute for all items in the list. If you change to:

Vec.iter().enumerate().skip(n).map(...) // Calling skip before map

The map will be executed after skipping the items. You can test using something like:

pub fn main() {
    let data: Vec<i32> = vec![1, 2, 3, 4, 5, 6, 7];
    let res: Vec<i32> = data.iter().enumerate().map(|(_s, x)| {
        println!("Running for: {:?}", *x);
        *x * *x
    })
    .skip(2)
    .collect();
    
    
    println!("Res: {:?}", res);
}

Execution of above sample here.

1 Like

Thanks for the insightful response. I ran your Rust playground sample code.

I believe I misunderstood how map/skip interacts.

If we do:

let x = blahblah.map(f).skip(n).sum();

Interpretation A = map is lazy, we don't need the first n results. Therefore, f is NEVER called on the first n elements.

Interpretation B = Because of the .sum(), we need the the full result of blahblah.map(f).skip(n). To get this, we are going to force f to execute on all of blahblah, then skip the first n.

The rust playground code you posted clearly shows that (B) is the correct interpretation. I posted the question incorrectly assuming that (A) was how things worked.

I don't think this is set in stone however. The default version of skip uses nth to skip items. Map doesn't override skip nor nth so the iterator have to go through every item.

I don't know if there is a reason to not override them or if it's just not implemented yet.

This would be a nice optimization to have though.

The difference in behavior of map would be easily observable.

Specifically the docs say

Takes a closure and creates an iterator which calls that closure on each element.

So that optimization would be inconsistent with this statement. So I don't think it would be a good idea, especially given you can manually get it by switching the order of map and skip.

2 Likes

Damn side-effects, thank you for the clarification.

I was surprised by this claim, and indeed, it does not seem to be true. Code:

fn main() {
    let v = vec![1, 2, 3, 4, 5, 6];
    
    v.iter().map(|x| println!("{}", x)).take(3).collect::<Vec<_>>();
    v.iter().take(3).map(|x| println!("{}", x)).collect::<Vec<_>>();
}

output:

~\tmp> .\lol.exe
1
2
3
1
2
3

skip, not take.

fn main() {
    let v = vec![1, 2, 3, 4, 5, 6];
    
    v.iter().map(|x| println!("{}", x)).skip(3).collect::<Vec<_>>();
    v.iter().skip(3).map(|x| println!("{}", x)).collect::<Vec<_>>();
}

outputs

1
2
3
4
5
6
4
5
6
3 Likes

Ah had thank you :slight_smile: