作者iterator (rotareti)
看板C_Sharp
标题Re: [问题] Dictionary的效能请益
时间Mon Oct 29 11:02:24 2012
※ 引述《stu87616 (以光为名)》之铭言：
: 有个专案要做整数对应字串的程序，
: 我原本是很笨的直接写个switch让数字下去跑，
: 後来教授跟我提过可以试试看用Dictionary，
: 我才去查了一下这个结构是怎麽用的
: 写了一个很简单的Dictionary(只取对应的功能)
: Dictionary <int, string> Dic = new Dictionary<int, string>();
: private String Find(int num)
: {
: if (Dic.ContainsKey(num))
: return Dic[num];
: else
: return "Not Found";
: }
: 应该够简单了，只是我用这个结构下去跑我原本的判断式，
: 作用正常，但效能大概低了一倍左右...
: 虽然也只是两毫秒之内的差距而已，
: 不过...因为我一直都是很不喜欢用switch写一长串的人，
: 很期待有个东西可以取代它，结果这个新玩意让我失望了T_T
: 所以，Dictionary的长处就是可以自由增加这点了吗?
: 比对速度上反而还是输给老牌的switch？
: 我应该没有理解错误吧ˊ_>ˋ
上面这个问题, "只讨论速度", 答案其实是没差别, 甚至 switch 会比较快.
这件事可以分成两个角度来看, 第一个是速度,
C# Compiler 在处理 switch case 时, 会自动作最佳化处理,
当遇到数字时, switch 会使用特殊的 switch op code.
(
http://tinyurl.com/8r476eb)
所有的数值会被处理成 jump table, 所以可以直接跳到对应处理的程式片段.
当遇到文字时, 在数量很少的情况下, Compiler 会编译成 if/else 的片段,
在数量更多的时候, Compiler 会私底下帮你建立一个 dictionary,
然後透过该 dictionary 进行状况选择.
(至於透过 Dictionary 与使用大量直接字串比对的速度差异问题,
就不在这边提了, 有兴趣可以 wiki "hash table")
所以, 你不用自己担心这些问题, C# Compiler 会帮你处理掉.
至於第二个角度, 就是程式码的可读性/可维护性,
现在 switch 选项有两三种, 怎麽写? 有十多种, 怎麽写?
有数千种, 又怎麽写?
当未来有需要增加删减项目时, 哪种写法会比较容易维护/比较不容易出错?
除非这个程式有特殊的需求, 不然最好以这个角度去撰写程式会比较好.
再回到你程式本身, 使用 Dictionary 取值时,
可以透过 .TryGetValue( ) 这个 method, 会比透过 Dic.ContainsKey + [] 快.
另外, 这里你需要的是 int -> string 的 mapping,
在 int 数值不是很疏散的情况下,
基本上字串阵列 string[] 就是种最简单又快速的 int -> string dictionary,
所以其实可能透过阵列就能解决你的要求了.
另外, 测试程式码速度时, 最好增加资料量/增加执行次数,
比较平均时间後, 比较不容易受到一些变数的影响.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.23.102