【Rust】クイックソート

アルゴリズム的にはこれが一番簡単。それでこれが早いのか。。

fn quick_sort(data: Vec<i32>) -> Vec<i32> {

    if data.len() <= 1{
        return data;
    }
    let pivot = data[0];
    let mut left: Vec<i32> = Vec::new();
    let mut right: Vec<i32> = Vec::new();
    let mut result: Vec<i32> = Vec::new();
    let mut same = 0;

    for i in data {
        if i < pivot {
            left.push(i);
        } else if i > pivot {
            right.push(i);
        } else {
            same += 1;
        }
    }
    left = quick_sort(left);
    right = quick_sort(right);
    result.append(&mut left);
    if same != 0 {
        for i in 0..same {
            result.push(pivot);
        }
    }
    result.append(&mut right);

    return result;
}

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

    println!("{:?}", quick_sort(data));
}

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

【Rust】axumでcsrfを使いたい(axum_csrf)

axum_csrf = “0.11.0”

use axum_csrf::{CsrfConfig, CsrfToken};

#[derive(Serialize, Deserialize)]
struct LoginForm {
    username: String,
    password: String,
    authenticity_token: String,
}

#[tokio::main]
async fn main() {

    // tracing_subscriber::fmt::init();
    let config = CsrfConfig::default();

    let serve_dir = ServeDir::new("static").not_found_service(ServeFile::new("static"));

    let app = Router::new()
        .route("/", get(handle_index))
        .route("/login", post(handle_login))
        .route("/home", get(handle_home))
        .route("/upload", post(handle_upload))
        .layer(DefaultBodyLimit::max(1024 * 1024 * 1024))
        .nest_service("/static", serve_dir.clone())
        .fallback_service(serve_dir)
        .with_state(config);

    let listener = tokio::net::TcpListener::bind("0.0.0.0:3000").await.unwrap();
    axum::serve(listener, app).await.unwrap();
}

async fn handle_index(token: CsrfToken) -> impl IntoResponse {

    let keys = token.authenticity_token().unwrap();

    let tera = tera::Tera::new("templates/*").unwrap();

    let mut context = tera::Context::new();
    context.insert("title", "Index page");
    context.insert("Keys", &keys);

    let output = tera.render("test.html", &context);
    (token, axum::response::Html(output.unwrap()))
}

async fn handle_login(token: CsrfToken, axum::Form(loginform): axum::Form<LoginForm>)-> axum::response::Html<String> {
    if token.verify(&loginform.authenticity_token).is_err() {
        println!("Token is invalid");
    } else {
        println!("Token is Valid lets do stuff!");
    }
    let username = loginform.username;
    let password = loginform.password;
    let authenticity_token = loginform.authenticity_token;
    println!("username:{}, password:{}, authenticity_token: {}", username, password, authenticity_token);
 
}

    <form method="post" action="/login">
        <input type="hidden" name="authenticity_token" value="{{ Keys }}"/>
        <div class="mb-3 mt-3">
        <input type="text" class="form-control" placeholder="user name" name="username"/>
          </div>
        <input type="password" class="form-control" placeholder="password" name="password">
        <span class="fs-s">If you don't have account, you can <a href="/signup">Sign up</a>.</span><br/>
        <input type="submit" class="btn submit" value="login" />
     </form>

Finished `dev` profile [unoptimized + debuginfo] target(s) in 3.90s
Running `target/debug/axum`
Token is Valid lets do stuff!
username:asdfggggg, password:asdfggggg, authenticity_token: QnDhKw70YahSelDPpBxJHzgdlXvhFCe2ZKOv+wH82zo=

おおおおおおおおおおおおお、なるほどこれは凄い!!!!
sessionにsession_tokenをセットするロジックを書く方法もありますが、これの方が楽ですね。

【PHP】CSRFの仕組み

セッションの値と比較して検証しているのね。理解できました。

<?php

session_start();

$toke_byte = openssl_random_pseudo_bytes(16);
$csrf_token = bin2hex($toke_byte);

$_SESSION['csrf_token'] = $csrf_token;
?>

<!DOCTYPE html>
<html>
<body>
    <form action="contact.php" method="POST">
        <div>
            <label for="name">お名前：</label>
            <input type="text" id="name" name="name" />
        </div>
        <div>
            <label for="email">メールアドレス：</label>
            <input type="email" id="email" name="email" />
        </div>
        <div>
            <label for="message">お問い合わせ本文</label>
            <textarea id="message" name="message"></textarea>
        </div>
        <input type="hidden" name="csrf_token" value="<?php echo $csrf_token; ?>" />
        <button type="submit">送信</button>
    </form>
</body>
</html>

session_start();
// ワンタイムトークンの一致を確認
if (!isset($_POST['csrf_token']) || $_POST['csrf_token'] !== $_SESSION['csrf_token']) {
  // トークンが一致しなかった場合
  die('お問い合わせの送信に失敗しました');
} else {
    echo('認証に成功しました。');
}

【Rust】マージソート

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

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]

何だこれは… 凄いな

【Rust】ヒープソート

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

木構造が
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】スタック(push, pop)を実装する

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]

【Rust】バブルソート

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

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);
}

【Rust】挿入ソート

挿入ソートも 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]

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

【Rust】選択ソート

1件ずつ調べていく手法です。最小値の抽出は以下の通り。

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

    let mut min = 0;
    for i in 0..data.len() {
        if data[min] > data[i] {
            min = i;
        }
    } 
    println!("minimal num:{}", data[min]);
}

### 選択ソート
n * (n – 1) / 2 の計算量が必要になる。もっとも小さいものを左から順番に並べていく。
mem::swap(&mut data[min], &mut data[i]);は使えない。

use std::mem;

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

    for i in 0..data.len() {
        let mut min = i;
        let k = i + 1; 
        for j in k..data.len() {
            if data[min] > data[j] {
                min = j;
            }
        }
        // mem::swap(&mut data[min], &mut data[i]);
        data.swap(i, min);
    }   
    println!("sorted data:{:?}", data);
}

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

なるほど、普段ソートとか考えたことなかったが、こうなってるのか。。面白いね。

[Vue.js] 初期値を入れてRange formの値と入力フォームを一致させる

range formもinput formも両方 v-modelの値を一致させる。

<div class="form-group">
                    <label for="customRange1" class="form-label">Request amount range</label>
                    <input type="range" class="form-range" id="customRange1" min="0" max="100" v-model="value">
                </div>
                <div class="form-group">
                    <label for="amount">amount:</label>
                    <input type="amount" name="amount" class="form-control" id="amount" v-model="value">
                </div>

初期値は設定するだけ。

    const app = new Vue({
        el: '#app',
        data: {
            title: '入力フォームバリデーション',
            name: '',
            value: 50,
        },

めちゃくちゃ簡単じゃん。もっと時間かかると思ったw