刹那的思考をメモる

AIのミトコンドリアになれるといいね

brainf*ckのllvmをバックエンドにしたAn optimising compilerのコードを眺める

概要

llvmをrustで使うべくllvm-sysのcrateのDocを見ていたら見かけたのでいい機会なのでコードを読んでみる. (”Wilfred's BF compiler”と書いてあり,BFってなんやねんと思ったら,brainf*ckだった...) https://crates.io/crates/llvm-sys

bfcの概要

bfc.wilfred.me.uk 以下上記サイトの引用

  • an industrial-grade Brainfuck compiler (産業レベルで耐えれても,産業では使うと誰も...と言いたいけど世界は広いので断言はやめておく.)
  • a fast compiler for a silly language
  • utterly over-engineered

An elaborate IR with position-preserving optimisations.

Extensive testing, even testing idempotence and observational equivalence of optimisations.

Coloured code diagnostics with position highlighting.

Gratuitous website.

軽い気持ちで読むつもりだったが,言語を作る人にはいい勉強になりそうだ.

一旦動かしてみる

bfc.wilfred.me.uk

cargo.tomlのバージョンを確認

brew install llvm@14

// .zshrcに書き込む
export PATH="/opt/homebrew/opt/llvm@14/bin:$PATH"
export LDFLAGS="-L/opt/homebrew/opt/llvm@14/lib"
export CPPFLAGS="-I/opt/homebrew/opt/llvm@14/include"

実行

 target/release/bfc sample_programs/hello_world.bf 

./hello_world                                                                   
Hello World!

最適化

--opt=0 # no optimisations
--opt=1 # peephole only
--opt=2 # peephole and speculative execution // のぞき穴の最適化と投機的実行

Peephole Optimisations

src/peephole.rs

    • combine_increments: 連続するインクリメントを単一の命令に統合。
  • –> ast arrayをcoalesceして,Incrementを統合
    • zeroing_loops: 特定のループをセルをゼロに設定する命令に置き換え。
    • remove_dead_loops: 実行されないループを削除。
    • remove_redundant_sets: 不要なセット操作を削除。[bf特有]
    • annotate_known_zero: 実行開始時にセルがゼロであることを注記。[bf特有]

test

bfcのテストがいい感じっぽいのでちょっと読んでみる. これ以降のコードのスニペットは,GNU General Public License v2.0に準拠する.

github.com

bfc.wilfred.me.uk

quickcheckを使っているっぽい.

Verifying Improvement

最適化を行ったあとに中間表現の命令数が多くなってはいけない.それはそう.

github.com

より抜粋.

    #[test]
    fn quickcheck_optimize_should_decrease_size() {
        fn optimize_should_decrease_size(instrs: Vec<AstNode>) -> bool {
            // The result of optimize() should never increase the number of
            // instructions.
            let result = optimize(instrs.clone(), &None).0;
            count_instrs(&result) <= count_instrs(&instrs)
        }
        quickcheck(optimize_should_decrease_size as fn(Vec<AstNode>) -> bool);
    }

Verifying Idempotence

冪等性があるよう. 最適化済みなものを最適化しても変化がない.    f(f(program)) == f(program)

github.com

    #[test]
    fn annotate_known_zero_idempotent() {
        fn is_idempotent(instrs: Vec<AstNode>) -> bool {
            let annotated = annotate_known_zero(instrs);
            let annotated_again = annotate_known_zero(annotated.clone());
            if annotated == annotated_again {
                true
            } else {
                println!("intermediate: {:?}", annotated);
                println!("final: {:?}", annotated_again);
                false
            }
        }
        quickcheck(is_idempotent as fn(Vec<AstNode>) -> bool);
    }

Verifying Behavioural Equivalence

最適化しても実行結果は変わらない.ただし,一部最適化において悪さする場合がある.例えば,無効な処理を削除する最適化がある.実行時のセル(bfでのセルはチューリングマシンでのテープの役割を果たす.)を確認する場合があるが,無効な処理がセルに書き込みをしていた場合,テストにパスしなくなるので注意.eval(f(program)) === eval(program).(テストを発掘するのは苦労した.#[test]で検索かけて159Hit.ほぼ最後の方に見たファイルの一番下にあった.他にもあったかもしれないが...コメントに,semanticsとかbehave周りの直接的な言葉がないのも辛かった.結局ほぼすべてのテストを眺めた,)

github.com

    fn test_overall_optimize_is_sound() {
        fn optimize_ignore_warnings(instrs: Vec<AstNode>) -> Vec<AstNode> {
            optimize(instrs, &None).0
        }

        fn optimizations_sound_together(
            instrs: Vec<AstNode>,
            read_value: Option<i8>,
        ) -> TestResult {
            // Since sort_by_offset and remove_read_clobber can change
            // cell values at termination, the overall optimize can change
            // cells values at termination.
            transform_is_sound(instrs, optimize_ignore_warnings, false, read_value)
        }

        quickcheck(optimizations_sound_together as fn(Vec<AstNode>, Option<i8>) -> TestResult);
    }

check_cells = falseなので,bfcのweb docsで述べられているように,cellは無視している. github.com

    fn transform_is_sound<F>(
        instrs: Vec<AstNode>,
        transform: F,
        check_cells: bool,
        dummy_read_value: Option<i8>,
    ) -> TestResult

まとめ

疲れた,どうでもいいが,soundってなんやねんと思ったら,soundnessが健全性的な意味があることをしった. 正当性とか検証とかの文脈でよく使われるんだろう,

gofのデザインパターン Visitor

背景

llvm.org これを読んでいて名前が出てきた.(チュートリアルを進めるうえではいらないが..)Gofも流し見を数年前にしたきり,詳細を知らないので良い機会なので学ぶ

gof(ギャングオブフォー)

デザインパターン23種. ja.wikipedia.org

Visitor

Visitor パターンは、オブジェクト指向プログラミング およびソフトウェア工学 において、 アルゴリズムをオブジェクトの構造から分離するためのデザインパターンである。分離による実用的な結果として、既存のオブジェクトに対する新たな操作を構造を変更せずに追加することができる。 by wikipedia

使い所

Visitorの使い所として, 同じ関数名で複数の型ごとに処理を変えたいときに使うという想定で問題ないですか

========以下GPT==============

はい、その想定で問題ありません。Visitor パターンは、特に同じ関数名(インターフェースのメソッド)で異なる型に対して異なる処理を実行したい場合に非常に有効です。このパターンは、異なる型のオブジェクトがそれぞれ独自の処理を要求する状況での多態性と拡張性を提供します。

Visitor パターンの役割

  1. 型ごとの処理の分離: Visitor パターンを使用すると、各オブジェクトの型ごとに異なる処理をvisitメソッドに実装できます。これにより、処理をオブジェクトの型に基づいて動的に変更することができます。

  2. オープン/クローズド プリンシプルのサポート: ソフトウェアエンティティは拡張に対してオープンであり、修正に対してクローズドであるべきという設計原則をサポートします。新しい型のオブジェクトが追加された場合、既存のクラスを変更することなく、新しい Visitor を実装することで対応できます。

  3. 単一責任の原則: 各visitメソッドは特定の型のオブジェクトに対する処理のみを担当します。これにより、クラスとメソッドの責任が明確に区分され、コードの保守性が向上します。

具体的な使用例

  • コンパイラ設計: 抽象構文木(AST)のノードごとに異なるコード生成処理を実行する際にVisitorパターンを使用します。
  • ドキュメント処理: 異なるタイプのドキュメント要素(テキスト、画像、表など)に対して、異なるレンダリング処理や書式設定を適用する場合に役立ちます。
  • システム監視とレポート: 異なる種類のシステムリソース(CPU、メモリ、ディスクなど)に対して、特定の監視またはログ処理を行う際に使用します。

まとめ

Visitor パターンは、特に複数の異なるオブジェクト型に対して同一のインターフェースを通じて異なる振る舞いを実装したい場合に非常に有効なデザインパターンです。型に基づいた処理の柔軟性と拡張性を提供するため、多くのアプリケーションでその利点が活かされています。

========以上GPT==============

実装例(Pretty Printer(pprint)とは)

Pretty Printerとは

Pretty Printerは、コードやデータ構造を整形して、人間が読みやすい形式で表示するツールです。例えば、プログラムのソースコードXML文書、抽象構文木(AST)などの構造を美しく印刷(表示)するために使われます。

json(簡易版)をきれいに表示

真面目にやるならrfcRFC 8259)を準拠する必要(正確には読んだことがないので完全に準拠しているか不明)があるが,今回はBool , Number, String,Arrayを許し再帰的な構造を許す jsonを表示するpprintを実装.parserの実装もしない.Rustで実装します.

抽象構文木の定義

enum Json {
    Null,
    Bool(bool),
    Number(f64),
    String(String),
    // Array(Vec<Json>), 後で追加
    Object(Vec<(String, Json)>),
}

コード

#[allow(dead_code)]
enum Json {
    Null,
    Bool(bool),
    Number(f64),
    String(String),
    Array(Vec<Json>),
    Object(Vec<(String, Json)>),
}

trait Vistor {
    fn visit_null(&mut self)->String;
    fn visit_bool(&mut self, v:&bool)->String;
    fn visit_number(&mut self, v:&f64)->String;
    fn visit_string(&mut self, v:&String)->String;
    fn visit_array(&mut self, v:&mut Vec<Json>)->String;
    fn visit_object(&mut self, v:&mut Vec<(String, Json)>)->String;
}

impl Json {
    fn accept(&mut self, vistor: &mut dyn Vistor) -> String {
        match self {
            Json::Null => vistor.visit_null(),
            Json::Bool(b) => vistor.visit_bool(b),
            Json::Number(n) => vistor.visit_number(n),
            Json::String(s) => vistor.visit_string(s),
            Json::Array(a) => vistor.visit_array(a),
            Json::Object(o) => vistor.visit_object(o),
        }
    }
}

struct JsonPrinter {
    indent: usize,
}

impl Vistor for JsonPrinter {
    fn visit_null(&mut self) -> String {
        "null".to_string()
    }

    fn visit_bool(&mut self, v: &bool) -> String {
        v.to_string()
    }

    fn visit_number(&mut self, v: &f64) -> String {
        v.to_string()
    }

    fn visit_string(&mut self, v: &String) -> String {
        format!("\"{}\"", v)
    }

    fn visit_array(&mut self, v: &mut Vec<Json>) -> String {
        let mut result = "[".to_string();
        for (i, item) in v.iter_mut().enumerate() {
            if i > 0 {
                result.push_str(", ");
            }
            result.push_str(item.accept(self).as_str());
        }
        result.push_str("]");
        result
    }

    fn visit_object(&mut self, v: &mut Vec<(String, Json)>) -> String {
        let mut result = "".to_string();
        result.push_str("{\n");
        
        self.indent += 1;
        for (i, (key, value)) in v.iter_mut().enumerate() {
            if i > 0 {
                result.push_str(", \n");
            }
            result.push_str(&"  ".repeat(self.indent));
            result.push_str(&format!("\"{}\": {}", key, value.accept(self)));
        }
        
        self.indent -= 1;
        result.push_str("\n");
        result.push_str(&"  ".repeat(self.indent));
        result.push_str("}");
        result
    }
    
}

fn main() {
    let mut json = Json::Object(vec![
        ("name".to_string(), Json::String("John".to_string())),
        ("age".to_string(), Json::Number(30.5)),
        ("is_student".to_string(), Json::Bool(false)),
        ("courses".to_string(), Json::Object(vec![
            ("name".to_string(),Json::String("Math".to_string())),
            ("day".to_string(),Json::String("Monday".to_string())),
        ])),
        ("grades".to_string(), Json::Array(vec![
            Json::Number(90.5),
            Json::Number(85.0),
            Json::Number(88.5),
        ])),
    ]);

    let mut printer = JsonPrinter{indent: 0};
    println!("{}", json.accept(&mut printer));
}

結果

{
  "name": "John", 
  "age": 30.5, 
  "is_student": false, 
  "courses": {
    "name": "Math", 
    "day": "Monday"
  }, 
  "grades": [90.5, 85, 88.5]
}

まとめ

実装すると,大体理解できた.確かにコンパイラ使うときには使えそう.コンパイラにdynを付けよと言われてつけたけど, よくわかっていない.認識的には「traitは実装によってメモリサイズが可変なのでそれを伝えるため」今度読むようにキーワードをメモ 仮想メソッドテーブル(vtable),動的ディスパッチ,動的サイズ型(Dynamically Sized Types、DST)

qnighy.hatenablog.com

Static single-assignment formってなんぞと思ったのでメモ

背景

wasm runtimeを作る選択肢としてllvmチュートリアルカレイドスコープ作ってみよう)を読んでいたら知らない概念が出てきたのでメモ.wikipediaを参照となっていたのでそこからスタート.(以後SSA) llvm.org

