作者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/cn.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