Combinatoire, C ++ et optimisation

Question

Remarque: j'ai une solution de travail, ma question porte sur l'optimisation et d'autres approches.

Description du problème

Bonjour, je réécris un ancien programme que j'ai créé qui résout les nonogrammes . Dans le cadre de sa résolution, je génère (pour certaines lignes) un tableau de toutes les façons possibles d'ajuster les nombres.

Je veux créer un morceau de code, qui itérera toutes les positions dans lesquelles je peux mettre les espaces, par exemple: s'il y a une ligne avec une taille 5et que les nombres sont 1, 1, il y a plusieurs façons de classer les nombres, comme 1-1--, 1--1-, 1---1, --1-1, ...( -est une boîte blanche, tandis que 1sera noire).

Répartition des problèmes

Donc, si nous regardons l'exemple ci-dessus, nous pouvons décrire les options comme ceci:

1. La taille totale est de 5, et nous en avons deux 1, donc nous avons 2des cases blanches avec lesquelles jouer (1 doit être entre les nombres), j'ai une autre fonction qui calcule cet "espace libre".

2. Nous pouvons indexer les emplacements possibles pour les espaces de cette façon:, ce qui [0] 1 [1] 1 [2]signifie que les espaces peuvent aller dans chacun des [indexes].

3. Toutes les options de placement des espaces peuvent être résolues avec des boucles imbriquées, mais comme "l'espace libre" et les index possibles sont dynamiques, ce n'est pas une option.

4. Pour la solution, j'essaie de créer des boucles imbriquées "dynamiques", avec n'importe quelle plage et profondeur, la question est:

Existe-t-il un moyen plus efficace de le faire?

Solution possible

La portée à laquelle ma question se réfère n'est pas spécifiquement liée à la résolution d'un non-orgramme ou même d'un langage spécifique, mais puisque j'écris ceci en C ++, je publierai ma tentative pour un code qui le fait:

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

Production:

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 quelqu'un est intéressé par l'implémentation complète, une fois qu'elle sera terminée et entièrement documentée, je la téléchargerai sur mon compte GitHub .

Merci d'avance pour les assistants et les commentateurs.

Answer 1

Observations générales

Plus vous fournissez de code, meilleures seront les critiques que vous obtiendrez. Il y a 2 déclarations, 1 dans la question et 1 dans les commentaires après la question qui font presque hors sujet pour le site de révision de code:

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".

Comme indiqué dans la question, le code est presque illisible et serait donc un problème de maintenance. Si j'étais un enseignant évaluant ce code, la meilleure note que je puisse lui donner est un C (70%) car il se compile et s'exécute. Les noms de variables sont significatifs. Dans un environnement professionnel, si j'étais votre manager, nous aurions une longue discussion en privé sur les raisons pour lesquelles il est important de rendre le code plus lisible.

Dans un environnement professionnel, il est très peu probable que vous soyez le seul à maintenir le code pour plusieurs raisons:

1. Vous pouvez être promu et ne plus être affecté à la maintenance du code.
2. Vous pouvez quitter et trouver un autre emploi.
3. Un bogue peut exister dans le code qui doit être corrigé et vous êtes assigné à un projet de priorité plus élevée, donc quelqu'un d'autre sera assigné pour corriger le code.

Il y a plus de raisons que les 3 ci-dessus. Pour toutes ces raisons, j'aborderai ici le style de codage.

Optimisations possibles

La première règle d'optimisation est de ne pas optimiser, la seconde est de trouver tous les goulots d'étranglement dans le code (les goulots d'étranglement étant des fonctions qui ralentissent le code). La principale façon d'optimiser le code C ++ consiste à utiliser l'optimisation intégrée du compilateur à l'aide des lignes de commande du compilateur -O à -O3. Cela produira généralement un code très rapide. Il sera très difficile de fournir des optimisations pour ce code tel qu'il est actuellement présenté, mais si vous compilez pour le débogage, une optimisation possible pourrait être d'utiliser les itérateurs C ++ fournis pour chacune des classes de conteneur telles que vector.

Vous pouvez également vouloir créer les variables iterators_numberet les iterators_rangeconstantes car elles ne changent pas.

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

Éviter using namespace std;

Si vous codez de manière professionnelle, vous devriez probablement perdre l'habitude d'utiliser l' using namespace std;instruction. Le code définira plus clairement d'où coutviennent les autres identifiants ( std::cin, std::cout). Lorsque vous commencez à utiliser des espaces de noms dans votre code, il est préférable d'identifier d'où vient chaque fonction car il peut y avoir des collisions de noms de fonction à partir d'espaces de noms différents. L'identifiant que coutvous pouvez remplacer dans vos propres classes, et vous pouvez également remplacer l'opérateur <<dans vos propres classes. Cette question de débordement de pile traite de cela plus en détail.

Déclarer la variable si nécessaire

Pour autant que je sache, la variable move_indexn'a pas besoin de maintenir sa valeur entre les itérations de la while (true)boucle, elle doit donc être déclarée dans la boucle, la déclaration doit inclure l'initialisation de la variable dans presque tous les cas, mais certainement dans ce cas.

N'utilisez pas de forboucles ou d' ifinstructions sur une ligne

Le code contient cette ligne:

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

Lors de ma première lecture du code, j'ai manqué le fait que la boucle for avait une action. Ce code doit être sur 2 lignes au moins mais de préférence 4. 2 lignes:

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

Pourquoi 4 lignes? L'une des erreurs les plus simples à faire lors de la gestion du code est d'ajouter une instruction à une boucle for ou if sans ajouter les accolades nécessaires pour l'intégrer à la boucle. Ainsi, lors de la création d'un nouveau code, il est préférable d'ajouter le pour commencer:

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

Je n'ai pas proposé cela, cela m'a été imposé par une norme de codage d'entreprise, mais j'ai vu l'intérêt d'avoir commis ce genre d'erreur à plusieurs reprises.

Cette version du code est légèrement plus longue mais plus lisible et plus facile à maintenir:

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