japan語で検索するなら

静的単一代入 ssa が良さげ.

wikipedia 曰く

In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element.

コンパイラ設計において、静的単一代入形式(しばしばSSA形式または単にSSAと略される)とは、中間表現(IR)の特性であり、各変数が正確に一度だけ代入され、使用される前に定義されることを要求する。元のIRの既存の変数はバージョンに分割され、新しい変数は教科書では通常、元の名前に添え字をつけて示され、すべての定義が独自のバージョンを持つようになる。SSAの形式では、use-defの連鎖は明示的で、それぞれが単一の要素を含んでいます。

下の例がバージョンを持つこと,一度だけ代入されることの例としてわかりやすかった.

y := 1 
y := 2 
x := y

=>

y 1  := 1 
y 2  := 2 
x 1  := y 2

use-defとdef-use

同じものかと思ったら別物だった.GPTに例を提示してもらい,自分の解釈と一致したので記載

=================以下GPT=================

使用定義チェーン(UD Chain)と定義使用チェーン(DU Chain)の具体例を以下に示します。これは簡単なコード例を通じて、これらの概念がどのように機能するかを説明するものです。

コード例

以下の簡単なプログラムを考えます:

1: int x = 5;
2: int y = x + 1;
3: x = 10;
4: int z = x + 2;

