Is there any way to avoid passing v around all the time to make the code cleaner?
After I sent the message last night, I attempted to make the helper take v: & ~mut [T] instead (or &mut ~[T] based on your last change): https://gist.github.com/0362eef759791558d13d but this gives the error "illegal borrow unless pure: creating immutable alias to mutable vec content" on the put(*v). It seems to me like this is safe so I filed https://github.com/mozilla/rust/issues/4331 but please correct me if I'm wrong here. I suppose it's probably not possible to get rid of the unsafe block with that approach. Ben On Wed, Jan 2, 2013 at 5:27 PM, Niko Matsakis <[email protected]> wrote: > Here is a revised version: > > https://gist.github.com/4439672 > > The only real change is the workaround for the lack of mutable function > arguments. Basically instead of a parameter `v: ~[mut T]` I changed it to > `v: ~[T]` and added `let mut v = v`. This takes advantage of inherited > mutability. It also means there is no need for unsafe code because the > compiler can see that the vector is owned by the permutation function and > thus allows it to be temporarily declared as immutable during the callback. > > > > Niko > > Ben Alpert wrote: > > Hi all, > > I was perusing the source code of vec::each_permutation and noticed the > comment: > > This does not seem like the most efficient implementation. You > could make far fewer copies if you put your mind to it. > > so I decided to try my hand at a faster version, which I have posted here: > > https://gist.github.com/48b14f37051e7b91c22c > > Code review would be appreciated. In particular, I did some awkward > shenanigans to pass v around my recursive function called 'helper' in > order to satisfy the ownership checker. Originally I had helper(v: > &mut [T], ...) -> bool, but that causes an error because put takes a > &[T]. It would be great if there was a simpler way to do this. > > For comparison, it seems to be around 100x faster on this trivial test: > > let mut i = 0; > for each_permutation(~[1,2,3,4,5,6,7,8,9,10,11]) |_| { i += 1; } > assert i == 39916800; > > Let me know whether it makes sense to open a pull request with this > new implementation. > > Thanks, > Ben > > P.S. I am puzzled by the fact that each_permutation is listed in the > docs but it's not marked as pub so it appears to be inaccessible from > outside the vec.rs > file. > _______________________________________________ > Rust-dev mailing list > [email protected] > https://mail.mozilla.org/listinfo/rust-dev _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
