こちらの記事 で Rust 0.5 向けに書かれたクイックソートのコードが紹介されていた。が、よく読むと、借用関連で、Rust 1.0 以降ではできなさそうな点があった。
fn partition<T: Ord>(ns: &mut [T], l: uint, r: uint) -> uint {
let p = &mut ns[l];
let mut i = l + 1;
for uint::range(l+1,r) |j| {
if ns[j] < *p {
ns[i] <-> ns[j];
i += 1;
}
}
ns[l] <-> ns[i-1];
i - 1
}
// 以下略
let p = &mut ns[l]; で、配列のスライスの１要素についてのミュータブルな参照を変数に束縛し、その束縛が有効な間に、ns[i] <-> ns[j]; で、同じスライスの別の２つの要素をスワップしている。スワップということは、こちらもミュータブルな参照が必要なはず。
たしかにこの３つの要素は別の値を指しているので、安全性では問題ないはずだけど、Rust 1.0 以降で同じスライスから２つのミュータブルな参照を持てたかなと、疑問に思ったわけだ。
コードを Rust 1.0 以降向け（1.6安定版を使用）に書き換えてみると、やはり、コンパイルエラーになった。
fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
let pivot = &mut ns[left];
let mut i = left + 1;
for j in (left + 1)..right {
if ns[j] < *pivot {
ns.swap(i, j);
i += 1;
}
}
i -= 1;
ns.swap(left, i);
i
}
コンパイルエラー：
src/quicksort-1.6-0.rs:5:12: 5:14 error: cannot borrow `*ns` as immutable because `ns[..]` is also borrowed as mutable [E0502]
src/quicksort-1.6-0.rs:5 if ns[j] < *pivot {
^~
src/quicksort-1.6-0.rs:2:22: 2:30 note: previous borrow of `ns[..]` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `ns[..]` until the borrow ends
src/quicksort-1.6-0.rs:2 let pivot = &mut ns[left];
^~~~~~~~
src/quicksort-1.6-0.rs:13:2: 13:2 note: previous borrow ends here
src/quicksort-1.6-0.rs:1 fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
...
src/quicksort-1.6-0.rs:13 }
^
src/quicksort-1.6-0.rs:6:13: 6:15 error: cannot borrow `*ns` as mutable more than once at a time [E0499]
src/quicksort-1.6-0.rs:6 ns.swap(i, j);
^~
src/quicksort-1.6-0.rs:6:13: 6:15 help: run `rustc --explain E0499` to see a detailed explanation
src/quicksort-1.6-0.rs:2:22: 2:30 note: previous borrow of `ns[..]` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `ns[..]` until the borrow ends
src/quicksort-1.6-0.rs:2 let pivot = &mut ns[left];
^~~~~~~~
src/quicksort-1.6-0.rs:13:2: 13:2 note: previous borrow ends here
src/quicksort-1.6-0.rs:1 fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
...
src/quicksort-1.6-0.rs:13 }
^
src/quicksort-1.6-0.rs:11:5: 11:7 error: cannot borrow `*ns` as mutable more than once at a time [E0499]
src/quicksort-1.6-0.rs:11 ns.swap(left, i);
^~
src/quicksort-1.6-0.rs:11:5: 11:7 help: run `rustc --explain E0499` to see a detailed explanation
src/quicksort-1.6-0.rs:2:22: 2:30 note: previous borrow of `ns[..]` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `ns[..]` until the borrow ends
src/quicksort-1.6-0.rs:2 let pivot = &mut ns[left];
^~~~~~~~
src/quicksort-1.6-0.rs:13:2: 13:2 note: previous borrow ends here
src/quicksort-1.6-0.rs:1 fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
...
src/quicksort-1.6-0.rs:13 }
^
error: aborting due to 3 previous errors
内容は、pivot のミュータブルな参照が有効な間に、イミュータブルな参照 if ns[j] も、ミュータブルな参照 ns.swap(i, j) もできません、というもの。
実は pivot はイミュータブルでいいので、let pivot = &ns[left] も試してみたが、ns.swap(i, j) でミュータブルな参照が必要なので、結局はコンパイルエラーになってしまう。
調べてみたところ、３つの解決法が見つかった。
解決法１：参照を変数に束縛しない
変数 pivot にスライスの参照が束縛しているから他とコンフリクトするわけで、それをやめればよい。このプログラムでは、pivot が参照している &ns[left] の値は、pivot が必要な間は変更されないので、このように書き換えても問題なく動く。
fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
let mut i = left + 1;
for j in (left + 1)..right {
if ns[j] < ns[left] {
ns.swap(i, j);
i += 1;
}
}
i -= 1;
ns.swap(left, i);
i
}
let pivot = &mut ns[left]; を削除して、if ns[j] < *pivot の代わりに if ns[j] < ns[left] とした。
解決法２：値を複製（clone）する
値が変更されないということは、値を複製（clone）してもいい。複製された値は元の ns[left] とは別物なので、コンフリクトしない。
fn partition<T: PartialOrd + Clone>(ns: &mut [T], left: usize, right: usize) -> usize {
let pivot = ns[left].clone();
let mut i = left + 1;
for j in (left + 1)..right {
if ns[j] < pivot {
ns.swap(i, j);
i += 1;
}
}
i -= 1;
ns.swap(left, i);
i
}
let pivot = ns[left].clone(); を追加した。なお、clone() メソッドを呼べるようにするために、ジェネリックのトレイト制限に Clone を追加した。
解決法３：スライスの借用を分割する
これは、Rust のアドバンスドユーザー向けの dark arts（魔術）本、「The Rustonomicon -- The Dark Arts of Advanced and Unsafe Rust Programming」の、「Borrow Splitting」の章で解説されていた方法。
と言っても、別に邪悪でも何でもない方法で、Rust のスライスプリミティブに用意されたメソッド split_at_mut() を呼ぶだけ。このメソッドを使うと、既存のスライスを、要素がオーバーラップしない２つのミュータブルなスライスに分割でき、それぞれを別に借用することが可能となる。
fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
let mut i = 0;
{
let (ns_left, ns_right) = ns.split_at_mut(left + 1);
let pivot = &ns_left[left];
for j in 0..(right - left - 1) {
if ns_right[j] < *pivot {
ns_right.swap(i, j);
i += 1;
}
}
}
i += left;
ns.swap(left, i);
i
}
ちなみに、split_at_mut() メソッドの中では unsafe ブロックを使用しているが、作られるスライスは全く安全なもので、使用にあたっての注意は必要ない。
fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
let len = self.len();
let ptr = self.as_mut_ptr();
assert!(mid <= len);
unsafe {
(from_raw_parts_mut(ptr, mid),
from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
}
}
今回のケースでは、この方法は少しやり過ぎな感があるが、覚えておくと何かの時に役立つかもしれない。
まとめ
- スライスプリミティブの借用は、スライス全体に対して行われる。要素単位ではない。
- スライスプリミティブの
split_at_mut()やsplit_at()メソッドを使うと、既存のスライスを、要素がオーバーラップしない２つのスライスに分割できる。これにより、それぞれを別に借用することが可能となる。
付録：Rust 1.0 以降向けに書き換えたクイックソートプログラム
- 解決法１を採用
- Rust 1.6 安定版での動作を確認済み
- こちらの記事に掲載されている Rust 0.5 向けのコードを元にした
- これは勉強目的のコード。スライスプリミティブには、sort() メソッドが用意されているので、通常はそちらを使うべき。
fn partition<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
let mut i = left + 1;
for j in (left + 1)..right {
if ns[j] < ns[left] {
ns.swap(i, j);
i += 1;
}
}
i -= 1;
ns.swap(left, i);
i
}
fn quicksort<T: PartialOrd>(ns: &mut [T], left: usize, right: usize) -> usize {
if right - left <= 1 {
0
} else {
let pivot = partition(ns, left, right);
let a = quicksort(ns, left, pivot);
let b = quicksort(ns, pivot + 1, right);
a + b + (right - left - 1)
}
}
fn main() {
let mut nums = [1, 3, 2, 5, 10, 4, 6, 7, 8, 9];
let len = nums.len();
println!("{:?}", &nums);
println!("");
quicksort(&mut nums, 0, len);
println!("{:?}", &nums);
assert_eq!([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], nums);
}