このコードを使って、UDチェーンとDUチェーンを説明します。

使用定義チェーン(UD Chain)

  • 行2の x のUDチェーン:

    • この場合、行2で x が使用されています。x の値は行1で定義されているので、行2の x のUDチェーンは行1の定義にリンクされます。
    • UD(x at line 2) = {definition at line 1}
  • 行4の x のUDチェーン:

    • 行4で x が再度使用されていますが、この時点での x の値は行3で再定義されています。そのため、行4の x のUDチェーンは行3の定義にリンクされます。
    • UD(x at line 4) = {definition at line 3}

定義使用チェーン(DU Chain)

  • 行1の x のDUチェーン:

    • 行1で x は5に設定されています。この定義から直接使用されるのは行2です。
    • DU(x at line 1) = {use at line 2}
  • 行3の x のDUチェーン:

    • 行3で x が再び定義され(10に設定)、この値は行4で使用されます。
    • DU(x at line 3) = {use at line 4}

これらのチェーンを理解することは、コンパイラがコードをどのように最適化するかを理解するのに役立ちます。例えば、もし行2と行4の間で x に関する操作がなければ、x の初期値が不変であると判断し、定数伝播を行うことができます。また、変数の生存期間やスコープを理解することで、メモリ管理の最適化も可能になります。

=================GPT終わり=================

コンパイラ最適化の文脈での恩恵

  • Constant propagation : 実行時からコンパイル時への計算の変換。たとえば、命令a=3*4+5をa=17であるかのように扱います。;
  • Value range propagation: 計算が取り得る潜在的な範囲を事前計算し、事前に分岐予測を作成できるようにします。
  • Sparse conditional constant propagation : 一部の値の範囲チェックにより、テストで最も可能性の高い分岐を予測できるようになります
  • Dead-code elimination: 結果に影響を与えないコードを削除します。
  • Global value numbering: 同じ結果を生成する重複した計算を置き換えます
  • Partial-redundancy elimination:プログラムの一部のブランチで以前に実行された重複した計算を削除します。
  • Strength reduction :高価な演算を、より安価だが同等の演算に置き換えます。たとえば、整数の乗算または 2 のべき乗による除算を、より安価な可能性のある左シフト (乗算の場合) または右シフト (除算の場合) に置き換えます。
  • Register allocation:限られた数のマシンレジスタを計算に使用する方法を最適化します。

