Kombinatorik, C ++ und Optimierung

Question

Hinweis: Ich habe eine funktionierende Lösung. Meine Frage bezieht sich auf Optimierung und andere Ansätze.

Problembeschreibung

Hallo, ich schreibe ein altes Programm neu, das Nonogramme löst . Als Teil der Lösung generiere ich (für einige der Zeilen) ein Array aller möglichen Möglichkeiten, um die Zahlen anzupassen.

Ich möchte einen Code erstellen, der alle Positionen wiederholt, an denen ich die Leerzeichen einfügen kann, zum Beispiel: Wenn es eine Zeile mit Größe 5gibt und die Zahlen sind 1, 1, gibt es mehrere Möglichkeiten, die Zahlen zu ordnen, wie 1-1--, 1--1-, 1---1, --1-1, ...( -ist eine weiße Box, während 1schwarz sein wird).

Problemaufschlüsselung

Wenn wir uns also das obige Beispiel ansehen, können wir die Optionen folgendermaßen beschreiben:

1. Die Gesamtgröße ist 5, und wir haben zwei 1, daher haben wir 2weiße Kästchen zum Spielen (1 muss zwischen den Zahlen liegen). Ich habe eine andere Funktion, die diesen "freien Speicherplatz" berechnet.

2. Wir können die möglichen Stellen für die Räume folgendermaßen indizieren: Das [0] 1 [1] 1 [2]heißt, die Räume können in jedem der Räume stehen [indexes].

3. Alle Optionen zum Platzieren der Leerzeichen können mit verschachtelten Schleifen gelöst werden. Da jedoch der "freie Speicherplatz" und die möglichen Indizes dynamisch sind, ist dies keine Option.

4. Zur Lösung versuche ich, "dynamische" verschachtelte Schleifen mit jedem Bereich und jeder Tiefe zu erstellen. Die Frage ist:

Gibt es einen effizienteren Weg, dies zu tun?

Mögliche Lösung

Der Bereich, auf den sich meine Frage bezieht, bezieht sich nicht speziell auf das Lösen eines Nicht-Programms oder sogar einer bestimmten Sprache. Da ich dies jedoch in C ++ schreibe, werde ich meinen Versuch für einen Code veröffentlichen, der dies tut:

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

Ausgabe:

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 

Wenn jemand an der vollständigen Implementierung interessiert ist, werde ich sie nach Abschluss und vollständiger Dokumentation auf mein GitHub-Konto hochladen .

Vielen Dank im Voraus für die Helfer und Kommentatoren.

Answer 1

Allgemeine Beobachtungen

Je mehr Code Sie bereitstellen, desto besser sind die Bewertungen, die Sie erhalten. Es gibt 2 Aussagen, 1 in der Frage und 1 in den Kommentaren nach der Frage, die es für die Code Review-Site fast zum Thema machen:

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

Wie in der Frage angegeben, ist der Code fast unlesbar und daher ein Problem für die Wartung. Wenn ich ein Lehrer wäre, der diesen Code benotet, ist die beste Note, die ich ihm geben kann, ein C (70%), weil er kompiliert und ausgeführt wird. Die Variablennamen sind aussagekräftig. In einem professionellen Umfeld würden wir, wenn ich Ihr Manager wäre, privat lange darüber sprechen, warum es wichtig ist, den Code lesbarer zu machen.

In einem professionellen Umfeld ist es aus mehreren Gründen sehr unwahrscheinlich, dass Sie der einzige sind, der den Code verwaltet:

1. Möglicherweise werden Sie befördert und nicht mehr mit der Pflege des Codes beauftragt.
2. Sie können kündigen und einen anderen Job bekommen.
3. Möglicherweise ist ein Fehler im Code vorhanden, der behoben werden muss, und Sie werden einem Projekt mit höherer Priorität zugewiesen, sodass jemand anderes zugewiesen wird, um den Code zu beheben.

Es gibt mehr Gründe als nur die 3 oben. Aus all diesen Gründen werde ich hier auf den Codierungsstil eingehen.

Mögliche Optimierungen

Die erste Regel für die Optimierung lautet "Nicht optimieren", die zweite lautet "Alle Engpässe im Code finden" (Engpässe sind Funktionen, die den Code verlangsamen). Die primäre Möglichkeit zur Optimierung von C ++ - Code besteht darin, die integrierte Compileroptimierung mithilfe der Compiler-Befehlszeilen -O bis -O3 zu verwenden. Dies erzeugt im Allgemeinen einen sehr schnellen Code. Es wird sehr schwierig sein, Optimierungen für diesen Code bereitzustellen, wie sie derzeit dargestellt werden. Wenn Sie jedoch für das Debuggen kompilieren, besteht eine mögliche Optimierung darin, die C ++ - Iteratoren zu verwenden, die für jede der Containerklassen bereitgestellt werden, z vector.

Möglicherweise möchten Sie auch die Variablen iterators_numberund iterators_rangeKonstanten erstellen, da sie sich nicht ändern.

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

Vermeiden using namespace std;

Wenn Sie professionell codieren, sollten Sie sich wahrscheinlich daran gewöhnen, die using namespace std;Anweisung zu verwenden. Der Code definiert klarer, woher coutund andere Bezeichner kommen ( std::cin, std::cout). Wenn Sie anfangen, Namespaces in Ihrem Code zu verwenden, ist es besser zu identifizieren, woher die einzelnen Funktionen stammen, da es möglicherweise zu Kollisionen von Funktionsnamen von verschiedenen Namespaces kommen kann. Die Kennung, die coutSie möglicherweise in Ihren eigenen Klassen überschreiben, und Sie können den Operator auch <<in Ihren eigenen Klassen überschreiben . In dieser Frage zum Stapelüberlauf wird dies ausführlicher erläutert.

Deklarieren Sie die Variable als notwendig

Soweit ich das beurteilen kann, muss die Variable move_indexihren Wert zwischen den Iterationen der while (true)Schleife nicht beibehalten, sodass sie innerhalb der Schleife deklariert werden sollte. Die Deklaration sollte in fast allen Fällen die Initialisierung der Variablen enthalten, in diesem Fall jedoch definitiv.

Verwenden Sie keine einzeiligen forSchleifen oder ifAnweisungen

Der Code enthält diese Zeile:

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

Beim ersten Durchlaufen des Codes habe ich die Tatsache übersehen, dass die for-Schleife eine Aktion hatte. Dieser Code sollte mindestens 2 Zeilen enthalten, vorzugsweise jedoch 4 Zeilen. 2 Zeilen:

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

Warum 4 Zeilen? Einer der einfachsten Fehler beim Verwalten von Code besteht darin, einer for-Schleife oder einer if-Anweisung eine Anweisung hinzuzufügen, ohne die Klammern hinzuzufügen, die erforderlich sind, um sie in die Schleife aufzunehmen. Wenn Sie also neuen Code erstellen, ist es besser, zunächst Folgendes hinzuzufügen:

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

Ich habe mir das nicht ausgedacht, es wurde mir durch einen Firmencodierungsstandard aufgezwungen, aber ich sah, dass der Wert davon mehrmals einen solchen Fehler gemacht hatte.

Diese Version des Codes ist etwas länger, aber lesbarer und leichter zu warten:

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