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

GA地精研究院

 找回密码
 立即注册
查看: 3727|回复: 29

[文献资料] 创建连续的任意长度的handle、自己在GA的一岁生日

[复制链接]
发表于 2009-5-26 13:11:28 | 显示全部楼层 |阅读模式
气…………上一个贴居然没人看懂我………………呜呜呜呜呜呜呜呜呜呜呜呜…………太失败了……………………

因为疯人老大说,如果能创建出一连串(HandleAddress是连续的)任意长度的Handle,那就好了。
于是在家潜心研究了一番,并最后优化到了极限,总算达到了O(2*m)的时间复杂度~太棒了呢~~

1.关于为什么要开发这样的系统和上一个贴大家可能不太明白的地方
2.系统基本思想
3.O( m * ( 2n + n * n ) )优化到O( m * 2 * n )的算法
4.O( 2 * m )的极限压缩算法
5.杂谈


顺便说一下,今天是我在GA的一周年~可惜周末无法上网……见不到GA…………呜呜~~~~(>_<)~~~~
PS:本文所有“今天”是值得2009/5/23这时候……
现在还在家里奋笔疾书ing~~

//======================为自己在GA的一岁生日感到高兴================

    1.关于为什么要开发这样的系统和上一个贴大家可能不太明白的地方

首先,这个系统,就是用来为Handle存储数据之用,一个Handle的HandleAddress+1,+2,+3...+N都是与这个Handle同一类型(其实也可以不同类型)的Handle,且这些Handle是专门用来存储数据的。就像Location链表中的每一个Location结点一样,根据Handle类型,可以存储很多数据。获得/取出数据时,只要用ReturnBug或UnionBug将获得【被绑定数据的Handle】的HandleAddress增加指定位移量之后的Handle,然后再对它进行操作即可。
比如一个被绑定数据的Handle(假设为Timer),按照此系统的思路,【它的HandleAddress再加上(减去)1,2,3....n】为HandleAddress的Handle,都是Timer,而且是不会干正事的Timer,只会存储数据的Timer。

这样就相当于是一个在HandleAddress里的数组一样了。
╮(╯▽╰)╭……不知大家明白否,其实就是拿Handle存储数据,然后读取的方式不像是Location那样的链表是一个一个跳着读的,而是直接加上位移量读取数据的。

然后是大家再上一个贴中可能看不懂的几个地方,我再解释一下:
然后……突然发现我居然不知道有啥问题…………看来我的沟通……有问题……………………………………………………呜呜呜……………………%>_<%

唯一发现的问题:作用是啥?
不过作用其实就是存储数据,存储的结构就是Handle,而不是全局变量数组而已………………

……如果大家还有疑问,再往下看完这一贴,应该可能会有答案……

//======================为自己在GA的一岁生日感到高兴================

    2.系统基本思想
这个系统基本思想是,不断地创建Handle(这个系统独立创建),然后加入到一个Hash表中。每一次创建,在新创建的Handle周围(-n)~(+n)区域内,寻找可用的Handle,并映射到一个数组里,然后看这个数组是否有n个连续的Handle,如果有,那么返回这一连续中最小/大(其实这无所谓)的一个Handle;如果没有,不返回,再次创建Handle,直到有连续的一段长度为n的Handle产生。
创建的时间复杂度:O(?)
读取/设置的时间复杂度:O(1)
销毁的时间复杂度:O(1)
重点优化方向:
判断一个数组里是否有n个连续的Handle。

//======================为自己在GA的一岁生日感到高兴================

    3.O( m * ( 2n + n * n ) )优化到O( m * 2 * n )的算法
首先,我们发现,DeleteTimer和Get/Set都是很好弄的,只有New是很恶心的,不知道怎么编……
所以来看:
我们如果直译上面的文字,转化为程序,那么显而易见的是O(m * ( 2 * n + n*n ))的一个算法。
这个算法思想如下:
1.2*n范围内Handle扫一遍
2.每一个Handle,看后边有没有n个跟着连续的Handle。

如果我们把2*n的数组看成一个字符串,“0”代表没有Handle,“1”代表有Handle。
那么我们可以把这个问题看成字串匹配问题~
一个2*n的字符串,匹配一个n个全部为“1”的字串。

范例
Handle字符串“00111 1 11000”
匹配的字符串“111111”
那么当外层循环扫到"001"的1时,内层循环扫到“100”的1时,结束整个创建,返回"001"的1。