コンパイラの最適化の例で有名な(?)なStrength reduction(べき乗をシフト計算に変換)もこれなんだーといった感じ.

golangの静的解析の文脈でもSSA

golangは学生の頃息抜きに入門したきりでやった限りで知識が怪しいが,golangは静的解析のパッケージが標準ライブラリに含まれていることは知識としては知っていた. その標準ライブラリにSSAが含まれているようなので,SSAが静的解析の文脈でどのような利用されるかはGolangのこのパッケージ経由で調べると見つかりやすそう.

pkg.go.dev

軽くDocを眺めていたら,ここでもwikipediaのリンクがあった...わかりやすかったしそれはそう.

http://www.dcs.gla.ac.uk/~jsinger/ssa.htmlみたいに,DocのOverviewで色々紹介されているので,wikiとGoのssaのライブラリのdocを読むとざっくりわかっていいかもしれない.

まとめ

wikipediaを流し見しただけになったが,多分わかった(フラグ)のでllvmチュートリアルを読み進めることにする. またなんぞとなったらメモを書く.

rustの勉強がてらwasmのruntimeを作ってみる【準備編】

この分野は素人なのでなにか間違いがあれば教えて下さい

ゴール

github.com

$ rustup target add wasm32-wasi
$ rustc hello.rs --target wasm32-wasi
$ wasmtime hello.wasm

runtimeの一つである,wasmtimeの例のようにrustのwasm32-wasi(wasi)に準拠したwasmを解釈して実行できるバイナリ zucca-wasmを作る.(さすがにすべてのapiをさばけるようにするのはしんどいかもしれないので一部使えないようにするかもしれない)

まずはwasmのruntimeの設計の種類

wikipedia曰く,

参考資料

github.com github.com developer.mozilla.org engineering.linecorp.com github.com

結論

github.com

  • MVP実装
  • AOT(ahead-of-time)compiler

interpreterのほうが楽な気がするが一旦はAOTで行う.

【WIP】Atcoder Rustで使えるcrateのDocを全部眺めてみる

概要

Atcoderで最近Python -> Rustに移行している最中でライブラリを作成中. ライブラリーを作りつつ,Atcoderで使えるcrate一覧に記載があるcrateを眺めているのでそのメモ. 使えそうな問題があれば別途記事をまとめていく. https://img.atcoder.jp/file/language-update/language-list.html#:~:text=Rust

ac-library-rs@=0.1.1

acl (AtCoder Library)のRust実装版.

https://atcoder.github.io/ac-library/master/document_ja/atcoder.github.io

once_cell@=1.18.0

docs.rs

static_assertions@=1.1.0

docs.rs

varisat@=0.2.2

docs.rs

CDCLとSATに関連しているやつ.

使い方

jix.github.io

Aalto University(スウェーデン)の講義資料(まだ読んでない)

users.aalto.fi

SATソルバーを使って数独を解く. ipsj.ixsq.nii.ac.jp

如何せん全く知らない分野なので軽めに眺めてほへーという感じ.

memoise@=0.3.2

docs.rs

メモ化再帰を行うときに使えるattribute macro

例:

use memoise::memoise;
fn main() {

    #[memoise(n <= 10)]
    fn fib(n: i64) -> i64 {
        if n == 0 || n == 1 {
            return n;
        }
        fib(n - 1) + fib(n - 2)
    }
    let ans = fib(10);
    println!("{}",ans);

}

=> 55

use memoise::memoise;
fn main() {

    #[memoise(n <= 10)]
    fn fib(n: i64) -> i64 {
        if n == 0 || n == 1 {
            return n;
        }
        fib(n - 1) + fib(n - 2)
    }
    let ans = fib(10);
    println!("{}",ans);

}
thread 'main' panicked at src/bin/a.rs:4:5:
index out of bounds: the len is 11 but the index is 11

定義した枠を超えるとpanicする. 一応,キャッシュする定義域を指定しない方法もあるが,動的にキャッシュを残す.おそらくパフォーマンスは落ちる.

use memoise::memoise;
fn main() {

    #[memoise(n)]
    fn fib(n: i64) -> i64 {
        if n == 0 || n == 1 {
            return n;
        }
        fib(n - 1) + fib(n - 2)
    }
    let ans = fib(11);
    println!("{}",ans);

}

memoise => Memoise function by using Vec memoise_map=> Memoise function by using BTreeMap

キャッシュは,Vec版とBtreeMapがあるらしい.キャッシュするもの値が連続値でない場合は,BtreeMapを使うといいだろう.

使えそうな問題 atcoder.jp

argio@=0.2.0

docs.rs

use argio::argio;

#[argio]
fn main(n: usize, a: [i64; n]) -> i64 {
    a.into_iter().sum()
}

関数の引数と戻り値を標準入出力から取るように変更するマクロ.

[tex:N]
[tex:A_1 A_2 ... A_N]

この標準入力を受け,Aの合計値を標準出力で出力.

少しコード量が減り楽ができそう.ただし,自分のAtcoderのテンプレートはproconioで作っているので使わないかな...

bitvec@=1.0.1

docs.rs

bitvec provides a foundational API for bitfields in Rust. It specializes standard-library data structures (slices, arrays, and vectors of bool) to use one-bit-per-bool storage, similar to std::bitset and std::vector in C++.

Additionally, it allows a memory region to be divided into arbitrary regions of integer storage, like binaries in Erlang.

If you need to view memory as bit-addressed instead of byte-addressed, then bitvec is the fastest, most complete, and Rust-idiomatic crate for you.

