[JASS]HASH+Struct 數據系統,煙火 V006

各類的進階專題研究、WE Bug討論等。

版主: crassorz, tv580025

[JASS]HASH+Struct 數據系統,煙火 V006

文章Weberkkk » 2009年05月02日 6:06 pm

類似這樣的東西早就有人做過了,說明也解釋過了,但我仍不厭其煩的再介紹一次
HASH+Struct 雙鍊、多鍊系統,有一條主鍊與8191條小鍊

主鍊負責資源的分配,就跟普通的Struct沒有差別
小鍊負責搜尋與綁定,當I-I*8191/8191的HASH值產生衝突的時候
會有一個以上的資料落在同一條小鍊上,這時候循著小鍊做「線的遍歷」就可以快速的找到資料
而不用像其他HASH採用亂槍打鳥的方式去搜尋

這次發表的函數分成三個部分

初始化、普通Struct、雙鍊Struct

可以直接綁定Timer、Trigger,模擬一般HASH的功能
而這系統也支持使用String綁定數據,因此完完全全的取代掉GC的地位

唯一的缺點是8191上限問題,但要模擬8191以上的陣列並不困難
假如有需要也可以簡單的突破這個限制,所以整體來說沒有任何限制



代碼: 選擇全部
//===========================================================================
//                           Return Bug
//===========================================================================
function H2I takes handle h returns integer
      return h
      return 0
endfunction

function H2S takes handle h returns string
      return I2S(H2I(h))
endfunction

function RBS2I takes string s returns integer
      return s
      return 0
endfunction



//===========================================================================
//                           K DataSystem Int
//===========================================================================

function K_DataSystem_Int1 takes nothing returns nothing
local integer A = 4000
      loop
            exitwhen A > 8191
            set udg__TimK[A] = CreateTimer()
            set A = A+1
      endloop
endfunction

function K_DataSystem_Int takes nothing returns nothing
local integer A = 1
local trigger T = CreateTrigger()
local triggeraction TA = TriggerAddAction(T, function K_DataSystem_Int1)
      set udg__TimK[0] = CreateTimer()
      set udg_K_Hash_Start = H2I(udg__TimK[0])
      set udg_K_Struct_Now = 0
      set udg_K_Struct_Max = 0
      set udg__Int1[0] = 0
      set udg__Int0[99] = 0
      loop
            exitwhen A >= 4000
            set udg__TimK[A] = CreateTimer()
            set A = A+1
      endloop
      call TriggerExecute(T)
      call TriggerRemoveAction(T,TA)
      call DestroyTrigger(T)
      set T = null
      set TA = null
endfunction




這沒甚麼好講的,就是把該歸零的數據歸零,確保不會發生問題
然後連續創造8191個Timer用來做最高效率的TimerHASH

TimerHASH是效率最高的HASH,只綁定Timer的時候,我們沒有理由不用它



代碼: 選擇全部
//===========================================================================
//                           TimerHASH+Struct 適用於需要 Timer 的函數
//===========================================================================
// 用最高效率的 TimerHASH 來跑所有需要 Timer 的函數

function GetK takes nothing returns integer
local integer K = udg_K_Struct_Now //線頭
      if K != 0 then   //有經過回收則
            set udg_K_Struct_Now = udg_K_Struct_ReUse[K] //取第二個為線頭
      else   //否則
            set udg_K_Struct_Max = udg_K_Struct_Max + 1
            set K = udg_K_Struct_Max //取最大值使用
      endif
      //不考慮超過8191的情況,因此省略原本Struct之除錯
      return K
endfunction

function LoadK takes nothing returns integer
      return H2I(GetExpiredTimer()) - udg_K_Hash_Start
endfunction

function EndK takes integer K returns nothing
      //不考慮誤用的情況,因此省略原本Struct之除錯
      call PauseTimer(udg__TimK[K])
      set udg_K_Struct_ReUse[K] = udg_K_Struct_Now      //原線頭降為第二個
      set udg_K_Struct_Now = K   //保存新線頭
endfunction


傳說中的TimerHASH
利用Timer的H2I減去初始化計算出的Timer[0]的H2I,獲得陣列的編號,是目前效率最高的HASH
但缺點是只針對Timer綁定,而且只能用初始化創造的Timer跑TimerStart才有效(也就是針對udg__TimK[K])



代碼: 選擇全部
//===========================================================================
//                           HASH+Struct
//===========================================================================
// 用多鏈狀結構 Struct,用線的遍歷搜索資料,通常線的長度只有1

function GetKM takes integer I returns integer
local integer Hash=I-I/8191*8191
local integer K = GetK() //直接抓Struct的值
      if udg_K_Struct_Mult_Now[Hash] != 0 then //小鍊的線頭不為零,表示之前已經被用過了
            set udg_K_Struct_Mult_ReNow[udg_K_Struct_Mult_Now[Hash]] = K     //形成每個Hash值的小鍊,由後向前接
      endif
      set udg_K_Struct_Mult_ReUse[K] = udg_K_Struct_Mult_Now[Hash]     //形成每個Hash值的小鍊,由前向後接
      set udg_K_Struct_Mult_Now[Hash] = K     //形成每個Hash值的小鍊
      set udg_K_Struct_Mult_H2I[K] = I
      set udg_K_Struct_Mult_Hash[K] = Hash
      return K
endfunction

