c++ - usar - Cómo evitar el uso de goto y romper bucles anidados de manera eficiente

usar break en c

Question

Diría que es un hecho que usar goto se considera una mala práctica cuando se trata de programar en C / C ++.

Sin embargo, dado el siguiente código

for (i = 0; i < N; ++i) 
{
    for (j = 0; j < N; j++) 
    {
        for (k = 0; k < N; ++k) 
        {
            ...
            if (condition)
                goto out;
            ...
        }
    }
}
out:
    ...

Me pregunto cómo lograr el mismo comportamiento eficientemente sin usar goto . Lo que quiero decir es que podríamos hacer algo como verificar la condition al final de cada bucle, por ejemplo, pero AFAIK goto generará solo una instrucción de ensamblaje que será un jmp . Esta es la manera más eficiente de hacer esto, puedo pensar.

¿Hay alguna otra que se considere una buena práctica? ¿Me equivoco cuando digo que se considera una mala práctica usar goto? Si lo soy, ¿sería este uno de esos casos en los que es bueno usarlo?

Gracias

Answer 1

¿Hay alguna otra que se considere una buena práctica? ¿Me equivoco cuando digo que se considera una mala práctica usar goto?

goto puede ser mal usado y usado en exceso, pero no veo ninguno de los dos en su ejemplo. La ruptura de un bucle profundamente anidado se expresa más claramente con una simple goto label_out_of_the_loop; .

Es una mala práctica usar muchos goto s que saltan a diferentes etiquetas, pero en esos casos no es la palabra clave goto lo que hace que su código sea malo. Es el hecho de que estás saltando en el código haciendo que sea difícil de seguir lo que lo hace malo. Sin embargo, si necesita un solo salto de bucles anidados, entonces, ¿por qué no utilizar la herramienta que se hizo para ese fin?

Para usar una analogía de aire comprimido: imagina que vives en un mundo donde en el pasado era bueno clavar clavos en las paredes. En los últimos tiempos se hizo más fácil taladrar tornillos en las paredes con destornilladores y los martillos están completamente pasados ​​de moda. Ahora considera que tienes que (a pesar de ser un poco anticuado) clavar un clavo en la pared. No debe abstenerse de usar un martillo para hacer eso, pero tal vez debería preguntarse si realmente necesita un clavo en la pared en lugar de un tornillo.

(Por si acaso no está claro: el martillo está goto y el clavo en la pared es un salto de un bucle anidado mientras que el tornillo en la pared estaría usando funciones para evitar la anidación profunda);

Answer 2

Específico

OMI, en este ejemplo específico, creo que es importante notar una funcionalidad común entre sus bucles. (Ahora sé que tu ejemplo no es necesariamente literal aquí, pero solo ten paciencia conmigo por un segundo) ya que cada ciclo itera N veces, puedes reestructurar tu código de la siguiente manera:

Ejemplo

int max_iterations = N * N * N;
for (int i = 0; i < max_iterations; i++)
{
    /* do stuff, like the following for example */
    *(some_ptr + i) = 0; // as opposed to *(some_3D_ptr + i*X + j*Y + Z) = 0;
    // some_arr[i] = 0; // as oppose to some_3D_arr[i][j][k] = 0;
}

Ahora, es importante recordar que todos los bucles, mientras que para o de otra manera, son realmente solo azúcar sintáctica para el paradigma de si-goto. Estoy de acuerdo con los demás en que debe tener una función para devolver el resultado, sin embargo, quería mostrar un ejemplo como el anterior en el que tal vez no sea el caso. De acuerdo, marcaría lo anterior en una revisión del código, pero si reemplazara lo anterior con un goto, lo consideraría un paso en la dirección incorrecta. (NOTA: asegúrese de que puede ajustarlo de manera confiable en su tipo de datos deseado)

General