bitvec は、Rust におけるビットフィールドの基礎となる API を提供します。これは、C++のstd::bitset<N>やstd::vector<bool>と同様に、標準ライブラリのデータ構造(スライス、配列、boolのベクトル)を1ビット/ブールのストレージに特化したものです。
さらに、Erlangのバイナリのように、メモリ領域を整数ストレージの任意の領域に分割することができます。
もしメモリをバイトアドレスではなくビットアドレスで見る必要があるなら、bitvecは最も高速で、最も完全で、Rustらしいクレートです。

1bit(boolも1bit)の場合は,bitvecが高速らしい.このクレートのDocではErlangの名前が多々出てくるが詳しいことは知らないのでそこらへんは読み飛ばしています.(VMがあって,ElixirがそのVM上で動いていることことくらいの知識がない...Elixirも使ったことない,Rustを演る人はErlangくらい知っているよねレベルの話なんだろうか.)

counter@=0.5.7

docs.rs

Counter counts recurrent elements of iterables. It is based on the Python implementation.

Pythonのcollections.Counterをベースに作られている.

数学的にはこれが近いらしい. en.wikipedia.org

テストを眺めていて気になったものを抜粋 docs.rs

test_add_update_iterable

    #[test]
    fn test_add_update_iterable() {
        let mut counter = Counter::init("abbccc".chars());
        let expected = hashmap! {
            'a' => 1,
            'b' => 2,
            'c' => 3,
        };
        assert!(counter.map == expected);

        counter += "aeeeee".chars();
        let expected = hashmap! {
            'a' => 2,
            'b' => 2,
            'c' => 3,
            'e' => 5,
        };
        assert!(counter.map == expected);
    }

まさかの+=演算子(-=も実装されている)が定義されている.Counter同士ならわかるがこれは便利.

impl<I, T, N> AddAssign<I> for Counter<T, N>
where
    I: IntoIterator<Item = T>,

most_common_ordered

countが多いかつkeyでソート.

let by_common = "eaddbbccc".chars().collect::<Counter<_>>().most_common_ordered();
let expected = vec![('c', 3), ('b', 2), ('d', 2), ('a', 1), ('e', 1)];
assert!(by_common == expected);

test_total

    fn test_total() {
        let counter = Counter::init("".chars());
        let total: usize = counter.total();
        assert_eq!(total, 0);

        let counter = Counter::init("eaddbbccc".chars());
        let total: usize = counter.total();
        assert_eq!(total, 9);
    }

hashbag@=0.1.11

docs.rs

pathfinding@=4.3.0

docs.rs

recur-fn@=2.2.0

docs.rs

indexing@=0.4.1

docs.rs

amplify@=3.14.2

docs.rs

amplify_derive@=2.11.3

docs.rs

amplify_num@=0.4.1

docs.rs

easy-ext@=1.0.1

docs.rs

multimap@=0.9.0

docs.rs

btreemultimap@=0.1.1

docs.rs

bstr@=1.6.0

docs.rs

az@=1.2.1

docs.rs

glidesort@=0.1.2

docs.rs

tap@=1.0.1**

docs.rs

omniswap@=0.1.0

docs.rs

multiversion@=0.7.2

docs.rs

num@=0.4.1

docs.rs

num-bigint@=0.4.3

docs.rs

num-complex@=0.4.3

docs.rs

num-integer@=0.1.45

docs.rs

num-iter@=0.1.43

docs.rs

num-rational@=0.4.1

docs.rs

num-traits@=0.2.15

docs.rs

num-derive@=0.4.0

docs.rs

ndarray@=0.15.6

docs.rs

nalgebra@=0.32.3

docs.rs

alga@=0.9.3

docs.rs

libm@=0.2.7

docs.rs

rand@=0.8.5

docs.rs

getrandom@=0.2.10

docs.rs

rand_chacha@=0.3.1

docs.rs

rand_core@=0.6.4

docs.rs

rand_hc@=0.3.2

docs.rs

rand_pcg@=0.3.1

docs.rs

rand_distr@=0.4.3

docs.rs

petgraph@=0.6.3

docs.rs

indexmap@=2.0.0

docs.rs

regex@=1.9.1

docs.rs

lazy_static@=1.4.0

docs.rs

ordered-float@=3.7.0

docs.rs

ascii@=1.1.0

docs.rs

permutohedron@=0.2.4

docs.rs

superslice@=1.0.0

docs.rs

itertools@=0.11.0

docs.rs

itertools-num@=0.1.3

docs.rs

maplit@=1.0.2

docs.rs

either@=1.8.1

docs.rs

im-rc@=15.1.0

docs.rs

fixedbitset@=0.4.2

docs.rs

bitset-fixed@=0.1.0

docs.rs

proconio@=0.4.5

docs.rs

text_io@=0.1.12

docs.rs read!()マクロは、常に次のアスキー空白文字( \n, ˶r, ˶t, またはスペース)まで読みます.

rustc-hash@=1.1.0

docs.rs

Fast, non-cryptographic hash used by rustc and Firefox.

なんでFirefoxって思ったけど,どちらもmozillaか.

A speedy hash algorithm for use within rustc. The hashmap in liballoc by default uses SipHash which isn't quite as speedy as we want. In the compiler we're not really worried about DOS attempts, so we use a fast non-cryptographic hash.

HashのDOS攻撃 => hashテーブルで衝突を狙い計算機リソースを無駄に消費させる攻撃. Pythonのsetで起こるので気をつけよう的なことがAtcoderの解説でもされていた. atcoder.jp

smallvec@=1.11.0

docs.rs

