Loops Custosos

Programação Python
#1

Depois do canivete suíço apresentado pelo professor/escritor, aprendi algumas outras ferramentas, como o zip():
https://replit.com/@LeandroCGMS/LoopsCustosos#exemplo_zip.py


Bom dia.
Me deparei com um exercício, no qual, pede para mostrar todos os quadrados mágicos de 123.456.789 a 1.000.000.000, um bilhão, isto usando uma lista. Como eu estava usando prints para cada quadrado mágico dentro do loop, cheguei a conclusão que o problema era limitar a velocidade do loop pela taxa de atualização do monitor, reduzindo em milhões de vezes a velocidade, mas mesmo depois de ter retirado estes prints e apenas incrementado uma string, o loop permanece lento. Eu sei que o uso de fórmulas pode reduzir, em n vezes, os ciclos de repetição, porém partindo do princípio que é necessário fazer os quase 1 bilhão de repetições, gostaria de saber se é possível tornar este loop não custoso.
Observação, já levo em consideração o fato de linguagens de mais baixo nível serem mais rápidas, algo entre 100 a 400 vezes. Nos meus testes, para um loop apenas para chegar ao final, sem fazer nada, há pouca diferença de segundos, entre C e Python, e não são custosos apenas para contar.

#2

o que seria isso?

1 curtida
#3
#4

O problema é quando faz algo.
O processamento tem a ver muito mais com algorítimos que com o nivel em sí da linguagem, mas claro que o nivel não deve ser desconsiderado.

1 curtida
#5

Usei apenas lista para armazenar as listas com quadrados mágicos dentro da sequência e como são apenas poucos quadrados, não ocupa muita memória.
Não achei algo que justifique esta lentidão, como exemplo, poderia citar um armazenamento em memória RAM acima da capacidade dela, mas são poucas listas a serem armazenadas em outra.
Ademais, incremento uma string com estes poucos resultados. São menos de 10 linhas.

#6

Então a questão é o processamento mesmo.
Usando graalvm.org voce iguala ou até supera a linguagem C.
É multi linguagem e aceita o Python.

2 curtidas
#7

Quero poder concordar com você, mas e se eu ainda desconheço algum detalhe em relação a loops serem custosos, não sei. Acrescento, aqui, e, na primeira mensagem deste post, o código fonte em Python: https://repl.it/@LeandroCGMS/LoopsCustosos

#8

Depende do que você quer considerar como quadrado mágico. Por exemplo, esse aqui é:

1 1 1
1 1 1
1 1 1

Mas esses são considerados “triviais”, e dependendo de para quem você pergunta, nem é considerado tão mágico assim.

Se for para buscar todos esses em que pode ter números repetidos, aí não tem jeito, tem que buscar um a um mesmo (talvez exista algum “truque” matemátco para excluir alguns, não sei).

Mas se a ideia é buscar apenas os quadrados em que todos os números são diferentes, aí fica um pouco mais simples, pois basta pegar a string inicial e gerar todas as permutações dela (no caso de 9 dígitos, serão apenas 362.880 possibilidades para testar):

from itertools import permutations

def mostrar_quadrados_magicos(vetor):
    intervals = [ # somente para quadrados 3x3
      # linhas (exceto a primeira)
      [3, 4, 5], [6, 7, 8],
      # colunas
      [0, 3, 6], [1, 4, 7], [2, 5, 8],
      # diagonais
      [0, 4, 8], [2, 4, 6]
    ]
    results = []
    for digitos in permutations(vetor):
        novo_vetor_inteiro = list(map(int, digitos))
        # soma da primeira linha
        soma = sum(novo_vetor_inteiro[0:3])
        # se todos os intervalos tem a mesma soma da primeira linha, é mágico
        if all(soma == sum(novo_vetor_inteiro[i] for i in interval) for interval in intervals):
            results.append(f'{" ".join(digitos[0:3])}\n{" ".join(digitos[3:6])}\n{" ".join(digitos[6:])}\n\n')
    return ''.join(results)
    
print(mostrar_quadrados_magicos('123456789'))

Além disso, eu guardei as strings resultantes em uma lista, e só juntei no final com join (juntar tudo apenas uma vez costuma ser mais rápido do que concatenar várias strins em um loop). E claro, como eu reduzi drasticamente a quantidade de iterações, ficou bem mais rápido.

Mas como já dito, se você quer verificar também os casos que têm números repetidos, aí não tem jeito, tem que verificar um a um.

Lembrando que o código acima só funciona para quadrados 3x3. Para aceitar qualquer tamanho, aí teria que ajustar os intervalos e a formatação do resultado.

1 curtida
#9

É possível utilizar este iterador com as regras deste exercício 14, no qual só pode usar uma lista com números de 1 a 9? https://wiki.python.org.br/ExerciciosFuncoes

#10

Sim, só muda um pouco na hora de imprimir (pois join só aceita strings, então vc tem que converter os números para string), mas o resto é igual:

def mostrar_quadrados_magicos(vetor):
    intervals = [ # somente para quadrados 3x3
      # linhas (exceto a primeira)
      [3, 4, 5], [6, 7, 8],
      # colunas
      [0, 3, 6], [1, 4, 7], [2, 5, 8],
      # diagonais
      [ 0, 4, 8], [2, 4, 6]
    ]
    results = []
    for digitos in permutations(vetor):
        novo_vetor_inteiro = list(map(int, digitos))
        # soma da primeira linha
        soma = sum(novo_vetor_inteiro[0:3])
        # se todos os intervalos tem a mesma soma da primeira linha, é mágico
        if all(soma == sum(novo_vetor_inteiro[i] for i in interval) for interval in intervals):
            results.append(f'{" ".join(map(str, digitos[0:3]))}\n{" ".join(map(str, digitos[3:6]))}\n{" ".join(map(str, digitos[6:]))}\n\n')
    return ''.join(results)

Aí você pode chamar de qualquer um dos jeitos:

print(mostrar_quadrados_magicos('123456789'))
print(mostrar_quadrados_magicos([1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(mostrar_quadrados_magicos(range(1, 10))) # todos os números de 1 a 9
1 curtida
#12

Muito obrigado, professor.
Quero te perguntar algo que penso acrescentar a este conhecimento, mas se não querer responder, já ajudou muito. Percebi este módulo itertools como uma caixa de ferramentas economizadoras de linhas e tempo, mas acho que num loop de um a um bilhão, por exemplo, o tempo gasto seria igual. Estou errado?

#13

Se a quantidade de iterações for muito grande, vai demorar de qualquer jeito.

Por exemplo, se fosse um quadrado 4x4, teria que usar uma lista com 16 números, e permutations geraria mais de 20 trilhões de combinações. Isso ia demorar muito, independente de usar itertools ou não.

O que o itertools economiza é na memória, pois ele não gera todas as permutações de uma vez, e sim sob demanda (a cada iteração do loop ele gera uma e depois descarta). Mas se a quantidade for grande, demora do mesmo jeito…

1 curtida