Ahora, como respuesta general, las condiciones de salida para su ciclo pueden no ser las mismas siempre (como la publicación en cuestión). Como regla general, saque tantas operaciones innecesarias de sus bucles (multiplicaciones, etc.) tan lejos como pueda, mientras que los compiladores se vuelven más inteligentes todos los días, no hay reemplazo para escribir un código eficiente y legible.

Ejemplo

/* matrix_length: int of m*n (row-major order) */
int num_squared = num * num;
for (int i = 0; i < matrix_length; i++)
{
    some_matrix[i] *= num_squared; // some_matrix is a pointer to an array of ints of size matrix_length
}

en lugar de escribir *= num * num , ya no tenemos que confiar en el compilador para optimizar esto (aunque cualquier buen compilador debería). Por lo tanto, cualquier bucle anidado doble o triplicado que realice la funcionalidad anterior también beneficiaría no solo a su código, sino también a la OMI que escribe un código limpio y eficiente de su parte. En el primer ejemplo, podríamos haber tenido *(some_3D_ptr + i*X + j*Y + Z) = 0; ! ¿Confiamos en que el compilador optimice i*X y j*Y para que no se computen en cada iteración?

bool check_threshold(int *some_matrix, int max_value)
{
    for (int i = 0; i < rows; i++)
    {
        int i_row = i*cols; // no longer computed inside j loop unnecessarily.
        for (int j = 0; j < cols; j++)
        {
            if (some_matrix[i_row + j] > max_value) return true;
        }
    }
    return false;
}

¡Yuck! ¿Por qué no utilizamos las clases proporcionadas por el STL o una biblioteca como Boost? (debemos estar haciendo aquí algún código de bajo nivel / alto rendimiento). Ni siquiera podía escribir una versión en 3D, debido a la complejidad. Aunque hemos optimizado algo a mano, puede ser incluso mejor utilizar #pragma unrol o sugerencias de preprocesador similares si el compilador lo permite.

Conclusión

En general, cuanto mayor sea el nivel de abstracción que puede usar, mejor; sin embargo, si alias una matriz de orden de una fila unidimensional de enteros a una matriz bidimensional hace que su flujo de código sea más difícil de entender / extender, ¿vale la pena? ? Del mismo modo, eso también puede ser un indicador para hacer algo en su propia función. Espero que, dados estos ejemplos, puedan ver que se necesitan diferentes paradigmas en diferentes lugares, y es su trabajo como programador darse cuenta de eso. No te vuelvas loco con lo anterior, pero asegúrate de saber lo que significan, cómo usarlos, y cuándo se necesitan, y lo más importante, asegúrate de que las otras personas que usan tu base de código sepan lo que son y tengan sin reparos al respecto ¡Buena suerte!

Answer 3

Alternativa - 1

Puedes hacer algo como lo siguiente:

1. Establezca una variable bool al principio isOkay = true
2. Todas sus condiciones de bucle for agregan una condición adicional isOkay == true
3. Cuando su condición personalizada está satisfecha / falla, establezca isOkay = false .

Esto hará que tus bucles se detengan. Una variable bool extra a veces sería útil.

bool isOkay = true;
for (int i = 0; isOkay && i < N; ++i)
{
    for (int j = 0; isOkay && j < N; j++)
    {
        for (int k = 0; isOkay && k < N; ++k)
        {
            // some code
            if (/*your condition*/)
                 isOkay = false;
        }
     }
}

Alternativa - 2

En segundo lugar. si las iteraciones de bucle anteriores están en una función, la mejor opción es return resultado, siempre que se satisfaga la condición personalizada.

bool loop_fun(/* pass the array and other arguments */)
{
    for (int i = 0; i < N ; ++i)
    {
        for (int j = 0; j < N ; j++)
        {
            for (int k = 0; k < N ; ++k)
            {
                // some code
                if (/* your condition*/)
                    return false;
            }
        }
    }
    return true;
}

Answer 4

Creo que goto es una cosa completamente sana que hacer aquí, y es uno de sus casos de uso excepcionales según las Directrices básicas de C ++ .

