10周年のSPコンテンツ!
4
Kazunori Sato @kazunori_279
ぜひ #ajn8 BTでskiplist解説してほしすぅ~遠いかなぁ RT @koher: ランキングをSkiplistで実現してみたところ ... http://bit.ly/bWWmCW #appengine #ajn7
Kazunori Sato @kazunori_279
skiplistでランキングは英訳してMLで紹介したいくらいだ #appengine
Mikio Yoshida @kibayos
大量データの平均、max/miniなどの集約処理以外にランキングという問題もあったかぁ。面白い。RT @koher: ランキングをSkiplistで実現してみたところ、[snip] 詳しくはブログで。 http://bit.ly/bWWmCW #appengine #ajn7
Kazunori Sato @kazunori_279
なる、「skiplistでgroup by代わり」って一般化できるかな? RT @kibayos: 大量データの平均、max/miniなどの集約処理以外に... RT @koher: ランキングをSkiplistで http://bit.ly/bWWmCW #appengine
Mikio Yoshida @kibayos
lock free skip listを使うと面白そう。Java6のConcurrentSkipListMapはlock freeです。RT @koher: ランキングをSkiplistで [snip] http://bit.ly/bWWmCW #appengine #ajn7
Mikio Yoshida @kibayos
集約の方は、分散化のためSkip Graphを使ってますが、研究として面白そう。RT @kazunori_279: なる、「skiplistでgroup by代わり」って一般化できるかな? RT @kibayos: 大量データの平均、max/min... #appengine
Kazunori Sato @kazunori_279
100万件のデータから中間値を取得する、なんてのも数秒でできちゃうのかな #appengine でskiplist
Kazunori Sato @kazunori_279
@shin1ogawa ランキング以外にも一般化できれば、#appengine の弱いところを補う強力なデザインパターンになる予感がします。つかAPIにしてほしいw
Kazunori Sato @kazunori_279
もしかして indexable skiplistつかうと、#appengine で正確な全件カウントもO(log N)で得られちゃうってことか。更新コストはあるけど。
Mikio Yoshida @kibayos
総数(ラストのランキング)は簡単に解るだろうから、そうなりますね。RT @kazunori_279: 100万件のデータから中間値を取得する、なんてのも数秒でできちゃうのかな #appengine でskiplist
Mikio Yoshida @kibayos
Indexable skiplist自体をSkip Graphのように分散化させると、もっと面白いと思います。#appengine でskiplist
Kazunori Sato @kazunori_279
skiplistって #appengine Datastoreの諸問題の解決にかなり使えそうな予感がしますね~RT @kibayos: 総数(ラストのランキング)は簡単に解るだろうから、そうなりますね。RT @kazunori_279: 100万件のデータから中間値を...
Mikio Yoshida @kibayos
ふむ。http://bit.ly/aOH419 で集約Skip Graphの紹介がありますが、基本となるのはskip listの拡張なんです。RT @kazunori_279: skiplistって #appengine Datastoreの諸問題の解決にかなり使えそうな予感が
Kazunori Sato @kazunori_279
なる RT @kibayos: ふむ。http://bit.ly/aOH419 で集約Skip Graphの紹介がありますが、基本となるのはskip listの拡張なんです。RT @kazunori_279: skiplistって #appengine Datastoreの
Kazunori Sato @kazunori_279
#appengine で Indexable skiplist で実装できそうな問題:ランキング、全件カウント、最大/最小/中間値、全件対象のpagenation。基本「INSERTがんばれ」パターンの一種だね: http://goo.gl/bZHs
Kazunori Sato @kazunori_279
lock freeのskiplist実装ならbatch putで更新できるかな?そしたら更新処理時間は短縮できそう #appengine
Mikio Yoshida @kibayos
put, getを並行、非同期化できるので、親和性が高い。実装しやすくなるのでは。RT @kazunori_279: lock freeのskiplist実装ならbatch putで更新できるかな?そしたら更新処理時間は短縮できそう #appengine
Kazunori Sato @kazunori_279
#appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。single prop/compositeとか辞書順とかの制限なしに、例えばエンティティの全prop絡めた条件でも同じコストでソートできる
Kazunori Sato @kazunori_279
ORDER BY lastname asc, firstname asc, middlename asc, email asc... なんてのも、メモリ上ソート使わずに実装できる。 #appengine + skiplist
Kazunori Sato @kazunori_279
@kibayos ConcurrentSkipListMapのソースを読みたくなりました^^
Mikio Yoshida @kibayos
これは、nodeの全prop対象に順序がつくようにしておくということ? RT @kazunori_279: #appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。single prop/compositeとか...
Mikio Yoshida @kibayos
Indexable skiplistといえど、nodeはある順序で並ぶようにしておかないといけないので。RT @kazunori_279: #appengine + Indexable skiplistのキモは、ソート条件が「なんでもあり」なこと。
Kazunori Sato @kazunori_279
@kibayos いえ、ConcurrentSkipListMapでたとえると、Comparableを自由に指定できる、ということです。#appengineだと現状、特定の1つか2つのプロパティ値の辞書順/数値順でしかソートできません
Mikio Yoshida @kibayos
1990年にSkip Listが登場した時、既存のDBMSにも応用されたはず。でも詳細不明。RT @kazunori_279: ORDER BY lastname asc, firstname asc, middlename asc, email asc... なんてのも..
残りを読む(23)

コメント

ログインして広告を非表示にする
ログインして広告を非表示にする