使用 for 循环内的开关搜索字符串效率低下吗？

Question

最近做了一个在线编程评估，其中的问题本质上是“搜索指定整数的数字并递增计数”。

我的解决方案是将给定的数字转换为字符串，然后使用 for 循环和 switch 语句搜索字符串。所以基本上：

for (int i = 0; i < str.length(); i++;)
{
    switch(str[i]) {
      case  '1':
       count++;
       break;
      case  '4': 
       count++;
       break;
      case  '8': 
       count++;
       break;
       // etc
    }
}

我想知道的是，这是一种低效的方法吗？我相信时间复杂度是 O(n)，但我可能是错的。如果效率低下，有什么更好的解决方案？

** 为澄清起见进行了编辑，添加了案例“4”和“8”

Answer 1

Is searching a string using a switch inside a for loop inefficient?

一般不会。

What I'm wondering is, is this an inefficient way of accomplishing this?

首先，开关过于复杂。 if 语句更简单：

if (str[i] == '1')
    count++;

What about when there are multiple numbers to be matched?

那么 switch 可能更具可读性，但是您的示例已损坏，因为它多次计算 1 和 4。固定码：

switch(str[i]) {
  case  '1':
  case  '4': 
  case  '8': 
     count++;
}

其次，这可能不是最佳选择。重复使用余数运算符得到最低有效位并除以 10，然后比较数字可能会更快一些。这本质上是字符串转换函数在内部所做的一部分。

为了比较渐近复杂度，这与您的解决方案具有相同的时间复杂度，O(log N)，其中 N 是整数的大小。大小复杂度是恒定的，而您的解决方案需要 O(log N) 来存储字符串。请注意，如果由于范围有限而将其与原始整数一起使用，则渐近复杂度的比较基本上是无关紧要的。这对于任意精度算术很重要。

另一个潜在的优化是不在循环中使用分支，而是计算所有整数的频率，并在结束循环中仅在该循环中计算频率和开关。基准测试将判断这是否更快。

Answer 2

switch 一般不会低效；在内部，它通常是 implemented 作为各种选项的 jump-table，或者作为二进制搜索，或者作为一系列 if-then 语句，具体取决于 compiler/optimizer 的想法执行速度最快。

但是，在这种情况下，您可以通过完全避免 switch/case 块并使用 lookup-table 来提高效率，如下所示：

#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] = '[=10=]';
      
   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;
}

在我的电脑上，这样做的速度比原来的 (switch-based) 方法快两倍多。

Answer 3

对于您只执行一次的小输入操作，效率通常不是问题。很可能对于单个整数，大部分 CPU 时间将花在加载代码上（因为它不会在 CPU 缓存中）。即便如此，也不会超过一微秒。

如果您有一个 std::vector<int> 具有一百万个值，那么效率很重要。在这种情况下，目标是计算答案的速度与 CPU 可以从内存中加载新整数的速度一样快 - 使用向量，速度非常快。

正如 eeroika 所说，你做了不必要的工作。您首先创建一个字符串，这意味着您决定每个 str[i] 它是什么数字，然后存储该数字。但是你并不关心大多数数字，对于你关心的数字也没有必要存储它们。你只需要计算你是否会存储它们。

这很重要，因为存储这些数字需要将它们写入内存（嗯，缓存）。另一方面，CPU 可以轻松跟踪几个计数器。

使用 for 循环内的开关搜索字符串效率低下吗？

Is searching a string using a switch inside a for loop inefficient?

c++

for-loop

switch-statement