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

[cjcat2266 (CJ Cat)]

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
推 cowbaying: 碰撞問題在高速計算的應用程式比較容易遇到
→ cowbaying: 資料低於1億筆(我推測的)的情下應該不需要擔心  XD
→ cjcat2266: 我論所有遊戲公司其實都沒有實作解決碰撞 :/
→ cjcat2266: SID資料庫寫好了，下一步是VS debugger plugin
→ pttworld: 記憶體載入，對於每一句就會有SID加本文。
→ pttworld: 另外請益那一種類型的遊戲需要字串比較。
→ cjcat2266: 素材存取就會去比較key了呀
→ cjcat2266: 還是你是指strcmp這種lexicographical比較?
→ cjcat2266: 一般只要有字串排序或等值比較就會用到了
→ pttworld: 對的，我指的是兩字串間比較這個。
→ cjcat2266: 就算不做lexicographical排序，等值比較還是用strcmp
→ cjcat2266: 所以基本上只要檢查字串是否相同，就算是在比較了
→ cjcat2266: 這方面SID就比較有效率，因為只是比較整數而已
→ y3k: 這種Resource Key的東西 不是都應該在產生的時候計算重複問題
→ y3k: 嗎?XD
→ cjcat2266: 我們的做法是debug版本產生的時候跟資料庫確認
推 cowbaying: 其實我這幾天發現  OS本身就有一個SID系統
→ cowbaying: 所以這個部分應該是可以直接應用的?
→ cowbaying: 應該不是OS的  我覺得是FILE SYSTEM的
→ manaup: 明明就有uuid讓你用 https://en.wikipedia.org/wiki/uuid
→ cowbaying: 好像就是這個  XDDDD
→ cjcat2266: 就我所知UUID沒有O(n)的string concat功能吧
→ cjcat2266: 這功能蠻重要的，因為遊戲常需要動態生成字串串接的SID
※ 編輯: cjcat2266 (160.33.43.15), 09/09/2016 06:59:32
→ cjcat2266: 然後只要原SID就好，不需要另外保存對應的原始字串
→ cjcat2266: 我不太熟悉一般把字串對應到UUID會怎麼做
→ cjcat2266: 目前找不到類似把字串hash成UUID的討論
→ cjcat2266: 還是說是每遇到一個新字串，就生成一個UUID加到資料庫?
→ cjcat2266: 這樣的話用字串當key去找對應的UUID是O(n*log(n))?
→ cowbaying: 這個要詳加研究一下了  囧
→ cjcat2266: 另外如果真的沒有string->UUID的hash function
→ cjcat2266: 那這樣就做不到build-time constant和switch cases了
→ cjcat2266: 其實可以啦，就是要用個自製preprocessor處理一遍
→ cjcat2266: 不過還是沒辦法像SID macro這樣所見及所得
→ cjcat2266: 總之需求是可以串接字串的compile-time constant雜湊
→ cjcat2266: 若真有string->UUID hash，那也就只是多一個hash選擇
→ cjcat2266: 把我的SID範例裡面的FNV hash改掉而已，其他不變
→ cjcat2266: 啊，看來UUID v4標準說除了版本位元以外，其他隨意
→ cjcat2266: 所以就只要找個122-bit雜湊函式就解決了
→ cjcat2266: 這樣其實就是同一件事情，也不用硬要跟UUID搭關係了...
→ cjcat2266: 自言自語一大串，到頭還是是要有個string->SID hash
→ cjcat2266: 我想也不用刻意把hash結果跟UUID做關聯，豁然開朗 @.@
→ cjcat2266: 啊，UUID v5也就只是把SHA-1切成128bit
→ cjcat2266: 也去除了特殊位元，所以只要個128bit hash就可以了
→ cjcat2266: 這樣跟SID其實是同一件事情嘛...
推 cowbaying: XD