r/rust•
azerupi

Least square method - how to improve this code?

Hi,

I implemented the least square linear regression method. My code works and does what it is supposed. But I always have a feeling like it could be written in a much better way.

So to see how more experienced Rust programmers would write it, how could I improve this code:

fn least_square_slope<T>(points: &Vec<(T,T)>) where T: num::traits::ToPrimitive {

    let (x_mean, y_mean): (f64, f64) = (
        points.iter().fold(0f64, |acc, ref point| {
                acc + point.0.to_f64().unwrap()
            }
        ) / (points.len() as f64),

        points.iter().fold(0f64, |acc, ref point| {
                acc + point.1.to_f64().unwrap()
            }
        ) / (points.len() as f64)
    );

    let mut sum_x_diff_squared = 0f64;
    let mut sum_x_diff_y_diff = 0f64;

    for point in points {
        let x_diff = point.0.to_f64().unwrap() - x_mean;
        let y_diff = point.1.to_f64().unwrap() - y_mean;

        sum_x_diff_y_diff += x_diff * y_diff;
        sum_x_diff_squared += x_diff.powi(2);
    }

    let slope = sum_x_diff_y_diff / sum_x_diff_squared;

    println!("Slope: {}", slope);
}

Any suggestions are appreciated :)

Posted Jun 7, 2015, 7:55 AM UTC

1831
sellibitzerust•

Nothing related to the numerical algorithm, more of a Rust thing: Please avoid functions that take a &Vec<T> as parameter. Prefer &[T] instead. It's more general. &Vec<T> coerces to &[T] due to Vec<T> implementing Deref<[T]>, so, you don't even have to change the code where you invoke the function.

In this case, you could also take an iterator. For example:

fn least_squares_slope<I>(it: I) -> Option<f64> where I: Iterator<Item=(f64,f64)> + Clone {
    let (sumx, sumy, count) =
        it.clone().fold((0.0,0.0,0_isize), |(sx,sy,ct), (x,y)| {
            (sx + x, sy + y, ct + 1)
        });
    if count < 2 { return None; }
    let (meanx, meany) = (sumx / count as f64, sumy / count as f64);
    let (sxx, sxy) =
        it.fold((0.0,0.0), |(sxx,sxy), (x,y)| {
            let (dx, dy) = (x - meanx, y - meany);
            (sxx + dx*dx, sxy + dx*dy)
        });
    if sxx > 0.0 { Some(sxy / sxx) } else { None }
}

fn main() {
    let a = [(0.0, 0.0), (2.0, 3.0)];
    println!("slope is {}", least_squares_slope(a.iter().cloned()).unwrap());
}

But this may be overkill. If you always have the (x,y) pairs in an array, a function parameter of type &[(f64,f64)] should suffice and save you the additional .iter().cloned() at the call site.

8
azerupiOP•

Noted, I will not do it again ;)

Is &[T] the equivalent for arrays? What does indirection mean?

3
sellibitzerust•

The difference between &Vec<T> and &[T] is that &Vec<T> can only refer to a complete Vec while &[T] can refer to a subslice of a Vec's elements or something that is not even relaved to Vec at all, for example some slice of a "raw array" of known size. The reason we have Vec<T> is because we can't use [T] directly since [T] is a dynamically-sized type. But such types behind some kind of "indirection" (pointer, reference, box) are fine. Internally, Vec<T> also just stores a pointer to its elements along with some length and capacity information. But it's implemented in such a way that it feels like its elements are "inside" the Vec. :)

7
marcusklaas•

It could be even more general by accepting an IntoIterator. Then you won't have to change code at the call sites.

2
sellibitzerust•

IntoIterator is cool, yes. But in this case it would not help much at the call site because a borrowed slice/Vec will only convert into an iterator over borrowed items and a Vec's IntoIter is not Clone.

1
marcusklaas•

Are you sure about the borrowed slice part?

1
sellibitzerust•

Yes.

2
azerupiOP•

What would I have to change from @sellibitze's answer to make it work with IntoIterator ? I tried multiple things, but always get an error like:

