能否動(dòng)態(tài)實(shí)現(xiàn)case語(yǔ)句

songtebo

如下代碼速度很快

int foo(int a) {   switch(a)   {     case 1:       return 4;     case 8828042:       return 5;     case 4482232:       return 6;     default:       return 7;   } }

這是影響速度的關(guān)鍵函數(shù)，但問(wèn)題是函數(shù)中的所有數(shù)字在程序運(yùn)行中才能確定。a的值在0~4261478400之間，分支在4~100之間，返回結(jié)果在0~200之間。采用二分查找的方法性能還不達(dá)標(biāo)。

能否實(shí)現(xiàn)動(dòng)態(tài)的CASE語(yǔ)句？

nlylidb

不知道你研究過(guò)switch在編譯時(shí)的優(yōu)化沒(méi)有。這是我簡(jiǎn)單測(cè)試得到的結(jié)果
http://blog.chinaunix.net/u3/94078/showart.php?id=1888387

在這種數(shù)據(jù)跨越度比較大的時(shí)候，gcc編譯時(shí)會(huì)對(duì)case語(yǔ)句的數(shù)據(jù)進(jìn)行自動(dòng)優(yōu)化。
switch在編譯時(shí)會(huì)先獲得case中的各值，然后進(jìn)行排序，如果跨度（最大值與最小值之差與case個(gè)數(shù)比較）不是很大，會(huì)使用造表法（生成跳轉(zhuǎn)表），這種速度是最快的，為O（1），但是空間復(fù)雜度為O（n）
如果跨度比較大，編譯器會(huì)自動(dòng)生成使用二分法優(yōu)化的查找比較模式， 不妨直接使用case然后gcc －S看看匯編碼就知道了，生成的匯編碼與case中數(shù)據(jù)的排序方法無(wú)關(guān)，這時(shí)時(shí)間復(fù)雜度為O(log(n)),空間復(fù)雜度為O(1)。

而if-else嵌套使用需要程序員控制查找方法。最差為O(n)，但是if-else嵌套中的空間復(fù)雜度是一樣的

[ 本帖最后由 nlylidb 于 2009-4-17 10:00 編輯 ]

flyingtime

不知道用std::map<int,int>會(huì)不會(huì)更好一些:wink:

songtebo

試驗(yàn)過(guò)，std::map<int,int>比自己寫(xiě)的二分查找方法速度還慢一點(diǎn)點(diǎn)。

CASE是O(1)。
std::map<int,int>，二分查找方法這些都應(yīng)該是 O(log(n))

action08

這個(gè)優(yōu)化太底層了

假設(shè)數(shù)據(jù)類(lèi)型long是4B空間的，假設(shè)把數(shù)字表示成A-B-C-D(cd=256 *c+d...)（該思想可以直接優(yōu)化成二分查找）

可以先判斷A『最多256個(gè)空間，很快』，然后再判斷B，，，共判斷4次。

思想大概就是有原來(lái)的“一次查找”變成“四次查找”。分析一下業(yè)務(wù)，看看可以這樣做不？)

switch(a && oxff000000)
{
case :...
       switch(a && oxff0000)
               {;//類(lèi)似...}
case :...

}

===
其他方法都很底層，，我也想知道

[ 本帖最后由 action08 于 2009-4-17 09:45 編輯 ]

flyingtime

好像只有case是從0開(kāi)始依次遞增的情況時(shí)間復(fù)雜度才是O(1)吧
我這里找到一個(gè)在C#中關(guān)于對(duì)switch分析的一篇文章：
http://msdn.microsoft.com/zh-cn/downloads/dd310342.aspx
你可以看一下，我認(rèn)為Dictionary<TKey,TValue>類(lèi)似于std::map<key,value>

marxn

為啥不用hashtable

songtebo

原帖由 action08 于 2009-4-17 09:40 發(fā)表
這個(gè)優(yōu)化太底層了

假設(shè)數(shù)據(jù)類(lèi)型long是4B空間的，假設(shè)把數(shù)字表示成A-B-C-D(cd=256 *c+d...)（該思想可以直接優(yōu)化成二分查找）

可以先判斷A『最多256個(gè)空間，很快』，然后再判斷B，，，共判斷4次。

思想 ...

感覺(jué)這個(gè)速度和直接二分法應(yīng)該一致，但增加了代碼復(fù)雜程度。



非常感謝大家！！

swxlion

不太清楚樓主所言“動(dòng)態(tài)”是何意思？如果是if-else的話，通過(guò)函數(shù)的調(diào)用拼接（雖然不夠安全），是可以實(shí)現(xiàn)動(dòng)態(tài)變化的case。但如果用switch的話，我的理解是：switch不論編譯器再怎么優(yōu)化，都是靜態(tài)的。因?yàn)樗�不能再隨運(yùn)行期狀態(tài)而變動(dòng)case的數(shù)目和值。
如果優(yōu)化后造表的話，的確是可以達(dá)到時(shí)間復(fù)雜度為O(1)，但從 nlylidb 給出的資料看來(lái)，這個(gè)O(1)僅存在于連續(xù)值的情況下，如果值不連續(xù)，那就退化為O(log2(n))的二分法。但不論是否退化，case的數(shù)目和條件在編譯后已經(jīng)轉(zhuǎn)為靜態(tài)，無(wú)法動(dòng)態(tài)改變。如果需要?jiǎng)討B(tài)改變的話，用AVL Tree、RB Tree等時(shí)間復(fù)雜度為O(log2(n))的二叉搜索樹(shù)感覺(jué)應(yīng)該是個(gè)不錯(cuò)的選擇，就正如flyingtime 提議的本質(zhì)。但是stl的問(wèn)題就在于為了使用方便而對(duì)運(yùn)行期執(zhí)行效率作了妥協(xié)，所以可能還是自己寫(xiě)一個(gè)，或者使用其他的時(shí)間復(fù)雜度為O(log2(n))的樹(shù)結(jié)構(gòu)來(lái)的好。
另外一個(gè)疑問(wèn)就是，gcc/g++能對(duì)switch-case的連續(xù)值進(jìn)行查表優(yōu)化，但如果換到其他編譯器呢？而且，如果是連續(xù)值，而且連續(xù)值執(zhí)行非常類(lèi)似的操作的話，是否可以用一個(gè)類(lèi)推邏輯替代switch-case、if-else和造表？因?yàn)轭?lèi)推邏輯的時(shí)間復(fù)雜度也是O(1)，而且還可以動(dòng)態(tài)改變需要匹配的條目和數(shù)值。

xinglp

強(qiáng)貼留名，收貨很大