Want to iterate over a sequence of integers - several different possible sequences returned by a function. I expected the below would work, but it doesn't - the .rev() arm has a different type.
The default arm would also have a different type without .step_by(1)
That doesn't seem reasonable?
fn ray(i: usize, ray: usize) -> impl Iterator<Item = usize> {
match ray {
0 => (i + 8..7 * 8 + 1 + i % 8).step_by(8), // w
1 => (i % 8..i - 8 + 1).step_by(8).rev(), // e
_ => (0..0).step_by(1),
}
}
Iterator combiners take one iterator type and return another, usually as some sort of wrapper. So a different chain of combinators is going to be a different type.
There might be some convolutions in this particular case to make things the same type without type erasure, but that's probably easiest "out" to code .
fn ray(i: usize, ray: usize) -> Box<dyn Iterator<Item = usize>> {
match ray {
0 => Box::new( (i + 8..7 * 8 + 1 + i % 8).step_by(8) ), // w
1 => Box::new( (i % 8..i - 8 + 1).step_by(8).rev() ), // e
_ => Box::new( (0..0).step_by(1) ),
}
}
The takeaway here is that -> impl Trait allows you to return any type that implements the trait, but it must be a specific type. It is the same as naming the type, but allows the compiler to infer the name for you. (And sometimes it is impossible to name a type, so you must let the compiler do it).
-> dyn Trait would be the way to allow you to return different types that implement the trait. But since dyn Trait is unsized you need to make it sized, which is where the Box comes in for the first solution. The problem with this solution is that is does a relatively expensive heap allocation.
The second solution wraps both iterator types in a single type, allowing that type to be the inferred return type. It avoids the allocation, but as @steffahn demonstrates, gets uglier if more than 2 types need to be wrapped.
Thanks for that - seems to run efficiently so I assume there is zero cost for wrapping in Left/Right and also for tacking on step_by(1) to get the type to match?
I ended up with the below which has 8 arms - but two types are sufficient - it's the squares a queen can move to on an empty chess board. Works - but the extra cruft to get the types to check out is not pretty...
use either::Either;
fn ray(j: usize, ray: usize) -> impl Iterator<Item = isize> {
let i = j as isize;
match ray {
0 => Either::Left((i + 8..7 * 8 + 1 + i % 8).step_by(8)), // w
1 => Either::Right((i % 8..i - 8 + 1).step_by(8).rev()), // e
2 => Either::Left((i + 1..(i / 8) * 8 + 8).step_by(1)), // 2=n
3 => Either::Right(
((i / 8) * 8..i).step_by(1).rev(), // 3=s
),
4 => Either::Left((i + 9..min(64, i + (8 - i % 8) * 9)).step_by(9)),
5 => Either::Right(
(i - 7 * min(i / 8, 7 - i % 8)..i) // 5=u=ne
.step_by(7)
.rev(),
),
6 => Either::Left(
(i + 7..min(64, i + i % 8 * 7 + 1)) // 6=v=sw
.step_by(7),
),
7 => Either::Right(
(i - 9 * min(i / 8, i % 8)..i) // 7=x
.step_by(9)
.rev(),
),
_ => Either::Left((0..0).step_by(1)),
}
}
Why do you want to return iterators here? That's 28 bytes at most, or, maybe even better, 64 bits with representation of accessible fields. Much cheaper and simpler to pass around than iterators.
Not even on AVR this would make sense: all data size savings would be eaten by increase in size of the code.
Of course there is overhead.[1] The next method for the Either Iterator will meet to match on the Either variant, so there's potential for overhead in every iteration. This kind of iterator is one of those typical cases where for_each (or many other iterator methods that do the whole iterator with one method call) has the potential to be better than a for loop, because the for_each will also only need to match once, but for the whole iteration.
Similarly, step_by will make next() delegate to usage of nth() on the underlying iterator (as far as I can tell, in the current standard library implementation) which for ranges will be likely minimal overhead, as I'd assume this will end up effectively in adding this 1 stored in the StepBy iterator to be breaded and added instead of a sort of hard-coded/compiled increment operation.
Now, compared to usage of Box<dyn Iterator…>, the overhead from Either and step_by is likely smaller, so yeah.. the observation that it "runs efficiently" is probably an accurate one, too, and after all, "overhead" compared to what alternative would we even be discussing?
Unless perhaps if the use site is so specific that the optimizer manages to get rid of all overhead. ↩︎
Getting it is easy - shoving it inside your loved one and smuggling it across the border is not.
Why use iterators - because I want to iterate over the individual positions regardless of whether they are precomputed or calculated on the fly.
Precomputing is manageable - but you are underestimating the size. With bitmaps one result fits in a 64-bit word. For the whole board it is 64*64. Bishop and rook would need their own bitmaps - can't share as they do with the above function - though queen bitmap could be derived.
That space is manageable - 3*64*64 = 12288 bits - but it is still not obviously faster when you have to filter out the individual bits to get the same sequences.
Maybe I don't understand something you don't understand something.
You do know that on modern CPU's (for some definition of modern… basically anything newer that 80386 which was presented 38 years ago) there are leading_zeros and trailing zeros functions, right? On modern CPUs (this time really modern: Ryzen, latest generations of Intel Core, ARM CPUs made in last 5-7 years) you can execute these instructions as fast as normal aritmetic instructions. Certainly much faster then these iterators which would execute half-dozen if not dozen instructions for each position.
The big question is whether you would push out other things from L1 cache, but 12288 bis is only 1.5K, thus everything should work fine.
