Binary search on lazy iterable

[leonardo]

This is a not particularly efficient solution to a little Euler Project problem in Rust:

fn e44() -> i32 {
    let ps: Vec<i32> = (2 .. 3_000).map(|n| n * (3 * n - 1) / 2).collect();

    ps
    .iter()
    .flat_map(|&i| ps.iter().map(move |&j| (i, j)))
    .filter(|&(i, j)| ps.binary_search(&(i + j)).is_ok() &&
                      ps.binary_search(&(j - i)).is_ok())
    .map(|(i, j)| (i - j).abs())
    .next()
    .unwrap()
}

fn main() {
    assert_eq!(e44(), 5_482_660);
}

This is a similar solution in D language:

import std.stdio: writeln;
import std.array: array;
import std.algorithm.iteration: map, filter;
import std.range: iota, assumeSorted, isRandomAccessRange;
import std.math: abs;
import std.algorithm.setops: cartesianProduct;

int e42() {
    auto ps = iota(2, 3000).map!(n => n * (3 * n - 1) / 2)/*.array*/.assumeSorted;
    static assert(isRandomAccessRange!(typeof(ps)));

    return cartesianProduct(ps, ps)
           .filter!(ij => ps.contains(ij[0] + ij[1]) &&
                          ps.contains(ij[1] - ij[0]))
           .map!(ij => abs(ij[0] - ij[1]))
           .front;
}

void main() {
    assert(e42() == 5_482_660);
}

It uses assumeSorted that returns a SortedRange. If you call contains on a SortedRange, you get a binary search. ps is a lazy iterable (because I've commented out the .array part that converts it to a dynamic array), but it's still a random-access range (as statically asserted by the successive line of code). The ij[0] are there because D lacks a tuple unpacking syntax.

In Rust a binary_search_by_key isn't enough to replace that well. Do you like the idea of performing a binary search on a lazy iterable in Rust?

[elidupree]

I feel it could be misleading to describe this as "binary search on lazy iterable", because in Rust, when I hear "lazy iterable", I would think of the Iterator trait, which cannot do a binary search like this (because it doesn't have random access). It appears that Rust did have a RandomAccessIterator trait, but it was deprecated: https://doc.rust-lang.org/1.3.0/std/iter/trait.RandomAccessIterator.html

How does the D implementation work internally? If it's not an array, I guess it must recompute the values each time the binary search needs to read them. A Rust approach to this could be to implement a binary search function that takes a Fn(usize)->Ordering instead of taking a slice and indexing it. Of course, this could be implemented in a crate and doesn't need support from the compiler or std.

[leonardo]

@elidupree

It appears that Rust did have a RandomAccessIterator trait, but it was deprecated:

I didn't know that, it looks useful (Perhaps).

If it's not an array, I guess it must recompute the values each time the binary search needs to read them<

Yeah, similarly to binary_search_by_key.

Of course, this could be implemented in a crate and doesn't need support from the compiler or std .

That's true for lot of things that today get added to the std lib.

[bluss]

Rust's pre-1.0 RandomAccessIterator only supported shared reference access (not mutable), and had a hopeless addiction to bounds checking. Not a very good ground to build things on top of.

I think a trait that abstracts some of what a slice can do (split into ranges and access those by index or by iterator, both shared and mutable), could be a good Rustic solution instead of a "random access iterator".

[bill_myers]

The binary_search crate lets you binary search on an arbitrary closure, which is the correct abstraction for what you want.