一定数の要素をインライン(つまり、スタック上)に格納し、それを超える場合にはヒープに割当します。以下の利点があります.

キャッシュ局所性の向上

インラインに要素を格納することで、データが連続したメモリブロックに配置され、CPUキャッシュの効率が向上します。これは、データアクセス時のレイテンシを減らし、全体的なパフォーマンスを向上させることができます。

アロケータトラフィックの削減

小さなデータセットの場合、smallvecはヒープ割り当てを避けることができます。これは、メモリ割り当てと解放に関連するオーバーヘッドを減らし、特に割り当てが頻繁に行われるシナリオではパフォーマンスの向上につながります。

なんのこっちゃ.LLVMに同じ名前のデータ構造があるので,本気で最適化をする際にはよく使われるっぽい.背景知識がなさすぎて絶望. どういう理由でatcoderで使えるLibに追加されたのだろうか...

llvm.org

よく調べてみるとRust製のhtmlのレンダーの配下のプロジェクトっぽい.使い所がいまいちわからないのでここを見てみようと思う. github.com

以下GPT4

smallvecの特性は、競技プログラミングのようなパフォーマンスが重要な状況で非常に有用です。競技プログラミングでは、実行時間やメモリ使用量を最小限に抑えることが求められます。smallvecは、以下のような場面で特に役立ちます。

小さなグラフの操作

競技プログラミングの問題には、グラフに基づくものがよくあります。ノード数が比較的少ない場合や、各ノードが少数のエッジしか持たない場合、ノードの隣接リストをsmallvecで保持することで、メモリの割り当て回数を減らし、キャッシュの効率を向上させることができます。

効率的なスタックとキュー

アルゴリズムでスタックやキューが必要な場合、そのサイズが予測可能であれば、smallvecを用いることで実行効率を向上させることができます。たとえば、深さ優先探索(DFS)や幅優先探索(BFS)で探索するノードの数があらかじめわかっている場合、スタックやキューにsmallvecを使用することで、メモリ割り当てのオーバーヘッドを減らすことができます。

ダイナミックプログラミング

ダイナミックプログラミング(DP)の解法を実装する際、特に状態の数が限られているケースでは、DPテーブルをsmallvecの配列で表現することができます。状態遷移に必要なデータが少ない場合、smallvecを使用することでメモリアクセスの効率を上げることができます。

小さな集合の管理

競技プログラミングの問題で、小さな要素の集合を頻繁に作成・操作する必要がある場合(例えば、ある条件を満たす要素の集合)、smallvecを使用すると、集合の作成や操作時のメモリ割り当てコストを削減できます。

パフォーマンスチューニング

特定の問題において、アルゴリズムの実行時間がぎりぎりの場合、smallvecを使って微調整を行うことが解決策になることがあります。ヒープ割り当てを避けることで、わずかながらもパフォーマンスを改善できる場合があります。

これらの利用例からもわかるように、smallvec競技プログラミングにおいて、特定の条件下でパフォーマンスの最適化を図るための強力なツールとなり得ます。ただし、その効果は使用する状況やデータのサイズに依存するため、適切な場面での利用が重要です。

如何せん,allocにコストが掛かることは知識として知っているが,どのくらいパフォーマンスに影響出るかは,低レイヤー言語での実装経験がなさすぎるのでどこかで試してみよう.

todo

  • allocのパフォーマンスへの影響

ソフトウェアと人間どちらのほうがソフトか.【前編】

ソフトとは

ここでいうソフトとは,変更しやすさを指す.本記事ではソフトウェアの設計の話をしないので注意. 文脈的には企業でのDXを行う際に,ソフトウェアのロジックに追記を行うか,組織のフローを変えるかどちらが良いか的な話である. データなどはないのでいわゆるポエム記事である.筆者はITエンジニアなので気持ちそっちによった記事です.

本記事でのDXのゴール

世の中ではさまざまなDXの定義があると思うが,本記事での定義は 「組織全体のあらゆる工数を最小化する」がゴールの一つであると考えている. 他にも,「データを蓄積しやすくし,データを分析し新しいビジネスを生み出す」などデータを活用して組織やビジネスを変革(Transformation)するといった文脈でも使うが本記事では「組織全体のあらゆる工数を最小化する」をゴールとしてみる.(それってIT化ではという話はあるが...)

gpt4パイセンの意見A

とりあえずGPT4に上記の文章を放り込んでみた.

企業におけるデジタルトランスフォーメーション(DX)の文脈で、変更しやすさを基準に「ソフトウェア」と「人間(組織のフロー)」のどちらがより「ソフト」かを考慮すると、一般的には以下のような視点から考察できます。

ソフトウェアの変更しやすさ

  • 柔軟性:ソフトウェアはコードを編集することで機能を追加、修正、または削除できます。このプロセスは比較的迅速に行うことが可能です。
  • スケーラビリティ:デジタルシステムはスケールアップやスケールダウンが容易で、事業の成長や変化に応じて容易に調整できます。
  • 自動化の可能性:多くの業務プロセスはソフトウェアによって自動化可能で、効率化を図ることができます。

人間(組織のフロー)の変更しやすさ

  • 文化的・行動的変化:組織のフローや文化を変更することは、従業員の態度や行動パターンに影響を及ぼし、時間がかかる場合が多いです。
  • 抵抗と適応:新しい変更に対して従業員からの抵抗が生じる可能性があります。また、適応には教育とトレーニングが必要となります。
  • 持続可能性:組織の変更は持続的な努力が必要であり、継続的なコミュニケーションとサポートが重要です。

