搜索數組或開關？對於通過替換的密碼

我使用C++中的所有可打印字符進行替換來編碼經典密碼，我想知道哪個更快？在一個數組中搜索（編輯：一個非關聯的，只是像letters[] = {'a', 'b', ...);（線性或二進制）或switch語句？編譯器可以優化開關，不是嗎？也許不同是內存使用？我的選擇是開關，雖然代碼更大，但也許我錯過了一些東西。搜索數組或開關？對於通過替換的密碼

（也許這個問題似乎是主觀的，但我認爲會客觀的原因選擇一種或另一種方式。）

來源

2011-06-04 Tae

爲什麼你需要搜索一個數組？沒有太多的ASCII字符。將替換存儲在一個表中，並且查找由單個數組查找組成。 – sigfpe 2011-06-04 14:34:31

@ user207442我沒有使用關聯數組，因爲我們還沒有在課上研究它們。 – Tae 2011-06-04 20:43:27

確實有一個機會，一個足夠聰明的編譯器可以優化切換爲查找，這比二進制搜索更快。但你可以自己做這種優化，並得到短代碼：

char alphabet[] = { 
    'Z', 'E', 'B', 'R', 'A', 'S', 'C', 'D', 'F', 'G', 'H', 'I', 'J', 
    'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'T', 'U', 'V', 'W', 'X', 'Y' 
}; 
// now you can get the ciphertext for a single uppercase character with: 
alphabet[ch - 'A'];

來源

2011-06-04 14:34:42

I在字母表中輸入[ch - 'A']部分;你能幫我提供一點背景知識嗎？ – Tae 2011-06-04 20:03:58

是的，它和你的角色的ASCII代碼索引的數組基本相同。 A到Z的ASCII碼是連續的，顯然A' - A'是0.所以B' - 'A'是1，一直到'Z' - 'A'都是25.所以這是一種索引數組的方法只包含大寫字母。 – 2011-06-04 20:05:58

哦，對。我忘了提及，我們沒有在課堂上研究關聯數組。 – Tae 2011-06-04 20:34:40

爲什麼你需要搜索？只需要一個由你的ASCII字符索引的128條數組，這基本上就是編譯器用你的開關做的事情（你可以減去32並使用一個96條數組，非printables使用的空間。）

來源

2011-06-04 14:32:10 andrewdski

+1，我寫的完全一樣（： – 2011-06-04 14:36:00

）你有沒有看過爲彙編語句生成的程序集？編譯器不使用數組來實現開關，它們使用偏移跳轉 – 2011-06-04 14:37:37

@Vlad：GCC有時也使用二叉樹 – 2011-06-04 14:43:22

哪一個更快取決於很多因素：編譯器的優化（您必須查看程序集以瞭解它的作用）以及如何設置陣列。

如果性能非常重要，而且兩個解決方案的實現都相當簡單，那麼我會實施它們並在儘可能真實的設置中對它們進行基準測試，以確定哪個解決方案更快。

來源

2011-06-04 14:34:35 rlc

搜索數組或開關？對於通過替換的密碼

回答

相關問題