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.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呢？
突然想到
[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时的连续问题。

//============================膜拜疯人老大的分界线==================

血戮魔动冰

在这里放测试用地图~ + 文本版帖子~
End~~~~~~~

中文：2300，字符数计空格：14000

疯人￠衰人

写的好快……
恩，
在想一个问题……
基本上时早上起床时想到的
那就是把这个原理扩展使用
如果我们要创建N个连续handle的M型（M是handle型扩展的）怎么办
……
别的还没有想……

eff

其实吧。。我没想到你这个东西有啥用。。。。

而且为啥是个实数？按理说计算机只认整数

lunaflywar

或许在持续的堆精华的时候发现了一个惊天秘密

比如说魔兽争霸3的英文名不叫Warcraft III [s:166]

疯人￠衰人

实数可以存储比整数更多的信息

kook

说来说去最后决定用拉链hash了？嘛，这个蘑菇原来就用来串烧数组用的
我比较费解的一是原来用handle做储存，像是timer-location链表，比数组的好处在无8191上限，和连续handle值做表头上的结构简化。
这里出现连续的两个timer我没怎么看懂，那是干嘛的啊，或者说“每一个Timer都配一个Timer”是什么意思

linzefei

....看了几遍...我发现我理解能力比较低..
请问这个 和 TimerDataSystem
有什么差别
有什么优势

...或者 有实际应用例子没...

eff

唯一的优势是当大于8192个的时候仍然能方便地创建计时器。。不过我还没想出这个东西有啥意义。。。

其实这个相当于
struct
{
timer timer_true
timer timer_data
}
的意思

疯人￠衰人

意义吗
因为这个是初步研究……
恩，如果推广呢？
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
如果能够提升存储时的效率到一个满意的水平上
估计GC就可以淘汰了

eff

我的意见是gc是给逻辑不太好，或者英文不好的人用的。。。。

linzefei

引用第14楼疯人￠衰人于2009-05-19 10:50发表的  :
意义吗
因为这个是初步研究……
恩，如果推广呢？
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
.......

...能解释下参数作用么...
回答下12楼的问题...

疯人￠衰人

恩
我现在就对拉链hash理解不能
……

linzefei

.....我是对你们要实现的 理解不能....

或者 表达下 你们已经实现 和准备实现的?....没有主题  理解不能这贴说什么....

疯人￠衰人

基本上时无目的的
就是发表一个想法
区别呢
原先的方法，比如hash
都是读取时比较复杂的
这个在存储时复杂
基本上这个就是研究handle运行机理的一个副产品
恩，创建连续handle值的一系列变量实在是太没效率了
唯一突出的特点就是各次绑定都彼此无关
存储成功就一定能够使用
总之，就是让一个timer能够多存储一个实数变量
然后我们就可以通过这个变量来绑定一些东西