作者cjcat2266 (CJ Cat)
看板GameDesign
標題[程式] 字串ID (String ID, SID)
時間Mon Aug 29 08:35:49 2016
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://webptt.com/m.aspx?n=bbs/GameDesign/M.1472430955.A.74E.html
1F：推 cowbaying: 碰撞問題在高速計算的應用程式比較容易遇到 08/29 09:31
2F：→ cowbaying: 資料低於1億筆(我推測的)的情下應該不需要擔心 XD 08/29 09:31
3F：→ cjcat2266: 我論所有遊戲公司其實都沒有實作解決碰撞 :/ 08/29 10:28
4F：→ cjcat2266: SID資料庫寫好了，下一步是VS debugger plugin 08/29 12:32
5F：→ pttworld: 記憶體載入，對於每一句就會有SID加本文。 08/29 21:45
6F：→ pttworld: 另外請益那一種類型的遊戲需要字串比較。 08/29 21:45
7F：→ cjcat2266: 素材存取就會去比較key了呀 08/29 23:17
8F：→ cjcat2266: 還是你是指strcmp這種lexicographical比較? 08/29 23:18
9F：→ cjcat2266: 一般只要有字串排序或等值比較就會用到了 08/29 23:19
10F：→ pttworld: 對的，我指的是兩字串間比較這個。 08/29 23:26
11F：→ cjcat2266: 就算不做lexicographical排序，等值比較還是用strcmp 08/30 02:50
12F：→ cjcat2266: 所以基本上只要檢查字串是否相同，就算是在比較了 08/30 02:51
13F：→ cjcat2266: 這方面SID就比較有效率，因為只是比較整數而已 08/30 02:51
14F：→ y3k: 這種Resource Key的東西 不是都應該在產生的時候計算重複問題 08/30 07:23
15F：→ y3k: 嗎?XD 08/30 07:23
16F：→ cjcat2266: 我們的做法是debug版本產生的時候跟資料庫確認 08/30 08:39
17F：推 cowbaying: 其實我這幾天發現 OS本身就有一個SID系統 09/05 13:41
18F：→ cowbaying: 所以這個部分應該是可以直接應用的? 09/05 13:42
19F：→ cowbaying: 應該不是OS的 我覺得是FILE SYSTEM的 09/05 16:43
21F：→ cowbaying: 好像就是這個 XDDDD 09/08 20:53
22F：→ cjcat2266: 就我所知UUID沒有O(n)的string concat功能吧 09/09 06:51
23F：→ cjcat2266: 這功能蠻重要的，因為遊戲常需要動態生成字串串接的SID 09/09 06:52
※ 編輯: cjcat2266 (160.33.43.15), 09/09/2016 06:59:32
24F：→ cjcat2266: 然後只要原SID就好，不需要另外保存對應的原始字串 09/09 07:00
25F：→ cjcat2266: 我不太熟悉一般把字串對應到UUID會怎麼做 09/09 07:07
26F：→ cjcat2266: 目前找不到類似把字串hash成UUID的討論 09/09 07:08
27F：→ cjcat2266: 還是說是每遇到一個新字串，就生成一個UUID加到資料庫? 09/09 07:09
28F：→ cjcat2266: 這樣的話用字串當key去找對應的UUID是O(n*log(n))? 09/09 07:10
29F：→ cowbaying: 這個要詳加研究一下了 囧 09/09 13:42
30F：→ cjcat2266: 另外如果真的沒有string->UUID的hash function 09/10 00:04
31F：→ cjcat2266: 那這樣就做不到build-time constant和switch cases了 09/10 00:05
32F：→ cjcat2266: 其實可以啦，就是要用個自製preprocessor處理一遍 09/10 00:06
33F：→ cjcat2266: 不過還是沒辦法像SID macro這樣所見及所得 09/10 00:07
34F：→ cjcat2266: 總之需求是可以串接字串的compile-time constant雜湊 09/10 00:10
35F：→ cjcat2266: 若真有string->UUID hash，那也就只是多一個hash選擇 09/10 00:11
36F：→ cjcat2266: 把我的SID範例裡面的FNV hash改掉而已，其他不變 09/10 00:11
37F：→ cjcat2266: 啊，看來UUID v4標準說除了版本位元以外，其他隨意 09/10 00:20
38F：→ cjcat2266: 所以就只要找個122-bit雜湊函式就解決了 09/10 00:21
39F：→ cjcat2266: 這樣其實就是同一件事情，也不用硬要跟UUID搭關係了... 09/10 00:22
40F：→ cjcat2266: 自言自語一大串，到頭還是是要有個string->SID hash 09/10 00:25
41F：→ cjcat2266: 我想也不用刻意把hash結果跟UUID做關聯，豁然開朗 @.@ 09/10 00:27
42F：→ cjcat2266: 啊，UUID v5也就只是把SHA-1切成128bit 09/10 00:42
43F：→ cjcat2266: 也去除了特殊位元，所以只要個128bit hash就可以了 09/10 00:43
44F：→ cjcat2266: 這樣跟SID其實是同一件事情嘛... 09/10 00:43
45F：推 cowbaying: XD 09/10 02:26