はじめに
rustが10周年を迎えたらしい。
「Rust 1.0」がリリースされたのは米国時間の2015年5月15日なので、今年で10周年。
rustは「Stack Overflow Developer Survey」において7年連続エンジニアに愛されているプログラミング言語として選ばれています。
そこで今回はrustを使用して、オーダーの勉強をしたいと思っています。
オーダーとは
良いアルゴリズムかどうかを判断する基準として計算量という尺度を設けることができます。
計算量が分かると、実際にプログラミングをしなくても、コンピュータ上での実行時間をある程度見積もることができます。
オーダーとはその計算量の記法です。
オーダー記法はアルゴリズムの計算量を表現するための記法で、主に入力サイズが大きくなったときに、アルゴリズムの実行時間や使用メモリがどのように増加するかを表します。
例えば、「入力が増えると、処理時間がその2乗のスピードで増える」というのは$O(N^2)$で表します。
実際にrustでコードを書いてみる
では、実際にrustでコードを書いていきます。
今回は$O(1)$、$O(\log{N})$、$O(N)$、$O(N\log{N})$、$O(N^2)$を見ていきます。
以下が、rustのコードです。
use std::time::Instant;
use std::hint::black_box;
fn o1_operation() -> usize {
let mut count = 0;
count += 1;
black_box(count)
}
fn logn_operation(n: usize) -> usize {
let mut count = 0;
let mut i = n;
while i > 1 {
i /= 2;
count += 1;
}
black_box(count)
}
fn on_operation(n: usize) -> usize {
let mut count = 0;
for _ in 0..n {
count += 1;
}
black_box(count)
}
fn onlogn_operation(n: usize) -> usize {
let mut count = 0;
for i in 1..=n {
let mut j = i;
while j > 1 {
j /= 2;
count += 1;
}
}
black_box(count)
}
fn on2_operation(n: usize) -> usize {
let mut count = 0;
for i in 0..n {
for j in 0..n {
count += 1;
}
}
black_box(count)
}
fn measure<F: Fn() -> usize>(label: &str, f: F) {
let start = Instant::now();
let count = f();
let duration = start.elapsed();
println!("{:<12} | 回数: {:>20} | 時間: {:>10?}", label, count, duration);
}
fn main() {
let n = 10_000;
println!("=== n = {}===\n", n);
measure("O(1)", || o1_operation());
measure("O(logN)", || logn_operation(n));
measure("O(N)", || on_operation(n));
measure("O(NlogN)", || onlogn_operation(n));
measure("O(N^2)", || on2_operation(n));
}プログラム内で処理時間を計って出力させます。
実行結果は以下のようになりました。
=== n = 10000===
O(1) | 回数: 1 | 時間: 400ns
O(logN) | 回数: 13 | 時間: 300ns
O(N) | 回数: 10000 | 時間: 229.2µs
O(NlogN) | 回数: 113631 | 時間: 559.7µs
O(N^2) | 回数: 100000000 | 時間: 1.2585727sそれぞれのオーダーについて
それぞれのオーダーについて見ていきます。
$O(1)$は簡単です。
処理を1回するだけです。
では次の$O(\log{N})はどうでしょうか。
このlogNの底は2です。
処理をlogN回するということですが、今回のコードでは2で割っていってますね。
1024という数字にたいして、10回処理を行うと完了する訳です。
よってlogNで表すことができます。
次の$O(N)$もシンプルです。処理をN回実施することになります。
$O(N\log{N})$については$\log{N}$回の処理をN回繰り返しています。
ちなみに、$O(N\log{N})$の代表的なアルゴリズムとしてマージソートがあり、以下のようなアルゴリズムです。
Step 1: 分割（Divide）
[5, 3, 8, 4]
↓
[5, 3] + [8, 4]
↓
[5] + [3] + [8] + [4]
Step 2: ソートされたペアをマージ（Conquer）
[5] + [3] → [3, 5]
[8] + [4] → [4, 8]
Step 3: マージして全体をソート
[3, 5] + [4, 8] → [3, 4, 5, 8]pythonでrustと同じ処理を書いて比較する
比較のためにpythonでrustと同じコードを書いて、処理時間を確認してみます。
pythonのコードは以下のようになっています。
import time
import math
def o1_operation():
count = 0
count += 1
return count
def logn_operation(n):
count = 0
i = n
while i > 1:
i //= 2
count += 1
return count
def on_operation(n):
count = 0
for _ in range(n):
count += 1
return count
def onlogn_operation(n):
count = 0
for i in range(1, n + 1):
j = i
while j > 1:
j //= 2
count += 1
return count
def on2_operation(n):
count = 0
for _ in range(n):
for _ in range(n):
count += 1
return count
def measure(label, func):
start = time.perf_counter_ns()
count = func()
duration_ns = time.perf_counter_ns() - start
if duration_ns < 1_000:
duration_str = f"{duration_ns}ns"
elif duration_ns < 1_000_000:
duration_str = f"{duration_ns / 1_000:.1f}µs"
elif duration_ns < 1_000_000_000:
duration_str = f"{duration_ns / 1_000_000:.1f}ms"
else:
duration_str = f"{duration_ns / 1_000_000_000:.3f}s"
print(f"{label:<12} | 回数: {count:>20,} | 時間: {duration_str:>10}")
def main():
n = 10_000
print(f"=== n = {n} ===\n")
measure("O(1)", lambda: o1_operation())
measure("O(logN)", lambda: logn_operation(n))
measure("O(N)", lambda: on_operation(n))
measure("O(NlogN)", lambda: onlogn_operation(n))
measure("O(N^2)", lambda: on2_operation(n))
if __name__ == "__main__":
main()結果は以下のようになりました。
=== n = 10000 ===
O(1) | 回数: 1 | 時間: 2.2µs
O(logN) | 回数: 13 | 時間: 3.6µs
O(N) | 回数: 10,000 | 時間: 578.9µs
O(NlogN) | 回数: 113,631 | 時間: 11.3ms
O(N^2) | 回数: 100,000,000 | 時間: 4.859s$O(N^2)$のオーダーに関しては4倍ほどrustよりpythonの方が時間がかかっています。
rust強し！
最後に
rust、もっと使っていきたいですね。