総合的な考慮

  • 変更のスピード:ソフトウェアの変更は比較的迅速に行うことができますが、組織のフローを変更することは時間と労力を要します。
  • 影響範囲:ソフトウェアの変更は特定の業務プロセスやシステムに直接影響しますが、組織のフローを変更することは、より広範な影響を及ぼす可能性があります。

結論として、変更しやすさを基準にすると、一般的にはソフトウェアの方が人間(組織のフロー)よりも「ソフト」と考えられます。ただし、実際には組織の特定の状況やニーズによって、最適なアプローチは異なる場合があります。

なるほど.人間の文化や行動パターンを変えることは難解であるためソフトウェアのほうがソフトだろうという話.ただし上記の議論では,IT人材不足で組織に保守する人が少ないということが抜けているのでそれを追加してみよう.

IT人材不足であることを考慮に入れる

IT人材不足を前提とした場合、企業におけるデジタルトランスフォーメーション(DX)においてソフトウェアと組織のフローの変更しやすさを比較すると、いくつかの重要な点が浮かび上がります。

ソフトウェアの変更しやすさ(IT人材不足を考慮)

  • 専門技術の必要性:ソフトウェアの変更や開発には専門的なITスキルが必要です。人材不足の状況では、必要な技術を持つスタッフの確保やアウトソーシングが課題となります。
  • 開発リソースの制約:限られたITリソースのもとでは、ソフトウェアの変更や新規開発のプロジェクトが遅延する可能性があります。
  • コストと時間:適切なIT人材を確保するための追加コストや、新たなスタッフのトレーニングに必要な時間が増加する可能性があります。

人間(組織のフロー)の変更しやすさ(IT人材不足を考慮)

  • 非ITスキルの活用:組織のフローを変更する際には、ITスキルに依存しない他のスキルセットが重要になります。コミュニケーション、プロジェクト管理、リーダーシップなどのスキルが活用されます。
  • 内部リソースの活用:既存の従業員やチームを活用して組織変更を実施することで、外部からの人材確保に関連するコストや時間を節約できます。
  • 文化的変化の重要性:組織の文化や行動の変化はITスキルとは無関係に進めることが可能で、長期的な組織の効率性や柔軟性を向上させることができます。

総合的な考慮

  • リソースのバランス:ソフトウェアの変更は専門的なスキルを必要とするため、IT人材不足の状況では挑戦的です。一方で、組織のフローの変更は既存の従業員のスキルや経験を活用でき、より現実的な選択肢となるかもしれません。
  • 長期的な視点:IT人材の育成や外部リソースの活用により、長期的にはソフトウェア変更の能力を内部で構築することも重要です。

結論として、IT人材不足の状況では、ソフトウェアの変更よりも組織のフローを変更する方が「ソフト」であり、現実的なアプローチとなる可能性が高いです。ただし、組織の具体的な状況や長期的な目標に基づいて、最適な戦略を選択する必要があります。

ITエンジニア的には好みの回答がきました. ただし「組織の文化や行動の変化はITスキルとは無関係に進めることが可能」とのことだが,組織をより最適にする人事や組織論的なスキルセットとITスキルのどちらが希少であるかは注意が必要そうだ.

解決策

ここまではGPT4のそれっぽい納得できそうな話だけだったので,自身の薄っぺらい経験とどうするかの種をとりあえず並べようと思う. ちょっと記事がながくなりそうなので,概要だけ書いて続きは後編に任せようと思う.

  • ITエンジニアはコモンズなのかもしれない
  • ロジックの上にITを乗せるのではなく,ITの上にロジックを乗せることを前提にすること

気になった方は,あまり期待せずに後編へ(WIP)

以上

流行りのGPTsでウミガメのスープを錬成するやつを作った

作ったやつ

https://chat.openai.com/g/g-tx43vEgZF-umigamenosupu-situation-puzzle-solver

概要

openai.com 2023/11上旬, 任意の目的のためにchatgptをカスタマイズできる GPTsが公開された. ロゴを作成するものやデータをアップロードして分析して可視化したりと,openaiがサンプルを出していたり色々な人達が遊んでいるようだ. カスタマイズできることは,事前情報としてKnowledgeを入れてQ&Aをchatgptにさせたり,Web Browsing,DALL·E Image Generationなどできるようだ.今回作ったものは,そこらへんは使わないシンプルなものだがギリギリ遊べるものが15分くらいでできて感動したのでとりあえず記事を書いた次第である.また今後やる気が出れば,拡張または新しいカスタイマイズを作る予定なので,最後に展望をMemoっておく.

手順

1. 基本はchat形式で設定を書くことができる.(設定の会話ログは残らないようなので注意)

prompt

ウミガメのスープ(Situation puzzle)を作りたい

## フロー
1. AIが問題を作成
2. ユーザが行える行動は以下である
- ヒントを聞くこと
- Yes,Noで答えることができる質問をする
- ギブアップする
- 回答を言う

アイコンは幾何的な亀を書いてほしい.色は緑にしてほしい 

2. テストプレイ

以下の問題点が見つかった.

  • 難易度が低く感じた
  • 問題を生成してもらうために,問題よろしく的なことを言う必要があり少し不親切

3. 「難易度が低く感じた」解決

chatgptに聞いてみた.=> 解決したかはわからない

人間

ウミガメのスープの作問をしています.
難易度を上げるコツや良問になるようなコツを考えてください

gpt4

「ウミガメのスープ」という問題作成において難易度を上げるコツや良問になるためのコツについて考えると、以下の点が重要です:

