真野さん、松本さんと一緒にSoftware Designの特集記事に寄稿しました。
当初は3章構成の2章だけで、「配列 vs 連結リスト / HashMap vs Tree」みたいな企画内容として話が来たのですが、企画を見たときに「今どき連結リストとかわざわざ作ったり、古典的なアルゴリズムとデータ構造の話ってどこまで役に立つんだろうか？」みたいな、自分で何か設計するときに企画でいただいたような内容ってあんまり考慮することはないかな、ということを思い、オタク特有の早口でチャットに以下のようなことを書きました（一部読みにくかったので原文ママではない）
アルゴリズム選定。圧縮をJSで自前実装しないでネイティブで実装されたブラウザAPIを使おうとか、そういう方が実用的な気はしますね。木構造自前実装することなんてなさそう。今時は複雑なコードと速度がトレードオフになることはなさそう。
データ構造はどちらかというと機能性で選ぶことのほうが多そう
いまどきはよっぽど変なコーディングしないとCPUとかメモリで困ることってない。DBとか、通信の非同期かとか最適化とか、スクリプト言語はネイティブ言語のライブラリとかハードウェアアクセラレーションが効くようにしましょう、とかそっちの方が100倍効く。フロントエンドだと画面更新時の影響範囲が広くならないように・・・とかかな
これに関数型のエッセンスでもまぶしてあげれば良さそう
その結果、2章に引き続き3章も当社で、また内容も大幅変更ということになり、今回の記事となりました。
なぜこのような思いを持つようになったか
アルゴリズム的には高速とされる圧縮アルゴリズムLZ4に興味をもって実装したことがありました。ブラウザ上ではそのままは使えず、JSに移植してみたがそんなに早くなかった、というのが最初の原体験ですかね。実装言語とかそっちの方が影響が大きいと。当時のiPhone 3GSとか4の時代、WASMもその元になったasm.jsも出る前ですね。もちろん、実装言語とかが選べない場合に、限られた選択肢の中でベストを尽くすみたいなケースはあります。
また、当時はZStandardが出る直前ぐらいの時代で、いろんな圧縮アルゴリズム、画像圧縮アルゴリズムとかをどのように組み込むかみたいなことをしていましたが、このレベルまで来ると基本的にゼロからのアルゴリズムの自作は難しくなってきます。コンピュータサイエンスのすごく深い知識とかが前提になりますし、今から既存の圧縮アルゴリズムを超えるようなものを作れたとしたら即論文になるレベル。
そのようになってくると、だんだん組み合わせの工夫、みたいな話になってきます。以下のQiitaで書いた記事とかもそれですね。
それ以外にはPNG画像生成時に圧縮アルゴリズムを取り換えて高圧縮を狙うとかは僕もやってみました。Zopfliを使って互換性を保ったまま高圧縮にするとか、Brotliを使って互換性がなくてもいいからさらに頑張るとか。モバイルゲームだとGPUに読み込ませるときは無圧縮画像で渡すので、途中の互換性は不要だったりするので、そういう工夫もでき、いろいろ自由に試行錯誤できたのはよい経験になりました。あとは既存のアルゴリズムでも圧縮しやすいように可逆のPNGでもあえてディザリングで色数を落として16bitの色数に絞る（GPUにも16bitモードがあるので実環境上でも省メモリ）とか。
僕が良く使うたとえでいえば、ファッションというものが、自分で洋服を作るのではなく服の選び方にシフトしていく、みたいな時代の変遷ですね。ファッション全然わかんないですが。
もう1つ、二分探索とかTimSortとか頑張ってみたけど早くなかった、というのも経験としてありました。Goにジェネレータが来る前に、C++のSTLのように使えるコードジェネレータを作ってみたことがありました。アルゴリズムの本の通りにそのまま実装するだけでは実用的なものを作るのは難しいです。ただ、作ってみたこと自体は無駄ではなかったな、と思っています。
昔、本を読んで感動したBM法というアルゴリズムも、誰から聞いたか忘れましたが「今どきは使わないのだよ。SIMDでやっちゃうし」みたいな話も、自分には影響がありましたね。
データ構造について考えた
そんな時代にあって、アルゴリズムとデータ構造に求められるものはなんだろうか？というのが最初のチャットの話になります。データ構造とアルゴリズムの本を見ると、データのコレクションとソートみたいな話が多いです。動的計画法みたいなものもありますが、今回はそこは割愛しました。で、現代の言語だと最初からデータ構造が提供されているし、検索のメソッドも最初からついていることが当たり前です。原稿にも書きましたが、C言語とかC++の1990年代は当たり前ではなかったのですが、今は「どうやって検索しよう」と悩むこととかは減ったのでは、と思います。一方で、ウェブフロントエンドでは、イミュータブルという話が最近多く出てきますね。そのあたりを考えて2章の前半の僕のパートは構成しています。
- 配列、ソート済み配列、辞書
- データ構造のバリエーション
- 標準のデータ構造を扱う性能以外のメリット
- データ構造の理解がアドバンテージを産んだ時代
- 現代のデータ構造に求められる不変性
- なぜデータ構造やアルゴリズムの自作が難しくなったのか
- O記法の落とし穴
- 組み込みの配列や辞書の応用
- データ構造のようなアルゴリズム
- それでもデータ構造が大事なケース
まずは言語に組み込みのデータ構造をきちんと理解して使いましょう、という内容にしています。Go/JavaScript/Pythonの紹介をしています。当初はJavaとC++もありましたが。
1章は別の会社の方が書かれていたので内容は確認できませんでしたが、おそらくO記法とかの話は来るだろうと（そして来た）思い、それを踏まえた構成にしています。前節で書いた内容にプラスして、ジェネレータのような疑似データ構造のようなものとか、関数型の話をプラスして構成しています。
ぜひお手に取っていただけると
松本さんが書いたDuckDBの話も、本当はもっといろいろ興味深い話もありましたが紙面の都合でちょっと割愛されちゃっていたりしますが、それでも結構興味深い内容になっています。真野さんの3章も、アーキテクチャの失敗はアルゴリズムで覆せないぞ、という辛口な内容でネットワークからデータベースから幅広い話が入っていて、かなり実用的な内容となっています。
なかなかいい特集になったと思います。是非お近くの書店にダッシュしてお手に取っていただければと思います。