el switch generalmente no es ineficiente; internamente, normalmente se implementa como una tabla de salto a las diversas opciones, o como una búsqueda binaria, o como una serie de declaraciones si-entonces, dependiendo de lo que el compilador/optimizador crea que se ejecutará más rápido.

Sin embargo, podría obtener algo de eficiencia en este caso si evita el bloque de cambio/caso por completo y usa una tabla de búsqueda en su lugar, como esta:

 #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; }

En mi computadora, hacerlo de esta manera se ejecutó un poco más del doble de rápido que el enfoque original (basado en interruptores).

¿Es ineficiente buscar una cadena usando un interruptor dentro de un bucle for?

En general, no.

Lo que me pregunto es, ¿es esta una forma ineficiente de lograr esto?

En primer lugar, el cambio es innecesariamente complejo. Una sentencia if es más simple:

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

¿Qué pasa cuando hay varios números para hacer coincidir?

Entonces, un interruptor probablemente sea más legible, pero su ejemplo está roto ya que cuenta 1 y 4 más de una vez. Código fijo:

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

En segundo lugar, esto probablemente no sea óptimo. Probablemente será un poco más rápido usar repetidamente el operador de resto para obtener el dígito menos significativo y dividir por 10, y comparar el dígito. Esto es esencialmente parte de lo que hace internamente la función de conversión de cadenas.

Para comparar la complejidad asintótica, tiene la misma complejidad temporal que su solución, O(log N) donde N es el tamaño del número entero. La complejidad del tamaño es constante, mientras que su solución requiere O (log N) para el almacenamiento de cadenas. Tenga en cuenta que la comparación de la complejidad asintótica es en su mayoría irrelevante si usa esto con números enteros primitivos debido a su rango limitado. Esto es importante para la aritmética de precisión arbitraria.

Otra optimización potencial es no usar una rama en el ciclo, sino contar la frecuencia de todos los números enteros y, al final, hacer un ciclo de las frecuencias y cambiar solo en ese ciclo. La evaluación comparativa dirá si esto es más rápido.

La eficiencia generalmente no es un problema para una operación que se realiza una vez, con una pequeña entrada. Es muy probable que para un solo entero, la mayor parte del tiempo de la CPU se dedique a cargar el código (ya que no estará en la memoria caché de la CPU). E incluso entonces será menos de un microsegundo.

La eficiencia importaría si tiene un std::vector<int> con un millón de valores. En este caso, el objetivo es calcular las respuestas tan rápido como su CPU pueda cargar nuevos enteros desde la memoria, y con un vector, eso es bastante rápido.

Como mencionó eeroika, haces trabajo innecesario. Primero crea una cadena, lo que significa que decide para cada str[i] qué dígito es, y luego almacena ese dígito. Pero a usted no le importan la mayoría de los dígitos, y para los dígitos que sí le importan, tampoco hay necesidad de almacenarlos. Solo necesita contar si los almacenaría.

Esto es importante porque almacenar esos dígitos requiere escribirlos en la memoria (bueno, caché). Por otro lado, una CPU puede realizar fácilmente un seguimiento de algunos contadores.