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

GA地精研究院

 找回密码
 立即注册
查看: 3379|回复: 9

[讨论] 还是说数组存储系统

[复制链接]
发表于 2009-2-14 18:56:26 | 显示全部楼层 |阅读模式
tv580025
[範例]好久不見的見面禮 - 類似緩存的存取系統
http://forums.wasabistudio.ca/viewtopic.php?f=5&t=18070
actboy168
物品合成
http://www.islga.org/bbs/read.php?tid=19253
注:↑两篇文章中作者都提出了他们使用了Hash表,我也是在看了他们的文章之后才开始思考如何使用Hash表
tv580025 和  Weberkkk的谈论贴
[備註]借我放一下HASH
http://forums.wasabistudio.ca/viewtopic.php?f=56&t=22426
Weberkkk
【WB】減少洩漏、提高效率、數據系統
http://bbs.tbswe.com/thread-90285-1-1.html
注:作者是文中提出
目前有三種方式可以取代或改良 ReturnBug + GC 的缺點
分別是VJ的Struct、HASH
還有介於 ReturnBug 與 HASH 之間的 DataSystem

另:Weberkkk在另外一个讨论之中也指出了
HASH用運算取得index,而我直接從GC取得index(这里的方式指的就是DataSystem--编者注),取得index之後再存取全局變量,就跟HASH的概念一樣了

仔细检查了几遍,应该没有什么大的错误了。早上写这些的时候觉得东西好像有点多,但是现在看来其实也没有什么特别的东西。近一段试图抛弃缓存使用数组来做地图,所以也比较留心这一类的方法。其实这些东西在之前的讨论过程中就说过了,但是我觉得没有汇总起来太散乱了,于是就整理了下大胆发表出来了,其实可能还是有点乱...以上是我写这篇文章的一些参考,他们提出了Hash表的原型(更早的我不晓得,如有错误请指正),并且就其效率以及与其他方法的比较做出了一些讨论。而本人目前只接触到DataSystem和Hash,所以本篇的讨论就限于此了。

