Simple-9について解説 - tsubosakaの日記 http://ameblo.jp/th0083/entry-10483740192.htmlSimple9は、整数列を高速に圧縮するアルゴリズムです。32bitのint値を上位4bitと下位28bitに分けて、下位28bitにデータをできるだけ多く詰め込み、上位4bitで詰め込…

最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつ…

Blogopolisから学ぶ計算幾何：連載｜gihyo.jp … 技術評論社gihyo.jpでの連載が、全12回で終了しました。当初の予定通り、線分交差、面分交差、ボロノイ図の3テーマを取り上げることができました。最終回記事のページから、GUIのデモを含めて、全プログラムの…

Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割…

K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。これに対して、X-means法というK-means法の拡張が提…

K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不…

要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ上記エントリに書いたSkipListとSkipListSetのベンチマークを取ってみました。数値の単位はミリ秒、CPUはCore Duo 1.66GHzです。 タスク ArrayList LinkedList SkipList Skip…

スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅…