Binary Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。 分割統治（Divide-and-conquer）はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。 今回はランダムに数値…

ファイヤウォールの設定が厳しいネットワークや、ロードバランサーが動作するネットワーク、使用するパケットのプロトコルによる違い、等を考えて最も経路発見しやすい方法を考える。 ファイヤウォールの設定が厳しいネットワーク ファイヤウォールの設定が…

Git for Windows (Git bash)でrubyのプログラムを走らせているときプログラムが停止しているような挙動に遭遇した。デバッグしてみると、停止している箇所はユーザからの入力を受け付ける部分であったが、入力待ちで停止しているのではなく、putsでユーザに…

仮想マシン＝ゲスト＝ゲストOS 仮想マシンモニタ＝VMM＝ハイパーバイザー 仮想化コンセプト 仮想マシンモニタ＝VMM（Virtual Machine Monitor）は、自身の子プロセスとして仮想マシンを実行し、ユーザモードでは実行できない命令を仮想マシンが発行したとき…

Quick Sortは理論上は対象データの並び順によって最速のソートになる可能性があるが、最悪の場合（降順にソートされている場合かつPivotを先頭あるいは最後の要素に選択する場合）はO(n^2)かかってしまう、という問題点があり、Merge Sortは安定してO(nlog(n…

Binary Search – topcoder Binary Searchは、例えばソートされている整数のリストにある値が含まれているかどうかを確認するときに使うと、単純なループでチェックするよりもかなり計算量を抑えることができる。単純にループで確認するやり方は計算量がO(n)…