Geohashでインデックスしたデータ構造

cocoraでは、現在位置の近くでの発言を高速に探索する必要がありました。
また、cocoraではプラットフォームとしてGoogle App Engineを用いましたが、DBからの検索はただでさえ時間がかかる上、複数のプロパティに対する範囲検索ができないという特徴があります。

そこで、Geohashをキーとしたマップ(辞書)型のpython用クラスライブラリを作りました(geohashtree)。
このデータ構造の特徴は、k-NN探索を効率的に行うことが出来るという点です。
このライブラリはGitHubに置いてあります。
以下、データ構造の説明です。

Geohashは、緯度経度を文字列で表現する手法で、xとyのビットが交互に続く構造となっています。
これはモートン順序と解釈することができ、また、kd木との類似性を見出すことができます。
geohashtreeでは、エッジをGeohashの各ビットの01に対応させて一意に判別できるように(葉ノードに)データを格納します。
計算量は、追加、探索、削除、そしてNN探索(最近傍探索)が実質的にO(logN)なはずです。(最悪はO(N)ですが)

cocora

cocoraというサービスを作りました。
同じ"場"を共有してる他のひとたちが、どういうことを感じているのか、気になったりすることがあったりします。
そいういうときに、その"場"にローカルな"つぶやき"ができる空間があってもいいのでは、というふうなコンセプトで作りました。

トップページがタイムラインになっていて、ここに自分の近くでの発言が流れます。
タイムラインの距離の広がりは、周りの発言の状況によって動的に変動します。

cocora

Chatploo

Chatploo（チャットプルー）は、シンプルな使い捨てチャットです。
特徴としては、

• すぐに専用URLのチャットルームでグループチャットが始められる。
• 更新がPushで届く。リロードいらず。
• Flashなどのプラグインも不用。

など。
まだまだ改良の余地はありそう、といった感じですが、とりあえずベータ版として公開してみました。
ブラウザさえあれば誰でも使えるので、ちょっとしたディスカッションになど、いかがでしょう。

Chatploo

GAEでの実行について

GAE(Google App Engine)では、毎回のHTTPリクエストごとにpythonファイルが新たに実行されてるものと思っていたが、どうやら違うみたい。
少なくとも、短い間隔で同じファイルの実行を要求するアクセスがあると、それが新しい環境で実行されないことがある。
GAEの内部では、実行するファイルはimportされてて、アクセスごとにその中のハンドラが呼び出されているようなイメージ。

ところで、pythonではデフォルト引数が

def f(a=[]):
  a.append(len(a))
  print a

みたいな書きかたの関数だと、これを続けて実行した場合

>>> f()
[0]
>>> f()
[0, 1]
>>> f()
[0, 1, 2]
>>> f()
[0, 1, 2, 3]

となってしまう。
デフォルト引数は、関数の呼び出し時ではなく、ファイルのロード時に評価されるため。
毎回の呼び出しのたびに引数aを[]で初期化したいときは別の書き方をしなければならない。
たとえば

def f(a=None):
  a = a if a != None else []
  a.append(len(a))
  print a

のような感じで。

今回、GAEではHTTPリクエストごとに実行環境が新しくなる、と勘違いしてて、前者みたいな書き方をしてて不具合になってしまってた。

追記(2010/11/04):
GAEドキュメントのアプリケーション キャッシュの「ハンドラ スクリプトのキャッシュ」に書いてた

Twitter風に”〜分前”などを返すJS関数

検索して上位に引っかかるライブラリがなんか長いので、シンプルなのをひとつ

function beforeTime(sec){
	var d = new Date();
	var diff = d.getTime() - sec * 1000;
	var dd = new Date(diff);
	return (
		dd.getUTCFullYear() - 1970 ? dd.getUTCFullYear() - 1970 + '年前' :
		dd.getUTCMonth() ? dd.getUTCMonth() + 'ヶ月前' :
		dd.getUTCDate() - 1 ? dd.getUTCDate() - 1 + '日前' :
		dd.getUTCHours() ? dd.getUTCHours() + '時間前' :
		dd.getUTCMinutes() ? dd.getUTCMinutes() + '分前' :
		dd.getUTCSeconds() + '秒前'
	);
}

引数secは 1970/01/01 00：00：00 UTC からの経過秒

いろいろなチャットの分類まとめ

広大なネットには様々なチャット系のサービスがあるもの。
どんなものがあるのか、いくつか調べて分類してみた。

古典的チャットルーム

• いくつかの部屋から選択、入室してグループチャット
• ここで挙げたのはいずれも登録不要の日本語サービス

teacup.

チャベリ

もなちゃと

見知らぬ人とチャット

• 一対一でいきなりチャット開始

ChatPad

日本語。

Chatroulette

英語。ビデオチャット。

Omegle

英語。テキストチャットおよびビデオチャットから選択可。

Verbling

語学学習。言語交換。ビデオチャット。

SNSの登録ユーザとチャット

Beluga

FaceBookの友達とグループチャット。iPhone用アプリ。ブラウザからも。

Convore

Twitter、FaceBookの知り合いとグループチャット。

メッセンジャー系

• 自前の登録ユーザとチャット

Skype

言わずと知れた

Google トーク

XMPP互換

チャットワーク

チャットを軸にした便利ツール

使い捨てグループチャット

TodaysMeet

Tinychat

その他

Envolve

自分のWebサイトやブログに手軽にチャット機能を設置できる

アダルト系

• いろいろありそう

ほかにもいろいろあると思うけど、とりあえず
あと、ここで述べたサービスについて、すべて試したわけではないので間違いなどあるかも