Si-else-if frente mapa

Question

Supongamos que tengo como un if/else-if cadena:

if(x.GetId() == 1) 
{ 
} 
else if(x.GetId() == 2) 
{ 
} 
// ... 50 more else if statements 

Lo que me pregunto es, si sigo un mapa, va a ser mejor en términos de rendimiento? (suponiendo que las claves sean números enteros)

Answer 1

¿por qué no utiliza un conmutador?

swich(x.GetId()) 
{ 
    case 1: /* do work */ break; // From the most used case 
    case 2: /* do work */ break; 
    case ...: // To the less used case 
} 

EDIT:

puesto el caso de uso más frecuente en la parte superior del interruptor (esto puede tener algún problema de rendimiento si x.GetId es generalmente igual a 50)

Answer 2

switch es la mejor Lo que creo

Answer 3

La mejor solución sería una declaración switch. Esto le permitirá verificar el valor de x.GetId() solo una vez, en lugar de (en promedio) 25 veces como lo hace su código ahora.

Si desea obtener lujo, puede utilizar una estructura de datos que contiene punteros a funciones que manejan lo que sea que esté entre llaves. Si sus valores de ID son consecutivos (es decir, números entre 1 y 50), entonces sería mejor una matriz de punteros de función. Si están dispersos, entonces un mapa sería más apropiado.

Answer 4

Los mapas (generalmente) se implementan utilizando árboles rojo-negro que proporciona búsquedas O (log N) ya que el árbol se mantiene constantemente en equilibrio. Su lista lineal de sentencias if será O (N) el peor caso. Entonces, sí, un mapa sería significativamente más rápido para la búsqueda.

Muchas personas recomiendan utilizar una instrucción de conmutación, que puede no ser más rápida para usted, dependiendo de sus declaraciones if reales. Un compilador a veces puede optimizar el cambio utilizando una tabla de salto que sería O (1), pero esto solo es posible para los valores que tienen un criterio indefinido; por lo tanto, este comportamiento puede ser algo no determinista. Aunque hay un excelente artículo con algunos consejos para optimizar las declaraciones de interruptor aquí Optimizing C and C++ Code.

Técnicamente podría incluso formular un árbol balanceado manualmente, esto funciona mejor para datos estáticos y recientemente creé una función para encontrar rápidamente qué bit se estableció en un byte (Esto se usó en una aplicación incrustada en un I/O de interrupción pasador y tenía que ser rápido cuando 99% de las veces solamente 1 bit se encuentra en el byte):

unsigned char single_bit_index(unsigned char bit) { 
    // Hard-coded balanced tree lookup 
    if(bit > 0x08) 
     if(bit > 0x20) 
      if(bit == 0x40) 
       return 6; 
      else 
       return 7; 
     else 
      if(bit == 0x10) 
       return 4; 
      else 
       return 5; 
    else 
     if(bit > 0x02) 
      if(bit == 0x04) 
       return 2; 
      else 
       return 3; 
     else 
      if(bit == 0x01) 
       return 0; 
      else 
       return 1; 
} 

Esto da una búsqueda constante en 3 pasos para cualquiera de los 8 valores que me da un rendimiento muy determinista, una búsqueda lineal - datos aleatorios dados - promediaría búsquedas de 4 pasos, con un mejor caso de 1 y el peor caso de 8 pasos.

Este es un buen ejemplo de un rango que un compilador probablemente no optimizaría en una tabla de salto ya que los 8 valores que estoy buscando están muy separados: 1, 2, 4, 8, 16, 32, 64, y 128. Tendría que crear una tabla de 128 posiciones muy dispersa con solo 8 elementos que contengan un objetivo, que en una PC con un montón de RAM podría no ser un gran problema, pero en un microcontrolador sería asesino.

Answer 5

La respuesta, como con la mayoría de las preguntas relacionadas con el rendimiento, es tal vez.

Si los ID están en un rango afortunado, un switch podría convertirse en una mesa de salto, proporcionando búsquedas de tiempo constante para todos los ID. No se encontrará mucho mejor que esto, salvo el rediseño.Alternativamente, si los ID son consecutivos pero no obtiene una tabla de salto del compilador, puede forzar el problema llenando una matriz con punteros de función.

