要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
Twitter本文と言及URLの圧縮 - kaisehのブログ
最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつgzip等で圧縮してもほとんど意味がないか、オーバーヘッドが出て逆効果になってしまいます。 そこで、収集済みのサンプルデータを元にハフマン木を作っておき、それを共通利用してtweetを圧縮してみました。 用意したのは、英語ユーザ/日本語ユーザ/韓国語ユーザ各1000人のtweetサンプルをベースにしたハフマン符号と、tweet本文から抽出したURL文字列をベースにしたハフマン符号の4種類です。 頻度表は次のようになりました。 char (en) freq (en) char (ja) freq (ja) char (ko) f
Java Cloud Meeting Tokyo 2010: 『Google Web Toolkitのすすめ』発表資料 - kaisehのブログ
Java Cloud Meeting Tokyo 2010で、『Google Web Toolkitのすすめ』と題して発表を行いました。スタッフの皆さま、お疲れ様でした。 発表中に、Google PluginでGWTアプリをGAEにデプロイする予定だったのですが、Eclipseで謎のエラーが出てしまいました。そこであらかじめデプロイしておいたアプリを表示しようと思ったのですが、動揺でApp IDをど忘れしてしており、URLを間違えて404を連発という失態を演じてしまいました。ネットワークを使うデモは会場でのリハーサルが必須ですね...。 以下、発表資料です。 Google Web ToolkitのすすめView more presentations from kaiseh.
Solr 1.3と1.4の検索パフォーマンス比較 - kaisehのブログ
TopHatenarとBlogopolisでは現在、全文検索用途にApache Solr 1.3を使っていますが、去年11月にSolr 1.4がリリースされたので、近いうちに1.4に移行したいと思っています。 そこで、1.3と1.4の検索パフォーマンスにどのくらい差があるのか、TopHatenarで収集しているブログの本文データを使って、以下の条件で計測してみました。 計測は、事前にSolrをウォームアップし、キャッシュが十分に効いた状態で行いました。 Solrサーバ環境 OS: CentOS 5.4 (x86_64) CPU: Phenom II X4 905e RAM: DDR2-800 9GB HDD: Seagate ST3160815AS (160GB, 7200rpm) JRE: 1.6.0_17-b04 (64bit) Tomcat: 6.0.20 Solrのキャッシュ設定
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
エラーを含んだXMLをルーズにパースする - kaisehのブログ
各種ブログのRSSのようなWeb上のXMLリソースをdom4jやJDOMなどで読み込むと、パースに失敗するケースがとても多いです。というのも、こういうXMLは基本的に、validであることをあまり期待できないからです（エスケープ漏れがあったり、"<!--"で始まったコメントの直後に"-"が来たりする[追記: これはinvalidな例じゃなく非well-formedな例でした]）。ひどいときはwell-formedですらないこともあります。 こういう問題がある場合、HTMLであれば、MayaaやS2JSFでも採用されているNekoHTMLというライブラリを使って、エラーを出さずにルーズにパースできます。このNekoHTMLを、HTMLではなくXMLに適用する方法を調べたので、メモしておきます。 パーサを以下のような構成にすると、XMLの解析に適した状態になります。 NekoHTML側ではなく
JavaからWindowsのUSBデバイスにアクセス - kaisehのブログ
WindowsのUSBデバイスにJavaからアクセスしたかったので、方法を調べてみました。JavaのUSBサポートってJSR-80に上がってるんですけど、Windows用のまともな実装は出ていないみたいです。 JSR-80以外で情報量の多いのがjUSBですが、これもWindows向け実装がいまいちで、自分の環境では動きませんでした。 jUSB: Java USB jUSB - Java USB API for Windows その後も調べ続けたところ、libusbというUSBライブラリのJNIラッパを発見。 start [LibusbJava] こちらは問題なく動作したので、今回はlibusbを使おうと思います。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