(大家如果实在受不了我这个帖子大段大段的东西的话,嗯,我已经上传了一个地图,还是《屠夫山寨》...不过方法已经由之前的Hash修改为DataSystem了,个别地方还做了些许优化。然后大家可以参考帖子http://www.islga.org/bbs/read.php?tid=21595,只看这两个图的代码就可以了,因为DataSystem和Hash方法都很简单,我也不知道具体怎样解释,大家有兴趣的话可以多实践实践。好了,正文开始了

不可否认,ReturnBug + GC的应用是魔兽制图水平的一个飞跃,使用它之后解决了很多制图者遇到的难题,甚至在现在也有其无可取代的优点。我看过某人在某篇文章中说自从使用了此技术在他的图中几乎再找不到全局变量的影子了,由此可见该技术的强大。

但是强大归强大,缺点仍然是有的,比如缓存的读取速度较慢,在每段代码之前的繁琐的读取缓存数据的过程,还有所谓String的泄露,等等。很显然,上述的缺点在适当的使用全局数组变量是可以有效的缓解的,但是Jass中的数组的下脚标限定了只能是0-8191的整数,所以如何能将数据绑定到全局数组就是接下来要考虑的问题了。同时,需要指出的是,使用数组的前提是你明白你可以用来记录的数据的地址不能超过8191,这就是数组的缺点。

------------------------           一(1)------------------------------------------------
Weberkkk口中的DataSystem的特点是基于GC的,这个技术同时使用了缓存与数组,思路简单明了,其中TimerDataSystem 的代码如下:
(注:大家可以在Weberkkk的帖子中查看详细的介绍。)
[codes=jass]①
初始化函數
function SetDateSystem takes nothing returns nothing
    local integer A = 0
    call InitGameCacheBJ( "MapName.w3v" )
    set udg_Z_Gc = GetLastCreatedGameCacheBJ()
        loop
            exitwhen A > 8191
            set udg_Gcs_BL[A] = true
            set A = A + 1
        endloop
    call TriggerSleepAction( 0.00 )
        set A = 0
        loop
            exitwhen A > 4000
            set udg_Gcs_TimIX[A] = CreateTimer()
            call StoreInteger(udg_Z_Gc,H2S(udg_Gcs_TimIX[A]),"Index",A)
            set A = A+1
        endloop
    call TriggerSleepAction( 0.00 )
        loop
            exitwhen A > 8191
            set udg_Gcs_TimIX[A] = CreateTimer()
            call StoreInteger(udg_Z_Gc,H2S(udg_Gcs_TimIX[A]),"Index",A)
            set A = A+1
        endloop
endfunction[/codes]
Weberkkk
魔獸的線程執行有一定的上限,若達到上限,function的操作會被中斷,必須加入TriggerSleepAction 才能繼續執行。
然后Weberkkk给出的使用方法如下:
[codes=jass]function GetIndex takes nothing returns integer
local integer A = GetRandomInt(0,8191)
    loop
        exitwhen udg_Gcs_BL[A]
        set A = GetRandomInt(0,8191)
    endloop
    set udg_Gcs_BL[A] = false
    return A
endfunction

function LoadIndex takes nothing returns integer
    return GetStoredInteger(udg_Z_Gc,H2S(GetExpiredTimer()),"Index")
endfunction

function EndIndex takes integer Index returns nothing
    call PauseTimer(udg_Gcs_TimIX[Index])
    set udg_Gcs_BL[Index] = true
endfunction[/codes]
一些必要的解释:
Weberkkk
↑這三條函數依序是資源分配、指標讀取、資源回收。

使用隨機數的理由在於,假如200~299號的數組已經被占用
若以A=A+1的方式搜尋未使用空間,則會收到一百個false
使用貌似Struct的資源分配方式,則無法做到有效回收。

使用隨機數即使在四千個數組被佔用的情況下
仍有50%機率第一次就找到可用空間
即使佔用了七千個數組,仍有10%以上的機率直接找到可用空間。

嗯,思路打断下,现在的问题是为什么先做计时器的DataSystem?答案就是计时器比任何东西都需要ReturnBug + GC,而后者在很大一方面的应用就是在和计时器做配合,所以简化这个组合就是很必要的了。在上述的代码里面,通过ReturnBug + GC将下脚标与计时器绑定了起来,因此我们已经可以将需要记录的数据存储在数组里面了,它实现了计时器与数组的初步对接。

自然,该方法还没有脱离缓存,并且下脚标的分配也不算是最高效的。接下来我们看看TimerDataSystem的另外的版本:
(注:画中人的《我的个人函数集》http://www.islga.org/bbs/read.php?tid=8439也有TimerDataSystem,但是我的测试结果是存在泄露,所以不在此讨论了,但是必须要说的是,正是由于对画中人在此系统提出的原理的应用才会产生下面两个TimerDataSystem。↓这个代码取自 冰块 的 数组储存系统http://www.islga.org/bbs/read.php?tid=23076
[codes=jass]②
globals
integer FIRST_TIMER_H2I
timer array TIMER
integer array TIMER_STATE
endglobals

初始化函数
function ITS takes nothing returns nothing
local integer i = 1
set TIMER[0] = CreateTimer()
set TIMER_STATE[0] = 0
set FIRST_TIMER_H2I = H2I(TIMER[0])
loop
exitwhen (i > 8000)
set TIMER = CreateTimer()
set TIMER_STATE = 0
set i = i + 1
endloop
endfunction

↓三个函数依次为资源分配、指针读取、资源回收。
function GetTimerofID takes nothing returns integer
local integer i = 0
loop
if (TIMER_STATE == 0) then
    set TIMER_STATE = 1
    return i  
endif
set i = i + 1
endloop
return 0
endfunction

function GetTimerID takes timer t returns integer
return H2I(t) - FIRST_TIMER_H2I
endfunction

function RecTimerofID takes integer id returns nothing
call PauseTimer(TIMER[id])
set TIMER_STATE[id] = 0
endfunction[/codes]
一些必要的解释:
上述代码中的初始化函数中使用了一个大家都熟知的原理,那就是在地图刚刚创建之时,连续生成的计时器的handle值是连续的。将第一个计时器的handle值作为head(代码中为FIRST_TIMER_H2I),后面依次生成的计时器的handle减去head的值作为记录它的下脚标。这样,TimerDataSystem已经摆脱的GC的束缚,并且其指针读取的速度相当可观,仅使用一个减法就可以获取。需要注意的是,初始化函数ITS必须要地图初始化时运行才能保证该系统的正常使用,此TimerDataSystem仍然存在缺点,就是其资源分配的效率稍微偏下,应当改进。

需要指出的是,上面所有的代码中使用到的常用的ReturnBug函数我并没有添加,相信大家应该知道。然后由于本人更喜欢使用UnionBug,所以以下的代码中诸位看官有不理解的地方请查看 Renee 大人的 《[Union Bug]多值多类型对多值多类型的强制类型转换~~替代H2I和I2H的新方案~~》http://www.islga.org/bbs/read.php?tid=8722

[codes=jass]③
globals
integer I
timer Tm
integer Timer_F
integer array Timer_Data
integer Timer_maxN=-1
endglobals
//! define Timer_N 3000
↓初始化函数
function Timer_cre takes nothing returns nothing
local timer array t
local integer n=1
local integer bugs=-1
local integer id
local integer I
local timer Tm=CreateTimer()
local integer fid=-I
loop
    set Tm=CreateTimer()
    set id=I+fid
    if(id>0 and id<8191)then
        set Timer_Data[n]=id
        set n=n+1
    else
        set bugs=bugs+1
        set t[bugs]=Tm
    endif
    exitwhen n>=Timer_N
endloop
loop
    exitwhen bugs<=-1
    call DestoryTimer(t[bugs])
    set t[bugs]=null
    set bugs=bugs-1
endloop
set Timer_F=fid
set I=0
endfunction
↓三个函数依次为资源分配、指针读取、资源回收。
function Timer_get takes nothing returns integer
if(Timer_maxN<Timer_N)then
    set Timer_maxN=Timer_maxN+1
    return Timer_Data[Timer_maxN]
else
    return -1
endif
endfunction

//! define Timer_id(t) Timer_getid(0,t)
function Timer_getid takes integer I,timer Tm returns integer
return I+Timer_F
endfunction

function Timer_des takes integer id returns nothing
local timer Tm
local integer I=-Timer_F+id
call PauseTimer(Tm)
if Timer_maxN>=0 then
    set Timer_Data[Timer_maxN]=id
    set Timer_maxN=Timer_maxN-1
endif
set I=0
endfunction[/codes]
一些必要的解释:
上述代码的初始化函数添加了一段纠错的代码,可以在初始化时将可能存在的不正确的计时器删除,不过仍然推荐在地图初始化时运行。在资源分配和资源回收中使用了一个链表,保证了资源分配的高效率,在指针读取中沿用了前辈的做法,同样是高效率的。由于代码很简单,解释多了反而显的累赘,如果有不懂的地方,您可以在地图中自己试验看下指针是如何分配的。

现在来看,三个TimerDataSystem的指针获取速度都是很快的,因为它们都使用了空间换时间的做法,可以这么做也归功于计时器可以回收利用,并且即使在一个成品图中,计时器的数量也不会太多。在地图初始化时创建1000-8000不等的计时器所占用的内存不算多,但是却得到了一个高效率的代码,怎么看这个买卖都是值得的。

尽管它们在整体来看基本是相同的,但是相比较而言,我觉得最后一个TimerDataSystem的代码是最好的,因为一,它完全摆脱了缓存,二,它的资源分配是最高效的(当然,仅仅将刚才第二个例子中的代码中的“资源分配”修改为例三的链表形式也是可以的,这个完全随大家的习惯)。所以,我推荐大家使用它。

------------------------       一(2)------------------------------------------------
那么DataSystem在计时器之外的应用是如何进行的呢?我再举例一个适用于单位的系统吧。
[codes=jass]④
globals
integer Unit_maxN=1
integer array Unit_data
endglobals

↓三个函数依次为资源分配+指针读取、资源回收。
当然了,你如果确定你的单位已经有一个自定义值了,你可以直接使用。
function Unit_id takes unit u returns integer
local integer i=GetUnitUserData(u)
if i==0 then
    set i=Unit_maxN
    if i<8191 then
        set Unit_maxN=i+1
        if Unit_data!=0 then
            set i=Unit_data
        endif
        call SetUnitUserData(u,i)
        return i
    endif
    return -1
endif
return i
endfunction

假设下面这个函数是在单位死亡触发事件后调用,则你应当注意地图上是否有复活、尸体复活等技能,并且单位是英雄的话则不需要调用,等等。
function Unit_des takes unit u returns nothing
local integer n
local integer id=GetUnitUserData(u)
if id!=0 then
    set n=Unit_maxN-1
    if n>=1 then
        set Unit_data[n]=id
        set Unit_maxN=n
    endif
endif
endfunction[/codes]
由于有了GetUnitUserData和SetUnitUserData两个函数,所以上面的系统依然是简单而高效的,因此它同样适用于物品。

再然后呢,你的地图上有大量的动态触发,你想将大量的单位或者数据绑定到这个动态的触发上面;你会随时销毁一个触发,但是触发的触发条件你却获取不到,这怎么办?trigger不同于计时器的一点是它的重复利用的可能性不大,你无法使用雷同于计时器的减法,而且trigger不能设置自定义值,你也无法使用单位的自定义值的方法了。我觉得这时你应该使用缓存,就如上面最初的DataSystem的模样,现在我给出一个参考代码。
[codes=jass]⑤
globals
gamecache RGC=InitGameCache("DataSystem")
integer Trigger_maxN=1
integer array Trigger_data
endglobals

↓两个函数依次为资源分配+指针读取、资源回收。
function Trigger_id takes trigger t returns integer
local string s=H2S(t)
local integer i=GetStoredInteger(RGC,"trigger",s)
if i==0 then
    set i=Trigger_maxN
    if i<8191 then
        set Trigger_maxN=i+1
        if Trigger_data!=0 then
            set i=Trigger_data
        endif
        call StoreInteger(RGC,"trigger",s,i)
        return i
    endif
    return -1
endif
return i
endfunction

function Trigger_des takes trigger t returns nothing
local integer n
local string s=H2S(t)
local integer id=GetStoredInteger(RGC,"trigger",s)
if id!=0 then
    set n=Trigger_maxN-1
    if n>=1 then
        set Trigger_data[n]=id
        set Trigger_maxN=n
    endif
    call FlushStoredInteger(RGC,"trigger",s)
endif
endfunction[/codes]
好吧,大家会发现⑤和④是雷同的,我只能解释说因为它们都是DataSystem。
于是,除了计时器、单位、物品之外的所有的handle类型的变量都有了解决办法了,你可能会感到高兴,因为DataSystem能够解决所有的问题,但是我想,大部分人会很沮丧,因为我们看到了TimerDataSystem到底走了多远的路,它高效而简单,并且脱离了缓存,但是DataSystem在推广到其他的方面时又被迫回到了最初的方法,当然,我并不是说最初的方法不好,可是我们真的不能找到一个通用并且便捷的方法来使用数组吗?

------------------------     二(1)------------------------------------------------
让我们的思路从②开始,在这个代码里面我们将计时器的handle值减去head而获得了一个位于0-8191的整数,但是正是因为使用了减法,于是这个handle值是不能无限制的增长的,但是好在一个地图中同时运行的计时器不会大于8191,所以我们在地图初始化时就创建了足够的计时器等着我们去使用,根本不需要担心它们的差值会超过8191。可是这个方法不适用于trigger或者其他的handle元素,那么我们为何不找出一个方法,使得任意时刻创建的handle都对应一个小于8191的整数呢。最简单的方法如下:
[codes=jass]⑥Ⅰ
function Handle_id takes handle h returns integer
local integer i=H2I(h)
return i-i/8191*8191//取余
endfunction[/codes]
好吧,现在我们有了一个小于8191的整数了,但是我们很难保证这个整数和另个handle得到的整数是不相等的。嗯,不能应用于实际的方法就不能称之为方法,所以我们得改进一下。
[codes=jass]⑥Ⅱ
globals
integer array Handle_data
endglobals

↓三个函数依次为资源分配、指针读取、资源回收。
function Handle_id takes handle h returns integer
local integer i=H2I(h)
set i=i-i/8191*8191
loop
    exitwhen Handle_data==0
    set i=i+1
    if i>=8191 then
        set i=i-8191
    endif
endloop
set Handle_data=H2I(h)
return i
endfunction

function Handle_get takes handle h returns integer
local integer i=H2I(h)
local integer n=i-i/8191*8191
loop
    exitwhen Handle_data[n]==i
    set n=n+1
    if n>=8191 then
        set n=n-8191
    endif
endloop
return n
endfunction

function Handle_des takes integer n returns nothing
set Handle_data[n]=0
endfunction[/codes]
我想,大家已经明白了,⑥Ⅱ使用的是Hash表的方法,但是在比较⑥Ⅱ和DataSystem之间的区别和优劣之前我们首先要做的就是完善前者,第一,我们发现它在资源分配和指针读取时经过了相同的步骤,因此我们可以合并这两个函数,第二,循环的语句并不好,当我们发现参数handle对应的整数被占用的时候,我们所做的是将这个整数加一,这很容易造成大量的整数堆积尤其是在魔兽中这些handle值是连续的情况下。修改后的代码如下:
[codes=jass]⑥Ⅲ
globals
integer array hashi
endglobals
function hash takes integer I,handle H,boolean b returns integer
local integer ha=I-I/8191*8191
local integer hb=I-I/8179*8179+1
local integer n=0
local integer val
if(b)then
      set val=0
else
      set val=I
endif
loop
      exitwhen(hashi[ha]==val)or(n>499)
      set ha=ha+hb
      set n=n+1
      if(ha>=8191)then
            set ha=ha-8191
      endif
endloop
if(n>499)then
      return -1
else
      if(b)then
            set hashi[ha]=I
      endif
endif
return ha
endfunction[/codes]
⑥Ⅱ和⑥Ⅲ都可以称为Hash法,但是具体来说后者使用的双重Hash法,它相对于前者效率要高了不少。帖子http://forums.wasabistudio.ca/viewtopic.php?f=56&t=22426中讨论了这个方法的效率,但是目前来看,情况有所不同,我先将代码贴出来↓
[codes=jass]⑥Ⅳ(这是我刚开始的拙作,也正是帖子中所讨论的)
globals
constant integer Ha=8191
constant integer Hb=1987
integer I
handle H
integer array Hi
endglobals
function Hash takes integer I,handle H,boolean b returns integer
local integer ha=I-I/Ha*Ha
local integer hb=(I/Hb+1)*Hb-I
local integer n=0
loop
    exitwhen (b and Hi[ha]==0)or(not b and Hi[ha]==I)or(n>Ha)
    set ha=ha+hb
    if ha>=Ha then
        set ha=ha-Ha
    endif
    set n=n+1
endloop
if b then
    set Hi[ha]=I
endif
return ha
endfunction[/codes]
可以说⑥Ⅲ和⑥Ⅳ的差别还是蛮大的,Weberkkk认为Hash函数循环跑的次数越多,就显示出Hash方法的效率越高,确实是这样的,同为Hash方法,循环跑的越多,说明它的L值越小(关于L值的相关资料可以查看 zyl910的代码执行次数上限研究 http://www.islga.org/bbs/read.php?tid=855),而L小了则证明它的代码相对简洁一些,但是却不是全部,效率高不仅要保证L值小,还要保证要在最小的循环次数内找到存储地址。

影响这个效率的因素有:
1,Hb的取值,它必须小于Ha(8191),但是要尽量大,actboy168说要Ha-2就好了,嗯,我取了个最接近8191的质数8179,Hmmm....怎样都行啦。
2,hb的计算式,我之前使用了(I/Hb+1)*Hb-I,而事实证明最好的是I-I/Hb*Hb+1。
满足以上两点可以使得函数在循环里面少跑几圈。
3,exitwhen 后面的判断式,循环里面的代码差别最大的就是它了,简洁的判断式可以减少L值。

我之前经过了测试,⑥Ⅲ中
1,循环可以跑的次数至少在8200以上,也就是完全可以历遍数组的所有地址
2,hashi数组占用在从0到8000后,循环跑的次数的平均数小于3.5,而从0-4000,这个平均数远远小于2.0
我觉得我现在可以认为Hash方法算是高效的了,那么现在我们来比较下⑥Ⅲ、③和④&⑤。

------------------------     二(2)------------------------------------------------

③和④&⑤代表了DataSystem应用中的两个方面
1,它们获取指针的方法稍有不同,但是都是高效的(⑤使用了缓存,但是代码很简单;④只调用了一个函数;③最简单,一个加法就OK了)
2,它们分配指针的时候都使用了链表,这保证了在0-8191个整数中,获取指针都只需要一步。销毁指针的时候,因为需要构造链表,所以只多了几个赋值。
3,③不同于④&⑤的是,③可以使用的前提是需要在初始化的时候创建足够量的计时器,但是我认为这不能完全算是缺点,因为它虽然在初期占用了较大的内存,但是却免去了在游戏过程中反复创建和销毁计时器,保证了游戏的流畅度,而且获得了DataSystem中获取指针最快的速度,应当算是利弊参半。

也就是DataSystem的特点是
1,获取指针简单高效
2,分配与销毁指针也同样高效
3,它在计时器、单位、物品之外的handle元素的应用依然得依靠缓存。

⑥Ⅲ是我现在在使用的Hash方法
1,它获取和分配指针的效率是相同的,因为经过了相同的步骤,在存储量小于4000时,可以算是高效的,但是低于DataSystem
2,它销毁指针很简单,就一步,赋值为0就可以了。
3,它是适用范围高于DataSystem,所有的handle元素都可以使用这个方法

在此我得指出,我不同意Weberkkk对的DataSystem与Hash方法回收效率的评价,因为这两个方法都不能进行自动排泄,回收效率的高低取决于使用者的代码。

DataSystem与Hash并不冲突,你可以在地图中同时使用它们,在计时器、单位、物品上绑定数据时你可以使用DataSystem,而在其他的方面使用Hash,或者使用另外的方法。总之它们都是高效的,我们需要做的就是选取最适合我们要求的方法来编写代码。嗯,这就算是我这篇东西的结论吧。

谢谢大家可以看到这里,如果你通过这个帖子得到了启发,我希望你可以在编图时用到它们。如果你发现了错误或者发现了更好的方法,请跟帖讨论(尤其是Vjass的Struct,本人完全不了解)。如果你想转载,请注明原作者cccty1l,但是更不能舍去了上面的所有的链接,因为正是有了前辈们的努力,我们才能使用更好的方法来完善我们的地图!

评分

参与人数 1威望 +20 收起 理由
kook + 20 蘑菇GJ!看来得找个时间好 ..

查看全部评分

 楼主| 发表于 2009-2-16 21:03:09 | 显示全部楼层
在wow8看到 aeris提到了Hash法,于是发帖和他讨论了下,收获很大,今天早上重新写了另外一个Hash方法,用拉链法来处理地址冲突,在aeris的提示下完成。

具体可以查看帖子http://bbs.wow8.org/thread-87523-1-1.html

aeris那里有vJ版的哈希法,喜欢vJ的同学可以去上面的帖子查看,嗯。

-------------------修改的分隔线------------------------------
代码更美观了,合并为两个函数;将一些繁重的工作交与hashfree处理,因为hashget的调用次数应当更高;做了Debug处理,去除了代码中地址销毁可能出现的Bug。
相对来说目前不需要较大的改变了,拉链法比起再哈希还是有不少的优点的。
1,引用 aeris的话“当哈希表中数据多的时候,handle连续增加时,如果使用开放定址法,效率会有比较严重的下降(引用者注:这个数大概为8191/2),而分离链接法则基本不受影响
比如handle从0依次增加到8000,分离链接法依然会很快”
当然,快是很快,但是随着拉链的增长,效率依然会下降的。
2,拉链法的纠错能力比起再哈希有了质的提高,具体来说当索引一个未存储的句柄时,拉链法会自动分配一个指针,而不是想后者一样疯跑而找不到。
3,代码中实现的拉链法是模拟的,因为根据要求:在拉链法中,装填因子α可以大于1,但一般均取α≤1(设m和n分别表示表长和表中填人的结点数,则将α=n/m定义为散列表的装填因子)。可是在代码中,就是不考虑效率的因素,α依然不能大于1。除此之外,效率应该没有影响。
==========再次修改的分隔线=================
经过zxcf的提醒,再次修改了代码,节省了一个数组。3楼会付注解。

2009-3-2 其实之前在wow8已经更新了的,这里给忘掉了...其实只修改了一点点,调用和使用方法大家感兴趣的话自己研究吧,下面的注解我就不重新编辑了。
原理很简单,就是在Jass不支持二维数组的情况下模拟Hash的拉链法。嗯。

一个简陋的图....

一个简陋的图....

[codes=jass]globals
integer I
handle H
integer array Ha
integer maxN=1
integer Hnf=0
integer array Hb1
integer array Hb2
integer array Hc
endglobals

function hashget takes integer I,handle H,boolean b returns integer
local integer n=I-I/8191*8191
local integer x=Ha[n]
local integer y=x
if x!=0 then
    loop
        if Hc[x]==I then
            return x
        endif
        set x=Hb2[x]
        exitwhen x==0
    endloop
endif
if b then
    set x=Hnf
    if x!=0 then
        set Hnf=Hb2[x]
    else
        set x=maxN
        if x>8191 then
            return 0
        endif
        set maxN=x+1
    endif
    if y!=0 then
        set Hb1[y]=x
    endif
    set Hb2[x]=y
    set Ha[n]=x
    set Hc[x]=I
endif
return x
endfunction

function hashfree takes integer m returns nothing
local integer x=Hb1[m]
local integer y=Hb2[m]
local integer n
if x!=0 then
    set Hb1[m]=0
    set Hb2[x]=y
else
    set n=Hc[m]
    if n==0 then
        return
    endif
    set n=n-n/8191*8191
    set Ha[n]=y
endif
if y!=0 then
    set Hb1[y]=x
endif
set Hc[m]=0
set Hb2[m]=Hnf
set Hnf=m
endfunction[/codes]
回复 支持 反对

使用道具 举报

发表于 2009-2-16 23:13:07 | 显示全部楼层
每次看你们写数据结构就忍不住进来想学学 每次看到一半就一片茫然
555 我数学不怎么滴 学面向对象语言也不教啥算法之类东东 大家又都不喜欢进行详解
看得 唉!~~
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-2-16 23:24:12 | 显示全部楼层
嗯,这楼修改了,现在讨论下vJ的struct吧,参考资料查看Hke的http://www.islga.org/bbs/read.php?tid=18895
我现在把Hke帖子里面的代码全复制过来了。

[codes=jass]struct hkeTri
      trigger tri
      triggercondition cond
endstruct[/codes]
转化为Jass代码就成了下面的了(注释是Hke的)
[codes=jass]globals
constant integer si__hkeTri=1//干啥的捏...
integer si__hkeTri_F=0//最后一次的清除东东
integer si__hkeTri_I=0//引索
integer array si__hkeTri_V//储存指针
//下面两个就不用说了吧
//我们定义的东东
//嗯 看到了吧 其实是数组 这也是struct不能有数组变量的原因 JASS不支持多维数组嘛
trigger array s__hkeTri_tri
triggercondition array s__hkeTri_cond
endglobals

//分配 hkeTri.create()
function s__hkeTri__allocate takes nothing returns integer
local integer this=si__hkeTri_F//把新指针设置成最后清楚的引索
         if (this!=0) then //上次清除的引索不为0(就是清除过)
                  set si__hkeTri_F=si__hkeTri_V[this]
//最后清楚的东西设置成这个引索 等下能找到避免浪费空间
         else//为0 就是说之前没有空的 分配个新的
                  set si__hkeTri_I=si__hkeTri_I+1 //设置成这个引索然后总数+1
                  set this=si__hkeTri_I
         endif
         if (this>8190) then //超过数组最大数量则失败
                  return 0
         endif

         set si__hkeTri_V[this]=-1 //标记
return this
endfunction

//销毁 hkeTri.destroy()
function s__hkeTri_destroy takes integer this returns nothing
         if this==null then//空的就不清理了
                  return
         elseif (si__hkeTri_V[this]!=-1) then//链表前端没有指针
                  return
         endif
         set si__hkeTri_V[this]=si__hkeTri_F//设置新的指针
         set si__hkeTri_F=this//设置新清除引索
endfunction[/codes]

我们现在看Jass代码中的全局变量,si__hkeTri就不说了;trigger array s__hkeTri_tri和triggercondition array s__hkeTri_cond就是之前struct里面的trigger tri和triggercondition cond了,它们在获取了vJ分配的指针之后用于存储;剩下了一个数组和两个变量就是用于vJ分配指针了。

我第一次看这个代码最后确实是刮出来了一个“看完迷糊奖”...不过不怕,现在已经懂了,但是要我说的话还是不好说,嗯,我就用举例来分析吧。

首先,我们调用函数s__hkeTri__allocate五次。让我们看看变量和数组都发生了什么变化。

si__hkeTri_V的下脚标1
2
3
4
5
...

-1
-1
-1
-1
-1
0

[align=justify]si__hkeTri_I=0→1→2→3→4→5
si__hkeTri_F=0→0→0→0→0→0
返回的this=1,2,3,4,5

现在,我们调用函数s__hkeTri_destroy,传参3。

si__hkeTri_V的下脚标1
2
3
4
5
...

-1
-1
0
-1
-1
0

[align=justify]si__hkeTri_I=5
si__hkeTri_F=3
没返回this

然后,再调用函数s__hkeTri__allocate两次。

si__hkeTri_V的下脚标1
2
3
4
5
6
...

-1
-1
-1
-1
-1
-1
0

[align=justify]si__hkeTri_I=5→5→6
si__hkeTri_F=3→0→0
返回的this=3,6

接下来,我们再调用函数s__hkeTri_destroy两次,分别传参2,4。

si__hkeTri_V的下脚标1
2
3
4
5
6
...

-1
0
-1
2
-1
-1
0

[align=justify]si__hkeTri_I=6→6→6
si__hkeTri_F=0→2→4
没返回this

然后,我们最后调用函数s__hkeTri__allocate三次。

si__hkeTri_V的下脚标1
2
3
4
5
6
7
...

-1
-1
-1
-1
-1
-1
-1
0

[align=justify]si__hkeTri_I=6→6→6→7
si__hkeTri_F=4→2→0→0
返回的this=4,2,7

当然,上面列出的只是结果,具体过程和其中的vJ纠错的原理我没有列出。也许上面的例子是多余的,但至少我是通过这个方法理解了struct的,它的特点就是最后被销毁的指针会被最先使用。然后大家看我的拉链Hash表的代码,它就使用了struct的方法来分配新的指针。

[codes=jass]globals
//这两个依然不解释
integer I
handle H
//这个用于记录拉链的起点
integer array Ha
//下面4个东西用途是节点的分配以及删除用
integer maxN=1
integer Hnf=0
integer array Hb1
integer array Hb2
//存储句柄,用于指针的提取和句柄的比对
integer array Hc
endglobals

//调用此函数可以获取一个与上传句柄相关的唯一指针,用于数组的数据存取
function hashget takes integer I,handle H returns integer
//将句柄的值哈希得到一个整数n
local integer n=I-I/8191*8191
local integer x=Ha[n]
local integer y=x
//判断n是否指向一个拉链的起点
if x!=0 then
    //是!进入循环
    loop
        //判断该句柄是否已经有了对应的指针
        if Hc[x]==I then
            //是!返回该指针x
            return x
        endif
        //否!通过数组Hb2指向下一个节点
        set x=Hb2[x]
        //是拉链的末尾则跳出
        exitwhen x==0
    endloop
endif
//下面的10行代码就应用了struct的方法,具体不解释了
set x=Hnf
if x!=0 then
    set Hnf=Hb2[x]
else
    set x=maxN
    if x>8191 then
    return 0
    endif
    set maxN=x+1
endif
//用于补足双链表,同时销毁Hb2之前的记录
if y!=0 then
    set Hb1[y]=x
endif
set Hb2[x]=y
//将n指向拉链的起点
set Ha[n]=x
//存储句柄
set Hc[x]=I
//返回指针x
return x
endfunction

function hashfree takes integer m returns nothing
//读取节点m的前一个与后一个节点
local integer x=Hb1[m]
local integer y=Hb2[m]
local integer n
//判断节点m是否为拉链的起点
if x!=0 then
    //否!则销毁节点m存储的前一节点数据,同时补足双链表
    set Hb1[m]=0
    set Hb2[x]=y
else
    //是!则获取m存储的句柄
    set n=Hc[m]
    //判断是否存储了句柄
    if n==0 then
        //否!错误,跳出
        return
    endif
    set n=n-n/8191*8191
    //将n指向新的起点
    set Ha[n]=y
endif
//补足双链表
if y!=0 then
    set Hb1[y]=x
endif
//销毁节点m存储的句柄,主要用于上面的纠错
set Hc[m]=0
//下面的代码就应用了struct的方法,具体不解释了
set Hb2[m]=Hnf
set Hnf=m
endfunction[/codes]

这个拉链Hash法我认为是优于双重Hash法的,是在aeris和zxcf的提示下完成的。
它的作用就是当你想用数组来记录绑定于一个句柄的数据的时候为你提供一个可以使用而且不冲突的下脚标。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-2-19 02:23:48 | 显示全部楼层
呵呵,自从我从Ga开始发帖起就一直是Hash.Hash的,大家可能都烦了吧,呵呵。
看看我ID的注册时间,我接触We到现在已经有一年的时间了,我在Ga学到了很多东西,但是真正的自己的心得也就是上面的那点东西了吧,现在全发出来了,也算是毫无保留了吧,呵呵。
嗯,怎么说呢,很喜欢Ga,也很喜欢编图,但是现在我有更重要的事情去追求了,有可能的话,若干年后,http://www.scumedit.cn见吧,大家。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-2-19 02:26:42 | 显示全部楼层
嗯,我华丽的三连喽,这可是百贴留念哦。
希望大家再见到我时,还记得我这个新手。

再见了,大家!

再见了,大家!
回复 支持 反对

使用道具 举报

发表于 2009-2-19 02:29:34 | 显示全部楼层
lz要离开了么………………?
常来看看哦~~

分别,这个是我最讨厌的事情啊啊………………………………
为什么在GA就碰到了那么多次呢………………………………
回复 支持 反对

使用道具 举报

发表于 2009-2-19 13:50:01 | 显示全部楼层
很有收获~感谢LZ的无私奉献~~~~
LZ走好~~希望以后还能看见你的身影~
回复 支持 反对

使用道具 举报

发表于 2009-2-19 15:18:39 | 显示全部楼层
lz开学了?

还是忙事业了?
~~

祝一路顺风``
回复 支持 反对

使用道具 举报

发表于 2009-2-19 17:33:35 | 显示全部楼层
希望LZ多多回来
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2019-10-15 11:58 , Processed in 0.344143 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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