Combinatoria, C ++ e ottimizzazione

Question

Nota: ho una soluzione funzionante, la mia domanda riguarda l'ottimizzazione e altri approcci.

Descrizione del problema

Ciao, sto riscrivendo un vecchio programma che ho creato che risolve i nonogrammi . Per risolverlo, genero (per alcune linee) un array di tutti i modi possibili per adattare i numeri.

Voglio creare un pezzo di codice, che itererà tutte le posizioni in cui posso inserire gli spazi, ad esempio: se c'è una linea con la dimensione 5ei numeri sono 1, 1, ci sono diversi modi per ordinare i numeri, come 1-1--, 1--1-, 1---1, --1-1, ...( -è una scatola bianca, mentre 1sarà nera).

Analisi del problema

Quindi, se guardiamo l'esempio sopra, possiamo descrivere le opzioni in questo modo:

1. La dimensione totale è 5, e ne abbiamo due 1, quindi abbiamo 2caselle bianche con cui giocare (1 deve essere tra i numeri), ho un'altra funzione che calcola quello "spazio libero".

2. Possiamo indicizzare i possibili posti per gli spazi in questo modo [0] 1 [1] 1 [2]:, il che significa che gli spazi possono andare in ciascuno dei [indexes].

3. Tutte le opzioni di posizionamento degli spazi possono essere risolte con cicli annidati, ma poiché lo "spazio libero" e gli eventuali indici sono dinamici, questa non è un'opzione.

4. Per soluzione cerco di creare loop annidati "dinamici", con qualsiasi intervallo e profondità, la domanda è:

C'è un modo più efficiente per farlo?

Possibile soluzione

L'ambito a cui si riferisce la mia domanda non è correlato specificamente alla risoluzione di un nonorgramma o anche di un linguaggio specifico, ma poiché sto scrivendo questo in C ++, pubblicherò il mio tentativo per un codice che lo fa:

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

Produzione:

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 

Se qualcuno è interessato all'implementazione completa, una volta completata e completamente documentata, la caricherò sul mio account GitHub .

Grazie in anticipo per gli aiutanti e i commentatori.

Answer 1

Osservazioni generali

Più codice fornisci, migliori saranno le recensioni che otterrai. Ci sono 2 affermazioni, 1 nella domanda e 1 nei commenti dopo la domanda che la rendono quasi fuori tema per il sito Code Review:

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

Come previsto nella domanda il codice è quasi illeggibile e quindi sarebbe un problema per la manutenzione. Se fossi un insegnante a valutare questo codice, il voto migliore che posso dare è un C (70%) perché si compila e funziona. I nomi delle variabili sono significativi. In un ambiente professionale se fossi il tuo manager faremmo una lunga chiacchierata in privato sul perché è importante rendere il codice più leggibile.

In un ambiente professionale è molto improbabile che tu sia l'unico a mantenere il codice per molteplici ragioni:

1. Potresti essere promosso e non più assegnato a mantenere il codice.
2. Puoi lasciare e ottenere un altro lavoro.
3. Potrebbe esistere un bug nel codice che deve essere corretto e ti viene assegnato un progetto con priorità più alta, quindi qualcun altro verrà assegnato per correggere il codice.

Ci sono più ragioni oltre alle 3 precedenti. Per tutti questi motivi tratterò lo stile di codifica qui.

Possibili ottimizzazioni

La prima regola di ottimizzazione è non ottimizzare, la seconda è trovare tutti i colli di bottiglia nel codice (i colli di bottiglia sono funzioni che rallentano il codice). Il modo principale per ottimizzare il codice C ++ è utilizzare l'ottimizzazione del compilatore incorporata utilizzando le righe di comando del compilatore da -O a -O3. Questo generalmente produrrà codice molto veloce. Sarà molto difficile fornire ottimizzazioni per questo codice come presentato attualmente, ma se si sta compilando per il debug una possibile ottimizzazione potrebbe essere quella di utilizzare gli iteratori C ++ forniti per ciascuna delle classi contenitore come vector.

Potresti anche voler creare le variabili iterators_numbere le iterators_rangecostanti poiché non cambiano.

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

Evitare using namespace std;

Se stai codificando in modo professionale, probabilmente dovresti perdere l'abitudine di usare l' using namespace std;istruzione. Il codice definirà più chiaramente la coutprovenienza e gli altri identificatori ( std::cin, std::cout). Quando inizi a utilizzare gli spazi dei nomi nel codice, è meglio identificare da dove proviene ciascuna funzione perché potrebbero esserci conflitti di nomi di funzioni da diversi spazi dei nomi. L'identificatore coutè possibile sovrascrivere all'interno delle proprie classi e si può sovrascrivere l'operatore anche <<nelle proprie classi. Questa domanda sull'overflow dello stack discute questo in modo più dettagliato.

Dichiara variabile come necessaria

Per quanto posso dire che la variabile move_indexnon ha bisogno di mantenere il suo valore tra le iterazioni del while (true)ciclo, quindi dovrebbe essere dichiarata all'interno del ciclo, la dichiarazione dovrebbe includere l'inizializzazione della variabile in quasi tutti i casi, ma sicuramente in questo caso.

Non utilizzare forcicli di una riga o ifistruzioni

Il codice contiene questa riga:

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

La prima volta che ho letto il codice mi sono perso il fatto che il ciclo for avesse un'azione. Questo codice dovrebbe essere su 2 righe almeno ma preferibilmente 4. 2 righe:

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

Perché 4 righe? Uno degli errori più facili da fare quando si mantiene il codice è aggiungere un'istruzione a un ciclo for o if senza aggiungere le parentesi graffe necessarie per renderlo parte del ciclo. Quindi, quando si crea un nuovo codice, è meglio aggiungere per cominciare:

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

Non l'ho inventato, mi è stato imposto da uno standard di codifica aziendale, tuttavia, ho visto il valore di aver commesso quel tipo di errore più volte.

Questa versione del codice è leggermente più lunga ma è più leggibile e più facile da mantenere:

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