Hash_Timer——动态TimerDataSystem
曾经我说过,用Handle来做存储结构是绝对没问题的,虽说效率可能没有全局变量数组那么高,但它确实有可取之处~这回又是疯人老大和我聊QQ(话说聊QQ……疯人老大老是把想法说给我听……结果每次文字帖都我写……每次精华都我拿…………………………)的时候,他跟我说,他又想到了一个Timer绑定的方法,他说,如果每一个Timer都配一个Timer存一个实数的话,不是也可以达到绑定数据的目的吗(至于为什么有一个实数,就可以绑定一切数据……自己看别的贴吧~)?然后,他又说,关键在于Timer的连续问题怎么达到。Timer的连续问题就是说,一个Timer的Handle地址-1,就可以得到用来绑定数据的那个Timer了。而且要求必须是【动态】的……原本想脱口而出“TimerDataSystem”的某人只好又咽了下去……
然后他又跟我说了一大堆……
基本就是如何实现Timer的连续问题,不过我先帮大家梳理一下这个“【动态】”“TimerDataSystem”是什么个意思。
按照设想,它应有一个创建Timer的函数,返回用来计时和运行函数的Timer,两个获得/设置Timer的数据的函数,和一个销毁函数,将不用的Timer销毁。我们可以很容易地办到创建、销毁和获得数据,可前提是Timer必须能通过某种方式链接到数据上(废话,那么多人写那么多存储数据的帖子都是达到这一效果……)。疯人老大当时把我的思维限定在Timer1_HandleAddress + 1 = Timer2_HandleAddress 上……不得不说,这是个把我思维挤到极限的好方法…………………………………………………………………………………………………………………………………………
1.Handle表的回收原理猜想
2.如何实现Timer的连续
3.最终的系统~
//============================膜拜疯人老大的分界线==================
1
1.Handle表的回收原理猜想首先,我们来猜一猜Handle表的回收原理,因为Timer在创建时可是严格遵循这个原理获得自己的HandleAddress的~如果搞不清的话……你就会像疯人一样用了5个测试地图来弄好自己的东东~
很多人认为HandleAddress回收的时候是排好序的,并且每次创建新Handle的时候,都会得到一个所有为空的HandleAddress中最小的一个HandleAddress(如疯人老大一开始想的那样……)。
这是绝对有错误的,因为按照插入排序,这样的时间复杂度也是O(n)级别的,而如果使用像VJ中struct的原理的话,那时间复杂度就是O(1)级别的了。所以暴雪是不可能这么干的。
而且用过ReturnBug计算自己排泄情况的人都知道,这是不可能这么有顺序的。
最后,我从疯人那里了解到他的猜想,估计已经八九不离十了。
Handle使用完、且变量连接数为0后,在触发执行完毕或等待时,这个HandleAddress加入【空位Handle表】。然后,有新的handle创建的时候,把【空位Handle表】中的一个空的HandleAddress给新的Handle的占用。
虽然没有任何证据证明【空位Handle表】就是一个栈,但我是这样认为的。
//============================膜拜疯人老大的分界线================== 2.如何实现Timer的连续
既然如此,我们就知道,新的Handle的HandleAddress是没有一定顺序的,也就是说,随机的、无法预估的HandleAddress会被新的Handle占用。
而如果是有顺序的话,我们很快就能得出一个算法:
循环:
{
创建一个Timer。
对比这个Timer和【前一个创建的Timer】的Handle值,如果差1,那么清空未形成连接的Timer,返回这个Timer。
如果没有差1则
将【前一个创建的Timer】存入一个数组,等待删除。
将这个Timer存入【前一个创建的Timer】的值。
}
而由于Handle表永远不可能到顶,所以我们一定会有一次找到连接的Timer。 //======专门放图======
//======专门放图====== 这样的算法非常简单……但……是在错误的思想上建立起来的,所以不行……
然后,我再想,在那个随机情况下,怎么判断新的Timer+1和-1的Handle是Timer呢?而且是“不用的”Timer呢?
突然想到
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
总觉得检测XXX ==/!= null有神奇的效果……
就当我没写这段吧……
然后,我又想到,如果每次都创建Timer直到有连续后,再删除不连续的Timer,这样每次创建的效率就非常慢了……如果将前面创建的不连续的Timer保存下来,等以后旁边有空位之后就可以更快的得到两个连续的Timer。
我首先想到,将Timer存到数组里,每新创建一个Timer,就对比所有以前创建的Timer,看差是否为1,如果为1则退出……
这样的时间复杂度是O(n^2 / 2),尤其是到后期后,会变得非常慢。
代码(不能编译!):
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 = Union_Timer
set Timers_HA = Union_Int
set Timers_Top = Timers_Top + 1
endif
set Union_Timer = CreateTimer()
endloop
endfunction
这个方法的效率是非常不快的……
于是我又想,不是Hash的效率很快吗?那就用它来保存各个Timer吧。
至于哪种嘛……当然是最快的拉链Hash。
每创建一个Timer,就检测是否有可链接的Timer。如果没有就将这个Timer加入Hash表里。
基本思想就是这个,只不过数据结构改变了。
代码(应该无Bug):
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
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
set Hash_Next = HH
if HH != 0 then
set Hash_Before = HA
endif
set Hash_Before = 0
set Hash_Head = HA
set Hash_Timers_HA = t_a
set Hash_Timers = t
endfunction
function RemoveOldHash takes integer address, integer index returns nothing
local integer before = Hash_Before
local integer next = Hash_Next
if before != 0 then
set Hash_Next = next
else
set Hash_Head = next
endif
if next != 0 then
set Hash_Before = before
endif
set Hash_Timers = null
set Hash_Timers_HA = 0
set Hash_Before = 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
loop
exitwhen HA == 0
if Hash_Timers_HA - 1 == t_a then
return HA
endif
set HA = Hash_Next
endloop
set HA = Hash_Head
loop
exitwhen HA == 0
if Hash_Timers_HA + 1 == t_a then
return HA
endif
set HA = Hash_Next
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
用的是双拉链Hash。
这样我们解决了创建新Timer时的连续问题。
//============================膜拜疯人老大的分界线================== 在这里放测试用地图~ + 文本版帖子~
End~~~~~~~
中文:2300,字符数计空格:14000 写的好快……
恩,
在想一个问题……
基本上时早上起床时想到的
那就是把这个原理扩展使用
如果我们要创建N个连续handle的M型(M是handle型扩展的)怎么办
……
别的还没有想…… 其实吧。。我没想到你这个东西有啥用。。。。
而且为啥是个实数?按理说计算机只认整数 或许在持续的堆精华的时候发现了一个惊天秘密
比如说魔兽争霸3的英文名不叫Warcraft III 实数可以存储比整数更多的信息 说来说去最后决定用拉链hash了?嘛,这个蘑菇原来就用来串烧数组用的
我比较费解的一是原来用handle做储存,像是timer-location链表,比数组的好处在无8191上限,和连续handle值做表头上的结构简化。
这里出现连续的两个timer我没怎么看懂,那是干嘛的啊,或者说“每一个Timer都配一个Timer”是什么意思 ....看了几遍...我发现我理解能力比较低..
请问这个 和 TimerDataSystem
有什么差别
有什么优势
...或者 有实际应用例子没... 唯一的优势是当大于8192个的时候仍然能方便地创建计时器。。不过我还没想出这个东西有啥意义。。。
其实这个相当于
struct
{
timer timer_true
timer timer_data
}
的意思 意义吗
因为这个是初步研究……
恩,如果推广呢?
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
如果能够提升存储时的效率到一个满意的水平上
估计GC就可以淘汰了 我的意见是gc是给逻辑不太好,或者英文不好的人用的。。。。 引用第14楼疯人¢衰人于2009-05-19 10:50发表的:
意义吗
因为这个是初步研究……
恩,如果推广呢?
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
....... http://www.islga.org/bbs/images/back.gif
...能解释下参数作用么...
回答下12楼的问题... 恩
我现在就对拉链hash理解不能
…… .....我是对你们要实现的 理解不能....
或者 表达下 你们已经实现 和准备实现的?....没有主题理解不能这贴说什么.... 基本上时无目的的
就是发表一个想法
区别呢
原先的方法,比如hash
都是读取时比较复杂的
这个在存储时复杂
基本上这个就是研究handle运行机理的一个副产品
恩,创建连续handle值的一系列变量实在是太没效率了
唯一突出的特点就是各次绑定都彼此无关
存储成功就一定能够使用
总之,就是让一个timer能够多存储一个实数变量
然后我们就可以通过这个变量来绑定一些东西