这样是非常非常慢的。我们再看这个数组。
我们发现匹配的字符串所有的字符都是“1”,那么我们可以这样想,从左至右扫一遍Handle字符串,发现有0时,就说明在它前面是没有连续的n长度的字符串的,计数器清零。而如果是1,那么计数器+1,当计数器>=n时,说明有连续的Handle。
这样只用扫一遍数组,就可以得到连续的Handle。
时间复杂度O(2*n)
加上需要扫2*n的HashTable里的Handle,总的时间复杂度为O( m * ( 2 * n + 2 * n ) )
基本相当于O( m * 4 * n )
但是,我们通过对整个匹配过程的观察,发现可以将匹配过程和查找Handle的过程合并,节约O(2*n)。
总的时间复杂度为O( m * 2 * n )
代码:
[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, integer n returns timer
    local integer up_index = index + 1
    local integer down_index = index - 1
    local integer move_index = index - n
    local integer HA = 0
    local integer i = 0
    local boolean Hash_Have = false
    local integer count = 0
    local integer array Set
    //这里有很多运用上限8190来减缩代码、提升效率的代码,微乱
    loop
        exitwhen i >= n
        if move_index > 8191 then
            set up_index = up_index - 8191
        endif
        //if move_index < 1 then
        //    set up_index = up_index + 8191
        //endif
        set HA = Hash_Head[move_index]
        loop
            exitwhen HA == 0
            if HA == t_a + i - n then
                set Hash_Have = true
                set Set[count] = HA
                set count = count + 1
                if count == n then
                    set Return_Timer = Hash_Timers[Set[0]]
                    set i = count - 1
                    loop
                        exitwhen i < 0
                        call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
                        set i = i - 1
                    endloop
                    return Return_Timer
                endif
                exitwhen true
            endif
            set HA = Hash_Next[HA]
        endloop
        if not Hash_Have then
            set count = 0
        else
            set Hash_Have = false
        endif
        set move_index = move_index + 1
        set i = i + 1
    endloop
    //set Set[count] = index
    set count = count + 1
    if count == n then
        set Return_Timer = Hash_Timers[Set[0]]
        set i = count - 2
        loop
            exitwhen i < 0
            call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
            set i = i - 1
        endloop
        return Return_Timer
    endif
    set i = n + 1
    loop
        exitwhen i >= 2 * n
        if move_index > 8191 then
            set up_index = up_index - 8191
        endif
        //if move_index < 1 then
        //    set up_index = up_index + 8191
        //endif
        set HA = Hash_Head[move_index]
        loop
            exitwhen HA == 0
            if HA == t_a + i - n then
                set Hash_Have = true
                set Set[count] = HA
                set count = count + 1
                if count == n then
                    set Return_Timer = Hash_Timers[Set[0]]
                    set i = count - 1
                    loop
                        exitwhen i < 0
                        if Set != index then
                            call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
                        endif
                        set i = i - 1
                    endloop
                    return Return_Timer
                endif
                exitwhen true
            endif
            set HA = Hash_Next[HA]
        endloop
        if not Hash_Have then
            set count = 0
        else
            set Hash_Have = false
        endif
        set move_index = move_index + 1
        set i = i + 1
    endloop
    return null
endfunction

function NewTimer takes integer n returns timer
    local timer Union_Timer = null
    local integer Union_Int = 0
   
    local integer timer_hashindex = 0
    local integer i = 0
   
    local integer Timer_HA = 0
   
    set Union_Timer = CreateTimer()
    loop
        set timer_hashindex = Hash( Union_Int )
        set Return_Timer = CheckHashTimers( timer_hashindex, Union_Timer, Union_Int, n )
        if i != null then
            set Union_Timer = null
            return Return_Timer
        endif
        call AddNewHash( timer_hashindex, Union_Timer, Union_Int )
        set Union_Timer = CreateTimer()
    endloop
    set Union_Timer = null
    return null
endfunction
[/jass]
至此,对于匹配过程的优化已经完毕。

再在这里讲一下,为什么要在上一帖中的NewTimer和DeleteTimer使用所谓“双struct”,是因为我脑子犯浑……只想着struct不想着Stack………………其实一个Stack就可以解决问题了…………
Timer可以回收使用,所以创建完的Timer就可以保存到栈中,等到下一次需要用的时候再拿出来就可以,不用在创建新的timer了。
按照创建新Handle段和读取旧Handle段分担效率的情况估计,可以将获得Handle段的时间复杂度降至O(m*n)

注意事项:
注意注意~~我这个系统的连续Timer的长度n是要“从始至终”的,不能中途改变,否则可能有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
   
    timer array Stack_Timers
    integer Stack_Top = 0
   
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, integer n returns timer
    local integer up_index = index + 1
    local integer down_index = index - 1
    local integer move_index = index - n
    local integer HA = 0
    local integer i = 0
    local boolean Hash_Have = false
    local integer count = 0
    local integer array Set
    //这里有很多运用上限8190来减缩代码、提升效率的代码,微乱
    loop
        exitwhen i >= n
        if move_index > 8191 then
            set up_index = up_index - 8191
        endif
        //if move_index < 1 then
        //    set up_index = up_index + 8191
        //endif
        set HA = Hash_Head[move_index]
        loop
            exitwhen HA == 0
            if HA == t_a + i - n then
                set Hash_Have = true
                set Set[count] = HA
                set count = count + 1
                if count == n then
                    set Return_Timer = Hash_Timers[Set[0]]
                    set i = count - 1
                    loop
                        exitwhen i < 0
                        call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
                        set i = i - 1
                    endloop
                    return Return_Timer
                endif
                exitwhen true
            endif
            set HA = Hash_Next[HA]
        endloop
        if not Hash_Have then
            set count = 0
        else
            set Hash_Have = false
        endif
        set move_index = move_index + 1
        set i = i + 1
    endloop
    //set Set[count] = index
    set count = count + 1
    if count == n then
        set Return_Timer = Hash_Timers[Set[0]]
        set i = count - 2
        loop
            exitwhen i < 0
            call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
            set i = i - 1
        endloop
        return Return_Timer
    endif
    set i = n + 1
    loop
        exitwhen i >= 2 * n
        if move_index > 8191 then
            set up_index = up_index - 8191
        endif
        //if move_index < 1 then
        //    set up_index = up_index + 8191
        //endif
        set HA = Hash_Head[move_index]
        loop
            exitwhen HA == 0
            if HA == t_a + i - n then
                set Hash_Have = true
                set Set[count] = HA
                set count = count + 1
                if count == n then
                    set Return_Timer = Hash_Timers[Set[0]]
                    set i = count - 1
                    loop
                        exitwhen i < 0
                        if Set != index then
                            call RemoveOldHash( Set, Hash( Hash_Timers_HA[Set] ) )
                        endif
                        set i = i - 1
                    endloop
                    return Return_Timer
                endif
                exitwhen true
            endif
            set HA = Hash_Next[HA]
        endloop
        if not Hash_Have then
            set count = 0
        else
            set Hash_Have = false
        endif
        set move_index = move_index + 1
        set i = i + 1
    endloop
    return null
endfunction

function NewTimer_GetLine takes integer n returns timer
    local timer Union_Timer = null
    local integer Union_Int = 0
   
    local integer timer_hashindex = 0
    local integer i = 0
   
    local integer Timer_HA = 0
   
    set Union_Timer = CreateTimer()
    loop
        set timer_hashindex = Hash( Union_Int )
        set Return_Timer = CheckHashTimers( timer_hashindex, Union_Timer, Union_Int, n )
        if i != null then
            set Union_Timer = null
            return Return_Timer
        endif
        call AddNewHash( timer_hashindex, Union_Timer, Union_Int )
        set Union_Timer = CreateTimer()
    endloop
    set Union_Timer = null
    return null
endfunction

//====================================
function NewTimer takes integer n returns timer
    local integer temp = Stack_Top
    if temp == 0 then
        return NewTimer_GetLine( n )
    else
        set temp = temp - 1
        set Return_Timer = Stack_Timers[temp]
        set Stack_Timers[temp] = null
        set Stack_Top = temp
    endif
    return Return_Timer
endfunction

function DeleteTimer takes timer t returns nothing
    set Stack_Timers[Stack_Top] = t
    set Stack_Top = Stack_Top + 1
endfunction

function GetTimerData takes timer ti, integer index returns real
    local integer Union_Int = 0
    local timer Union_Timer = ti
    local real temp = 0.0
    set Union_Int = Union_Int + index + 1
    set temp = TimerGetTimeout( Union_Timer )
    set Union_Timer = null
    return temp
endfunction

function SetTimerData takes timer ti, integer index, real v returns nothing
    local integer Union_Int = 0
    local timer Union_Timer = ti
    set Union_Int = Union_Int + index + 1
    call TimerStart( Union_Timer, v, false, null )
    call PauseTimer( Union_Timer )
    set Union_Timer = null
endfunction
[/jass]

这个算法优化的不错吧~~~
O(m*n)……O(m*n)………………O(m*n)………………………………

狠狠……又是一个不好的东东…………
首先说一下,创建的效率考虑到Hash小拉链的长度一般都为1,所以我就略掉了,为了让大家再弄明白一些,我引入一个系数k,表示Hash小拉链的长度(很小)。
m是得到连续的Handle需要创建的Handle数。
分析如下:
销毁函数:
HashTable:O(1)
MyTimerSystem:O(1)
不用对比。
HashGet/Set:O(k)
MYGet/Set:O(1)
需要对比。
HashCreate:O(1)
MYCreate:O(m*n*k)
由此得出结论:
使用我的系统和Hash绑定一个Handle,需要Get/Set(m*n)次以上,才能体现出我的高效来…………

而更深一层的估计,是建议在m>=n上。
我们取最小值m=n估计。
得出O(n^2)………………………………

这也太失败了!!!!!!!!!
也就是个攻击响应系统需要这个吧!!
每个Unit至少需要保存20个数据,这样就需要4000次才能超过Hash!!!!!!!!!!!!!!!!
啊啊啊啊啊啊啊啊啊啊啊啊啊啊…………
这是什么啊!!!!!!!!!
……………………………………………………
……………………………………………………
……………………………………………………
……………………………………………………


结论:对这个充满绝望的世界绝望了!!!!
我要去死了!!!!
谁也别拦我!!!!


这样不行………………
不是有句名言吗?

生命诚可贵,
爱情价更高。
若为WE故,
两者皆可抛。

所以需要再强悍一些的算法…………………………

//======================我要去死了!!!!!谁也别拦我!!!!================

    4.O( 2 * m )的极限压缩算法
后来我想了想,能不能直接从已连续的在Hash表中的Handle段的一端直接跳到另一端,这样很快就能得出连续的数量。
原理解释:
一个新Handle假定放入Hash表中。
那么,如果他的HandleAddress-1的Handle在Hash表中,我们得到它,然后和Address+1的长度加起来看够不够。
如果不在,说明-2,-3,-4....都是不能组成Handle连续段的,而-1又不在,所以无法与-XX的Handle连成一段。
+1,+2,+3....+n的也一样。
所以这样我们需要访问的结点,就只有两个:
1.HandleAddress+1的结点
2.HandleAddress-1的结点
但是我在上机编了之后……发现了个恶心的问题…………

就是最后的排泄,需要将所有n个Hash结点排除………………

这也太恶心了!效率为O(2*m+n)
怎么说我也是GA“较强人”(自恋呢~今天是我在GA的一周岁,大家就无视我吧~)
怎么能让“+n”这个小尾巴出现呢?
于是………………
我想出了恶魔般的算法:
将一段一连串的Handle在Hash表中只用两个节点表示……………………

于是O(2*m)的算法横空出世!!
总的时间复杂度:O(m*k)。
也就是说,Unit存20个数据,现在被攻击+攻击20次,就超过Hash了!!
哇哈哈哈哈!!!!


     >(' )
       )/
      /(
     /  `----/
     \  ~=- /
鸭子
嘎嘎!老兄,Unit只用struct就行~

噼里啪啦噼里啪啦噼里啪啦噼里啪啦

……我要去死了!!!我在说第3遍了!!!!

[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
   
    integer array Hash_OtherHead_HA
    integer array Hash_OtherHead
   
    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
   
    set Hash_OtherHead[HA] = HA
    set Hash_OtherHead_HA[HA] = t_a
   
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
   
    set Hash_OtherHead[address] = 0
    set Hash_OtherHead_HA[address] = 0
   
    call FlushHashAddress( address )   
endfunction

function UnionHashLine takes integer up_HA, integer down_HA, integer index, timer t, integer t_a returns nothing
    local integer left = 0
    local integer right = 0
    if up_HA == 0 and down_HA == 0 then
        call AddNewHash( index, t, t_a )
        return        
    endif
    if up_HA != 0 and down_HA != 0 then
        set left = Hash_OtherHead[down_HA]
        set right = Hash_OtherHead[up_HA]
    elseif up_HA != 0 then
        set left = AddNewHash( index, t, t_a )
        set right = Hash_OtherHead[up_HA]
    elseif down_HA != 0 then
        set left = Hash_OtherHead[down_HA]
        set right = AddNewHash( index, t, t_a )
    endif
    set Hash_OtherHead[left] = right
    set Hash_OtherHead_HA[left] = Hash_Timers_HA[right]
    set Hash_OtherHead[right] = left
    set Hash_OtherHead_HA[right] = Hash_Timers_HA[left]
    if up_HA != right and up_HA != 0 then
        call RemoveOldHash( up_HA, Hash( Hash_Timers_HA[up_HA] ) )
    endif
    if down_HA != left and down_HA != 0 then
        call RemoveOldHash( down_HA, Hash( Hash_Timers_HA[down_HA] ) )
    endif
endfunction

function CheckHashTimers takes integer index, timer t, integer t_a, integer n returns timer
    local integer up_index = index + 1
    local integer down_index = index - 1
    local integer HA = 0
    local integer i = 0
    local integer down_HA = 0
    local integer up_HA = 0
    local integer count = 1
    local integer temp = 0
    local timer UnionTimer = null
    local integer UnionInt = 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
            set up_HA = HA
            exitwhen true
        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
            set down_HA = HA
            exitwhen true
        endif
        set HA = Hash_Next[HA]
    endloop
    if up_HA != 0 then
        set count = count + ( Hash_OtherHead_HA[up_HA] - Hash_Timers_HA[up_HA] ) + 1
    endif
    if count >= n then//此时情况只有上边的timers数量+1=n这种情况
        set Union_Timer = null
        if up_HA != 0 then
            if Hash_OtherHead[up_HA] != up_HA then
                call RemoveOldHash( Hash_OtherHead[up_HA], Hash( Hash_OtherHead_HA[up_HA] ) )
            endif
            call RemoveOldHash( up_HA, Hash( Hash_Timers_HA[up_HA] ) )
        endif
        return t
    endif
    if down_HA != 0 then
        set count = count + ( Hash_Timers_HA[down_HA] - Hash_OtherHead_HA[down_HA] ) + 1
    endif
    if count >= n then
        if up_HA != 0 then
            if Hash_OtherHead[up_HA] != up_HA then
                call RemoveOldHash( Hash_OtherHead[up_HA], Hash( Hash_OtherHead_HA[up_HA] ) )
            endif
            call RemoveOldHash( up_HA, Hash( Hash_Timers_HA[up_HA] ) )
        endif
        call RemoveOldHash( down_HA, Hash( Hash_Timers_HA[down_HA] ) )
        if count - n - 1 >= 0 then
            set UnionInt = Hash_OtherHead_HA[down_HA] + (count - n - 1)
            call AddNewHash( Hash( UnionInt ), UnionTimer, UnionInt )
            set UnionInt = UnionInt + 1
        else
            set UnionInt = Hash_OtherHead_HA[down_HA] + (count - n)
        endif
        set Return_Timer = UnionTimer
        set UnionTimer = null
        return Return_Timer
    else
        call UnionHashLine( up_HA, down_HA, index, t, t_a )
    endif
    set Union_Timer = null
    return null
endfunction

function NewTimer takes integer n returns timer
    local timer Union_Timer = null
    local integer Union_Int = 0
   
    local integer timer_hashindex = 0
    local integer i = 0
   
    local integer Timer_HA = 0
   
    set Union_Timer = CreateTimer()
    loop
        set timer_hashindex = Hash( Union_Int )
        set Return_Timer = CheckHashTimers( timer_hashindex, Union_Timer, Union_Int, n )
        if i != null then
            set Union_Timer = null
            return Return_Timer
        endif
        set Union_Timer = CreateTimer()
    endloop
    set Union_Timer = null
    return null
endfunction
[/jass]

//======================我要去死了!!!!!谁也别拦我!!!!================

    5.杂谈

这个系统其实说白了就是个Handle原理研究的衍生品,其实还是很好的~
比如就拿绑定一个Timer来说,其实一个real就能达到struct的要求,效率不仅比所谓DataSystem要快许多(注意,这是真的,绑定一个数据的此种系统绝对比DataSystem要快),而且Create/Get/Set/Delete的时间复杂度都是O(1),比Hash要稳定多了。
但是硬伤是作为媒介的Handle本身并不适用来存储数据,基本每一个数据的存入都会引发Handle内部的方法运行。所以虽然效率比GameCache高,但却要比数组低(但是不是真的肯定就比数组低,Jass的数组是个表,不是真正的数组,所以他的效率也会比O(1)慢),只能算是一个拿来观赏的东西吧。说起来,其实也就只有“Handle表回收原理猜想”还有价值一些呢~

好啦~~今天是我在GA的一周岁~恩好高兴~
所以祝诸位GAer们也过得愉快哦~~

感谢疯人大哥如此不计较的把想法说给我~
感谢kook大人做我的路人~
感谢所有和我关系较亲密的人~~
剩下的人就不感谢了哦~~~嘻嘻~~(*^__^*) 嘻嘻……

恩恩~~嘎嘎~~
饿……忘了一件事……还没去死呢…………算了……………………生日怎么好去死……太丢人了我…………

中文字数:3000 字符数:23000
发表于 2009-5-26 13:40:59 | 显示全部楼层
虽然说我觉得这个系统没什么用处的说。。。

那,一周岁生日快乐
回复 支持 反对

使用道具 举报

发表于 2009-5-26 13:42:53 | 显示全部楼层
e....................
400行代码.............
还是玩游戏好了
回复 支持 反对

使用道具 举报

发表于 2009-5-26 13:55:39 | 显示全部楼层
如此之长的代码量推广很难呢。。
回复 支持 反对

使用道具 举报

发表于 2009-5-26 14:12:12 | 显示全部楼层
LS写的最长的代码是多长呢?
回复 支持 反对

使用道具 举报

发表于 2009-5-26 14:44:01 | 显示全部楼层
LZ的帖子实在太长了,看完都有困难的说
另外全文jass不带缩进,格式很混乱,注释又很少,非常影响理解和推广
回复 支持 反对

使用道具 举报

发表于 2009-5-26 14:52:23 | 显示全部楼层
你是说单个函数么。。。

单个函数最长的一百行不到吧。
回复 支持 反对

使用道具 举报

发表于 2009-5-26 15:28:30 | 显示全部楼层
我终于还是想到了一个猥亵、YD、无耻、下流……的方法来解决效率的问题
保证依次创建的handle都是连续的
……
但是这个方法也许会用到japi、JASSBUG等……N多有难度的技术……
实现的可能不下于对以上代码的效率的再次提高……
那么方法是什么呢?

就是找到判断Handle表是否有空位的方法
修改其关键内容
也就是说
如果在我们需要创建连续handle时
将有空位的handle表伪装成已经满的
然后在创建完成后再恢复正常
这样
因为JASS虚拟机判断handle表是满的
所以它会将新建的handle放在handle表的表头
这样新建的handle就连续了……

但是这种方法的实现,已经超出了J的范围
除非有某个bug可利用
否则……

而且这样实现
基本上可以说
DATASYSTEM都可以被淘汰了
如果要绑定任意个handle
只要使用这个方法
依次创建或者用Location绑定就一切OK
通过连续handle任意一个就可以找到跟它绑定到一起的
只要知道这个变量的handle和它的位置等信息就行
而这些是在你创建连续handle时确定的
只要对应好函数,根本不会出什么问题……
可惜
回复 支持 反对

使用道具 举报

发表于 2009-5-26 15:32:29 | 显示全部楼层
血戮不在
我帮他上传吧
那三段代码的j文件

新建文件夹.rar

4 KB, 下载次数: 20

回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-26 16:35:55 | 显示全部楼层
无缩进问题解决了~~
貌似看预览好像会让代码没有缩进呢~
回复 支持 反对

使用道具 举报

发表于 2009-5-26 17:28:46 | 显示全部楼层
嗯,就我所理解的说一下吧。
这个“创建任意长度的handle”似乎是以取代TimerDataSystem为目标,但是以现在的情况相比之前的“L数组”在我感觉反而是个退步呢。最理想的情况应该是创建一个计时器后,依次获得连续的N个Location,这样因为Location可以存储两个real数据(比计时器的1个好,呃,那使用镜头呢, 疯人¢衰人 参考的帖子中有指出吧),而其Handle值由于是递增的关系所以本身就是一个模拟的数组了(计时器是0,后面的点依次为1,2,3...)。
这样的话,情况就有些复杂了,也就是需要记录下所有创建了的计时器和点,而且不恰当的计时器又会打断点的连续性。
现在LZ你的代码不再使用“L数组”了,也就是说使用连续的Timer来存储数据,当然也是可以的,但在我看来并没有比TimerDataSystem好一点,而且TimerDataSystem也是可以扩展的,比如让一个Timer绑定不定数量的数据,这个我已经有发帖讨论过方法了。另一方面,就是8191的数量限制,这个大家也有说了,模拟超过8191的数组并不难,但是说实话,也并不如想象当中的简单,我的想法是如果你觉得8191不够,那就把数据分类,用多个数组来存储,相比来说,依然会比LZ你的方法要好一些的吧。

嗯,最后一点了,所有的系统都要为实战做准备的,使用LZ的方法创建的一大堆的计时器,若想形成一个连续的数量,那就要求地图的排泄达到极致才可以,若是有疏忽,有一个地方没有set null,这样有一小段的计时器很可能被废掉,况且还有很多无法避免的Handle的增加,比如Condition一类,或者地图要求在中途创建一个永远运行下去的触发,都会对计时器的连续性造成困难,这个也是该系统中不得不考虑的问题吧。

呵呵,祝LZ生日快乐啦。
回复 支持 反对

使用道具 举报

发表于 2009-5-26 18:44:44 | 显示全部楼层
引用第10楼cccty1l于2009-05-26 17:28发表的  :
嗯,就我所理解的说一下吧。
这个“创建任意长度的handle”似乎是以取代TimerDataSystem为目标,但是以现在的情况相比之前的“L数组”在我感觉反而是个退步呢。最理想的情况应该是创建一个计时器后,依次获得连续的N个Location,这样因为Location可以存储两个real数据(比计时器的1个好,呃,那使用镜头呢, 疯人¢衰人 参考的帖子中有指出吧),而其Handle值由于是递增的关系所以本身就是一个模拟的数组了(计时器是0,后面的点依次为1,2,3...)。
这样的话,情况就有些复杂了,也就是需要记录下所有创建了的计时器和点,而且不恰当的计时器又会打断点的连续性。
现在LZ你的代码不再使用“L数组”了,也就是说使用连续的Timer来存储数据,当然也是可以的,但在我看来并没有比TimerDataSystem好一点,而且TimerDataSystem也是可以扩展的,比如让一个Timer绑定不定数量的数据,这个我已经有发帖讨论过方法了。另一方面,就是8191的数量限制,这个大家也有说了,模拟超过8191的数组并不难,但是说实话,也并不如想象当中的简单,我的想法是如果你觉得8191不够,那就把数据分类,用多个数组来存储,相比来说,依然会比LZ你的方法要好一些的吧。

.......
创建任意长度的handle”似乎是以取代TimerDataSystem为目标
也许有这个想法吧,这个思路从开始就是一个逆向的思维
而且又是研究handle表的副产品
它思路是承接连续Location来的……
Location使用单向链表的方法做的,
它的主要缺点就是读取的太慢
要一个个的找
即使使用搭建多维度链表的方法
效率也是达不到要求
那么如果创建 Location如果handle连续的话就没有这个问题了……

最初是创建两个连续Timer做简单的Timer绑定
多handle是后来提出的
基本上就是想扩展下……

关于连续handle的内容
创建Location还是Timer是无所谓的
基本上都是一个记录数据的作用
用Timer的目的也不过是为了方便使用TimerStart方便些

血戮的函数我自己看的也不是很明白
只是我再向他解释思路的时候
我的目的是创建一次性的连续handle
以最简单的两个连续handle的Timer为例
我的目的是在每次要对Timer绑定一个实数时创建连续的Timer
一个绑定数据一个做正常的Timer使用
用完就排泄掉
这样每次绑定都不相关
这样即使同时使用10000000……个也没有问题
(当然谁也不可能用那么多)
这是上一个贴发表内容的目的

对于多个连续
我最初也是这样希望的
但是很无奈
这样多个连续式没有多大意义的
因为只能创建同样的变量类型的变量
所以于是又走了Location的老路

这个东西用处不大
只是个纯想法上的东西
相比而言
我前面说的伪造handle表已满状态的方法更有价值
如果能够成功
我们就可以讲多个handle做成一个类似结构体的东西
不过这个方法的实现更加不可能
回复 支持 反对

使用道具 举报

发表于 2009-5-27 01:27:10 | 显示全部楼层
2.系统基本思想
这个系统基本思想是,不断地创建Handle(这个系统独立创建),然后加入到一个Hash表中。每一次创建,在新创建的Handle周围(-n)~(+n)区域内,寻找可用的Handle,并映射到一个数组里,然后看这个数组是否有n个连续的Handle,如果有,那么返回这一连续中最小/大(其实这无所谓)的一个Handle;如果没有,不返回,再次创建Handle,直到有连续的一段长度为n的Handle产生。
创建的时间复杂度:O(?)
读取/设置的时间复杂度:O(1)
销毁的时间复杂度:O(1)
重点优化方向:



这个创建很无语的...记得我和ls说过 要超8192方法很多。。。而且时间复杂度都可以是o(1)
只要初始化创建些连续~~既然你地图确定会用到那么大。。那不如开始一次性创建好算了。。。

而你这个即时创建。。只是节约了 开始创建的消耗。。但游戏时即时创建。。
还要保证一直创建到连续。。。那消耗总量  远远大于预先创建好了的。。。



至于其他的就是根据连续的来储存绑定了 那和datasystem没区别了
回复 支持 反对

使用道具 举报

发表于 2009-5-27 05:29:42 | 显示全部楼层
地图内置C语言脚本和C编译器才是王道。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-27 12:50:35 | 显示全部楼层
嘻嘻(*^__^*) 嘻嘻……顶LS哦~~~~
至于这个系统的价值~~我倒无所谓~
反正是提升自己的编程功底~~我也不在意~~啦~~~
顺便说一下……cccty1l的一个Timer配N个Location的想法基本无法实现哦~~
因为这要求Timer的特定连续长度的HandleAddress都是空的或者是Location,就算是系统函数创建的timer,也非常难达到要求。
回复 支持 反对

使用道具 举报

发表于 2009-5-27 17:34:28 | 显示全部楼层
编程功底不是因为设计或者分析逻辑过程而提升的。。
回复 支持 反对

使用道具 举报

发表于 2009-5-27 22:28:03 | 显示全部楼层
引用第14楼血戮魔动冰于2009-05-27 12:50发表的  :
顺便说一下……cccty1l的一个Timer配N个Location的想法基本无法实现哦~~
因为这要求Timer的特定连续长度的HandleAddress都是空的或者是Location,就算是系统函数创建的timer,也非常难达到要求。
所以我才认为你们是由于妥协才选择只创建计时器的,还有这根本就不是我的想法呢。

既然是自己认为目前还无用的东西,现在做的应该是完善吧,不需要这么着急把每个过程都发表出来的,精华啥的都是浮云呢。
回复 支持 反对

使用道具 举报

发表于 2009-5-31 07:12:14 | 显示全部楼层
引用第16楼cccty1l于2009-05-27 22:28发表的  :

所以我才认为你们是由于妥协才选择只创建计时器的,还有这根本就不是我的想法呢。

既然是自己认为目前还无用的东西,现在做的应该是完善吧,不需要这么着急把每个过程都发表出来的,精华啥的都是浮云呢。
不是妥协呢
只是创建的handle要是相同类型的
因为无法在不使用等待的情况下
将两个handle变量创建到同一个handle值上
这个很无奈
回复 支持 反对

使用道具 举报

发表于 2009-5-31 07:48:42 | 显示全部楼层
引用第17楼疯人¢衰人于2009-05-31 07:12发表的  :

不是妥协呢
只是创建的handle要是相同类型的
因为无法在不使用等待的情况下
将两个handle变量创建到同一个handle值上
.......

貌似我说的有些过了,其实在这一方面,你和血戮魔动冰 是走的最远的人了。
我就期待后文吧。
回复 支持 反对

使用道具 举报

发表于 2009-5-31 10:38:21 | 显示全部楼层
后文很难呢……
到处找BUG
如果不使用bug的话
基本上到此就结束了
效率无法再增加了
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2019-10-21 03:46 , Processed in 0.320893 second(s), 28 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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