Why is it so slow? Java beats Rust? What's more, Rust doesn't beat Python too much

My original version used half-open bounds instead of inclusive bounds; perhaps that's the difference.

Still much faster than mine, great, :smiley:

Along similar lines, here's a version that uses the smallvec crate for the coordinates. If the dimensionality is small enough (<= 8 as written, but tunable), there won't be heap allocations.

use smallvec::SmallVec; // 1.5.1

type Coord = SmallVec<[u8;8]>;

struct CellIter {
    start: Coord,
    end: Coord,
    pending: Coord,
    done: bool,
}

impl Iterator for CellIter {
    type Item = Coord;
    fn next(&mut self) -> Option<Coord> {
        (!self.done).then(|| {
            let result = self.pending.clone();
            self.done = (0..self.pending.len()).rev().all(|i| {
                if self.pending[i] < self.end[i] {
                    self.pending[i] += 1;
                    false
                } else {
                    self.pending[i] = self.start[i];
                    true
                }
            });
            result
        })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        if self.done {
            (0, Some(0))
        } else {
            let mut x = 1_usize;
            let mut r = 1_usize;
            for i in (0..self.pending.len()).rev() {
                r += (self.end[i] - self.pending[i]) as usize * x;
                x *= (self.end[i] - self.start[i]) as usize + 1;
            }
            (r, Some(r))
        }
    }
}

impl ExactSizeIterator for CellIter {}

fn calc_cells(start: Coord, end: Coord) -> CellIter {
    assert_eq!(start.len(), end.len());
    CellIter {
        done: start.iter().zip(end.iter()).any(|(s, e)| s > e),
        pending: start.clone(),
        start,
        end,
    }
}

fn main() {
    let start = SmallVec::from_vec(vec![0, 0, 0]);
    let end:Coord = SmallVec::from_vec(vec![127,127,29]);
    let all_cells = calc_cells(start.clone(), end.clone()).collect::<Vec<_>>();
    let mut l = dbg!(all_cells.len());
    let mut iter = calc_cells(start, end);
    assert_eq!(iter.size_hint().0, l);
    while let Some(_) = iter.next() {
        l -= 1;
        assert_eq!(iter.size_hint().0, l);
    }
    assert_eq!(l, 0);
}

(Rust Playground)

4 Likes