最近做了一個在線編程評估，問題本質上是“在一個數字中搜索指定的整數并增加一個計數”。
我的解決方案是將給定的數字轉換為字串，然后使用 for 回圈和 switch 陳述句搜索字串。所以基本上：
for (int i = 0; i < str.length(); i ;)
{
switch(str[i]) {
case '1':
count ;
case '4':
count ;
case '8':
count ;
// etc
}
}
我想知道的是，這是一種低效的方法嗎？我相信時間復雜度是 O(n)，但我可能是錯的。如果效率低下，有什么更好的解決方案？
**為澄清而編輯，添加案例“4”和“8”
uj5u.com熱心網友回復：
使用 for 回圈內的開關搜索字串效率低嗎？
一般來說，沒有。
我想知道的是，這是一種低效的方法嗎？
首先，開關不必要地復雜。if 陳述句更簡單：
if (str[i] == '1')
count ;
當有多個數字要匹配時怎么辦？
然后一個開關可能更具可讀性，但是您的示例被破壞了，因為它不止一次計數 1 和 4。固定代碼：
switch(str[i]) {
case '1':
case '4':
case '8':
count ;
}
其次，這可能不是最優的。重復使用余數運算子來獲取最低有效位并除以 10，然后比較該數字可能會更快一些。這本質上是字串轉換函式在內部所做的一部分。
為了比較漸近復雜度，這與您的解決方案具有相同的時間復雜度，O(log N) 其中 N 是整數的大小。大小復雜度是恒定的，而您的解決方案需要 O(log N) 來存盤字串。請注意，由于范圍有限，如果將其與原始整數一起使用，漸近復雜度的比較幾乎是無關緊要的。這對于任意精度算術很重要。
另一個潛在的優化是不在回圈中使用分支，而是計算所有整數的頻率，最后回圈頻率并僅在該回圈中切換。基準測驗將判斷這是否更快。
uj5u.com熱心網友回復：
switch一般不會低效；在內部，它通常被實作為各種選項的跳轉表，或二進制搜索，或一系列 if-then 陳述句，具體取決于編譯器/優化器認為將執行得最快的內容。
但是，在這種情況下，您可以通過完全避免 switch/case 塊并使用查找表來獲得一些效率，如下所示：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int, char **)
{
const int BUFSIZE=1024*1024*10; // 10MB
char * str = new char[BUFSIZE];
for (int i=0; i<BUFSIZE; i ) str[i] = (rand()%127) 1;
str[BUFSIZE-1] = '\0';
unsigned char mask[256];
memset(mask, 0, sizeof(mask));
mask['1'] = 1;
mask['4'] = 1;
mask['8'] = 1;
for (int i=0; i<BUFSIZE; i ) count = mask[(unsigned)str[i]];
printf("count=%i\n", count);
return 0;
}
在我的計算機上，以這種方式執行的速度比原來的（基于開關的）方法快兩倍多。
uj5u.com熱心網友回復：
對于您在少量輸入上執行一次的操作，效率通常不是問題。對于單個整數，很可能大部分 CPU 時間將用于加載代碼（因為它不會在 CPU 快取中）。即便如此，它也將不到一微秒。
如果您擁有std::vector<int>一百萬個值，效率將很重要。在這種情況下，目標是盡可能快地計算答案，因為您的 CPU 可以從記憶體中加載新整數 - 并且使用向量，這非常快。
正如 eeroika 提到的，你做不必要的作業。您首先創建一個字串，這意味著您決定每個str[i]數字是什么，然后存盤該數字。但是您并不關心大多數數字，對于您關心的數字也不需要存盤它們。你只需要計算你是否會存盤它們。
這很重要，因為存盤這些數字需要將它們寫入記憶體（嗯，快取）。另一方面，CPU 可以輕松地跟蹤幾個計數器。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/439188.html
上一篇：使for回圈在R中運行得更快