Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。

#appengine で skiplist ってすごくね?

まとめました。
4
Kazunori Sato @kazunori_279

ぜひ #ajn8 BTでskiplist解説してほしすぅ~遠いかなぁ RT @koher: ランキングをSkiplistで実現してみたところ ... http://bit.ly/bWWmCW #appengine #ajn7

2010-04-25 16:26:17
Kazunori Sato @kazunori_279

skiplistでランキングは英訳してMLで紹介したいくらいだ #appengine

2010-04-25 16:27:50
Mikio Yoshida @kibayos

大量データの平均、max/miniなどの集約処理以外にランキングという問題もあったかぁ。面白い。RT @koher: ランキングをSkiplistで実現してみたところ、[snip] 詳しくはブログで。 http://bit.ly/bWWmCW #appengine #ajn7

2010-04-25 16:40:37
Kazunori Sato @kazunori_279

なる、「skiplistでgroup by代わり」って一般化できるかな? RT @kibayos: 大量データの平均、max/miniなどの集約処理以外に... RT @koher: ランキングをSkiplistで http://bit.ly/bWWmCW #appengine

2010-04-25 16:44:17
Mikio Yoshida @kibayos

lock free skip listを使うと面白そう。Java6のConcurrentSkipListMapはlock freeです。RT @koher: ランキングをSkiplistで [snip] http://bit.ly/bWWmCW #appengine #ajn7

2010-04-25 16:46:48
Mikio Yoshida @kibayos

集約の方は、分散化のためSkip Graphを使ってますが、研究として面白そう。RT @kazunori_279: なる、「skiplistでgroup by代わり」って一般化できるかな? RT @kibayos: 大量データの平均、max/min... #appengine

2010-04-25 16:51:06
Kazunori Sato @kazunori_279

100万件のデータから中間値を取得する、なんてのも数秒でできちゃうのかな #appengine でskiplist

2010-04-25 16:58:22
Kazunori Sato @kazunori_279

@shin1ogawa ランキング以外にも一般化できれば、#appengine の弱いところを補う強力なデザインパターンになる予感がします。つかAPIにしてほしいw

2010-04-25 17:03:24
Kazunori Sato @kazunori_279

もしかして indexable skiplistつかうと、#appengine で正確な全件カウントもO(log N)で得られちゃうってことか。更新コストはあるけど。

2010-04-25 17:13:04
Mikio Yoshida @kibayos

総数(ラストのランキング)は簡単に解るだろうから、そうなりますね。RT @kazunori_279: 100万件のデータから中間値を取得する、なんてのも数秒でできちゃうのかな #appengine でskiplist

2010-04-25 17:16:25
Mikio Yoshida @kibayos

Indexable skiplist自体をSkip Graphのように分散化させると、もっと面白いと思います。#appengine でskiplist

2010-04-25 17:23:01
Kazunori Sato @kazunori_279

skiplistって #appengine Datastoreの諸問題の解決にかなり使えそうな予感がしますね~RT @kibayos: 総数(ラストのランキング)は簡単に解るだろうから、そうなりますね。RT @kazunori_279: 100万件のデータから中間値を...

2010-04-25 17:23:15
Mikio Yoshida @kibayos

ふむ。http://bit.ly/aOH419 で集約Skip Graphの紹介がありますが、基本となるのはskip listの拡張なんです。RT @kazunori_279: skiplistって #appengine Datastoreの諸問題の解決にかなり使えそうな予感が

2010-04-25 17:28:28
Kazunori Sato @kazunori_279

なる RT @kibayos: ふむ。http://bit.ly/aOH419 で集約Skip Graphの紹介がありますが、基本となるのはskip listの拡張なんです。RT @kazunori_279: skiplistって #appengine Datastoreの

2010-04-25 18:12:50
Kazunori Sato @kazunori_279

#appengine で Indexable skiplist で実装できそうな問題:ランキング、全件カウント、最大/最小/中間値、全件対象のpagenation。基本「INSERTがんばれ」パターンの一種だね: http://goo.gl/bZHs

2010-04-25 21:14:56
Kazunori Sato @kazunori_279

lock freeのskiplist実装ならbatch putで更新できるかな?そしたら更新処理時間は短縮できそう #appengine

2010-04-25 21:16:25
Mikio Yoshida @kibayos

put, getを並行、非同期化できるので、親和性が高い。実装しやすくなるのでは。RT @kazunori_279: lock freeのskiplist実装ならbatch putで更新できるかな?そしたら更新処理時間は短縮できそう #appengine

2010-04-25 21:45:49
Kazunori Sato @kazunori_279

#appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。single prop/compositeとか辞書順とかの制限なしに、例えばエンティティの全prop絡めた条件でも同じコストでソートできる

2010-04-25 21:46:49
Kazunori Sato @kazunori_279

ORDER BY lastname asc, firstname asc, middlename asc, email asc... なんてのも、メモリ上ソート使わずに実装できる。 #appengine + skiplist

2010-04-25 21:50:56
Kazunori Sato @kazunori_279

@kibayos ConcurrentSkipListMapのソースを読みたくなりました^^

2010-04-25 21:52:26
Mikio Yoshida @kibayos

これは、nodeの全prop対象に順序がつくようにしておくということ? RT @kazunori_279: #appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。single prop/compositeとか...

2010-04-25 21:56:53
Mikio Yoshida @kibayos

Indexable skiplistといえど、nodeはある順序で並ぶようにしておかないといけないので。RT @kazunori_279: #appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。

2010-04-25 21:59:13
Kazunori Sato @kazunori_279

@kibayos いえ、ConcurrentSkipListMapでたとえると、Comparableを自由に指定できる、ということです。#appengineだと現状、特定の1つか2つのプロパティ値の辞書順/数値順でしかソートできません

2010-04-25 22:00:30
Mikio Yoshida @kibayos

1990年にSkip Listが登場した時、既存のDBMSにも応用されたはず。でも詳細不明。RT @kazunori_279: ORDER BY lastname asc, firstname asc, middlename asc, email asc... なんてのも..

2010-04-25 22:03:21
残りを読む(23)

コメント