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
