○○した順に保つデータ構造
http://www.amazon.co.jp/dp/475981339X を読みつつ、もしランキング = 確率的ランキングとみなし、注文した順をランキングとして採用し、実現するとしたら、どうやって実現するだろうか、というのを考えてみた。 (実際のところ、かなりの更新頻度がないといけないであろうことや、spamなどのデメリットもあるので、現実的に使えそうなポイントはかなり考えないといけないのだろうけど。
確率的ランキング
本の中で説明されている数学的なバックグラウンドについてはちゃんとなぞっているわけでもないし、まったくしっかり理解できているわけではないです。
本のあらすじを乱暴にまとめると、Amazonのランキングを観察してみると、中間層の順位の推移を長期にわたって観察すると、大きく変動しているのが観察されて、そのデータから全体を統計的に推測すると、Amazonのランキングは、注文された商品の順番に近似している、と説明している。
ある瞬間の注文された商品の順番を切りとると、上位の商品は注文頻度は圧倒的に多いのでこのような仮定が成立する、らしい。
やりたいこと
商品数がとてもたくさんあるような場合に、注文した商品の順番をランキングとしてなるべくリアルタイムに反映したい
各々の商品のページには、現在その商品が何位なのか?といった情報も表示されているので、順位が下位である場合に時間のかかるような状態だと困る
私が考えたこと
まず考えたのは順番を保ちつづけないといけないので、更新のコストを下げることについて考えました。
1つ順位が入れかわるごとに、それ以降の順位情報をすべて更新しないといけないようだと、更新速度や、商品数がどんどんあがるごとに破綻していってしまう。
中間データの更新コストが低いデータ構造といえば何かな、と考えて思いついたのは、LinkedListでした。
単にLinkedListにすると、各々の順位を求めるのが、ひとつひとつのノードをたどっていかないといけないので、下位のアイテムの順位を求めるほど遅い、という欠点があります。
そこで、2の指数の順位のランキングはどのアイテムという辞書をつくってやり、ランキングを求める際は、一番近い2の指数の順位へ飛んでからポインタをたどる、という構造にしてみました。例えば、2位、4位、8位、16位、32位、64位、128位などは辞書を一回引くだけでどの商品か判別することができます。順位が下位であるほどポインタへ飛んでから辿る回数が多くなってしまう傾向にありますが、一からたどるよりはマシでしょう。(どちらからも辿れるように双方向なリストが望ましい
また、データを更新する際には、itemのidをベースにして、探索し、更新をかけないといけないので、itemのidをもとにリンクリストのノードへ飛ぶ辞書も用意しました。
以下のアイディアを実装したのが下記です。
https://gist.github.com/1663101
module Orderd class Ranking def initialize @first = @last = Node.new @item_id_of = {} @marker_of = {} @size = 0 end def top item_id n = @item_id_of[item_id] if n.nil? n = Node.new n.value = item_id @item_id_of[item_id] = n @size += 1 update_markers else return n if n.prev.nil? # nをLinkListから切りはなす np = n.prev n.prev = nil nn = n.next np.next = nn nn.prev = np update_markers n end n.next = @first @first.prev = n @first = n n end # markerの位置を調整してやる def update_markers node=nil marker_of = {} @marker_of.each do |k, v| marker_of[v] = k end start_marker = 0 unless node.nil? n = node counter = 1 n = node until n.next.nil? if marker_of[n] start_marker = marker_of[n] break end n = n.next counter += 1 end end get_markers(0, @size).each do |i| if @marker_of[i] if i < start_marker # top内から呼ばれることを想定しているので、データを抜いたところより前のランキングは1ずつずらす @marker_of[i] = @marker_of[i].prev else if node.nil? # nodeがなかった場合は、件数がかわってくるので順番をズラす @marker_of[i] = @marker_of[i].prev end end else counter = 1 n = @last until n.prev.nil? rank = @size - counter if rank == i @marker_of[i] = n end counter += 1 n = n.prev end end end end # 与えられた範囲内で # 2のn乗の配列を返す def get_markers start, last markers = [] num = 2 while num <= last if num >= start markers.push num end num *= 2 end return markers end def get_item item_id item = @item_id_of[item_id] i = 1 node = item marker_of = {} @marker_of.each do |k, v| marker_of[v] = k end counter = 0 until node.prev.nil? if marker_of[node] return marker_of[node] + counter end counter += 1 node = node.prev end return nil end def rank_list rank, num result = [] node = @first start_rank = get_markers(rank, @size) if @marker_of[start_rank[0]] i = start_rank[0] node = @marker_of[i] else i = 1 node = @last end until node.prev.nil? if i >= rank if i > rank + num else result.unshift node end else return result end node = node.prev i -= 1 end return result end def size @size end end class Node attr_accessor :prev, :next, :value def inspect prev_object_id = @prev.nil? ? "" : @prev.object_id next_object_id = @next.nil? ? "" : @next.object_id "<Node ##{self.object_id} value=#@value prev=#{prev_object_id} next=#{next_object_id}>" end end end orderd = Orderd::Ranking.new NUM = 10000 orderd.top(15) (1..NUM).each do |i| num = rand(NUM) p [i, num] orderd.top(num) end p orderd.get_item 15 p orderd.rank_list(100, 100).map { |n| n.value }
このような場合に、もっと良く知られたデータ構造とかあったりするんでしょうか?