Combinatoria, C ++ y optimización

Question

Nota: tengo una solución que funciona, mi pregunta es sobre optimización y otros enfoques.

Descripción del problema

Hola, estoy reescribiendo un programa antiguo que hice que resuelve nonogramas . Como parte de la solución, genero (para algunas de las líneas) una matriz de todas las formas posibles de encajar los números.

Quiero crear un fragmento de código, que iterará todas las posiciones en las que puedo poner los espacios, por ejemplo: si hay una línea con tamaño 5, y los números son 1, 1, hay varias formas de ordenar los números, como 1-1--, 1--1-, 1---1, --1-1, ...( -es una caja blanca, mientras 1que será negra).

Desglose del problema

Entonces, si miramos el ejemplo anterior, podemos describir las opciones de esta manera:

1. El tamaño total es 5, y tenemos dos 1, por lo tanto tenemos 2casillas blancas para jugar (1 debe estar entre los números), tengo otra función que calcula ese "espacio libre".

2. Podemos indexar los posibles lugares para los espacios de esta manera:, lo que [0] 1 [1] 1 [2]significa que los espacios pueden ir en cada uno de los [indexes].

3. Todas las opciones de colocar los espacios se pueden resolver con bucles anidados, pero dado que el "espacio libre" y los posibles índices son dinámicos, esta no es una opción.

4. Para la solución, trato de crear bucles anidados "dinámicos", con cualquier rango y profundidad, la pregunta es:

¿Existe una forma más eficaz de hacerlo?

Solución posible

El alcance al que se refiere mi pregunta no está relacionado específicamente con la resolución de un nonorgram o incluso un lenguaje específico, pero como estoy escribiendo esto en C ++, publicaré mi intento de un código que lo haga:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.
    int move_index;

    vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";
        cout << endl;

        for (move_index = iterators_number - 1;
             (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1); move_index--);
        if (move_index < 0) break;
        int new_value = options_iteration[move_index] + 1;
        for (; move_index < iterators_number; move_index++) options_iteration[move_index] = new_value;
    }

    return 0;
}

Salida:

0 0 0 
0 0 1 
0 0 2 
0 0 3 
0 1 1 
0 1 2 
0 1 3 
0 2 2 
0 2 3 
0 3 3 
1 1 1 
1 1 2 
1 1 3 
1 2 2 
1 2 3 
1 3 3 
2 2 2 
2 2 3 
2 3 3 
3 3 3 

Si alguien está interesado en la implementación completa, una vez que esté hecha y completamente documentada, la subiré a mi cuenta de GitHub .

Gracias de antemano por los ayudantes y comentaristas.

Answer 1

Observaciones generales

Cuanto más código proporcione, mejores serán las revisiones que obtendrá. Hay 2 declaraciones, 1 en la pregunta y 1 en los comentarios después de la pregunta que casi se desvían del tema del sitio de Revisión de código:

1. ... my real code does not print for each iteration, this is for easy testing.
2. I have another function that calculates that "free space".

Como se indica en la pregunta, el código es casi ilegible y, por lo tanto, sería un problema de mantenimiento. Si yo fuera un profesor que califica este código, la mejor calificación que puedo darle es una C (70%) porque se compila y se ejecuta. Los nombres de las variables son significativos. En un entorno profesional, si yo fuera su gerente, tendríamos una larga charla en privado sobre por qué es importante hacer que el código sea más legible.

En un entorno profesional, es muy poco probable que sea el único que mantiene el código por varias razones:

1. Es posible que lo asciendan y no se le asigne más para mantener el código.
2. Puede renunciar y conseguir otro trabajo.
3. Es posible que exista un error en el código que deba corregirse y usted esté asignado a un proyecto de mayor prioridad, por lo que se asignará a otra persona para corregir el código.

Hay más razones que las 3 anteriores. Por todas estas razones, abordaré el estilo de codificación aquí.

Posibles optimizaciones

La primera regla de optimización es no optimizar, la segunda es encontrar todos los cuellos de botella en el código (los cuellos de botella son funciones que ralentizan el código). La forma principal de optimizar el código C ++ es utilizar la optimización del compilador incorporada utilizando las líneas de comando del compilador -O a -O3. Esto generalmente producirá un código muy rápido. Será muy difícil proporcionar optimizaciones para este código como se presenta actualmente, pero si está compilando para depuración, una posible optimización podría ser utilizar los iteradores de C ++ proporcionados para cada una de las clases de contenedor, como vector.

Es posible que también desee crear las variables iterators_numbery iterators_rangeconstantes, ya que no cambian.

    const int iterators_number = 3;
    const int iterators_range = 3;

Evitar using namespace std;

Si está codificando profesionalmente, probablemente debería dejar el hábito de usar la using namespace std;declaración. El código definirá más claramente de dónde coutprovienen y otros identificadores ( std::cin, std::cout). A medida que empiece a usar espacios de nombres en su código, es mejor identificar de dónde proviene cada función porque puede haber colisiones de nombres de funciones de diferentes espacios de nombres. El identificador coutque puede anular dentro de sus propias clases, y también puede anular el operador <<en sus propias clases. Esta pregunta de desbordamiento de pila analiza esto con más detalle.

Declarar variable según sea necesario

Por lo que puedo decir, la variable move_indexno necesita mantener su valor entre iteraciones del while (true)bucle, por lo que debe declararse dentro del bucle, la declaración debe incluir la inicialización de la variable en casi todos los casos, pero definitivamente en este caso.

No use forbucles o ifdeclaraciones de una línea

El código contiene esta línea:

        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";

La primera vez que revisé el código, me perdí el hecho de que el bucle for tenía una acción. Este código debe tener al menos 2 líneas, pero preferiblemente 4. 2 líneas:

        for (int i = 0; i < iterators_number; i++)
            cout << options_iteration[i] << " ";

¿Por qué 4 líneas? Uno de los errores más fáciles de cometer al mantener el código es agregar una instrucción a un bucle for o if sin agregar las llaves necesarias para que forme parte del bucle. Entonces, al crear un nuevo código, es mejor agregar el para comenzar:

        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }

No se me ocurrió esto, me lo impuso un estándar de codificación de la empresa, sin embargo, vi el valor de haber cometido ese tipo de error varias veces.

Esta versión del código es un poco más larga pero mucho más legible y más fácil de mantener:

#include <vector>
#include <iostream>

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.

    std::vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }
        std::cout << std::endl;

        int move_index = iterators_number - 1;
        for ( ;
            (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1);
            move_index--)
            ;
        if (move_index < 0)
            break;

        int new_value = options_iteration[move_index] + 1;
        for ( ; move_index < iterators_number; move_index++)
        {
            options_iteration[move_index] = new_value;
        }
    }

    return 0;
}