Skip list (日本語)

スキップ・リストは高速なランダム・アクセスよりむしろ高速な挿入および削除があるデータ構造が求められるタイムライン、スプライトでZ-インデックスまたはその他のタスクを実装するのに効果的なツールです。

警告、本格的な小記事: (インデックス付加可能な)スキップ・リストは蓋然的データ構造の挿入、削除および探査は O(log(n)) として整列され、さらに空き容量 O(n*log(n)) を使用します。二分木に対する主な優位点として Lua にて ~= 150 LOC を実装するのが非常に簡単であることです。

一つだけ制限があり、それは整列されたデータ構造であるため、その要素が < および <= により比較可能でなければならないということです。

こちらに Lua 実装の元となったPython 版 があります。

-- ファイル: skiplist.lua

--[[------------------------------------------------------------------
The MIT License

Original Python version Copyright (c) 2009 Raymond Hettinger 
see http://code.activestate.com/recipes/576930/

Lua conversion + extensions Copyright (c) 2010 Pierre-Yves Gérardy

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
--]]------------------------------------------------------------------

local log, floor, ceil, min, random 
= math.log, math.floor, math.ceil, math.min, math.random

local makeNode = function(value,size)
	return {
		value=value, 
		next={}, 
		width={}, 
		size=size
	}
end

local End ={}
local NIL = makeNode(End,0)

local insert = function(self,value)
	local node, chain, stepsAtLevel = self.head, {}, {}
	for i=1, self.maxLevel do stepsAtLevel[i]=0 end
	for level = self.maxLevel, 1, -1 do
		while node.next[level] ~= NIL and node.next[level].value <= value do
			stepsAtLevel[level] = ( stepsAtLevel[level] or 0 ) + node.width[level]
			node = node.next[level]
			-- print(level, stepsAtLevel[level],value)
		end
		chain[level]=node
	end

	local nodeLevel = min( self.maxLevel, - floor(log(random()) / log(2) ) )
	local newNode = makeNode( value,  nodeLevel)
	local steps, prevNode = 0
	for level= 1, nodeLevel do
		prevNode = chain[level]
		newNode.next[level] = prevNode.next[level]
		prevNode.next[level] = newNode
		newNode.width[level] = prevNode.width[level] - steps
		prevNode.width[level] = steps + 1
		steps = steps + stepsAtLevel[level]
	end
	for level = nodeLevel + 1, self.maxLevel do
		chain[level].width[level] = chain[level].width[level] +1
	end
	self.size = self.size + 1
end

local delete = function(self,value)
	-- ここで node.next[levels].value >= value により各レベルにある第一ノードを検索します。

	node, chain = self.head, {}
	for level = self.maxLevel, 1, -1 do
		while node.next[level] ~= NIL and node.next[level].value < value do
			node = node.next[level]
		end
		chain[level] = node
	end
	if value ~= chain[1].next[1].value then
		return nil, "value not found: "..value
	end

	-- 各レベルにあるリンクを一つ削除します。
	nodeLevel = chain[1].next[1].size
	for level = 1, nodeLevel do
		prevnode = chain[level]
		prevnode.width[level] = prevnode.width[level] + prevnode.next[level].width[level] - 1
		prevnode.next[level] = prevnode.next[level].next[level]
	end
	for level = nodeLevel+1, self.maxLevel do
		chain[level].width[level] = chain[level].width[level] - 1
	end
	self.size = self.size - 1
	return true -- 成功
end


local first = function(self)
	return self.head.next[1].value
end

local pop=function (self)
	if self.size == 0 then return nil, "Trying to pop an empty list" end
	
	local node, head = self.head.next[1], self.head
	for level = 1, node.size do
		head.next[level]=node.next[level]
		head.width[level]=node.width[level]
	end
	for level = node.size + 1, self.maxLevel do
		head.width[level] = head.width[level] -1
	end
	self.size = self.size - 1
	return node.value
end

-- i ( O( log( n ) ) ) により索引にあるノードの値を取得します。

local tostring = function (self)
	local t = {}
	for k,v in self:ipairs() do table.insert(t,v) end
	return "( "..table.concat(t,", ").. " )"
