Re: 雙層排序問題

[yoco315 (眠月)]

※ 引述《yauhh (喲)》之銘言：
: 這小事,只要寫個普通的對應程式,把字母對應為順序號碼:
: enum Letter {
:      None = -1,
:      B = 0, R,
:      O, Y,
:      G, L,
:      P, W
: };
: enum Letter charToLetter(char ch) {
:      switch (ch) {
:      default:
:           return None;
:      }
: }
: 雖然寫得很長,但就是 O(1) 程度,並且可以把不連續資料調整為連續資料.
: 然後在任何 sort 的 compare 函式會看到這樣的程式碼:

媽阿，太累了吧 XD

char a[255] ;
a['B'] = 0 ;
a['R'] = 1 ;
a['O'] = 2 ;
a['Y'] = 3 ;
a['G'] = 4 ;
a['L'] = 5 ;
a['P'] = 6 ;
a['W'] = 7 ;

這樣 a[c] 就知道優先順序啦

而且你講的那個 O(1) 也要 compiler 夠聰明才有，不然還是 O(n)

--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈.              　   L. Peter Deutsch

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.160.109.130
推 softwind:switch case ? 應該是還是 O(n)吧?
→ yauhh:沒差啦,反正是小事
→ yauhh:原po只是問怎麼寫,給個方向;但一堆人拼命給越快越好的作法,
→ yauhh:這一點我很不能理解. 先給一個適當的作法不就可以了嗎
→ yoco315:and why did you remark you algo is O(1)   -_-||
→ yoco315:(which actually not...)
→ yoco315:not to mention the solution is complicated O_O
推 Fenikso:寫死在code裡面的switch case就算有1000000項也是O(1)
→ yoco315:It depends on the case value and the compiler.
推 Fenikso:no, 1000000 is a constant
推 softwind:對於寫死的switch是O(1) 我比較有興趣 compiler有說明嗎?
→ softwind:或是哪家的compiler有說明? 有人看過的可以share一下
推 Fenikso:我想講的只是.. n是input size, switch的數量並不會因為
→ Fenikso:input而改變, 所以就算裡面有100000個case也還是constant
→ Fenikso:time
→ Fenikso:這點yauhh講的並沒有錯
→ yoco315:這樣算的話，那我乾脆說所有的 input 都是有限多的..
→ yoco315:對任何一個問題，我都用 code generator 生出 switch 碼
→ yoco315:然後交給 compiler 直接 output 答案就好..
→ yoco315:這種論點無異跟白痴一樣嘛..
→ yoco315:人家現在講的就是 case 的數目跟決策的時間..
→ yoco315:好的 compiler 遇到好的 case 可以做出 O(1) 的跳轉沒錯
→ yoco315:但是 general case 就不是