maikiichanのブログ

いろいろ

「実践コンパイラ構成法」を読んだ

www.coronasha.co.jp

実は1年くらい積んでました。OCamlコンパイラでも書いてみるかと思って読んでみましたが思っていたより良い本でした。 ちなみにOCaml自体には

プログラミングの基礎 ((Computer Science Library)) | 浅井 健一 |本 | 通販 | Amazon

で入門済み。 コンパイラには

低レイヤを知りたい人のためのCコンパイラ作成入門

で入門済みですが、OCamlコンパイラの前提知識がなくても十分読めそうな本だと思います。 本ではビルド部分はMakefileで頑張ってる感じですが、私はDuneでやりました。

8月に読んだ本

  • データ指向アプリケーションデザイン
  • 秋本治の仕事術
  • みんなのGo言語(改訂2版)

ある程度話題性のある技術書は大体全部買うようにしている。

秋本治の本だけはちょっと違っていて、自分はこち亀を全巻持っているくらいにはこち亀フリークで秋本治という人間そのものの大ファンなので買った。幼少期の頃からこち亀を読んで育ってきた。そのおかげで今現在こうなっているとも言えるし、このざまとも言える。

ちなみにこの「秋本治の仕事術」の内容は実に凡庸で、普通のよくある仕事本だと思った。

Rustでプライオリティキューを扱う

RustにはC++でいうstd::priority_queue的なものとしてstd::collection::BinaryHeapが存在する。 使い方はC++や他言語のqueueと一緒だが、Option型を返すので少し気を使う必要がある。

以下サンプル

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(5);

// unwrap()を使うパターン。あまり行儀がよくない(競技プログラミングでは使うかもしれない)
    println!("{}", heap.pop().unwrap()); // => 5

    // if letでアンラップするパターン。
    if let Some(n) = heap.pop() {
        println!("{}", n) // => 3
    }

     // パターンマッチ。
    match heap.pop() {
        Some(n) => println!("{}", n),  // => 1
        None => unreachable!(),
    }
}

RustでPOJ 3253を解く

POJ 3253、蟻本にも載ってる。身近な問題がモデルになっているが、ハフマン符号を作るときのアルゴリズムとほとんど一緒で、Queueを使って実装すればO(NlogN)で解ける。

この実装では貪欲法でナイーブな実装なので時間計算量は O(n^ 2)になっているけど、Rustの練習的な側面もあるので今回は妥協する。 競技プログラミング的な文脈ではこれで十分ACが取れる。

use std::mem::swap;

fn main() {
    let mut n = 3;
    let mut l = vec![8, 5, 8];

    let mut ans = 0;
    while n > 1 {
        let mut mii1 = 0;
        let mut mii2 = 1;

        if l[mii1] > l[mii2] {
            swap(&mut mii1, &mut mii2);
        }

        for i in 2..n {
            if l[i] < l[mii1] {
                mii2 = mii1;
                mii1 = i;
            } else if l[i] < l[mii2] {
                mii2 = i;
            }
        }

        let t = l[mii1] + l[mii2];
        ans += t;

        if mii1 == n - 1 { swap(&mut mii1, &mut mii2); }
        l[mii1] = t;
        l[mii2] = l[n - 1];
        n -= 1;
    }

    println!("{}", ans);
}

アルゴリズムについての解説は蟻本p.50に任せる。

ポートフォリオサイト的なもの

をつくりました。

https://fumita.tech

見た目はシンプルだけど、Google domainsでドメイン取ってCDNから配信とかしたりしているようです。

以上です。

競プロを始めた

エンジニアとしての能力にはいろいろあると思うけど、フロントエンドとかバックエンドみたいないわゆる「Webアプリケーションエンジニア」をやっているとライブラリの使い方だとか無駄に消耗するような事柄に終始しがち。

やれRailsMySQLの相性がーとか。やれVue.jsとTypeScriptの相性がーとか。 そういう非本質的なことで消耗するのが我々の理想とするエンジニア像なのだろうか。少なくとも自分は違うと思っていて、やっぱり圧倒的なコーディング力というものに強い憧れがある。

自分が「こうなりたい」と思うエンジニアはLinus TorvaldsとかJeff DeanとかChris Lattnerとか、真賀田四季とか玖渚友とか是枝一希のようなタイプで。

自分と彼らとの違いは「データ構造とアルゴリズム」や「問題解決」とかの力量差だと今は考えていて、令和の今の時代にそこを効率よく鍛えようとするのであれば競技プログラミングが手っ取り早いのではないかと思っている。はっきり言って自分にはTAOCPを読みながら演習問題を全部解く時間はない。

というわけで競技プログラミング始めてみました。とりあえずAtCoderのABCのC問題くらいまでは安定して解けるようになりたいなぁ。

そもそもフロントエンドよりもバックエンドとかインフラの方が向いているような気がしなくもない

「プログラミングRust」を読んだ

1ヶ月くらい使ってずっとRustの勉強をしていて、やっとプログラミングRustを通読しました。 よく考えたらプログラミング言語についての本でここまで分厚い本を読んだのは初めてかもしれない...

この本はよくあるリファレンス的に用いる本とは違って、最初から最後まで通読して初めて価値の出てくる本のような気がします。

若干のオライリー本っぽさがありますが、厳密性とのトレードオフを考えれば現状で最高の入門書だと思います。(そもそもRustの学習曲線的に一番最初が山場だと思うので、入門書がこの分厚さになってしまうのは仕方のないこと)