「線形合同法」による簡単な疑似乱数生成器です。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python 乱数 をお読みくださいませ。
リスト : 乱数 (線形合同法)
// 乱数生成器
struct Rand {
seed: u32
}
// 乱数の最大値
const RAND_MAX: u32 = 0xffff_ffff;
// メソッドの実装
impl Rand {
// 生成
fn new(x: u32) -> Rand {
Rand { seed: x }
}
// 整数 (0 - RAND_MAX) の一様乱数
fn rand(&mut self) -> u32 {
let x = self.seed as u64;
self.seed = ((69069 * x + 1) & RAND_MAX as u64) as u32;
self.seed
}
// 実数 (0.0 以上 1.0 未満) の一様乱数
fn random(&mut self) -> f64 {
(1.0 / (RAND_MAX as f64 + 1.0)) * self.rand() as f64
}
// 配列をシャッフルする (Fisher-Yates shuffle アルゴリズム)
fn shuffle<T>(&mut self, buff: &mut [T]) {
for i in 0 .. buff.len() {
let j = (self.random() * buff.len() as f64) as usize;
buff.swap(i, j);
}
}
}
fn main() {
let mut rng = Rand::new(1);
for _ in 0..8 {
println!("{}", rng.rand());
}
for _ in 0..8 {
println!("{}", rng.random());
}
let mut buff = [0,1,2,3,4,5,6,7,8, 9];
rng.shuffle(&mut buff);
println!("{:?}", buff);
rng.shuffle(&mut buff);
println!("{:?}", buff);
rng.shuffle(&mut buff);
println!("{:?}", buff);
}
69070 475628535 3277404108 772999773 3877832058 3821835443 1662200408 2044158073 0.8821929632686079 0.1857799997087568 0.6387998843565583 0.2692126233596355 0.24668282689526677 0.1361708294134587 0.18301675841212273 0.7844867671374232 [8, 0, 6, 3, 5, 9, 7, 2, 1, 4] [7, 8, 4, 6, 5, 1, 2, 3, 0, 9] [1, 3, 8, 7, 6, 4, 9, 0, 5, 2]
簡単なソート (バブルソート、選択ソート、挿入ソート) です。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python 整列 [1] をお読みくださいませ。
リスト : 簡単なソート (遅いソート)
// バブルソート
fn buble_sort<T: Ord>(buff: &mut [T]) {
for i in 0..buff.len() {
let mut j = buff.len() - 1;
while j > i {
if buff[j] < buff[j - 1] {
buff.swap(j, j - 1);
}
j -= 1;
}
}
}
// 選択ソート
fn select_sort<T: Ord>(buff: &mut [T]) {
for i in 0 .. buff.len() - 1 {
let mut n = i;
for j in i + 1 .. buff.len() {
if buff[j] < buff[n] {
n = j;
}
}
buff.swap(i, n);
}
}
リスト : 単純挿入ソート
fn insert_sort<T: Ord>(buff: &mut [T]) {
for i in 1 .. buff.len() {
let mut j = i;
while j > 0 && buff[j] < buff[j - 1] {
buff.swap(j, j - 1); // ちょっと遅くなる
j -= 1;
}
}
}
fn insert_sort1<T: Ord + Copy>(buff: &mut [T]) {
for i in 1 .. buff.len() {
let mut j = i;
let temp = buff[i];
while j > 0 && temp < buff[j - 1] {
buff[j] = buff[j - 1]; // このほうが速くなるが Copy が必要になる
j -= 1;
}
buff[j] = temp;
}
}
リスト : 簡単なテスト
// 乱数 で作成した Rand を使う
fn test(func: fn(&mut [i32]) -> (), rng: &mut Rand) {
let mut buff: [i32; 20] = [0; 20];
for i in 0 .. 20 { buff[i] = i as i32; }
rng.shuffle(&mut buff);
println!("{:?}", buff);
func(&mut buff);
println!("{:?}", buff);
buff.reverse();
println!("{:?}", buff);
func(&mut buff);
println!("{:?}", buff);
func(&mut buff);
println!("{:?}", buff);
}
fn main() {
let mut rng = Rand::new(1);
println!("----- buble sort -----");
test(buble_sort, &mut rng);
println!("----- select sort -----");
test(select_sort, &mut rng);
println!("----- insert sort -----");
test(insert_sort, &mut rng);
test(insert_sort1, &mut rng);
}
----- buble sort ----- [0, 2, 13, 14, 10, 8, 7, 19, 5, 3, 12, 17, 4, 15, 16, 1, 6, 11, 18, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] ----- select sort ----- [4, 13, 11, 6, 18, 0, 12, 16, 19, 2, 14, 8, 15, 9, 3, 17, 5, 10, 1, 7] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] ----- insert sort ----- [14, 11, 6, 4, 7, 8, 15, 9, 13, 5, 2, 19, 17, 12, 18, 16, 10, 3, 0, 1] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 6, 16, 15, 7, 4, 8, 10, 14, 18, 2, 12, 17, 9, 5, 13, 19, 11, 3] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
単純なクイックソートです。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python 整列 [1] をお読みくださいませ。
リスト : クイックソート
fn quick_sort<T: Ord + Copy>(buff: &mut[T]) {
if buff.len() < 2 { return; }
let pivot = buff[buff.len() / 2];
let mut i = 0;
let mut j = buff.len() - 1;
loop {
while pivot > buff[i] { i += 1; }
while pivot < buff[j] { j -= 1; }
if i >= j { break; }
buff.swap(i, j);
i += 1;
j -= 1;
}
if i > 0 { quick_sort(&mut buff[.. i]); }
if j < buff.len() - 1 { quick_sort(&mut buff[j + 1 ..]); }
}
fn main() {
let mut rng = Rand::new(1);
//
// 省略
//
println!("----- quick sort -----");
test(quick_sort, &mut rng);
}
----- quick sort ----- [1, 2, 12, 13, 16, 18, 3, 14, 0, 7, 19, 4, 17, 6, 11, 10, 8, 9, 5, 15] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。つまり、バブルソートや挿入ソートと同じくらい遅くなってしまうのです。たとえば、配列の先頭要素を枢軸として選ぶ場合、配列の要素が昇順または降順に並んでいると最悪の結果になります。
このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
最後に、要素数が少なくなったらクイックソートから挿入ソートに切り替えます。データ数が少ない場合は、クイックソートよりも単純なソートアルゴリズムの方が高速です。
プログラムは次のようになります。
リスト : クイックソート (改)
const LIMIT: usize = 16;
// 枢軸の選択
fn select_pivot<T: Ord + Copy>(buff: &[T]) -> T {
let a = buff[0];
let b = buff[buff.len() / 2];
let c = buff[buff.len() - 1];
if a < b {
if b < c {
b // a < b < c
} else if a < c {
c // a < c < b
} else {
a // c < a < b
}
} else {
if a < c {
a // b < a < c
} else if b < c {
c // b < c < a
} else {
b // c < b < a
}
}
}
// クイックソートの改良
fn quick_sort1<T: Ord + Copy>(buff: &mut[T]) {
if buff.len() <= LIMIT {
insert_sort1(buff);
return;
}
let pivot = select_pivot(buff);
let mut i = 0;
let mut j = buff.len() - 1;
loop {
while pivot > buff[i] { i += 1; }
while pivot < buff[j] { j -= 1; }
if i >= j { break; }
buff.swap(i, j);
i += 1;
j -= 1;
}
if i > 0 { quick_sort1(&mut buff[.. i]); }
if j < buff.len() - 1 { quick_sort1(&mut buff[j + 1 ..]); }
}
リスト : 簡単なテスト
fn is_sorted(buff: &[i32]) -> bool {
for i in 1 .. buff.len() {
if buff[i] < buff[i - 1] { return false; }
}
true
}
fn test1(func: fn(&mut [i32]) -> (), rng: &mut Rand) {
let mut buff: [i32; 10000] = [0; 10000];
for i in 0 .. 10000 { buff[i] = i as i32; }
rng.shuffle(&mut buff);
func(&mut buff);
println!("{}", is_sorted(&buff));
buff.reverse();
func(&mut buff);
println!("{}", is_sorted(&buff));
func(&mut buff);
println!("{}", is_sorted(&buff));
}
fn main() {
let mut rng = Rand::new(1);
//
// 省略
//
println!("----- quick sort1 -----");
test(quick_sort1, &mut rng);
test1(quick_sort1, &mut rng);
}
----- quick sort1 ----- [5, 12, 18, 13, 0, 9, 7, 19, 4, 3, 8, 15, 17, 1, 16, 14, 6, 11, 10, 2] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] true true true
単純なマージソートです。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python 整列 [2] をお読みくださいませ。
リスト : マージソート
fn merge_sort<T: Ord + Copy>(buff: &mut [T]) {
if buff.len() < 2 {
return;
} else if buff.len() == 2 {
if buff[0] > buff[1] { buff.swap(0, 1); }
} else {
let mid = buff.len() / 2;
merge_sort(&mut buff[.. mid]);
merge_sort(&mut buff[mid ..]);
// 前半部分を work に退避
let mut work: Vec<T> = Vec::with_capacity(mid);
for i in 0 .. mid { work.push(buff[i]); }
let mut i = 0;
let mut j = mid;
let mut k = 0;
while i < mid && j < buff.len() {
if work[i] <= buff[j] {
buff[k] = work[i];
i += 1;
} else {
buff[k] = buff[j];
j += 1;
}
k += 1;
}
while i < mid {
buff[k] = work[i];
i += 1;
k += 1;
}
}
}
// 簡単なテスト
fn main() {
let mut rng = Rand::new(1);
//
// 省略
//
println!("----- merge sort -----");
test(merge_sort, &mut rng);
test1(merge_sort, &mut rng);
}
----- merge sort ----- [5, 18, 6, 19, 12, 1, 0, 15, 9, 10, 4, 13, 7, 17, 16, 14, 2, 11, 3, 8] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] true true true
簡単な例題として、「ヒープ (heap)」を使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。この場合のヒープは「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。詳しい説明は拙作のページ Algorithms with Python 二分木とヒープ をお読みください。
一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。
なお、Rust の標準ライブラリには BinaryHeap が用意されているので、私たちがプライオリティキューを自作する必要はありませんが、Rust のお勉強ということで簡単なプログラムを作ってみましょう。
リスト : プライオリティキュー
struct PriorityQueue<T> {
buff: Vec<T>
}
impl <T: Ord> PriorityQueue<T> {
// 生成
fn new() -> PriorityQueue<T> {
PriorityQueue { buff: vec![] }
}
// 挿入
fn push(&mut self, x: T) {
self.buff.push(x);
let mut n = self.buff.len() - 1;
loop {
if n == 0 { break; }
let p = (n - 1) / 2;
if self.buff[p] <= self.buff[n] { break; }
self.buff.swap(p, n);
n = p;
}
}
// 取得
fn pop(&mut self) -> Option<T> {
if self.buff.len() == 0 { return None; }
let k = self.buff.len() - 1;
let mut n = 0;
self.buff.swap(n, k); // 先頭要素を最後尾に移動
loop {
let mut c = 2 * n + 1;
if c >= k { break; }
if c + 1 < k {
if self.buff[c] > self.buff[c + 1] { c += 1; }
}
if self.buff[n] <= self.buff[c] { break; }
self.buff.swap(n, c);
n = c;
}
self.buff.pop()
}
// 先頭データを参照
fn peek(&self) -> Option<&T> {
if self.buff.len() > 0 {
Some(&self.buff[0])
} else {
None
}
}
// 空か？
fn is_empty(&self) -> bool {
self.buff.len() == 0
}
}
fn main() {
let mut q = PriorityQueue::new();
for x in vec![5,6,4,7,3,8,2,9,1,0] {
q.push(x);
}
while !q.is_empty() {
println!("{}", q.peek().unwrap());
q.pop();
}
}
0 1 2 3 4 5 6 7 8 9
ヒープを使ったソートも優秀なアルゴリズムの一つです。実行時間は N * log2 N に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python 整列 [2] をお読みくださいませ。
リスト : ヒープソート
fn heap_sort<T: Ord + Copy>(buff: &mut [T]) {
// ヒープの構成
let mut i = buff.len() / 2;
while i > 0 {
let mut n = i - 1;
let x = buff[n];
loop {
let mut c = 2 * n + 1;
if c >= buff.len() { break; }
if c + 1 < buff.len() && buff[c] < buff[c + 1] { c += 1; }
if x >= buff[c] { break; }
buff[n] = buff[c];
n = c;
}
buff[n] = x;
i -= 1;
}
// 最大値を取り出す
i = buff.len();
while i > 0 {
let x = buff[i - 1];
buff[i - 1] = buff[0];
let mut n = 0;
loop {
let mut c = 2 * n + 1;
if c >= i - 1 { break; }
if c + 1 < i - 1 && buff[c] < buff[c + 1] { c += 1; }
if x >= buff[c] { break; }
buff[n] = buff[c];
n = c;
}
buff[n] = x;
i -= 1;
}
}
fn main() {
let mut rng = Rand::new(1);
//
// 省略
//
println!("----- heap sort -----");
test(heap_sort, &mut rng);
test1(heap_sort, &mut rng);
}
前半部分でヒープを構築します。親子関係がプライオリティキューと逆になっていることに注意してください。つまり、親が子より大きいという関係を満たすようにヒープを構築します。したがって、配列の先頭 (buff[0]) が最大値になります。
後半部分で、最大値を取り出してヒープを再構築します。配列の先頭には最大値がセットされているので、これを配列の最後尾のデータと交換します。あとは、そのデータを除いた範囲でヒープを再構築すれば、その次に大きいデータを求めることができます。これを繰り返すことで、大きいデータが配列の後ろから整列していくことになります。
----- heap sort ----- [3, 14, 6, 2, 5, 19, 7, 9, 12, 11, 15, 16, 8, 13, 1, 4, 17, 10, 0, 18] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] true true true
フィボナッチ数を生成するイテレータです。フィボナッチ数の性質は拙作のページ Puzzle DE Programming フィボナッチ数 で簡単に説明しています。興味のある方はお読みくださいませ。
リスト : フィボナッチ数
struct Fibonacci {
a: i64, b: i64
}
// 生成
impl Fibonacci {
fn new() -> Fibonacci {
Fibonacci { a: 0, b: 1 }
}
}
// イテレータの実装
impl Iterator for Fibonacci {
type Item = i64;
fn next(&mut self) -> Option<i64> {
let x = self.a;
self.a = self.b;
self.b += x;
Some(x)
}
}
fn main() {
let mut fibo = Fibonacci::new();
// F40 から 10 個のフィボナッチ数を求める
let xs: Vec<i64> = fibo.skip(40).take(10).collect();
println!("{:?}", xs);
fibo = Fibonacci::new();
// 300,000,000 未満で最も大きいフィボナッチ数 Fn を求める
println!("{}", fibo.take_while(|&x| x < 300_000_000).last().unwrap());
// 300,000,000 未満のフィボナッチ数の総和を求める
fibo = Fibonacci::new();
let a: i64 = fibo.take_while(|&x| x < 300_000_000).sum();
println!("{}", a);
// 300,000,000 未満のフィボナッチ数の偶数項の総和を求める
fibo = Fibonacci::new();
let b: i64 = fibo.filter(|&x| x % 2 == 0).take_while(|&x| x < 300_000_000).sum();
println!("{}", b);
}
[102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049] 267914296 701408732 350704366
簡単な例題として「ハミングの問題」を解いてみましょう。
7 以上の素数で割り切れない正の整数を小さい順に N 個求めよ
参考文献 : 奥村晴彦,『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991 (361 ページより引用)7 以上の素数で割り切れない正の整数は、素因子が 2, 3, 5 しかない自然数のことです。これを「ハミング数 (Hamming Numbers)」といいます。ハミング数は素因数分解したとき、\(2^i \times 3^j \times 5^k \ (i, j, k \geq 0)\) の形式になります。たとえば、100 以下のハミング数は次のようになります。
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100
参考文献のプログラムを Rust のイテレータを使って書き換えると次のようになります。
リスト : ハミング数
// ハミング数
struct HammingNumbers {
buff: Vec<i64>,
m2: i64, m3: i64, m5: i64,
i2: usize, i3: usize, i5: usize
}
// 生成
impl HammingNumbers {
fn new() -> HammingNumbers {
HammingNumbers {
buff: vec![],
m2: 1, m3: 1, m5: 1,
i2: 0, i3: 0, i5: 0
}
}
}
// イテレータの実装
impl Iterator for HammingNumbers {
type Item = i64;
fn next(&mut self) -> Option<i64> {
let m = std::cmp::min(std::cmp::min(self.m2, self.m3), self.m5);
self.buff.push(m);
while self.m2 <= m {
self.m2 = self.buff[self.i2] * 2;
self.i2 += 1;
}
while self.m3 <= m {
self.m3 = self.buff[self.i3] * 3;
self.i3 += 1;
}
while self.m5 <= m {
self.m5 = self.buff[self.i5] * 5;
self.i5 += 1;
}
Some(m)
}
}
fn main() {
// ハミング数
let hs = HammingNumbers::new();
println!("{:?}", hs.take(100).collect::<Vec<i64>>());
}
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729, 750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152, 1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536]
「エラトステネスの篩」で素数を求めるプログラムです。アルゴリズムの説明は拙作のページ Puzzle DE Programming 素数 をお読みください。
リスト : エラトステネスの篩
fn sieve(n: usize) -> Vec<usize> {
let mut ps: Vec<usize> = vec![2];
let mut xs: Vec<bool> = vec![true; n / 2];
let mut x = 3;
while x * x <= n {
let mut y = (x - 3) / 2;
if xs[y] {
ps.push(x);
y += x;
while y < xs.len() {
xs[y] = false;
y += x;
}
}
x += 2;
}
while x <= n {
if xs[(x - 3) / 2] { ps.push(x); }
x += 2;
}
ps
}
// その２ (速度は sieve() よりも遅い)
fn sieve2(n: i32) -> Vec<i32> {
let mut buff: Vec<i32> = (2.. n + 1).collect();
let mut ps: Vec<i32> = vec![];
loop {
let p = buff[0];
if p * p > n { break; } // push する前にチェックするよう修正 (2022/07/30)
ps.push(p);
buff = buff.into_iter().filter(|x| x % p != 0).collect();
}
ps.append(&mut buff);
ps
}
fn main() {
// 素数
println!("{:?}", sieve(100));
println!("{:?}", sieve(1000));
// println!("{:?}", sieve2(100));
// println!("{:?}", sieve2(1000));
}
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
素数列を生成するイテレータです。
リスト : 素数のイテレータ
struct Primes {
primes: Vec<i32>,
idx: usize
}
// メソッド
impl Primes {
fn new() -> Primes {
Primes { primes: vec![2, 3], idx: 0 }
}
// 素数列をリセットする
fn reset(&mut self) { self.idx = 0; }
}
// 素数列を生成するイテレータ
impl Iterator for Primes {
type Item = i32;
fn next(&mut self) -> Option<Self::Item> {
if self.idx < self.primes.len() {
self.idx += 1;
Some(self.primes[self.idx - 1])
} else {
let mut n = self.primes[self.primes.len() - 1] + 2;
loop {
if self.primes.iter().take_while(|&&x| x * x <= n).all(|&x| n % x != 0) {
self.primes.push(n);
self.idx += 1;
return Some(n);
}
n += 2;
}
}
}
}
fn main() {
let mut ps = Primes::new();
for _ in 0 .. 25 {
print!("{} ", ps.next().unwrap());
}
println!("");
ps.reset();
for _ in 0 .. 100 {
print!("{} ", ps.next().unwrap());
}
println!("");
}
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
差が 2 である素数の組を「双子素数 (twin prime)」といいます。Primes を使うと、双子素数を出力するイテレータを簡単に作ることができます。
リスト : 双子素数
// 素数のイテレータ (略)
// 双子素数
struct TwinPrimes {
ps: Primes,
prev: i32
}
// メソッド
impl TwinPrimes {
fn new() -> TwinPrimes {
TwinPrimes { ps: Primes::new(), prev: 1 }
}
fn reset(&mut self) {
self.ps.reset();
self.prev = 1;
}
}
// イテレータの実装
impl Iterator for TwinPrimes {
type Item = (i32, i32);
fn next(&mut self) -> Option<Self::Item> {
loop {
let p = self.ps.next().unwrap();
if p - self.prev == 2 {
let q = self.prev;
self.prev = p;
return Some((q, p));
}
self.prev = p;
}
}
}
fn main() {
let mut twinps = TwinPrimes::new();
for _ in 0 .. 100 {
print!("{:?}", twinps.next().unwrap());
}
println!("");
twinps.reset();
// 3,000,000 以下で最大の双子素数を求める
println!("{:?}", twinps.take_while(|x| x.1 < 3_000_000).last().unwrap());
}
(3, 5)(5, 7)(11, 13)(17, 19)(29, 31)(41, 43)(59, 61)(71, 73)(101, 103)(107, 109)(137, 139)(149, 151) (179, 181)(191, 193)(197, 199)(227, 229)(239, 241)(269, 271)(281, 283)(311, 313)(347, 349)(419, 421) (431, 433)(461, 463)(521, 523)(569, 571)(599, 601)(617, 619)(641, 643)(659, 661)(809, 811)(821, 823) (827, 829)(857, 859)(881, 883)(1019, 1021)(1031, 1033)(1049, 1051)(1061, 1063)(1091, 1093)(1151, 1153) (1229, 1231)(1277, 1279)(1289, 1291)(1301, 1303)(1319, 1321)(1427, 1429)(1451, 1453)(1481, 1483)(1487, 1489) (1607, 1609)(1619, 1621)(1667, 1669)(1697, 1699)(1721, 1723)(1787, 1789)(1871, 1873)(1877, 1879)(1931, 1933) (1949, 1951)(1997, 1999)(2027, 2029)(2081, 2083)(2087, 2089)(2111, 2113)(2129, 2131)(2141, 2143)(2237, 2239) (2267, 2269)(2309, 2311)(2339, 2341)(2381, 2383)(2549, 2551)(2591, 2593)(2657, 2659)(2687, 2689)(2711, 2713) (2729, 2731)(2789, 2791)(2801, 2803)(2969, 2971)(2999, 3001)(3119, 3121)(3167, 3169)(3251, 3253)(3257, 3259) (3299, 3301)(3329, 3331)(3359, 3361)(3371, 3373)(3389, 3391)(3461, 3463)(3467, 3469)(3527, 3529)(3539, 3541) (3557, 3559)(3581, 3583)(3671, 3673)(3767, 3769)(3821, 3823) (2999831, 2999833)
ファイルの先頭 10 行を表示するプログラムと、ファイルの末尾 10 行を表示するプログラムを作ります。コマンドラインでファイル名が省略された場合は標準入力を使います。なお、Unix 系 OS には同等以上の機能を持つコマンド head と tail があります。
リスト : ファイルの先頭 10 行を表示 (head0.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn head<R: Read>(reader: BufReader<R>) {
for xs in reader.lines().take(10) {
println!("{}", xs.unwrap());
}
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() == 1 {
head(BufReader::new(io::stdin()));
} else {
match File::open(&args[1]) {
Ok(file) => head(BufReader::new(file)),
Err(_) => println!("{} not found", &args[1])
}
}
}
リスト : ファイルの末尾 10 行を表示 (tail0.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
use std::collections::VecDeque;
fn tail<R: Read>(reader: BufReader<R>) {
let mut que: VecDeque<String> = VecDeque::new();
for xs in reader.lines() {
if que.len() == 10 { que.pop_front(); }
que.push_back(xs.unwrap());
}
for xs in que.iter() {
println!("{}", xs);
}
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() == 1 {
tail(BufReader::new(io::stdin()));
} else {
match File::open(&args[1]) {
Ok(file) => tail(BufReader::new(file)),
Err(_) => println!("{} not found", &args[1])
}
}
}
ファイルの文字数 (ファイルサイズ) と行数と単語をカウントするプログラムを作ります。単語は空白文字で区切られた文字列とします。コマンドラインでファイル名が省略された場合は標準入力を使います。なお、Unix 系 OS には同等の機能を持つコマンド wc があります。
リスト : 単語のカウント (wc0.rc)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn wc<R: Read>(reader: BufReader<R>) {
let mut word = 0; // 単語数
let mut line = 0; // 行数
let mut size = 0; // 文字数
let mut inword = false;
for c in reader.bytes() {
let code = c.unwrap() as char;
if code.is_whitespace() {
inword = false;
if code == '\n' { line += 1; }
} else if !inword {
inword = true;
word += 1;
}
size += 1;
}
println!("lines: {}, words: {}, chars: {}", line, word, size);
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 2 {
wc(BufReader::new(io::stdin()));
} else {
match File::open(&args[1]) {
Ok(file) => wc(BufReader::new(file)),
Err(_) => println!("{} not found", &args[1])
}
}
}
リスト : 単語のカウント (wc1.rc)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn wc<R: Read>(mut reader: BufReader<R>) {
let mut word = 0; // 単語数
let mut line = 0; // 行数
let mut size = 0; // 文字数
let mut buff = String::new(); // バッファ
loop {
let n = reader.read_line(&mut buff).unwrap();
if n == 0 { break; }
line += 1;
size += n;
word += buff.split_whitespace().count();
buff.clear();
}
println!("lines: {}, words: {}, chars: {}", line, word, size);
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 2 {
wc(BufReader::new(io::stdin()));
} else {
match File::open(&args[1]) {
Ok(file) => wc(BufReader::new(file)),
Err(_) => println!("{} not found", &args[1])
}
}
}
ファイルから文字列を探索し、見つけたらその行を出力するプログラムを作ります。コマンドラインでファイル名が省略された場合は標準入力を使うものとします。なお、Unix 系 OS には正規表現を使って文字列を検索するコマンド grep があります。
リスト : 文字列の検索 (find0.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn find_string<R: Read>(reader: BufReader<R>, key: &String) {
let mut n = 1;
for xs in reader.lines() {
let s = xs.unwrap();
match s.find(key) {
Some(_) => println!("{}: {}", n, s),
None => ()
}
n += 1;
}
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 2 {
println!("usage: find0 keyword [file_name]");
} else if args.len() < 3 {
find_string(BufReader::new(io::stdin()), &args[1]);
} else {
match File::open(&args[2]) {
Ok(file) => find_string(BufReader::new(file), &args[1]),
Err(_) => println!("{} not found", &args[1])
}
}
}
ファイルを読み込んで、ある特定の文字を他の文字で置換するプログラムを作ります。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。
コマンドラインの第 1 引数が置換対象となる文字、第 2 引数が置き換える文字とします。これらの引数は文字列で指定することができ、たとえば tr0 abc ABC とすると、a -> A, b -> B, c -> C と置換します。引数の長さが異なる場合は終了するものとします。なお、Unix 系 OS にはもっと多くの機能を持つコマンド tr があります。
リスト : 文字の置換 (tr0.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn tr<R: Read>(reader: BufReader<R>, src: &String, dst: &String) {
let tbl: Vec<_> = dst.chars().collect();
for xs in reader.bytes() {
let c = xs.unwrap() as char;
match src.find(c) {
Some(n) => print!("{}", tbl[n]),
None => print!("{}", c)
}
}
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: tr0 old_chars new_chars [file_name]");
} else if args.len() < 5 {
if args[1].len() != args[2].len() {
println!("{} と {} の長さが違います", &args[1], &args[2]);
} else if args.len() == 3 {
tr(BufReader::new(io::stdin()), &args[1], &args[2]);
} else {
match File::open(&args[3]) {
Ok(file) => tr(BufReader::new(file), &args[1], &args[2]),
Err(_) => println!("{} not found", &args[3])
}
}
}
}
ファイルを読み込んで、第 1 引数で指定した文字列を、第 2 引数で指定した文字列に置換するプログラムを作ります。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。なお、Unix 系 OS ではコマンド sed で文字列の置換を行うことができます。
リスト : 文字列の置換 (replace.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufReader};
fn replace_string<R: Read>(reader: BufReader<R>, src: &String, dst: &String) {
for xs in reader.lines() {
println!("{}", xs.unwrap().replace(src, dst));
}
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: replace old_string new_string [file_name]");
} else if args.len() < 4 {
replace_string(BufReader::new(io::stdin()), &args[1], &args[2]);
} else {
match File::open(&args[3]) {
Ok(file) => replace_string(BufReader::new(file), &args[1], &args[2]),
Err(_) => println!("{} not found", &args[3])
}
}
}
簡単な例題として、ファイルを行単位で連結するプログラムを作りましょう。Unix 系 OS には paste というコマンドがありますが、今回作成するプログラムは paste の簡易バージョンで、空白文字を挟んで連結することにします。動作例を図に示します。
$ cat file1.txt abcde fghij klmno $ cat file2.txt ABCDE FGHIJ KLMNO 12345 $ ./paste0 file1.txt file2.txt abcde ABCDE fghij FGHIJ klmno KLMNO 12345
paste0.rs は 2 つのファイル file1.txt と file2.txt の各行を連結して標準出力へ出力します。この場合、2 つのファイルを同時にオープンしなければいけませんが、近代的なプログラミング言語であれば特別なことをしなくても複数のファイルを扱うことができます。
リスト : ファイルを行単位で連結する (paste0.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
// 行の連結
fn paste(fname1: &String, fname2: &String) -> std::io::Result<()> {
let mut rd1 = BufReader::new(File::open(fname1)?).lines();
let mut rd2 = BufReader::new(File::open(fname2)?).lines();
loop {
match (rd1.next(), rd2.next()) {
(Some(xs), Some(ys)) => println!("{} {}", xs?, ys?),
(Some(xs), None) => {
println!("{}", xs?);
for ls in rd1 { println!("{}", ls?); };
break;
},
(None, Some(ys)) => {
println!("{}", ys?);
for ls in rd2 { println!("{}", ls?); };
break;
},
(None, None) => break
}
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: paste0 file_name1 file_name2");
} else if args.len() < 4 {
match paste(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
ファイルのエントロピーを計算するプログラムです。エントロピーについては拙作のページ Algorithms with Python シャノン・ファノ符号とハフマン符号 で詳しく説明しています。興味のある方はお読みくださいませ。
リスト : ファイルのエントロピー (entoropy.rs)
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
// エントロピーの計算
fn entoropy(fname: &String) -> std::io::Result<(f64, f64)> {
let reader = BufReader::new(File::open(fname)?);
let mut table: [usize; 256] = [0; 256];
for c in reader.bytes() {
table[c? as usize] += 1;
}
let total = table.iter().sum::<usize>() as f64;
let mut e = 0.0;
for &x in table.iter() {
if x == 0 { continue; }
let p = x as f64 / total;
e += - p * p.log2();
}
// エントロピーとファイルサイズの下限値を返す
Ok((e, e * total / 8.0))
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 2 {
println!("usage: entoropy file_name");
} else {
match entoropy(&args[1]) {
Ok((e, s)) => println!("{}, {} bytes", e, s),
Err(err) => println!("{}", err.to_string())
}
}
}