请选择 进入手机版 | 继续访问电脑版

GA地精研究院

 找回密码
 立即注册
查看: 4085|回复: 46

[文献资料] Hash_Timer——动态TimerDataSystem

[复制链接]
发表于 2009-5-18 13:07:29 | 显示全部楼层 |阅读模式
曾经我说过,用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.最终的系统~

//============================膜拜疯人老大的分界线==================
 楼主| 发表于 2009-5-18 13:07:49 | 显示全部楼层

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表】就是一个栈,但我是这样认为的。

//============================膜拜疯人老大的分界线==================
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-18 13:08:01 | 显示全部楼层
2.如何实现Timer的连续
既然如此,我们就知道,新的Handle的HandleAddress是没有一定顺序的,也就是说,随机的、无法预估的HandleAddress会被新的Handle占用。
而如果是有顺序的话,我们很快就能得出一个算法:

循环:
{
    创建一个Timer。
    对比这个Timer和【前一个创建的Timer】的Handle值,如果差1,那么清空未形成连接的Timer,返回这个Timer。
    如果没有差1则
    将【前一个创建的Timer】存入一个数组,等待删除。
    将这个Timer存入【前一个创建的Timer】的值。
}
而由于Handle表永远不可能到顶,所以我们一定会有一次找到连接的Timer。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-18 13:08:43 | 显示全部楼层
//======专门放图======
Hash_Timer1.jpg
//======专门放图======
回复 支持 反对

使用道具 举报

 楼主| 发表于 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时的连续问题。

//============================膜拜疯人老大的分界线==================
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-18 13:11:20 | 显示全部楼层
在这里放测试用地图~ + 文本版帖子~
End~~~~~~~

中文:2300,字符数计空格:14000
回复 支持 反对

使用道具 举报

发表于 2009-5-18 15:09:10 | 显示全部楼层
写的好快……
恩,
在想一个问题……
基本上时早上起床时想到的
那就是把这个原理扩展使用
如果我们要创建N个连续handle的M型(M是handle型扩展的)怎么办
……
别的还没有想……
回复 支持 反对

使用道具 举报

发表于 2009-5-18 17:35:48 | 显示全部楼层
其实吧。。我没想到你这个东西有啥用。。。。

而且为啥是个实数?按理说计算机只认整数
回复 支持 反对

使用道具 举报

发表于 2009-5-18 17:37:59 | 显示全部楼层
或许在持续的堆精华的时候发现了一个惊天秘密

比如说魔兽争霸3的英文名不叫Warcraft III [s:166]
回复 支持 反对

使用道具 举报

发表于 2009-5-18 17:43:31 | 显示全部楼层
提示: 该帖被管理员或版主屏蔽
回复 支持 反对

使用道具 举报

发表于 2009-5-18 19:52:14 | 显示全部楼层
实数可以存储比整数更多的信息
回复 支持 反对

使用道具 举报

发表于 2009-5-18 22:25:45 | 显示全部楼层
说来说去最后决定用拉链hash了?嘛,这个蘑菇原来就用来串烧数组用的
我比较费解的一是原来用handle做储存,像是timer-location链表,比数组的好处在无8191上限,和连续handle值做表头上的结构简化。
这里出现连续的两个timer我没怎么看懂,那是干嘛的啊,或者说“每一个Timer都配一个Timer”是什么意思
回复 支持 反对

使用道具 举报

发表于 2009-5-18 22:30:01 | 显示全部楼层
....看了几遍...我发现我理解能力比较低..
请问这个 和 TimerDataSystem
有什么差别
有什么优势

...或者 有实际应用例子没...
回复 支持 反对

使用道具 举报

发表于 2009-5-18 23:25:54 | 显示全部楼层
唯一的优势是当大于8192个的时候仍然能方便地创建计时器。。不过我还没想出这个东西有啥意义。。。

其实这个相当于
struct
{
timer timer_true
timer timer_data
}
的意思
回复 支持 反对

使用道具 举报

发表于 2009-5-19 10:50:18 | 显示全部楼层
意义吗
因为这个是初步研究……
恩,如果推广呢?
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
如果能够提升存储时的效率到一个满意的水平上
估计GC就可以淘汰了
回复 支持 反对

使用道具 举报

发表于 2009-5-19 11:07:59 | 显示全部楼层
我的意见是gc是给逻辑不太好,或者英文不好的人用的。。。。
回复 支持 反对

使用道具 举报

发表于 2009-5-19 19:13:39 | 显示全部楼层
引用第14楼疯人¢衰人于2009-05-19 10:50发表的  :
意义吗
因为这个是初步研究……
恩,如果推广呢?
恩推广到创建有限个连续handle值的同类型handle变量
也许有用了吧
.......


...能解释下参数作用么...
回答下12楼的问题...
回复 支持 反对

使用道具 举报

发表于 2009-5-19 19:14:09 | 显示全部楼层

我现在就对拉链hash理解不能
……
回复 支持 反对

使用道具 举报

发表于 2009-5-19 19:18:55 | 显示全部楼层
.....我是对你们要实现的 理解不能....

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

使用道具 举报

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

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|移动端|小黑屋|地精研究院

GMT+8, 2019-10-14 13:57 , Processed in 0.313947 second(s), 28 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表