¿Con qué frecuencia se preocupa por cuántos casos se necesitarán procesar?

StackOverflow https://stackoverflow.com/questions/172831

Pregunta

Si tiene lo siguiente: 

$var = 3; // we'll say it's set to 3 for this example
if ($var == 4) {
    // do something
} else if ($var == 5) {
    // do something
} else if ($var == 2) {
    // do something
} else if ($var == 3) {
    // do something
} else {
    // do something
}

Si el 80% del tiempo $ var es 3, ¿te preocupa el hecho de que esté pasando por 4 si es un caso antes de encontrar el caso verdadero?

Estoy pensando en un sitio pequeño, no es un gran problema, pero ¿qué pasa cuando esa declaración if se va a ejecutar miles de veces por segundo?

Estoy trabajando en PHP, pero creo que el idioma no importa.

¿Fue útil?

Solución

Así es como lo hicimos cuando escribía software para sistemas de radar. (La velocidad importa en el radar. Es uno de los pocos lugares donde "tiempo real" significa realmente "real" en lugar de "rápido").

[Cambiaré a la sintaxis de Python, es más fácil para mí y estoy seguro de que puedes interpretarlo.] 

if var <= 3:
    if var == 2:
        # do something
    elif var == 3:
        # do something
    else: 
        raise Exception
else:
    if var == 4:
        # do something
    elif var == 5:
        # do something
    else:
        raise Exception

Sus declaraciones if forman un árbol en lugar de una lista plana. A medida que agrega condiciones a esta lista, se agita alrededor del centro del árbol. La secuencia plana de las comparaciones de n toma, en promedio, n / 2 pasos. El árbol conduce a una secuencia de comparaciones que toma comparaciones de registro ( n ).

Otros consejos

Bueno, creo que casi todo el tiempo , la legibilidad de, digamos, tener valores ordenados numéricamente anularía cualquier beneficio pequeño que pueda obtener al reducir el número de instrucciones de comparación.

Habiendo dicho eso, como con toda optimización:

  1. Haz que funcione
  2. mídelo
  3. Si es lo suficientemente rápido, déjalo en paz
  4. Si es demasiado lento, LUEGO optimícelo

¡Ah, y probablemente usaría un interruptor / caja desde el principio! ;-)

Un caso clásico de esta ocurrencia (con literalmente 5 opciones como en tu publicación) fue en ffmpeg, en la función decode_cabac_residual. Esto fue bastante importante, ya que el perfil (¡muy importante, no lo optimice antes del perfil!) Mostró que contabilizó más del 10-15% del tiempo empleado en la decodificación de video H.264. La declaración if controlaba un conjunto de declaraciones que se calcularon de manera diferente para los diversos tipos de residuos que se descodificarían y, desafortunadamente, se perdió demasiada velocidad debido al tamaño del código si la función se duplicó 5 veces para cada uno de los 5 tipos de residual. Así que en su lugar, se tuvo que usar una cadena if.

El perfilado se realizó en muchos flujos de prueba comunes para ordenarlos en términos de probabilidad; La parte superior era la más común, la parte inferior la menos común. Esto le dio una pequeña ganancia de velocidad.

Ahora, en PHP, sospecho que hay mucho menos de la ganancia de velocidad de estilo de bajo nivel que obtendría en C, como en el ejemplo anterior.

El uso de una declaración de cambio / caso es definitivamente el camino a seguir aquí.

Esto le da al compilador (intérprete) la oportunidad de utilizar una tabla de salto para llegar a la rama correcta sin tener que hacer N comparaciones. Piense en ello creando una matriz de direcciones indexadas como 0, 1, 2, ... luego puede buscar la correcta en la matriz en una sola operación.

Además, como la sobrecarga sintáctica es menor en una declaración de caso, también es más fácil de leer.

Actualizar: si las comparaciones son adecuadas para una declaración de cambio, esta es un área en la que pueden ayudar las optimizaciones guiadas por perfil. Al ejecutar una compilación PGO con cargas de prueba realistas, el sistema puede generar información de uso de la sucursal y luego usar esto para optimizar la ruta tomada.

En lugar de responder a la pregunta de PHP, responderé un poco más generalmente. No se aplica directamente a PHP, ya que pasará por algún tipo de interpretación.

Muchos compiladores pueden convertir desde y hacia if-elif-elif -... bloques para cambiar bloques si es necesario y las pruebas en las partes de elif son bastante simples (y el resto de la semántica resulta ser compatible). Para las pruebas 3-4 no hay necesariamente nada que ganar usando una tabla de salto.

La razón es que el predictor de rama en la CPU es realmente bueno para predecir lo que sucede. En efecto, lo único que sucede es una presión un poco más alta en la búsqueda de instrucciones, pero no va a ser tan impactante.

Sin embargo, en su ejemplo, la mayoría de los compiladores reconocerían que $ var es una constante 3 y luego reemplazará $ var con 3 en los bloques if..elif .. Esto, a su vez, hace que las expresiones sean constantes, por lo que se doblan en verdadero o falso. Todas las ramas falsas son eliminadas por el eliminador de código muerto y la prueba de verdadero también se elimina. Lo que queda es el caso donde $ var == 3. Sin embargo, no puedes confiar en que PHP sea tan inteligente. En general, no puede hacer la propagación de $ var, pero podría ser posible desde algunos sitios de llamadas.

Puedes intentar tener una matriz de bloques de código, a los que llamas. Entonces, todos los bloques de código tienen la misma sobrecarga.

Perl 6: 

our @code_blocks = (
  { 'Code Block 0' },
  { 'Code Block 1' },
  { 'Code Block 2' },
  { 'Code Block 3' },
  { 'Code Block 4' },
  { 'Code Block 5' },
);

if( 0 <= $var < @code_blocks.length ){
  @code_blocks[$var]->();
}

Si el código tiene que hacer pruebas adicionales, entonces se ejecutará más lentamente. Si el rendimiento es crítico en esta sección de código, debe poner primero los casos más comunes.

Normalmente estoy de acuerdo con la medida " luego optimizo " método cuando no está seguro de si el rendimiento será lo suficientemente rápido, pero si el código simplemente necesita ejecutarse lo más rápido posible Y la solución es tan fácil como reorganizar las pruebas, entonces yo haría el código rápido y realizar algunas mediciones después de que se active, asegúrese de que su suposición (por ejemplo, que 3 va a suceder el 80% del tiempo) sea realmente correcta.

Con el código donde es puramente un análisis de igualdad, lo movería a un conmutador / caja, ya que proporciona un mejor rendimiento. 

$var = 3; // we'll say it's set to 3 for this example
switch($var)
 {
   case 4:
      //do something
      break;
   case 5:
      //do something
      break;
   case:
      //do something when none of the provided cases match (same as using an else{ after the elseif{
 }

ahora, si estás haciendo comparaciones más complicadas, las anidaré en el conmutador o solo usaré el elseif.

En los lenguajes orientados a objetos, si una opción proporciona ifs masivos, eso significa que simplemente debe mover el comportamiento (por ejemplo, sus bloques de // hacer algo ) al objeto que contiene el valor.

Solo usted puede saber si la diferencia de rendimiento de optimizar el orden, o reorganizarlo para que sea un árbol binario, haría una diferencia significativa. Pero sospecho que tendrá que tener millones de veces por segundo, no miles, incluso para molestarse en pensar en PHP (y más aún en otros idiomas).

Tiempo. Vea cuántas veces por segundo puede ejecutar lo anterior si / else if / else sentencia sin acción y $ var no es una de las opciones.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top