1. **多角的な思考を促す設定**:問題が一つの視点からではなく、多様な角度から考える必要があるような設定を用意します。これにより、解答者は異なる可能性を探求し、論理的思考を深めることができます。

2. **適切な情報の隠蔽**:重要な手がかりや情報を巧みに隠すことで、解答者が自ら推理する必要があります。ただし、あまりにも多くの情報を隠しすぎると、問題が不公平になる可能性があるため、バランスが重要です。

3. **誤解を招く表現の使用**:表面上は明確に見えるが、よく考えると異なる解釈が可能な表現を用いることで、解答者が思い込みに陥るのを避け、深い思考を促すことができます。

4. **複数の正解や解釈の可能性**:一つの正解だけでなく、複数の可能性が考えられるような問題を作成することで、解答者の創造性や柔軟な思考を引き出すことができます。

5. **ストーリーテリングの要素**:単なる論理問題ではなく、物語の要素を取り入れることで、問題に対する興味や関心を高めることができます。これにより、解答者はより深く問題に没頭することができるでしょう。

これらのコツを念頭に置きながら、「ウミガメのスープ」の問題を作成すると、より高度で興味深い問題が生まれる可能性が高まります。

人間

英語でお願いします.

gpt4

Creating "Umi-Ga-Me no Soup" (Turtle Soup) puzzles with increased difficulty and quality involves several key strategies:

Encourage Multifaceted Thinking: Design scenarios that require thinking from multiple perspectives, not just a single viewpoint. This encourages solvers to explore various possibilities and deepen their logical reasoning.

Strategic Concealment of Information: Skillfully hide key clues or information to compel solvers to deduce answers themselves. However, be careful not to hide too much, as it could make the puzzle feel unfair. Balancing the amount of information given and withheld is crucial.

Use of Misleading Statements: Employ statements that seem clear on the surface but can be interpreted differently upon deeper consideration. This prevents solvers from jumping to conclusions and promotes thorough thinking.

Multiple Correct Answers or Interpretations: Instead of having just one correct answer, create puzzles where multiple outcomes are possible. This approach stimulates creativity and flexible thinking in solvers.

Incorporating Storytelling Elements: Adding narrative elements to your puzzles can increase engagement and interest. By weaving a story into the puzzle, solvers are more likely to be immersed and invested in finding the solution.

By keeping these tips in mind while creating "Umi-Ga-Me no Soup" puzzles, you can craft more challenging and intriguing problems that engage and stimulate solvers in thoughtful and creative ways.

4. gptが生成した文章を"Instructions" に登録

I am the Situation Puzzle Solver, designed to create and guide users through situation puzzles, commonly known as 'lateral thinking puzzles' or 'yes-no puzzles'. In each session, I will automatically generate a unique puzzle scenario. Users can interact with me by asking yes-or-no questions to gather clues about the scenario. They can also request hints, attempt to solve the puzzle by stating their solution, or give up and ask for the answer. My responses will be concise, encouraging users to think laterally and ask insightful questions. I'll provide up to three hints upon request, each one revealing more about the puzzle. If a user gives up, I'll explain the solution and then present a new puzzle. I am designed to offer a challenging yet enjoyable puzzle-solving experience.
Creating "Umi-Ga-Me no Soup" (Turtle Soup) puzzles with increased difficulty and quality involves several key strategies:

Encourage Multifaceted Thinking: Design scenarios that require thinking from multiple perspectives, not just a single viewpoint. This encourages solvers to explore various possibilities and deepen their logical reasoning.

Strategic Concealment of Information: Skillfully hide key clues or information to compel solvers to deduce answers themselves. However, be careful not to hide too much, as it could make the puzzle feel unfair. Balancing the amount of information given and withheld is crucial.

Use of Misleading Statements: Employ statements that seem clear on the surface but can be interpreted differently upon deeper consideration. This prevents solvers from jumping to conclusions and promotes thorough thinking.

Multiple Correct Answers or Interpretations: Instead of having just one correct answer, create puzzles where multiple outcomes are possible. This approach stimulates creativity and flexible thinking in solvers.

Incorporating Storytelling Elements: Adding narrative elements to your puzzles can increase engagement and interest. By weaving a story into the puzzle, solvers are more likely to be immersed and invested in finding the solution.

By keeping these tips in mind while creating "Umi-Ga-Me no Soup" puzzles, you can craft more challenging and intriguing problems that engage and stimulate solvers in thoughtful and creative ways.

5. 問題を生成してもらうために,問題よろしく的なことを言う必要があり少し不親切

Conversation startersに登録(IT知識が必要な問題など制約を設けてそれっぽい問題を作ってくれる)

6. prompt injection対策

learnprompting.org prompt injectionとは

Prompt injection is the process of hijacking a language model's output. It allows the hacker to get the model to say anything that they want.

言語モデルの出力をハイジャックするプロセスのこと.クラッカー(ハッカー)は言語モデルに言わせたいことを言わせることができます

事前情報として入力したKnowledgeなど,カスタマイズする際に使ったpromptやノウハウなどを抜き出すことができます.今回使った対策はあえて載せません,この記事が古くなったときなんの対策にもならなくなったプロンプトを,万一コピペで使う人が出てくるのも問題なので...prompt injectionと検索すればたくさん出てくるのでそちらを参考にしてください.

7 . 完成品

https://chat.openai.com/share/c5aa20f9-4917-4e0f-b92b-31b3eb315d19

今後の展望

  • 難易度設定ができるようにする(質問回数などを制約)
  • あらゆる設定のTRPG(まとめ or 投稿サイトもあるとおもしろいかも)

以上