function LoadKM takes integer I returns integer
local integer Hash=I-I/8191*8191
local integer K = udg_K_Struct_Mult_Now[Hash] //抓到Hash值的小鍊線頭
      loop
            exitwhen udg_K_Struct_Mult_H2I[K] == I or K == 0 // 防錯 V006
            set K = udg_K_Struct_Mult_ReUse[K]
      endloop //鍊的遍歷,逐一搜尋小鍊的值去比對
      return K     //若未註冊則 return 0
endfunction

function EndKM takes integer K returns nothing
local integer Hash=udg_K_Struct_Mult_Hash[K]
local integer TempK=udg_K_Struct_Mult_Now[Hash] //抓到Hash值的小鍊線頭
      if TempK != K then      //如果小鍊的結構在一段以上,就重新執行雙向連接,將這段從鏈中消去
            set udg_K_Struct_Mult_ReUse[udg_K_Struct_Mult_ReNow[K]] = udg_K_Struct_Mult_ReUse[K]
            set udg_K_Struct_Mult_ReNow[udg_K_Struct_Mult_ReUse[K]] = udg_K_Struct_Mult_ReNow[K]
      else
            set udg_K_Struct_Mult_Now[Hash] = udg_K_Struct_Mult_ReUse[K] //如果小鍊是線頭,就把線頭連接到下一節
      endif
      call EndK(K)
endfunction


雙鍊Strict,也就是泛用型的HASH
原理開頭講過了,詳細思路不容易解釋,請自行研究

功能為傳入任意integer給GetKM即可綁定資料並獲得一個K用於DataSystem之應用
下次只要傳入相同的integer給LoadKM即可拿回這個K

EndKM則是回收用



代碼: 選擇全部
//===========================================================================
//                           Handle 一對一綁定資料,適用於 Trigger
//===========================================================================
// H2I 值在一百萬以上,S2I 值從0開始,因此排除衝突的可能
// 在衝突前魔獸已經LAG到掛掉了

function GetKH takes handle H returns integer
      return GetKM(H2I(H))
endfunction

function LoadKH takes handle H returns integer
      return LoadKM(H2I(H))
endfunction


//===========================================================================
//                           String 用來綁定一個 Hanedle 多個資料,適用於 Unit
//===========================================================================
// H2I 值在一百萬以上,S2I 值從0開始,因此排除衝突的可能
// 在衝突前魔獸已經LAG到掛掉了

function GetKS takes string S returns integer
      return GetKM(RBS2I(S))
endfunction

function LoadKS takes string S returns integer
      return LoadKM(RBS2I(S))
endfunction




很簡單,就是分別針對Handle跟String製作對GetKM的接口

資源回收就直接用EndKM了,要我做貌似BJ的雞肋函數我做不到...




底下附上演示地圖,漂亮的煙花V006版,作者就是我,千萬別懷疑... XD
◆◆◆◆◆ 《 免費線上簽約服務,你也可以改變世界 》 ◆◆◆◆◆
 
「你知道打一場三國,會消耗多少能量嗎? 燃燒的能量,少於栽培的能量。」
「宇宙能量在不斷減少,所以WB發明了將玩家感情轉換為宇宙能量的技術。」
「主堡被推掉的瞬間,因戰敗爆發的各種情感,就是WB想蒐集的宇宙能量。」
「默契越好的玩家,釋放的能量越大,最厲害的團隊,會爆發出最強的能量。」
「XD化程度與能量蒐集率有關,WB理所當然的進行三國XD改造與實驗。」
「每次RE都會造成平行世界能量增幅,再過不久也許能培育出三國之神吧。」
頭像
Weberkkk
騎士
騎士
 
文章: 241
註冊時間: 2008年04月14日 12:06 am

Re: [JASS]HASH+Struct 數據系統,煙火 V006

文章HeartStation » 2009年05月02日 6:13 pm

又有新的煙火秀了!即使我看不懂寫法,不過做這個還真的是很厲害呢0.0
小箱子比起大箱子裝著更多的幸福。

知足才能常樂。


http://www.wretch.cc/blog/despairLrA
頭像
HeartStation
士兵
士兵
 
文章: 108
註冊時間: 2008年04月09日 10:36 am
來自: 黑洞

Re: [JASS]HASH+Struct 數據系統,煙火 V006

文章iceman6 » 2009年05月07日 11:21 pm

看不懂寫法

恩,完全看不懂+1.....


前一陣子我在測HASHGC的執行效率比上GC
測多結構附著,效率約100:71(正規化過)
不過有時71浮動範為60~80,不太穩定....初步估計可能是母群體不夠大,當時loop只設定2000個
測試環境也不太穩定,所以還努力測中
有時間的話順便也測看看這個 :lol:
徵人幫作
地圖:燃燒古戰場
說明:無論你是對觸發、模組、宣傳、編故事、又或是平衡...等等方面有長材的都可以來
快來發揮你的專長吧
連絡方式:hexpanace@hotmail.com

回顧
[Script]自訂腳本
[ABC]石牆
[TT]飛彈追跡
[PUI]怪物重生
[SIC]物品調製系統
頭像
iceman6
農民
農民
 
文章: 99
註冊時間: 2007年08月28日 9:49 pm


回到 專題討論區

誰在線上

正在瀏覽這個版面的使用者:沒有註冊會員 和 1 位訪客

cron