Kazunori Sato
@kazunori_279
ぜひ #ajn8 BTでskiplist解説してほしすぅ～遠いかなぁ RT @koher: ランキングをSkiplistで実現してみたところ ... http://bit.ly/bWWmCW #appengine #ajn7
2010-04-25 16:26:17
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
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