C で使える LRU キャッシュ

uthash の example に LRU キャッシュの例が入っているので,これを自分のユースケースに特化して改造して利用した.

uthash: a hash table for C structures

github.com

(備考) python における LRU cache のはなし. pylru は 2018/3 時点の最新版では,put を get を繰り返していると evict 時の callback が呼ばれないことがある.原因は追及していない.lru-dict は確認した限りでは想定通りに動作した.

PowerPoint を Illustrator を介して eps に変換する

PowerPoint で作成した図を eps として利用する際に,以下の手順で変換すると楽であった.

  1. 図を選択して,右クリックして .xmf (ウインドウズメタデータフォーマット)で保存する.
  2. Illustrator で 1. で保存した .xmf を開く.
  3. eps として保存する.

特に,画像のリサイズや回転,およびポストスクリプトファイルの編集が不要で,そのまま使える点が楽であった.

lldb-rust を使うときの注意と問題

Ubuntu 16.04 標準で apt install lldb したときに入る lldb-3.8 とあわせて rust-lldb 使うと,breakpoint の設定が関数名経由でできない(ソースコードの行数指定によるbreakは可能).さらに,すべてのstep out 実行がstep in実行になる.これは非常に不便.lldb-4.0 とあわせて使うと,これらの問題は解決した.

しかし,lldb-4.0 のバイナリは libedit (readline の BSD 版)が有効になっていないようで,補完が効かなくなる.lldb-5.0 でも同じ状態だった.ビルドするしかないのだろうか... bugs.launchpad.net

Coursera Algorithm Part I を受講し終えた

Algorithms, Part I | Coursera を受講していて,先日無事に完了した.全体的に課題がかなり歯ごたえがあって,よい勉強になった.この講義は,全体的に応用を強く意識した説明がなされる.そのため,応用指向の人(わたしとか)に興味が持てる構成となっており,幅広い Software engineer の皆様にお勧めできる内容だと感じた.

講義中で一番面白いと感じたトピックは, Left-leaning Red-black tree の話である.Left-leaning Red-black tree は本講義のビデオに出てくる Robert Sedgewick 先生の発明で,より simple に Red-black tree を実装できるというもの.Red-black tree は非常に便利データ構造で,Self-balancing binary tree の中でも性能が安定している(insert, delete, search が log(n) で実行可能な)データ構造である.その性能の安定性から,ファイルシステムで利用されている他,C++ STLJava Collection など標準ライブラリにも幅広く利用されている.その Red-black tree が simple に書けるのはとても魅了的だと思った.というのも,Red-black tree の self-balancing の部分は特に複雑で,正しく実装するのは大変だからだ .ところが,少し調べたところLeft-Leaning Red-Black Trees Considered Harmfulという記事が見つかった.この記事では,Left-leaning Red-black tree の性能上の弱点や,利点として主張されている simplicity について疑わしいという主張がなされている.なかなか美味しい話はないものだ.

この手の「有用だが正確に作成することが難しいアルゴリズム・データ構造の単純化」や単純化による副作用の研究は,(分散合意アルゴリズムでいうところの Paxos made simple,Raft にあたると思うのだけど)非常に重要なので,もっと進むとよいと思った.アルゴリズムの実用性を上げる上で重要であるし,一昔前のquick sort の性能解析の話などを彷彿とさせるので熱い.