[程式] 字串ID (String ID, SID)

看板GameDesign作者 (CJ Cat)時間7年前 (2016/08/29 08:35), 7年前編輯推噓3(3推 0噓 42→)
留言45則, 5人參與, 最新討論串1/2 (看更多)
String ID (SID)是開發遊戲常用到的工具 主要是當作在遊戲中存取素材(asset look-up)的鑰值(key) 基本上就是把字串用雜湊值取代 最近開始計畫撰寫遊戲程式系列文 對SID的需求迅速演變成一個獨立專案... https://github.com/TheAllenChou/string-id 主要的好處有: - 每個SID使用的記憶體量是固定的(取決於雜湊值的型別) - SID之間的比較是constnat-time - 一般用SID當作存取素材的key比用字串當key有效率 - SID若實作成編譯時期常數，則可以用作switch case，字串則不行 - 動態將SID串接字串生成新的SID是linear-time，且不需要原SID之對應字串 主要的壞處與解決方式: - SID較難除錯，因為其本質是雜湊值 一般的做法是另外做個資料庫，儲存SID與對應字串的對照表 然後再做個debugger外掛，讓watch window顯示對應字串 有了這些應變措施之後，SID除錯起來就跟一般字串沒兩樣 - 因為SID是雜湊值，會有兩個字串產生相同SID的可能性(雜湊碰撞, hash collision) 遇到這種狀況，要嘛額外實作解決雜湊碰撞的機制，要嘛改變其中一個字串 雜湊函示選擇恰當和運氣好的話，雜湊碰撞的機率不高 (公司十年來還沒碰過SID雜湊碰撞，所以一直還沒有實作解決方式XD) 我的SID專案進度是已經有可以實用的SID 但是還在開發除錯用的資料庫和debugger plugin 開始撰寫遊戲程式系列文的預訂日無限推延中... -- Web http://AllenChou.net Twitter http://twitter.com/TheAllenChou LinkedIn http://linkedin.com/in/MingLunChou -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 23.242.26.50 ※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1472430955.A.74E.html
推
08/29 09:31, , 1F
碰撞問題在高速計算的應用程式比較容易遇到
08/29 09:31, 1F
→
08/29 09:31, , 2F
資料低於1億筆(我推測的)的情下應該不需要擔心 XD
08/29 09:31, 2F
→
08/29 10:28, , 3F
我論所有遊戲公司其實都沒有實作解決碰撞 :/
08/29 10:28, 3F
→
08/29 12:32, , 4F
SID資料庫寫好了，下一步是VS debugger plugin
08/29 12:32, 4F
→
08/29 21:45, , 5F
記憶體載入，對於每一句就會有SID加本文。
08/29 21:45, 5F
→
08/29 21:45, , 6F
另外請益那一種類型的遊戲需要字串比較。
08/29 21:45, 6F
→
08/29 23:17, , 7F
素材存取就會去比較key了呀
08/29 23:17, 7F
→
08/29 23:18, , 8F
還是你是指strcmp這種lexicographical比較?
08/29 23:18, 8F
→
08/29 23:19, , 9F
一般只要有字串排序或等值比較就會用到了
08/29 23:19, 9F
→
08/29 23:26, , 10F
對的，我指的是兩字串間比較這個。
08/29 23:26, 10F
→
08/30 02:50, , 11F
就算不做lexicographical排序，等值比較還是用strcmp
08/30 02:50, 11F
→
08/30 02:51, , 12F
所以基本上只要檢查字串是否相同，就算是在比較了
08/30 02:51, 12F
→
08/30 02:51, , 13F
這方面SID就比較有效率，因為只是比較整數而已
08/30 02:51, 13F
→
08/30 07:23, , 14F
這種Resource Key的東西 不是都應該在產生的時候計算重複問題
08/30 07:23, 14F
→
08/30 07:23, , 15F
嗎?XD
08/30 07:23, 15F
→
08/30 08:39, , 16F
我們的做法是debug版本產生的時候跟資料庫確認
08/30 08:39, 16F
推
09/05 13:41, , 17F
其實我這幾天發現 OS本身就有一個SID系統
09/05 13:41, 17F
→
09/05 13:42, , 18F
所以這個部分應該是可以直接應用的?
09/05 13:42, 18F
→
09/05 16:43, , 19F
應該不是OS的 我覺得是FILE SYSTEM的
09/05 16:43, 19F
→
09/08 19:36, , 20F
明明就有uuid讓你用 https://en.wikipedia.org/wiki/uuid
09/08 19:36, 20F
→
09/08 20:53, , 21F
好像就是這個 XDDDD
09/08 20:53, 21F
→
09/09 06:51, , 22F
就我所知UUID沒有O(n)的string concat功能吧
09/09 06:51, 22F
→
09/09 06:52, , 23F
這功能蠻重要的，因為遊戲常需要動態生成字串串接的SID
09/09 06:52, 23F
※ 編輯: cjcat2266 (160.33.43.15), 09/09/2016 06:59:32
→
09/09 07:00, , 24F
然後只要原SID就好，不需要另外保存對應的原始字串
09/09 07:00, 24F
→
09/09 07:07, , 25F
我不太熟悉一般把字串對應到UUID會怎麼做
09/09 07:07, 25F
→
09/09 07:08, , 26F
目前找不到類似把字串hash成UUID的討論
09/09 07:08, 26F
→
09/09 07:09, , 27F
還是說是每遇到一個新字串，就生成一個UUID加到資料庫?
09/09 07:09, 27F
→
09/09 07:10, , 28F
這樣的話用字串當key去找對應的UUID是O(n*log(n))?
09/09 07:10, 28F
→
09/09 13:42, , 29F
這個要詳加研究一下了 囧
09/09 13:42, 29F
→
09/10 00:04, , 30F
另外如果真的沒有string->UUID的hash function
09/10 00:04, 30F
→
09/10 00:05, , 31F
那這樣就做不到build-time constant和switch cases了
09/10 00:05, 31F
→
09/10 00:06, , 32F
其實可以啦，就是要用個自製preprocessor處理一遍
09/10 00:06, 32F
→
09/10 00:07, , 33F
不過還是沒辦法像SID macro這樣所見及所得
09/10 00:07, 33F
→
09/10 00:10, , 34F
總之需求是可以串接字串的compile-time constant雜湊
09/10 00:10, 34F
→
09/10 00:11, , 35F
若真有string->UUID hash，那也就只是多一個hash選擇
09/10 00:11, 35F
→
09/10 00:11, , 36F
把我的SID範例裡面的FNV hash改掉而已，其他不變
09/10 00:11, 36F
→
09/10 00:20, , 37F
啊，看來UUID v4標準說除了版本位元以外，其他隨意
09/10 00:20, 37F
→
09/10 00:21, , 38F
所以就只要找個122-bit雜湊函式就解決了
09/10 00:21, 38F
→
09/10 00:22, , 39F
這樣其實就是同一件事情，也不用硬要跟UUID搭關係了...
09/10 00:22, 39F
→
09/10 00:25, , 40F
自言自語一大串，到頭還是是要有個string->SID hash
09/10 00:25, 40F
→
09/10 00:27, , 41F
我想也不用刻意把hash結果跟UUID做關聯，豁然開朗 @.@
09/10 00:27, 41F
→
09/10 00:42, , 42F
啊，UUID v5也就只是把SHA-1切成128bit
09/10 00:42, 42F
→
09/10 00:43, , 43F
也去除了特殊位元，所以只要個128bit hash就可以了
09/10 00:43, 43F
→
09/10 00:43, , 44F
這樣跟SID其實是同一件事情嘛...
09/10 00:43, 44F
推
09/10 02:26, , 45F
XD
09/10 02:26, 45F
‣ 更多 cjcat2266 的文章
文章代碼(AID): #1NmuDhTE (GameDesign)
‣ 更多 cjcat2266 的文章
文章代碼(AID): #1NmuDhTE (GameDesign)