Sin embargo, tal vez otra solución a considerar es una IIFE lambda. ¡En mi opinión, esto es un poco más elegante que declarar una función separada!

[&] {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; ++k)
                if (condition)
                    return;
}();

¡Gracias a JohnMcPineapple en reddit por esta sugerencia!

Answer 5

Divide tus bucles en funciones. Hace que las cosas sean mucho más fáciles de entender porque ahora puedes ver lo que está haciendo realmente cada ciclo.

bool doHerpDerp() {
    for (i = 0; i < N; ++i) 
    {
        if (!doDerp())
            return false;
    }
    return true;
}

bool doDerp() {
    for (int i=0; i<X; ++i) {
        if (!doHerp())
            return false;
    }
    return true;
}

bool doHerp() {
    if (shouldSkip)
        return false;
    return true;
}

Answer 6

En cuanto a su comentario sobre la eficiencia de compilación, ambas opciones en modo de lanzamiento en visual studio 2017 producen exactamente el mismo ensamblaje.

for (int i = 0; i < 5; ++i)
{
    for (int j = 0; j < 5; ++j)
    {
        for (int k = 0; k < 5; ++k)
        {
            if (i == 1 && j == 2 && k == 3) {
                goto end;

            }
        }
    }
}
end:;

y con una bandera

bool done = false;
for (int i = 0; i < 5; ++i)
{
    for (int j = 0; j < 5; ++j)
    {
        for (int k = 0; k < 5; ++k)
        {
            if (i == 1 && j == 2 && k == 3) {
                done = true;
                break;
            }
        }
        if (done) break;
    }
    if (done) break;
}

ambos producen ..

xor         edx,edx  
xor         ecx,ecx  
xor         eax,eax  
cmp         edx,1  
jne         main+15h (0C11015h)  
cmp         ecx,2  
jne         main+15h (0C11015h)  
cmp         eax,3  
je          main+27h (0C11027h)  
inc         eax  
cmp         eax,5  
jl          main+6h (0C11006h)  
inc         ecx  
cmp         ecx,5  
jl          main+4h (0C11004h)  
inc         edx  
cmp         edx,5  
jl          main+2h (0C11002h)    

entonces no hay ganancia. Otra opción si usa un compilador moderno de c ++ es envolverlo en un lambda.

[](){
for (int i = 0; i < 5; ++i)
{
    for (int j = 0; j < 5; ++j)
    {
        for (int k = 0; k < 5; ++k)
        {
            if (i == 1 && j == 2 && k == 3) {
                return;
            }
        }

    }
}
}();

de nuevo, esto produce el mismo ensamblaje exacto. Personalmente, creo que usar goto en tu ejemplo es perfectamente aceptable. Está claro lo que le está sucediendo a cualquier otra persona y hace que el código sea más conciso. Podría decirse que el lambda es igualmente conciso.

Answer 7

En este caso , no querrás evitar el uso de goto .

En general, se debe evitar el uso de goto , sin embargo, hay excepciones a esta regla, y su caso es un buen ejemplo de uno de ellos.

Veamos las alternativas:

for (i = 0; i < N; ++i) {
    for (j = 0; j < N; j++) {
        for (k = 0; k < N; ++k) {
            ...
            if (condition)
                break;
            ...
        }
        if (condition)
            break;
    }
    if (condition)
        break;
}

O:

