職場ではPHP/Ruby(on Rails)/JSを使用してWEB関連の開発を行っていますが、C++を10年以上経験したこともあり、rustに興味を持ちました。
また、H本を読んだことにより、型システムにも興味を持ちました。
本記事では、アルゴリズムクイックリファレンスを実装していくことにより、rustを練習していこうと思います。
インストール
まずは、homebrewを使用してrustをインストールします。
brew install rust
archlinuxでは、
yaourt -S rust cargo
使用する環境
- MacBook Pro (Sierra 10.12.6 Retina)
- 2.3GHz IntelCore i7
- Memory 16GB
- NVIDIA GeForce GT 750M 2048MB Intel Iris Pro 1536MB
- rustc v.1.19.0
挿入ソート
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。
整列してある配列に追加要素を適切な場所に挿入すること。
平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
実装
pub fn sort<T: Ord + Clone>(a: &mut Vec<T>) {
for i in 1..a.len() {
let mut j = i;
while 0 < j && a[j - 1] > a[j] {
let _t = a[j].clone();
a[j] = a[j - 1].clone();
a[j - 1] = _t;
j -= 1;
}
}
}
選択ソート
選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。
配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
内部ソート。後述するように、安定ソートではない。
実装
pub fn sort<T: Ord>(a: &mut Vec<T>) {
let mut n = a.len() - 1;
while n > 0 {
// 最大値を検索.
let max_index: usize = a.split_at(n + 1)
.0
.iter()
.enumerate()
.max_by(|x, y| x.1.cmp(y.1))
.unwrap().0;
// 最大値を最終要素と入れ替える.
a.swap(max_index, n);
n -= 1;
}
}
ヒープソート
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである
（ヒープ領域とは無関係であることに注意する）。
アルゴリズムは、以下のように2つの段階から構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
計算量は O {\displaystyle (n\log n)} (n\log n) となる[2]。安定ソートではない。
実装
// ヒープソート.
pub fn sort<T: Ord+Clone>(a: &mut Vec<T>) {
let mut len = a.len();
while len > 0 {
// ヒープを作成し、先頭と最後の要素を入れ替える.
create_heap(len, a);
a.swap(0, len - 1);
len -= 1;
}
}
// ヒープ作成.
fn create_heap<T: Ord>(len: usize, a: &mut Vec<T>) {
let mut p = len / 2;
loop {
let mut s = p;
while s < len {
let mut max_idx = 2 * s + 1; // 左ノード要素のほうが、親ノードより大きいと仮定.
// 右子要素を交換できるかチェック.
if max_idx + 1 < len && a[max_idx + 1] > a[max_idx] { max_idx += 1; }
// 範囲チェック.
if max_idx >= len || a[s] >= a[max_idx] { break; }
// 交換.
a.swap(max_idx, s);
s = max_idx;
}
// 先頭要素を処理したらループを抜ける.
if p == 0 { break; }
p -= 1;
}
}
処理速度
std::vec::Vec::sortと他のソートアルゴリズムの処理速度結果です。
ヒープソートが、挿入ソートより遅い結果となりました。
これは、実装がわるいのでは？、と思うので今後改善していきたいと思っています。
各要素をランダムに生成。要素数10000。cargo run --releaseで計測。
| Vec::sort | 挿入 | 選択 | ヒープ |
|---|---|---|---|
| 0.000651462sec | 0.054183412sec | 0.164332680sec | 0.058124022sec |
まとめ
rustを初めて使用してみましたが、全然うまくかけている気がしませんしまた、借用等が難しく感じました（コンパイルエラー出まくり）。
このあたりは、使用していくにつれて概念などもわかってくるようになり、慣れてくるのではないかなと思っています。
今後は、アルゴリズムを実装していき、パーサーコンビネータなどもrustで実装していきたいと思います。
（Arduino上でrustを使用していきたいです）
コード