Combinatória, C ++ e otimização

Question

Nota: Eu tenho uma solução de trabalho, minha pergunta é sobre otimização e outras abordagens.

Descrição do Problema

Olá, estou reescrevendo um programa antigo que fiz que resolve nonogramas . Como parte da solução, eu gerei (para algumas das linhas) uma matriz de todas as maneiras possíveis de ajustar os números.

Eu quero criar um pedaço de código, que irá iterar todas as posições em que posso colocar os espaços, por exemplo: se há uma linha com tamanho 5e os números são 1, 1, existem várias maneiras de ordenar os números, como 1-1--, 1--1-, 1---1, --1-1, ...( -é uma caixa branca, enquanto 1será preta).

Análise do problema

Portanto, se olharmos o exemplo acima, podemos descrever as opções como esta:

1. O tamanho total é 5, e temos dois 1, portanto temos 2caixas brancas para brincar (1 deve estar entre os números), tenho outra função que calcula esse "espaço livre".

2. Podemos indexar os lugares possíveis para os espaços desta forma [0] 1 [1] 1 [2]:, o que significa que os espaços podem ir em cada um dos [indexes].

3. Todas as opções de colocação dos espaços podem ser resolvidas com loops aninhados, mas como o "espaço livre" e os índices possíveis são dinâmicos, esta não é uma opção.

4. Como solução, tento criar loops aninhados "dinâmicos", com qualquer alcance e profundidade, a questão é:

Existe uma maneira mais eficiente de fazer isso?

Solução possível

O escopo a que minha pergunta se refere não está relacionado especificamente à resolução de um não ortograma ou mesmo de uma linguagem específica, mas como estou escrevendo isso em C ++, postarei minha tentativa de um código que faça isso:

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

Resultado:

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 alguém estiver interessado na implementação completa, uma vez feita e totalmente documentada, irei fazer o upload para minha conta GitHub .

Agradecemos antecipadamente pelos ajudantes e comentaristas.

Answer 1

Observações Gerais

Quanto mais código você fornecer, melhores serão as revisões. Existem 2 afirmações, 1 na pergunta e 1 nos comentários após a pergunta que quase o tornam fora do tópico do site de revisão 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".

Conforme fornecido na pergunta, o código é quase ilegível e, portanto, seria um problema para manutenção. Se eu fosse um professor dando notas a este código, a melhor nota que poderia dar a ele é um C (70%) porque ele compila e executa. Os nomes das variáveis ​​são significativos. Em um ambiente profissional, se eu fosse seu gerente, teríamos uma longa conversa em particular sobre por que é importante tornar o código mais legível.

Em um ambiente profissional, é muito improvável que você seja o único a manter o código por vários motivos:

1. Você pode ser promovido e não ter mais a atribuição de manter o código.
2. Você pode pedir demissão e conseguir outro emprego.
3. Pode haver um bug no código que precisa ser corrigido e você foi designado para um projeto de prioridade mais alta, então outra pessoa será designada para corrigir o código.

Existem mais razões do que apenas as 3 acima. Por todas essas razões, abordarei o estilo de codificação aqui.

Possíveis Otimizações

A primeira regra de otimização é não otimizar, a segunda é encontrar todos os gargalos no código (gargalos sendo funções que tornam o código lento). A principal maneira de otimizar o código C ++ é usar a otimização embutida do compilador usando as linhas de comando do compilador -O a -O3. Isso geralmente produzirá um código muito rápido. Será muito difícil fornecer otimizações para este código conforme apresentado atualmente, mas se você estiver compilando para depuração, uma possível otimização pode ser usar os iteradores C ++ fornecidos para cada uma das classes de contêiner, como vector.

Você também pode querer fazer as variáveis iterators_numbere iterators_rangeconstantes, pois elas não mudam.

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

Evitar using namespace std;

Se você está programando profissionalmente, provavelmente deve abandonar o hábito de usar a using namespace std;instrução. O código definirá mais claramente de onde coute outros identificadores estão vindo ( std::cin, std::cout). À medida que você começa a usar namespaces em seu código, é melhor identificar de onde vem cada função, porque pode haver conflitos de nomes de função de diferentes namespaces. O identificador que coutvocê pode substituir em suas próprias classes e também pode substituir o operador <<em suas próprias classes. Esta questão de estouro de pilha discute isso com mais detalhes.

Declarar variável conforme necessário

Pelo que eu posso dizer, a variável move_indexnão precisa manter seu valor entre as iterações do while (true)loop, então ela deve ser declarada dentro do loop, a declaração deve incluir a inicialização da variável em quase todos os casos, mas definitivamente neste caso.

Não use uma linha forLoops ou ifDemonstrações

O código contém esta linha:

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

Na minha primeira vez através do código, perdi o fato de que o loop for tinha uma ação. Este código deve ter pelo menos 2 linhas, mas de preferência 4. 2 linhas:

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

Por que 4 linhas? Um dos erros mais fáceis de cometer ao manter o código é adicionar uma instrução a um loop for ou if sem adicionar as chaves necessárias para torná-la parte do loop. Portanto, ao criar um novo código, é melhor adicionar o para começar:

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

Não fui eu que pensei nisso, foi imposto por um padrão de codificação da empresa, no entanto, vi o valor de ter cometido esse tipo de erro várias vezes.

Esta versão do código é um pouco mais longa, mas muito mais legível e fácil de manter:

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