|
楼主 |
发表于 2009-5-18 13:10:26
|
显示全部楼层
这样的算法非常简单……但……是在错误的思想上建立起来的,所以不行……
然后,我再想,在那个随机情况下,怎么判断新的Timer+1和-1的Handle是Timer呢?而且是“不用的”Timer呢?
突然想到
[jass]
globals
timer Union_Timer
integer Union_Int
endglobals
function Test takes integer i returns boolean
local timer Union_Timer = null
local integer Union_Int = i
if Union_Timer != null then
set Union_Timer = null
return true
endif
return false
endfunction
[/jass]
总觉得检测XXX ==/!= null有神奇的效果……
就当我没写这段吧……
然后,我又想到,如果每次都创建Timer直到有连续后,再删除不连续的Timer,这样每次创建的效率就非常慢了……如果将前面创建的不连续的Timer保存下来,等以后旁边有空位之后就可以更快的得到两个连续的Timer。
我首先想到,将Timer存到数组里,每新创建一个Timer,就对比所有以前创建的Timer,看差是否为1,如果为1则退出……
这样的时间复杂度是O(n^2 / 2),尤其是到后期后,会变得非常慢。
代码(不能编译!):
[jass]
globals
timer Union_Timer
integer Union_Int
timer array Timers
timer array Timers_HA
integer Timers_Top = 0
timer Return_Timer
endglobals
function Dis1 takes integer i, integer j returns boolean
if i + 1 == j or j + 1 == i then
return true
endif
return false
endfunction
function NewTimer takes nothing returns timer
local integer Union_Int = 0
local timer Union_Timer = CreateTimer()
local integer i = 0
loop
loop
exitwhen i >= Timers_Top
if Dis1( Union_Int, Timers_HA ) then
exitwhen true
endif
set i = i + 1
endloop
if i < Timers_Top then
set Timers = null
set Timers_HA = null
return ...//返回一个HandleAddress较大的Timer
else
set Timers[Timers_Top] = Union_Timer
set Timers_HA[Timers_Top] = Union_Int
set Timers_Top = Timers_Top + 1
endif
set Union_Timer = CreateTimer()
endloop
endfunction
[/jass]
这个方法的效率是非常不快的……
于是我又想,不是Hash的效率很快吗?那就用它来保存各个Timer吧。
至于哪种嘛……当然是最快的拉链Hash。
每创建一个Timer,就检测是否有可链接的Timer。如果没有就将这个Timer加入Hash表里。
基本思想就是这个,只不过数据结构改变了。
代码(应该无Bug):
[jass]
globals
timer array Hash_Timers
integer array Hash_Head
integer array Hash_Before
integer array Hash_Next // or Stack
integer array Hash_Timers_HA
integer Hash_Top = 0
integer Hash_NewAddress = 0
timer Union_Timer = null
integer Union_Int = 0
timer Return_Timer = null
endglobals
function Hash takes integer i returns integer
return i - (i / 8191) * 8191
endfunction
function NewHashAddress takes nothing returns integer
local integer temp = Hash_NewAddress
if temp == 0 then
set Hash_Top = Hash_Top + 1
if Hash_Top > 8191 then
return -1
endif
set temp = Hash_Top
else
set Hash_NewAddress = Hash_Next[Hash_NewAddress]
endif
return temp
endfunction
function FlushHashAddress takes integer i returns nothing
set Hash_Next = Hash_NewAddress
set Hash_NewAddress = i
endfunction
function AddNewHash takes integer index, timer t, integer t_a returns nothing
local integer HA = NewHashAddress()
local integer HH = Hash_Head[index]
set Hash_Next[HA] = HH
if HH != 0 then
set Hash_Before[HH] = HA
endif
set Hash_Before[HA] = 0
set Hash_Head[index] = HA
set Hash_Timers_HA[HA] = t_a
set Hash_Timers[HA] = t
endfunction
function RemoveOldHash takes integer address, integer index returns nothing
local integer before = Hash_Before[address]
local integer next = Hash_Next[address]
if before != 0 then
set Hash_Next[before] = next
else
set Hash_Head[index] = next
endif
if next != 0 then
set Hash_Before[next] = before
endif
set Hash_Timers[address] = null
set Hash_Timers_HA[address] = 0
set Hash_Before[address] = 0
call FlushHashAddress( address )
endfunction
function CheckHashTimers takes integer index, timer t, integer t_a returns integer//return hash address
local integer up_index = index + 1
local integer down_index = index - 1
local integer HA = 0
if up_index > 8191 then
set up_index = up_index - 8191
endif
if down_index < 1 then
set up_index = up_index + 8191
endif
set HA = Hash_Head[up_index]
loop
exitwhen HA == 0
if Hash_Timers_HA[HA] - 1 == t_a then
return HA
endif
set HA = Hash_Next[HA]
endloop
set HA = Hash_Head[down_index]
loop
exitwhen HA == 0
if Hash_Timers_HA[HA] + 1 == t_a then
return HA
endif
set HA = Hash_Next[HA]
endloop
return -1
endfunction
function NewTimer takes nothing returns timer
local timer Union_Timer = null
local integer Union_Int = 0
local integer timer_hashindex = 0
local integer i = 0
local timer Up_Timer = null
local integer Timer_HA = 0
local timer temp = null
set Union_Timer = CreateTimer()
loop
set timer_hashindex = Hash( Union_Int )
set i = CheckHashTimers( timer_hashindex, Union_Timer, Union_Int )
if i != -1 then
set Up_Timer = Hash_Timers
set Timer_HA = Hash_Timers_HA
call RemoveOldHash( i, Hash( Timer_HA ) )
if Timer_HA + 1 == Union_Int then
set temp = Union_Timer
set Timer_HA = Union_Int
set Union_Timer = Up_Timer
set Up_Timer = temp
endif
exitwhen true
endif
call AddNewHash( timer_hashindex, Union_Timer, Union_Int )
set Union_Timer = CreateTimer()
endloop
set Return_Timer = Up_Timer
set Union_Timer = null
set Up_Timer = null
set temp = null
return Return_Timer
endfunction
[/jass]
用的是双拉链Hash。
这样我们解决了创建新Timer时的连续问题。
//============================膜拜疯人老大的分界线================== |
|