Not logged in. Login

Exercise 9

Download and extract the code skeleton for this exercise. As last week, the code includes an outline of how to organize your work and some tests.

In this exercise, we will explore the Iterator trait in Rust.

For most of this exercise, any iteration will be done with an Iterator. You may not write loops in this exercise (except the two for loops specifically requested).

Iterators Are Efficient

You might look at the high-level code written around iterators and assume it's less efficient than a hand-written loop. Let's try it.

In sum.rs, write functions that calculate the sum of the values in a &Vec<i64>

  • sum_loop_index: counting from 0 to v.len()-1 and index into the vector in a for loop (i.e. C-style).
  • sum_loop_iter: iterate the vector in a for loop (for value in vector) and add the values.
  • sum_fold: using an iterator over the vector (vector.iter() or vector.into_iter()) and its .fold method.
  • sum_method: using an iterator over the vector and its .sum method.

Have a look at the provided benchmark code: if iterators add significant overhead, we would expect the iterator-based solutions to be slower.

Iterators Are Lazy

In primes.rs, write these functions:

  • factors_iterator that returns an iterator of the factors of n (not including 1 and n). Hint: you can create an iterator of useful integers with "(2..=n/2)".
  • factors that uses factors_iterator and returns a Vec of the factors of n. Hint: collect.
  • is_prime that uses factors_iterator and determines if the number is prime or not: primes will have an empty iterator of factors. Hint: look at what .next() returns for an iterator.

The function factors_iterator needs to return a something that implements Iterator<u64>. The specified return type "impl Iterator<Item=u64>" indicates exactly that.

Now we can test the assertion that iterators are lazily evaluated. Since is_prime needs only one value from the iterator of factors, we would expect is_prime to return quickly for a large even number (because it can find the factor 2 quickly and discard the rest of the calculation). If it's slow for a large even number, we would suspect it's strictly evaluated.

Have a look at the provided benchmark code: 7919 is prime, so the possible factors must be exhaustively searched; 7920 is a similarly-sized even number. If they take a similar amount of time, there's a problem with your is_prime implementation. If the 7920 check is fast, we can see the factors_iterator result being lazily evaluated.

Iterators Are Useful

In inventory.rs, you'll find a basic definition for a struct InventoryItem.

  • total_value: the sum of the count times the cost of each item.
  • out_of_stock: create and return a vector of the items that have count 0.
  • explode: a vector of the inventory items representing the same "inventory" but with all counts 1. That is, an item with .count==3 should produce three identical items with the count changed to 1. Hint: .flat_map()

The argument types here (impl IntoIterator<…>) are a way to specify "anything that implements the IntoIterator trait.

Submitting

Submit your files through CourSys for Exercise 9.

Updated Tue July 04 2023, 13:09 by ggbaker.