error: the trait `core::iter::Iterator` is not implemented for the type `[(_, _); 2]` [E0277]
1
sellibitzerust•

The idea is the following:

fn more_fancy_slope<II>(ii: II) -> Option<f64>
where II: IntoIterator<Item=(f64,f64)>, <II as IntoIterator>::IntoIter: Clone {
    least_squares_slope(ii.into_iter()) // just invoke the other function
}

so that it does some conversions for you to make it a little more convenient.

But this function is not very useful in your case because you don't have any types that actually fit these requirements. The standard provides the following IntoIterator-based conversions that are relevant here:

Self<Self as IntoIterator>::ItemIs the iterator clonable?
Vec<T>Tno
&Vec<T>&Tyes
&[T]&Tyes
&[T;N]&Tyes

The error you got is due to raw arrays not implementing IntoIterator. You would have to borrow it first.

Of course, you could change the other function to expect a &(f64,f64) as item type to make this IntoIterator thing work for borrowed slices but that would be more restricting which is why I intentionally used Item=(f64,f64). You can create these kinds of values on-the-fly, for example as a result of map.

But an additional function like this:

fn slope_from_slice(points: &[(f64,f64)]) -> Option<f64> {
    least_squares_slope(points.iter().cloned())
}

seems like a good idea because these kinds of slices are common.

4
azerupiOP•

Very nice explanation! Thank you :)

2
azerupiOP•

In this case, you could also take an iterator

How would that affect the body of the function? I have tried, but I can't make it work

1
azerupiOP•

Ow woaw, this looks so much more beautiful ! Thank you very much, I would never have thought about this myself :)

1
sellibitzerust•

Thanks. :)

1
expugnator3000•

I ran it through gzip or something:

#![feature(core)]

pub fn least_square_slope(points: &[(f64, f64)]) {
    let x_mean = points.iter().map(|&(x,_)| x).sum::<f64>() / points.len() as f64;
    let y_mean = points.iter().map(|&(_,y)| y).sum::<f64>() / points.len() as f64;
    let sum_x_diff_squared = points.iter().map(|&(x,_)| (x-x_mean)*(x-x_mean)).sum::<f64>();
    let sum_x_diff_y_diff = points.iter().map(|&(x,y)| (x-x_mean)*(y-y_mean)).sum::<f64>();

    let slope = sum_x_diff_y_diff / sum_x_diff_squared;

    println!("Slope: {}", slope);
}

Only works on nightly, and is slower than your code (until LLVM merges the iterators somehow), but smaller code is more good, right? ;)

EDIT: &

4
azerupiOP•
points.iter().map(|&(x,_)| x)

I totally forgot that you could do this! Destructuring FTW! I don't have the right mindset yet..

I would have used sum() too, but I don't like to use "unstable" methods. So I stick with what is in "Stable" at the moment :)

Generally I like shorter code, but only if it is easier to read. In this case I think I prefer @sellibitze way, because it looks so elegant and it seems like it's iterating a lot less, but I could be wrong because I don't know the internals of fold, map, sum, ... and how the compiler optimizes them

2
Aatchrust•

Generally I like shorter code, but only if it is easier to read. In this case I think I prefer @sellibitze way, because it looks so elegant and it seems like it's iterating a lot less, but I could be wrong because I don't know the internals of fold, map, sum, ... and how the compiler optimizes them

The iterator adapters are pretty efficient and optimize well. The standard library ones have had more work on making them fast as well.

Most of the iterator adapters are lazy, meaning they only do work when they need to. So the closure you pass to map (which is statically dispatched and probably inlined anyway) is only called when you try to get the next element from the iterator. Fold and sum do work, but they're just slightly abstracted versions of the equivalent loop anyway.

3
azerupiOP•

I'm still not sure I do understand it well. Does a.iter().map(...).sum(...) cycle 2 times through the iterators or just once?

If it does have to loop through the iterators 2 times, then .fold(...) seems to me more efficient in the fact that it has to go through the iterators only once, right? Or am I completely mistaken?

1
expugnator3000•