end


local islMT = {
	__index = function(self,i)
		if type(i) ~= "number" then return end
		if i > self.size then return end
		local node = self.head

		for level=self.maxLevel, 1, -1 do
			while node.width[level] <= i do
				i = i - node.width[level]
				node = node.next[level]
			end
		end
		return node.value
	end,
	__tostring=tostring
}


local ipairs = function (self)
	local node, size = self.head.next[1] , self.size
	count = 0
	return function()
		value=node.value
		node = node.next[1]
		count = count+1
		return count <= size and count or nil, value 
	end
end

local function new (expected_size)
	local size = expected_size or 16
	if not expected_size then
		expected_size = 16
	end
	
	local maxLevel = floor( log(expected_size) / log(2) ) 
	local head = makeNode("HEAD",maxLevel)
	for i=1,maxLevel do 
		head.next[i] = NIL
		head.width[i] = 1
	end
	
	return setmetatable( {
		size = 0,
		head = head,
		maxLevel = maxLevel,
		insert = insert,
		delete = delete,
		first = first,
		tostring = tostring,
		ipairs=ipairs,
		pop = pop
		}, islMT 
	)
end

return {
	new=new
}

API による用例:

local skiplist = require"skiplist"

math.randomseed(os.time())

-- 作成:

insdel = skiplist.new(8) -- 最適化された性能を得るためにリストの長さを算定して決定する必要があります。

-- 挿入
s = "YeeHoyeE" 
for i=1,#s do
	 insdel:insert(s:sub(i,i)) 
	print(insdel) 
end
print()

--  インデックス(索引)化
print(insdel[4])
print(insdel[8])
print(insdel[12]) -- 範囲外 --> nil
print()

-- リストを超えての反復
for k,v in insdel:ipairs() do 
	print(k,v) 
end
print()

-- 要素の削除
print(insdel:delete"Z") -->  見つからなかった

for i=1,#s do 
	insdel:delete(s:sub(i,i)) 
	print(insdel) 
end

-- pop() および first() の別の挿入分
insdel:insert("e")
insdel[0]=("g")

print( insdel:first() ) -- 最初の要素を返します。
print( insdel:pop() ) -- 最初の要素を返してリストから最初の要素を削除します。
print( insdel:first() )
print( insdel.size )
print( insdel:pop() )
print( insdel:pop() ) -- 空のリストに対して pop を試行します --> nil + エラーメッセージ。
print()

-------------------------------
-- ASCII 表現の構造:

-- この動作に対して以前のコードセクションの最後から 
-- 二番目の行にある _End 代入をコメントアウトしてください。

-- 次のコードはリスト内部の構造を示すために 
-- フードの下へ行くためにこれが要求されます。
-- これは通常使用において不要です。


l = skiplist.new(9)
s = "SweetLOVE"

for i=1,#s do local e = s:sub(i,i) l:insert(e) end

for level = l.maxLevel, 1, -1 do
	local line='Level '..level..": "
	node = l.head

	while node.value ~= _End do
		line=line..node.value..node.width[level].." "
		for i=1,node.width[level]-1 do line=line.."   " end
		node = node.next[level]
	end
	print(line.."NIL")
end

出力:

( Y )
( Y, e )
( Y, e, e )
( H, Y, e, e )
( H, Y, e, e, o )
( H, Y, e, e, o, y )
( H, Y, e, e, e, o, y )
( E, H, Y, e, e, e, o, y )

e
y
nil

1       E
2       H
3       Y
4       e
5       e
6       e
7       o
8       y

nil     value not found: Z
( E, H, e, e, e, o, y )
( E, H, e, e, o, y )
( E, H, e, o, y )
( E, e, o, y )
( E, e, y )
( E, e )
( E )
(  )
e
e
g
1
g       
nil     Trying to pop an empty list


Level 3: HEAD4          S6                NIL
Level 2: HEAD1 E3       S1 V2    e2    w1 NIL
Level 1: HEAD1 E1 L1 O1 S1 V1 e1 e1 t1 w1 NIL