int flag = 0
for (i = 0; (i < N) && !flag; ++i) {
    for (j = 0; (j < N) && !flag; j++) {
        for (k = 0; (k < N) && !flag; ++k) {
            ...
            if (condition) {
                flag = 1
                break;
            ...
        }
    }
}

Ninguno de estos es tan conciso o tan legible como la versión goto .

Usar un goto se considera aceptable en los casos en los que solo estás saltando hacia adelante (no hacia atrás) y hacerlo hace que tu código sea más legible y comprensible.

Si, por otro lado, utiliza goto para saltar en ambas direcciones, o para saltar a un alcance que potencialmente podría eludir la inicialización de la variable, eso sería malo.

Aquí hay un mal ejemplo de goto :

int x;
scanf("%d", &x);
if (x==4) goto bad_jump;

{
    int y=9;

// jumping here skips the initialization of y
bad_jump:

    printf("y=%d/n", y);
}

Un compilador de C ++ arrojará un error aquí porque el goto salta sobre la inicialización de y . Sin embargo, los compiladores de C compilarán esto, y el código anterior invocará un comportamiento indefinido al intentar imprimir y que no se inicializará si se produce el goto .

Otro ejemplo del uso correcto de goto es en el manejo de errores:

void f()
{
    char *p1 = malloc(10);
    if (!p1) {
        goto end1;
    }
    char *p2 = malloc(10);
    if (!p2) {
        goto end2;
    }
    char *p3 = malloc(10);
    if (!p3) {
        goto end3;
    }
    // do something with p1, p2, and p3

end3:
    free(p3);
end2:
    free(p2);
end1:
    free(p1);
}

Esto realiza toda la limpieza al final de la función. Compare esto con la alternativa:

void f()
{
    char *p1 = malloc(10);
    if (!p1) {
        return;
    }
    char *p2 = malloc(10);
    if (!p2) {
        free(p1);
        return;
    }
    char *p3 = malloc(10);
    if (!p3) {
        free(p2);
        free(p1);
        return;
    }
    // do something with p1, p2, and p3

    free(p3);
    free(p2);
    free(p1);
}

Donde la limpieza se realiza en varios lugares. Si luego agrega más recursos que necesitan ser limpiados, debe recordar agregar la limpieza en todos estos lugares más la limpieza de los recursos que se obtuvieron anteriormente.

El ejemplo anterior es más relevante para C que para C ++ ya que en este último caso puede usar clases con destructores apropiados y punteros inteligentes para evitar la limpieza manual.

Answer 8

La (mejor) versión no aprobada se parecería a esto:

void calculateStuff()
{
    // Please use better names than this.
    doSomeStuff();
    doLoopyStuff();
    doMoreStuff();
}

void doLoopyStuff()
{
    for (i = 0; i < N; ++i) 
    {
        for (j = 0; j < N; j++) 
        {
            for (k = 0; k < N; ++k) 
            {
                /* do something */

                if (/*condition*/)
                    return; // Intuitive control flow without goto

                /* do something */
            }
        }
    }
}

Dividir esto también es probablemente una buena idea porque te ayuda a mantener tus funciones cortas, tu código legible (si nombras las funciones mejor que yo) y las dependencias bajas.

Answer 9

La mejor solución es poner los bucles en una función y luego return de esa función.

Esto es esencialmente lo mismo que tu ejemplo goto , pero con el beneficio masivo que evitas tener otro debate goto .

Pseudo código simplificado:

bool function (void)
{
  bool result = something;


  for (i = 0; i < N; ++i) 
    for (j = 0; j < N; j++) 
      for (k = 0; k < N; ++k) 
        if (condition)
          return something_else;
  ...
  return result;
}

Otro beneficio aquí es que puede actualizar de bool a una enum si encuentra más de 2 escenarios. Realmente no puedes hacer eso con goto de una manera legible. En el momento en que comienzas a usar múltiples gotos y etiquetas múltiples, es el momento en que abrazas la codificación de espagueti. Sí, incluso si solo bifurca hacia abajo, no será agradable de leer y mantener.

Notablemente, si tiene 3 bucles anidados, puede ser una indicación de que debe intentar dividir su código en varias funciones y entonces toda esta discusión podría no ser relevante.

Answer 10

Lambdas te permite crear ámbitos locales:

[&]{
  for (i = 0; i < N; ++i) 
  {
    for (j = 0; j < N; j++) 
    {
      for (k = 0; k < N; ++k) 
      {
        ...
        if (condition)
          return;
        ...
      }
    }
  }
}();

si también desea la posibilidad de volver fuera de ese alcance:

if (auto r = [&]()->boost::optional<RetType>{
  for (i = 0; i < N; ++i) 
  {
    for (j = 0; j < N; j++) 
    {
      for (k = 0; k < N; ++k) 
      {
        ...
        if (condition)
          return {};
        ...
      }
    }
  }
}()) {
  return *r;
}

donde boost::nullopt {} o boost::nullopt es un "break", y devolver un valor devuelve un valor del alcance adjunto.

Otro enfoque es:

for( auto idx : cube( {0,N}, {0,N}, {0,N} ) {
  auto i = std::get<0>(idx);
  auto j = std::get<1>(idx);
  auto k = std::get<2>(idx);
}

donde generamos un iterable sobre las 3 dimensiones y lo hacemos un bucle 1 anidado profundo. Ahora el break funciona bien. Tienes que escribir el cube .

En c ++ 17 esto se convierte

for( auto[i,j,k] : cube( {0,N}, {0,N}, {0,N} ) ) {
}

lo cual es bueno.

Ahora, en una aplicación en la que se supone que debes responder, pasar por un gran rango tridimensional al nivel de flujo de control primario a menudo es una mala idea. Puedes sacarlo, pero incluso así terminas con el problema de que el hilo se ejecuta demasiado tiempo. Y la mayoría de las iteraciones grandes tridimensionales con las que he jugado pueden beneficiarse del uso de la subtarea de subprocesamiento.

Con ese fin, terminará queriendo categorizar su operación según el tipo de datos a los que accede, luego pasará su operación a algo que programe la iteración por usted .

auto work = do_per_voxel( volume,
  [&]( auto&& voxel ) {
    // do work on the voxel
    if (condition)
      return Worker::abort;
    else
      return Worker::success;
  }
);

entonces el flujo de control involucrado entra en la función do_per_voxel .

do_per_voxel no va a ser un simple círculo do_per_voxel , sino un sistema para reescribir las tareas por voxel en tareas por escaneo (o incluso tareas por plano dependiendo de qué tan grandes sean los planos / líneas de rastreo en tiempo de ejecución (!)) luego, envíelos a su vez a un planificador de tareas administradas del grupo de subprocesos, cose los identificadores de tarea resultantes y devuelva un trabajo futuro que se puede esperar o usar como un activador de continuación para cuando se termine el trabajo.

Y a veces solo usas goto. O puede dividir manualmente funciones para subloops. O usa banderas para salir de recursión profunda. O pones todo el bucle de 3 capas en su propia función. O compones los operadores de bucle utilizando una biblioteca de mónadas. O puede lanzar una excepción (!) Y atraparla.

La respuesta a casi todas las preguntas en c ++ es "depende". El alcance del problema y la cantidad de técnicas que tiene disponibles es grande, y los detalles del problema cambian los detalles de la solución.

Answer 11

Una posible forma es asignar un valor booleano a una variable que represente el estado. Este estado puede luego probarse usando una declaración condicional "IF" para otros fines más adelante en el código.

Answer 12

Ya hay varias respuestas excelentes que le dicen cómo puede refactorizar su código, por lo que no las repetiré. Ya no es necesario codificar de esa manera para la eficiencia; la pregunta es si es poco elegante. (De acuerdo, sugiero un refinamiento: si sus funciones auxiliares solo están destinadas a ser utilizadas dentro del cuerpo de esa función, puede ayudar al optimizador declarándolas static , por lo que sabe con certeza que la función no funciona tiene un enlace externo y nunca será llamado desde ningún otro módulo, y la sugerencia en inline no puede doler. Sin embargo, las respuestas anteriores dicen que, cuando se utiliza un lambda, los compiladores modernos no necesitan ninguna pista de ese tipo).

Voy a desafiar un poco el encuadre de la pregunta. Tiene razón en que la mayoría de los programadores tienen un tabú contra el uso de goto . Esto, en mi opinión, ha perdido de vista el propósito original. Cuando Edsger Dijkstra escribió: "Ir a la declaración considerada dañina", había una razón específica por la que pensaba: el uso "desenfrenado" de go to hace que sea demasiado difícil razonar formalmente sobre el estado actual del programa, y ​​qué condiciones deben ser actualmente ciertas , en comparación con el flujo de control de llamadas a funciones recursivas (que él prefería) o bucles iterativos (que aceptó). Él concluyó:

El enunciado de go to actual es demasiado primitivo; es una invitación demasiado grande para desordenar el programa. Uno puede considerar y apreciar las cláusulas consideradas como frenar su uso. No pretendo que las cláusulas mencionadas sean exhaustivas en el sentido de que satisfarán todas las necesidades, pero cualesquiera que sean las cláusulas sugeridas (por ejemplo, cláusulas de aborto) deben satisfacer el requisito de que se pueda mantener un sistema de coordenadas independiente del programador para describir el proceso en una Manera útil y manejable.

Muchos lenguajes de programación similares a C, por ejemplo Rust y Java, tienen una "cláusula adicional considerada como frenar su uso", la break de una etiqueta. Una sintaxis aún más restringida podría ser algo así como break 2 continue; para salir de dos niveles del ciclo anidado y reanudar en la parte superior del ciclo que los contiene. Esto no representa más un problema que una break al estilo C con lo que Dijkstra quería hacer: definir una descripción concisa del estado del programa que los programadores pueden seguir en la cabeza o un analizador estático sería tratable.

Restringir goto a construcciones como esta lo convierte simplemente en un cambio de nombre a una etiqueta. El problema restante es que el compilador y el programador no necesariamente saben que solo lo usarás de esta manera.

Si hay una condición posterior importante que se mantiene después del ciclo, y su preocupación con goto es la misma que la de Dijkstra, puede considerar incluirla en un breve comentario, algo así como // We have done foo to every element, or encountered condition and stopped. Eso aliviaría el problema para los humanos, y un analizador estático debería funcionar bien.

Answer 13

Si tiene bucles profundamente anidados así y debe salir, creo que goto es la mejor solución. Algunos lenguajes (no C) tienen una declaración de break(N) que saldrá de más de un bucle. La razón por la que C no la tiene es que es incluso peor que un goto : tienes que contar los bucles anidados para descubrir qué hace, y es vulnerable a que alguien venga más tarde y agregue o elimine un nivel de anidación, sin darse cuenta que el recuento de descansos debe ajustarse.

Sí, los gotos generalmente son mal vistos. Usar un goto aquí no es una buena solución; es simplemente el menor de varios males.

En la mayoría de los casos, la razón por la que tiene que salir de un bucle profundamente anidado es porque está buscando algo y lo ha encontrado. En ese caso (y como han sugerido varios otros comentarios y respuestas), prefiero mover el ciclo anidado a su propia función. En ese caso, un return del bucle interno cumple su tarea muy limpiamente.

(Hay quienes dicen que las funciones siempre deben regresar al final, no desde el medio. Esas personas dirían que la solución fácil de romper en una función no es válida, y forzarían el uso de las mismas técnicas incómodas de ruptura del bucle interno incluso cuando la búsqueda se dividió en su propia función. Personalmente, creo que esas personas están equivocadas, pero su kilometraje puede variar).

Si insiste en no usar un goto , y si insiste en no usar una función separada con un retorno anticipado, entonces sí, puede hacer algo como mantener variables de control booleanas adicionales y probarlas de forma redundante en las condiciones de control de cada ciclo anidado, pero eso es solo una molestia y un desastre. (Es uno de los males mayores que estaba diciendo que usar un simple goto es menor que).

Answer 14

bool meetCondition = false;
for (i = 0; i < N && !meetCondition; ++i) 
{
    for (j = 0; j < N && !meetCondition; j++) 
    {
        for (k = 0; k < N && !meetCondition; ++k) 
        {
            ...
            if (condition)
                meetCondition = true;
            ...
        }
    }
}