○○した順に保つデータ構造

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 }

このような場合に、もっと良く知られたデータ構造とかあったりするんでしょうか?