Category: Algorithm

大容量データの計算量が早い。

fn merge_sort(data: Vec<usize>) -> Vec<usize>{
    if data.len() <= 1 {
        return data;
    }
        
    let mid = data.len() / 2;
    let mut left: Vec<usize> = merge_sort(data[0..mid].to_vec());
    let mut right: Vec<usize>  = merge_sort(data[mid..].to_vec());

    return merge(left, right);
}

fn merge(left: Vec<usize>, right: Vec<usize>) -> Vec<usize> {
    let mut result: Vec<usize> = Vec::new();

    let mut i = 0;
    let mut j = 0;

    while (i < left.len()) && (j < right.len()) {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }

    if i < left.len() {
        result.append(&mut left[i..].to_vec());
    }
    if j < right.len() {
        result.append(&mut right[j..].to_vec());
    }
    return result;
}

fn main() {
    let mut data = vec![6, 15, 4, 2, 8, 5, 11, 9, 7, 13];
    println!("{:?}", merge_sort(data));
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.23s
Running `target/debug/rust`
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

何だこれは… 凄いな

ヒープは木構造で構成され、子ノードは常に親ノードより大きいか等しい。
ヒープに要素を追加する場合は、木構造の最後に要素を追加し、親と要素を比較して親よりも小さければ親と交換する。
最小値は必ずルートにある。
取り出した場合は、最後の要素を一番上に移して木を再構成する。

木構造が
A
B C
D E F G
の時、リストでは
[ABCDEFG] で表現する。

fn main() {
    
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 0..data.len() {
        let mut j = i;
        while ( j > 0 ) && (data[(j - 1) / 2] < data[j]) {
            data.swap(j, (j - 1) / 2);
            j = (j - 1) / 2;
        }
    }
    println!("{:?}", data);

    let mut n: Vec<usize> = Vec::new();
    for i in 1..(data.len()+1) {
        n.push(i.try_into().unwrap());
    }
    n.reverse();

    for i in n {
        data.swap(0, i - 1);
        let mut j = 0;
        while(((2 * j + 1) < (i - 1)) && (data[j] < data[2 * j + 1])) || (((2 * j + 2) < (i - 1)) && (data[j] < data[2 * j + 2])) {
            if ((2 * j + 2) == (i - 1)) || (data[2 * j + 1] > data[2 * j + 2]) {
                data.swap(2 * j + 1, j);
                j = 2 * j + 1;
            } else {
                data.swap(2 * j + 2, j);
                j = 2 * j + 2;
            } 
        }
    }
    println!("{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.37s
Running `target/debug/rust`
[15, 13, 11, 8, 9, 4, 5, 2, 7, 6]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

ヒープの構成のところで、
15
13 11
8 9 4 5
2 7 6
と、ヒープの構成になっていることがわかる。
heap sortはbubble, insert, selection sortより早いことがわかっている。

関数化する。

use std::collections::VecDeque;

fn heapify(data: &mut VecDeque<usize>, i: usize) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let size = data.len() - 1;
    let mut min = i;
    if left <= size && data[min] > data[left] {
        min = left;
    }
    if right <= size && data[min] > data[right] {
        min = right;
    }
    if min != i {
        data.swap(min, i);
        heapify(data, min);
    }
}

fn main() {
    
    let mut data = VecDeque::from([6, 15, 4, 2, 8, 5, 11, 9, 7, 13]);

    let mut n: Vec<usize> = Vec::new();
    for i in 0..(data.clone().len()/2) {
        n.push(i.try_into().unwrap());
    }
    n.reverse();

    println!("{:?}", n);

    for i in n {
        heapify(&mut data, i);
    }
    println!("{:?}", data);

    let mut sorted_data: VecDeque<usize> = VecDeque::new();

    for _ in 0..(data.len()) {
        let k = data.clone().len();
        data.swap(0, k - 1);
        sorted_data.push_back(data.pop_back().unwrap());
        println!("{:?}", sorted_data);
        println!("{:?}", data);
        if (k != 1) {
            heapify(&mut data, 0);
        }
    }

    println!("{:?}", sorted_data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.41s
Running `target/debug/rust`
[4, 3, 2, 1, 0]
[2, 6, 4, 7, 8, 5, 11, 9, 15, 13]
[2]
[13, 6, 4, 7, 8, 5, 11, 9, 15]
[2, 4]
[15, 6, 5, 7, 8, 13, 11, 9]
[2, 4, 5]
[9, 6, 11, 7, 8, 13, 15]
[2, 4, 5, 6]
[15, 7, 11, 9, 8, 13]
[2, 4, 5, 6, 7]
[13, 8, 11, 9, 15]
[2, 4, 5, 6, 7, 8]
[15, 9, 11, 13]
[2, 4, 5, 6, 7, 8, 9]
[15, 13, 11]
[2, 4, 5, 6, 7, 8, 9, 11]
[15, 13]
[2, 4, 5, 6, 7, 8, 9, 11, 13]
[15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

ほう、これは凄いな。というか、debugしながらやらないと理解できない。。

rustのvectorのスタックはpush, popを使う

fn main() {
    
    let mut stack: Vec<i32> = Vec::new();

    stack.push(3);
    stack.push(5);
    stack.push(2);

    println!("{:?}", stack);

    let temp = stack.pop();

    println!("{:?}", temp);
    println!("{:?}", stack);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.32s
Running `target/debug/rust`
[3, 5, 2]
Some(2)
[3, 5]

最初に入れたものから取り出すにはお馴染みのVecDequeを使います。

use std::collections::VecDeque;

fn main() {
    
    let mut stack: VecDeque<i32> = VecDeque::new();

    stack.push_back(3);
    stack.push_back(5);
    stack.push_back(2);

    println!("{:?}", stack);

    let temp = stack.pop_front();

    println!("{:?}", temp);
    println!("{:?}", stack);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.57s
Running `target/debug/rust`
[3, 5, 2]
Some(3)
[5, 2]

後ろから順番に定まっているのが分かります。

fn main() {
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 0..data.len() {
        for j in 0..(data.len() - i - 1) {
            if data[j] > data[j + 1] {
                data.swap(j, (j + 1));
            }
            println!("sorted data:{:?}", data);
        }
    }
    println!("sorted data:{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.82s
Running `target/debug/rust`
sorted data:[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted data:[6, 4, 15, 2, 8, 5, 11, 9, 7, 13]
sorted data:[6, 4, 2, 15, 8, 5, 11, 9, 7, 13]
sorted data:[6, 4, 2, 8, 15, 5, 11, 9, 7, 13]
sorted data:[6, 4, 2, 8, 5, 15, 11, 9, 7, 13]
sorted data:[6, 4, 2, 8, 5, 11, 15, 9, 7, 13]
sorted data:[6, 4, 2, 8, 5, 11, 9, 15, 7, 13]
sorted data:[6, 4, 2, 8, 5, 11, 9, 7, 15, 13]
sorted data:[6, 4, 2, 8, 5, 11, 9, 7, 13, 15]
sorted data:[4, 6, 2, 8, 5, 11, 9, 7, 13, 15]
sorted data:[4, 2, 6, 8, 5, 11, 9, 7, 13, 15]
sorted data:[4, 2, 6, 8, 5, 11, 9, 7, 13, 15]
sorted data:[4, 2, 6, 5, 8, 11, 9, 7, 13, 15]
sorted data:[4, 2, 6, 5, 8, 11, 9, 7, 13, 15]
sorted data:[4, 2, 6, 5, 8, 9, 11, 7, 13, 15]
sorted data:[4, 2, 6, 5, 8, 9, 7, 11, 13, 15]
sorted data:[4, 2, 6, 5, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 6, 5, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 6, 5, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 9, 7, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

fn main() {
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    let mut change = true;
    for i in 0..data.len() {
        if (change != true)  {
            break;
        }
        change = false;
        for j in 0..(data.len() - i - 1) {
            if data[j] > data[j + 1] {
                data.swap(j, (j + 1));
            }
            println!("sorted data:{:?}", data);
            change = true;
        }
    }
    println!("sorted data:{:?}", data);
}

挿入ソートも n * (n – 1) / 2 の計算量になる。
対象データを一時領域に確保しておき、値が大きかどうかを判定して、大きい場合は入れ替えるという作業を繰り返す。
usizeは-にならないため、 j== 0の時は判定しています。

fn main() {
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 1..data.len() {
        let temp = data[i];
        let mut j = i - 1;
  
        while (j >= 0) && (data[j] > temp) {
            data[j + 1] = data[j];
            if j == 0 {
                break;
            }
            j -= 1;
        }
        if j == 0 && (data[j] > temp) {
            data[0] = temp;
        } else {
            data[j + 1] = temp;
        }
        println!("sorted data:{:?}", data);
    }
    println!("sorted data:{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.52s
Running `target/debug/rust`
sorted data:[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted data:[4, 6, 15, 2, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 15, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 8, 15, 5, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 15, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 11, 15, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 9, 11, 15, 7, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 15, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

途中経過を見ると美しいが、これも計算量が多くなる模様。

use rand::Rng;
use std::cmp::Ordering;

static goal:[i32; 8] = [ 0b111000000, 0b000111000, 0b000000111, 0b100100100,
            0b010010010, 0b001001001, 0b100010001, 0b001010100];

fn check(player: i32) -> bool {
    for mask in goal {
        if player & mask == mask {
            return true
        }
    }
    return false 
}

fn minmax(p1: i32, p2: i32, turn: bool) -> i32 {
    if check(p2) {
        if turn {
            return 1
        } else {
            return -1
        }
    }
    let board: i32 = p1 | p2;
    if board == 0b111111111{
        return 0
    }

    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }

    let mut k = Vec::new();
    if turn {
        for i in w {
           k.push(minmax(p2, p1 | (1 << i), !turn))
        }
        return *k.iter().min().unwrap();
    } else {
        for i in w {
            k.push(minmax(p2, p1 | (1 << i), !turn))
        }
        return *k.iter().max().unwrap();
    }
    

}

fn play(p1: i32, p2: i32, turn: bool) {
    if check(p2) {
        println!("{:09b}, {:09b}", p1, p2);
        return
    } 

    let board: i32 = p1 | p2;
    if board == 0b111111111{
        println!("{:09b}, {:09b}", p1, p2);
        return
    }
    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }

    let mut r  = Vec::new();
    for i in w.clone() {
        r.push(minmax(p2, p1 | (1 << i), true))
    }
    let n = r.iter()
        .enumerate()
        .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal))
        .map(|(index, _)| index).unwrap();
    let j = w[n];
    play(p2, p1 | (1 << j), !turn);
}

fn main() {
    play(0, 0, true);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.32s
Running `target/debug/rust`
001110010, 110001101

う、なんか違うな…

    let mut rnd = rand::thread_rng();
    let k = rnd.gen_range(1..n);
    let j = w[k];

このようにすると、ランダム性が出る。。

マスを0と1で表現して、2進法の加算で判定する。

fn main() {

    println!("{:09b}", 0b111000000 & 0b000111111);
    println!("{:09b}", 0b111000000 & 0b101100010);
    println!("{:09b}", 0b111000000 & 0b111000010);
}

000000000
101000000
111000000

ちなみに、0b111000000など2進数の型はi32

use rand::Rng;

static goal:[i32; 8] = [ 0b111000000, 0b000111000, 0b000000111, 0b100100100,
            0b010010010, 0b001001001, 0b100010001, 0b001010100];

fn check(player: i32) -> bool {
    for mask in goal {
        if player & mask == mask {
            return true
        }
    }
    return false 
}

fn play(p1: i32, p2: i32) {
    if check(p2) {
        println!("{:09b}, {:09b}", p1, p2);
        return
    } 

    let board: i32 = p1 | p2;
    if board == 0b111111111{
        println!("{:09b}, {:09b}", p1, p2);
        return
    }
    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }
    let n = w.len() + 1;
    let mut rnd = rand::thread_rng();
    let r = rnd.gen_range(1..n);
    play(p2, p1 | (1 << r));
}

fn main() {
    play(0, 0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.30s
Running `target/debug/rust`
010001000, 001111000

これはさっぱりわからん…

ファイル、フォルダの取得
fs::read_dir()がファイルの一覧取得

use std::error::Error;
use std::fs;
use std::path;

pub fn read_dir(path: &str) -> Result<Vec<path::PathBuf>, Box<dyn Error>>{
    let dir = fs::read_dir(path)?;
    let mut files: Vec<path::PathBuf> = Vec::new();
    for item in dir.into_iter() {
        files.push(item?.path());
    }
    Ok(files)
}


fn main() {
    let files = read_dir("./");
    println!("{:?}", files);
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.43s
Running `target/debug/rust`
Ok([“./target”, “./.gitignore”, “./Cargo.lock”, “./Cargo.toml”, “./.git”, “./src”])

### 再帰的にディレクトリ内のファイルを取得

use std::error::Error;
use std::fs;
use std::path;

pub fn read_dir(path: &path::PathBuf) {
    let dir = fs::read_dir(path).unwrap();
    let mut files: Vec<path::PathBuf> = Vec::new();
    for item in dir.into_iter() {
        
        let name = item.unwrap().path();
        if name.is_dir() {
            read_dir(&name);
        } else {
            files.push(name);
        }
    }
    println!("{:?}", files);
}


fn main() {
    let path = path::PathBuf::from("./src");
    read_dir(&path);
}

    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.20s
     Running `target/debug/rust`
["./src/test/test.rs"]
["./src/binary_search.rs", "./src/linear_search.rs", "./src/fibonacci.rs", "./src/tree_search.rs", "./src/main.rs", "./src/maze.rs", "./src/cardinal.rs", "./src/vending_machine.rs", "./src/fizzbuzz.rs", "./src/8queen.rs", "./src/prime.rs"]

これは感覚的に理解しやすいですね。

### 幅優先探索
再帰で検索するのではなく、ディレクトリをvectorに追加していき、各ディレクトリのファイルをそれぞれ取得していく。答えは同じだが、深さで検索するのではなく、対象を一つ一つ処理していくところが面白い。

fn main() {
    let mut queue: VecDeque<path::PathBuf> = VecDeque::new();
    queue.push_back("./src".into());
    let mut files: Vec<path::PathBuf> = Vec::new();

    while queue.len() > 0 {
        let path = queue.pop_front();
        let dir = fs::read_dir(path.unwrap()).unwrap();
        for item in dir.into_iter() {
            let name = item.unwrap().path();
            if name.is_dir() {
                queue.push_back(name);
            } else {
                files.push(name);
            }
        }
    }
    println!("{:?}", files);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.42s
Running `target/debug/rust`
["./src/binary_search.rs", "./src/linear_search.rs", "./src/fibonacci.rs", "./src/tree_search.rs", "./src/main.rs", "./src/maze.rs", "./src/cardinal.rs", "./src/vending_machine.rs", "./src/fizzbuzz.rs", "./src/read_dir.rs", "./src/8queen.rs", "./src/prime.rs", "./src/test/test.rs"]

再起的なので、対象枚数が増えるほど、指数関数的に計算数が増えていく。

use std::env;

fn hanoi(n: i32, src: String, dist: String, via: String) { // n, 移動元、移動先、経由
    if n > 1 {
        hanoi(n - 1, src.clone(), via.clone(), dist.clone());
        println!("{} -> {}", src.clone(), dist.clone());
        hanoi(n - 1, via.clone(), dist.clone(), src.clone());
    } else {
        println!("{} -> {}", src.clone(), dist.clone());
    }

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let n = args[1].parse::<i32>().unwrap();
    println!("入力値:{}", n);

    hanoi(n, "a".to_string(), "b".to_string(), "c".to_string());
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust 3`
入力値:3
a -> b
a -> c
b -> c
a -> b
c -> a
c -> b
a -> b

### 考察
3 a b c (a->b)
2 a c b (a->c)
1 a b c (a->b)
1 b c a (b->c)
3 a b c (a->b)
2 ….

fn check()は逆順にして、左下もしくは右下にあるかチェックしてる？
なんとなくわかるが、完全に理解していないのが辛いところ。。

use std::collections::VecDeque;

static N: usize = 8;

fn check(x: usize, mut col: VecDeque<usize>)-> bool {
    col.make_contiguous().reverse();

    let mut i = 0;
    for row in col {
        if ((x + i + 1) == row) || ((x as i32- i as i32 - 1) == row.try_into().unwrap()) {
            return false
        }
        i = i + 1;
    }
    return true
}

fn search(mut col: VecDeque<usize>){
    if col.clone().len() == N {
        println!("{:?}", &col);
    }

    for i in 0..N {
        if !col.contains(&i) {
            // println!("{:?}", &col);
            // println!("{}", i);
            if check(i, col.clone()) == true {
                col.push_back(i);
                search(col.clone());
                col.pop_front();
            }
        }
    }
}

fn main() {
    let col: VecDeque<usize> = VecDeque::new();
    search(col);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.23s
Running `target/debug/rust`
[4, 1, 3, 5, 7, 2, 0, 6]
[1, 3, 5, 7, 2, 0, 6, 4]
[5, 2, 4, 6, 0, 3, 1, 7]
[2, 4, 6, 0, 3, 1, 7, 5]
[1, 3, 5, 7, 2, 0, 6, 4]
…