はてなブックマーク

Rust で平衡二分木を書くのは何となく難しいイメージがありました。 unsafe を使わずに実装できるものなのか気になったので、試しに実装してみました。 結論から言うと、unsafe を使わなくても平衡二分木は実装できました。また、unsafe だけでなく、Rc や RefCell も使っていません。 ただし NLL がないとコンパイルが通りませんでした。NLL は神機能ですね。 Splay 木 今回実装した平衡二分木は Splay 木というものです。 Splay 木は、search や insert などの典型的な操作を償却 時間で実行できます。 また、Splay 木は最後にアクセスしたノードを木のルートに持ってくる性質があるため、アクセスに局所性がある場合によい性能が出るそうです。 平衡二分木といえば何と言っても赤黒木ですが、赤黒木は実装が大変すぎるので今回は却下しました。 アルゴリ

この記事は KMC Advent Calendar 2017 の7日目の記事です。 昨日の記事は id:dnek さんの Unityで漢字パズルアプリを作ったよ(Android/iOS) でした。 シンプルだけどこだわって作っている感じがしてすごくよいですね。 (自分の作ったゲームはゲーム性へのこだわりが足りなくて微妙なのしかないので) さて、今日はインフラ的なレイヤーの話をします。 自由にメトリクスを取りたい！！ パフォーマンスの改善や障害対応を行うために、「fsync のレイテンシの分布が知りたい」「dentry cache のヒット率が知りたい」「IOオペレーションのサイズの分布が知りたい」といった、OS の低レイヤーの情報を集めたくなることがあります。 top, vmstat, sar などのコマンドを使ってメトリクスを得るのが普通ですが、OS が予め用意したメトリクスしか見ること

git grep や git log などのコマンドを実行したとき、デフォルトでは less がページャーとして使われる。 git log の場合はデフォルトの設定で特に困っていないが、git grep で出力が数行しかない場合にページャーが表示されるのはちょっと鬱陶しい。 git --no-pager grep とすればページャーなしで実行できるが、いちいちこのオプションを指定するのは面倒くさい。 これらのコマンドで利用されるページャーは git config で設定できる。 そこで、以下のように設定した。 git config --global core.pager "less -R -F -X" less の各オプションは以下のような意図で指定した： -R: 色を変更する制御文字をそのまま出力する。 -F: ファイル全体が一画面に収まる場合、less を自動的に終了する。 -X: l

(この記事は KMC アドベントカレンダー 2016 の3日目の記事です) はじめに みなさん以下のようなことで困ったことはないでしょうか？ ポート80を listen したいけど特権ポートなので、一般ユーザの権限で動くデーモンでは bind できない。 1024未満のポートは特権ポートと呼ばれ、一般ユーザの権限では bind することはできません。 この問題の解決策を考えてみます。 （なお、長々と説明を書いていますが、結論だけ知りたい人は一番下だけ読んで下さい） root で起動 まず、root であれば特権ポートを自由に bind できるので、root で対象デーモンを起動すれば、特権ポートを bind できます。 しかし、デーモンを root として動作させるのは一般にリスクが大きいです。 もしそのデーモンに脆弱性があった場合、root 権限を悪用される可能性があるわけです。 したが

Protocol Buffers で検索すると Protocol Buffersは遅い という MessagePack 作者による2008年の記事が未だに上位に来る。 一方で、Protocol Buffersは遅いのか という反論記事も見つかる。 一体遅いのか速いのかどっちなんだ！！ということで、ベンチマークを取ってみた。 2016年8月現在では、Protocol Buffer の最新バージョンは 3.0.0 であり、MessagePack の C++ バインディングの最新バージョンは 2.0.0 なので、これらのバージョンを使ってベンチマークを取ることにした。 ベンチマーク 元の記事を踏襲して、以下の４つのメッセージを使ってベンチマークを行った。 Test1: 2つの符号無し整数 Test2: 2つの符号付き整数 Test3: 8KBのバイト列 Test4: Test1 + Test2

はじめに お久しぶりです。KMC OB の id:nojima です。 この記事は KMC Advent Calendar 2014 の10日目の記事です。 昨日は id:murata さんの「受験生応援！Javascriptでひねくれ数列」 でした。 今日は C++ の unique_ptr の話です。 （最初は rvalue について書こうと思っていたのですが、書いてみると unique_ptr だらけになったのでタイトルを変えました。なので、KMC Advent Calendar 2014 に書いてあるタイトルとは食い違っています。すみません） 個人的には C++03 ではなく C++11 を使う最大の理由は unique_ptr の存在だと思っています。 例外発生時にももれなく delete してくれる。 生ポインタとパフォーマンスが同じ。(最適化されている場合) 所有権を型として

Windowsで快適にLaTeXで論文を書くためのメモ． LaTeXで論文を書いているときは， テキストエディタで.texを編集する → platexでコンパイル → Adobe Readerでプレビュー → 最初にもどる という流れで論文を書いていくことになるのですが，いちいちコンパイルしたり，Adobe Readerで開いたりするのは面倒なので，.texを変更したら自動的に変更を検出してコンパイルし自動的にプレビューに反映する環境を構築しました． 使用したソフトは w32tex．これがなくては始まらない．abtexinst を使えば何も考えなくてもインストールできます． OMake．いわゆるビルドツール．コンパイルの自動化に使用します． SumatraPDF．PDFビューワ．PDFを変更すると自動的にリロードしてくれます． です． 以下では書いているTeXファイルを document.