Skip to content

Instantly share code, notes, and snippets.

@walf443 walf443/gist:1663101
Created Jan 23, 2012

Embed
What would you like to do?
何々した順にならべるデータ構造
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 }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.