TLDR
関数などの引数に range を受け取って普通にイテレーションするとき(簡単のため u64 を使っています)
use std::ops::RangeBounds;
use std::iter::IntoIterator;
pub fn sum_n<R: RangeBounds<u64> + IntoIterator<Item=u64>>(range: R) -> u64 {
let mut result = 0;
for r in range {
result += r
}
return result
}
普通にイテレーションするわけではなく、 start と end の値がほしいとき
use std::ops::{Bound, RangeBounds};
pub fn sum_1<R: RangeBounds<u64>>(range: R) -> u64 {
let start = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Excluded(&s) => s + 1,
Bound::Included(&s) => s,
};
let end = match range.end_bound() {
Bound::Unbounded => panic!("end_bound should be decided"),
Bound::Excluded(&t) => t - 1,
Bound::Included(&t) => t,
};
assert!(start <= end);
(start + end) * (end - start + 1) / 2
}
※ スライスの範囲を指定するように使うときは、end_bound は Included のほうで +1 することが多いと思います。(そういうときは最大のサイズ max_len がどこかに存在すると思います)
let end = match range.end_bound() {
Bound::Unbounded => max_len,
Bound::Excluded(&t) => t.min(max_len),
Bound::Included(&t) => (t + 1).min(max_len),
};
Range 構造体
Range 構造体は、for 文などでよく使っている 0..10 のようなものです。
主には、 std::ops::Range です。
let mut result = 0;
for i in 0..10 {
result += i
}
assert_eq!(result, 45)
実は、 Range の他にも RangeFrom や RangeToInclusive などいろいろあります 。
start..end や start.. や ..=end などはそれぞれ違う構造体で表現されているんですね。
RangeBounds トレイト
Range 構造体の他にも RangeFrom 構造体や RangeToInclusive 構造体などがありました。しかし、これらは全て範囲を表すオブジェクトなので、共通するインターフェースが用意されていると嬉しいですよね。それが RangeBounds トレイトです。
Range 構造体や RangeFrom 構造体、 RangeToInclusive 構造体などにはこの RangeBounds トレイトが実装されています。
総和を計算する
RangeBounds トレイトの使用例として、受け取った範囲の和を返す関数を作成してみます。
use std::iter::IntoIterator;
use std::ops::RangeBounds;
pub fn sum_n<R: RangeBounds<u64> + IntoIterator<Item = u64>>(range: R) -> u64 {
let mut result = 0;
for r in range {
result += r
}
result
}
foldなど使えばfor文を使わずに書けますが、ここではfor文を使って書いておきます。
参考:
この sum_n 関数は、次のように使うことができます。
fn main() {
assert_eq!(sum_n(1..10), 45);
assert_eq!(sum_n(1..=10), 55);
}
しかし、この関数にはいくつか問題があります。..end のように書いたときの RangeTo などの構造体は、RangeBounds は実装しているものの、Iterator は実装していません。当然と言えば当然ですが、始点の情報がないのでイテレーションすることができません。次のように書くとコンパイルエラーとなってしまいます。
fn main() {
assert_eq!(sum_n(..10), 45);
}
error[E0277]: `RangeTo<u64>` is not an iterator
--> src/main1.rs:2:22
|
2 | assert_eq!(sum_n(..10), 45);
| ----- ^^^^ if you meant to iterate until a value, add a starting value
| |
| required by a bound introduced by this call
|
= help: the trait `Iterator` is not implemented for `RangeTo<u64>`
= note: `..end` is a `RangeTo`, which cannot be iterated on; you might have meant to have a bounded `Range`: `0..end`
= note: required because of the requirements on the impl of `IntoIterator` for `RangeTo<u64>`
また、単純に前から順に足していっているので、最初の値 start と最後の値 end が離れていると、当然処理に時間がかかってしまいます。さらには、end を指定しない、start.. のように書いたときの RangeFrom 構造体を渡してしまうと、この関数は、リリースビルドでは、無限ループに陥ってしまいます(デバッグビルドでは加算のオーバーフローでプログラムが終了します)。
イテレーションするだけなら RangeBounds は用いる必要がないですが、引数が Range (など)であってほしい、ということを型のレベルで表現することができるので、望まない入力をコンパイルエラーにできることはうれしいですね。
総和を効率化する
さて、先ほどの sum_n 関数では、最初の値 $s$ と最後の値 $t$ が大きく離れていると、計算に時間がかかってしまいました。幸いなことに、皆さんご存じの通り、 $s$ から $t$ までの和を計算する公式があります。
$$
\sum_{i=s}^{t} i = \frac{(s + t)(t - s + 1)}{2}
$$
先ほどの方法では時間計算量は $O(t-s)$ ですが、この方法であれば $O(1)$ です。どれだけ離れた $s$ と $t$ を持ってきても計算時間は(理論上)変わらないのでうれしいです。
これはRustのプログラムでは、次のsum_1 関数のように書けます。
use std::ops::{Bound, RangeBounds};
pub fn sum_1<R: RangeBounds<u64>>(range: R) -> u64 {
let start = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Excluded(&s) => s + 1,
Bound::Included(&s) => s,
};
let end = match range.end_bound() {
Bound::Unbounded => panic!("end_bound should be decided"),
Bound::Excluded(&t) => t - 1,
Bound::Included(&t) => t,
};
assert!(start <= end);
(start + end) * (end - start + 1) / 2
}
なんか長いですね、そのあたりについては最後に少し詳細を書きたいと思います。やっていることは単純で、RangeBound トレイトによって提供される start_bound メソッドと end_bound メソッドで最初と最後の値を持ってきているだけです。ただし、..end の場合と ..=end の場合で、end の値は 1 多かったり少なかったりします。それを表すのが Bound::Excluded や Bound::Included ですね。 Bound::Unbounded は単純に値が指定されていないことを表します。 start についても Excluded が用意されていますが、普通に使っている限りは start が Excluded になることは無いと思います(標準では用意されていないので)。
この sum_1 関数は、次のように使うことができます。
fn main() {
assert_eq!(sum_1(1..10), 45);
assert_eq!(sum_1(1..=10), 55);
assert_eq!(sum_1(..10), 45);
// println!("{}", sum_1(1..)); // panic!
}
最後にコメントアウトしている行は、range の最後を指定していないため、panic! するように sum_1 関数で記述されています。ここで適当な上限の値を好きに書いておけば、panic! を避けることもできます。range の最後を指定しないとき、初めの sum_n 関数では無限ループに陥ってしまっていましたが、この方法を使えば無限ループは避けることができます。
スライスの範囲を指定する場合
さて、ここまでは単純に range の和を扱ってきましたが、range はスライスの範囲を指定する用途で使用されることも多いと思います。
fn main() {
let v = vec![1, 2, 3, 4];
println!("{:?}", &v[1..3]) // [2, 3]
}
このようなものを表現したいときは、先ほどの sum_1 関数とは、end_bound の1足したり引いたりが少し変わってくると思います。
use std::ops::{Bound, RangeBounds};
pub fn range_decide<R: RangeBounds<usize>>(range: R, len: usize) -> (usize, usize) {
let start = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Excluded(&s) => s + 1,
Bound::Included(&s) => s,
};
let end = match range.end_bound() {
Bound::Unbounded => len,
Bound::Excluded(&t) => t.min(len),
Bound::Included(&t) => (t + 1).min(len),
};
assert!(start <= end);
(start, end)
}
fn main() {
let max_len = 100;
assert_eq!(range_decide(5..10, max_len), (5, 10));
assert_eq!(range_decide(5..=10, max_len), (5, 11));
assert_eq!(range_decide(0.., max_len), (0, 100));
assert_eq!(range_decide(..10, max_len), (0, 10));
assert_eq!(range_decide(..=10, max_len), (0, 11));
assert_eq!(range_decide(.., max_len), (0, 100));
assert_eq!(range_decide(5..5, max_len), (5, 5));
}
半開区間で表したいときはこちらの方がいいですね。
なんか長いがなぜか
スライスの範囲を指定するときと同じ様子で end_bound に1を足す std::slice::range メソッドが、標準で用意されています(2022/07/17 現在 nightly-only ですが…)。
この関数は、第一引数に任意の RangeBounds<usize> を指定し、第二引数には RangeTo のオブジェクト(..end のような形のもの)を指定します。usize 限定ではありますが、使用例としては次のようになります。
#![feature(slice_range)]
fn main() {
let max_len = 100;
let range = std::slice::range(..10, ..max_len);
assert_eq!((range.start, range.end), (0, 10));
}
このあたりについては GitHub のこのあたりの issue でやり取りされているようです。
まとめ
range 系の構造体を一括で扱うことができるトレイト RangeBounds を紹介しました。
このトレイトを用いることで、関数の引数などで、範囲を指定することができます。
単純にイテレーションしたい場合には別途 IntoIter なども求めることになりますが、RangeBounds を用いることで、range であることを指定できるのはうれしいですね。