It only cycles once, but my code calls sum() on the data 4 times, so it will loop 4 times in total (although LLVM could possibly merge the loops, but I'm not sure).

3
Gankrorust•

The iterator adapters are pretty efficient and optimize well.

Honestly I respectfully disagree. Fiddling around with various different idioms that amount to vec![0; n], LLVM seems to pretty frequently misoptimize them. Maybe they optimize better if you just use them for a for-loop and not collect...?

1
tektektektektek•

Can you please change &amp; to &? It would make your code so much more readable.

Also - can you please read your own post after posting and edit any obvious mistakes?

1
Atheriel•

Nice! I'd be interested to see the performance of these implementations compared to ones using Rust bindings to OpenBLAS, etc.

2
sandwichsaregood•

Just be careful to consider that LAPACK uses a totally different algorithm (QR/SVD + Householder) to solve it. OP's method is equivalent to solving the normal equations directly.

2
Atheriel•

That's true. I meant it more as a put-things-in-perspective exercise.

2
sandwichsaregood•

Yeah, what I was getting at was that a good comparison would be to using the standard dense-matrix solvers in LAPACK, not the actual least squares solvers.

But I mean, realistically I can already tell you what will happen... comparing to an optimized LAPACK implementation, for small problems there won't be any measurable difference or the Rust implementation will be marginally faster because of overhead, while for large problems LAPACK will absolutely crush it by order(s) of magnitude. That's not really that concerning though, LAPACK and BLAS are probably the most highly optimized codes in existence and it's pretty hard to even get into the same ballpark without specialized magic.

2
Atheriel•

For sure. Every time I read about LAPACK and BLAS all I can think about is that guy who hand-tuned the assembly routines for each CPU architecture...

2
nielsle•

Alternatively you can use for-loops. This is more verbose, but possibly also more transparent.

fn least_squares_slope(points: &[(f64,f64)]) -> Option<f64> {
    
    let mut sum_x = 0f64;
    let mut sum_y = 0f64;
    for &(x,y) in points {
        sum_x += x;
        sum_y += y;
    }
    
    let n = points.len() as f64;
    let mean_x = sum_x / n;
    let mean_y = sum_y / n;
    
    let mut sum_xx = 0f64;
    let mut sum_xy = 0f64;
    for &(x,y) in points {
        sum_xx += (x-mean_x)*(x-mean_x);
        sum_xy += (x-mean_x)*(y-mean_y);
    }

    if sum_xx > 0.0 { Some(sum_xy / sum_xx) } else { None }
}

fn main() {
    let data = vec![(0.0,2.0),(1.0,4.0),(2.0,6.0)];
    let slope = least_squares_slope(&data);
    println!("Slope: {:?}",slope);
}
1
azerupiOP•

Yeah, I have kind of a hybrid implementation :D

Actually i'm wondering what the difference is performance-wise between the simple for loop approach and the iterator adapters. I guess it's pretty similar since for loops use iterators also.. But if someone who actually knows, could give some insight on this, that would be nice :)

1
nielsle•

I don't have an answer, but rust has nice benchmarking tools, so you can check for yourself. :)

http://rustbyexample.com/meta/bench.html

2
azerupiOP•

That is so wicked cool ! :D

running 2 tests
test for_loop_slope  ... bench:     31825 ns/iter (+/- 1003)
test itterator_slope ... bench:     31803 ns/iter (+/- 934)

This is what I used for both test (except changing least_squares_slope_for(&a)):

#[bench]
fn for_loop_slope(b: &mut Bencher) {
    let mut a: Vec<(f64,f64)> = vec!();
    for i in 0..10000 {
        a.push((i as f64, (i as f64)*2f64));
    }
    // exact code to benchmark must be passed as a closure to the iter
    // method of Bencher
    b.iter(|| {
        least_squares_slope_for(&a)
    })
}

Pretty similar

Even with higher number of elements (1 000 000)

running 2 tests
test for_loop_slope  ... bench:   5451077 ns/iter (+/- 222847)
test itterator_slope ... bench:   5443483 ns/iter (+/- 709872)
2