[de aquí en adelante, switch se refiere a un if/else cadena genérico]

A map proporciona peor de los casos las operaciones de búsqueda logarítmica para cualquier ID dado, mientras que un switch sólo puede garantizar lineal. Sin embargo, si los ID no son aleatorios, ordenar los casos switch por uso podría garantizar que el peor de los escenarios sea lo suficientemente infrecuente como para que no importe.

A map incurrirá en una sobrecarga inicial al cargar los ID y asociarlos con las funciones, y luego incurrir en una sobrecarga de llamar a un puntero de función cada vez que accede a un ID. Un switch genera una sobrecarga adicional al escribir la rutina, y posiblemente una sobrecarga significativa al depurarlo.

El rediseño podría permitirle evitar la pregunta todos juntos. No importa cómo lo implemente, esto huele a problema. No puedo evitar pensar que hay una mejor manera de manejar esto.

Answer 6

Si realmente tuviera un potencial cambio de cincuenta posibilidades, definitivamente pensaría en un vector de punteros para las funciones.

#include <cstdio> 
#include <cstdlib> 
#include <ctime> 

const unsigned int Max = 4; 

void f1(); 
void f2(); 
void f3(); 
void f4(); 
void (*vp[Max])(); 

int main() 
{ 
    vp[ 0 ] = f1; 
    vp[ 1 ] = f2; 
    vp[ 2 ] = f3; 
    vp[ 3 ] = f4; 

    srand(std::time(NULL)); 
    vp[(rand() % Max)](); 
} 

void f1() 
{ 
    std::printf("Hello from f1!\n"); 
} 

void f2() 
{ 
    std::printf("Hello from f2!\n"); 
} 

void f3() 
{ 
    std::printf("Hello from f3!\n"); 
} 

void f4() 
{ 
    std::printf("Hello from f4!\n"); 
} 

Answer 7

Hay muchas sugerencias relacionadas con la caja del conmutador. En términos de eficiencia, esto podría ser mejor, podría ser lo mismo. No será peor

Pero si solo está configurando/devolviendo un valor o nombre basado en la ID, entonces SÍ. Un mapa es exactamente lo que necesitas. Los contenedores STL están optimizados, y si crees que puedes optimizarlos mejor, entonces eres increíblemente inteligente o asombrosamente tonto.

por ejemplo una sola llamada con un std :: mapa llamado myMap,

thisvar = mymap[x.getID()]; 

es mucho mejor que 50 de estos

if(x.getID() == ...){thisvar = ...;} 

porque es más eficiente ya que el número de ID de aumentos. Si está interesado en por qué, busque un buen manual sobre estructuras de datos.

Pero lo que realmente consideraría aquí es el tiempo de mantenimiento/reparación. Si necesita cambiar el nombre de la variable, o cambiar de usar getID() o getName(), o hacer cualquier tipo de cambio menor, debe hacerlo CINCUENTA VECES en su ejemplo. Y necesita una nueva línea cada vez que agrega una identificación.

El mapa reduce eso a un cambio de código SIN IMPORTAR CUANTAS IDENTIFICACIONES TIENE.

Dicho esto, si realmente lleva a cabo diferentes acciones para cada ID, una caja de conmutadores podría ser mejor. Con mayúsculas y minúsculas en lugar de declaraciones if, puede mejorar el rendimiento y la legibilidad. Vea aquí: Advantage of switch over if-else statement Evitaría los punteros a las funciones a menos que tenga muy claro cómo mejorarían su código, porque si no está 100% seguro de lo que está haciendo, la sintaxis puede estar en mal estado, y es exagerado para cualquier cosa con la que se pueda usar un mapa.

Básicamente, me interesaría el problema que está tratando de resolver. Puede que te vaya mejor con un mapa o una caja de cambios, pero si crees que puedes usar un mapa, eso es ABSOLUTAMENTE lo que deberías usar en su lugar.