|
|
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 才能繼續執行。
[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,但是更不能舍去了上面的所有的链接，因为正是有了前辈们的努力，我们才能使用更好的方法来完善我们的地图！ |
评分
-
查看全部评分
|
窥视卡
雷达卡
发表于 2009-2-14 18:56:26
提升卡
置顶卡
沉默卡
喧嚣卡
±????¨
千斤顶
???í?¨
发表于 2009-2-19 02:29:34
