Skip to main content
adicionou 4 caracteres ao conteúdo
Fonte Link
jsbueno
  • 31,5mil
  • 1
  • 51
  • 70

O seu código tem dois laços para percorrer cada pixel na "matriz original", o que, por si só já é um problema para algumas aplicações - mas aí você passa a percorrer, em outros dois laços mais internos, cada pixel novamente.isso é um número de execuções de vários blocos do seu programa igual ao quadrado do seu numero de pixels - algum algoritmo que realmente precise disso, independente das otimizações tomadas, vai naturalmente consumir recursos gigantescos. Em uma simples imagem de resolução VGA 640,480 isso implica em 94_371_840_000 - 94 bilhões de execuções do bloco de código. Se fosse uma única multiplicação em código nativo poderia ser feito em cerca de 10-20 segundos em uma CPU moderna, mas são dezenas de linhas manipulando objetos bem complexos.

Mas ainda, em cada passagem desses dois laços mais internos, você recria totalmente a "matriz_segmentada" - o que indica que provavelemente você tem uma falha em como escreveu esse algoritmo - você precida realmente percorrer todos os pixels para cada pixel?? (e se precisar, o programa está incorreto).

A parte desse processamento, aninhado, algumas dicas gerais sobre programação numérica com Python:

AlgmasAlgumas considerações gerais

Algmas considerações

O seu código tem dois laços para percorrer cada pixel na "matriz original", o que, por si só já é um problema para algumas aplicações - mas aí você passa a percorrer, em outros dois laços mais internos, cada pixel novamente.isso é um número de execuções de vários blocos do seu programa igual ao quadrado do seu numero de pixels - algum algoritmo que realmente precise disso, independente das otimizações tomadas, vai naturalmente consumir recursos gigantescos. Em uma simples imagem de resolução VGA 640,480 isso implica em 94_371_840_000 - 94 bilhões de execuções do bloco de código. Se fosse uma única multiplicação em código nativo poderia ser feito em cerca de 10-20 segundos em uma CPU moderna, mas são dezenas de linhas manipulando objetos bem complexos.

Mas ainda, em cada passagem desses dois laços mais internos, você recria totalmente a "matriz_segmentada" - o que indica que provavelemente você tem uma falha em como escreveu esse algoritmo - você precida realmente percorrer todos os pixels para cada pixel?? (e se precisar, o programa está incorreto).

A parte desse processamento, aninhado, algumas dicas gerais sobre programação numérica com Python:

Algumas considerações gerais

adicionou 4 caracteres ao conteúdo
Fonte Link
jsbueno
  • 31,5mil
  • 1
  • 51
  • 70
class Img:
    def __init__(self, altura, largura):
        self.altura = altura
        self.largura = largura
        self.dados = [0] * largura * altura
    def __getitem__(self, pos):
        return self.dados[pos[0] + pos[1] * self.largura]
    def __setitem__(self, pos, valor):
        self.dados[pos[0] + pos[1] * largura] = valor
    def repr__repr__(self):
        return f"Img <{self.largura} x {self.altura}>"
class Img:
    def __init__(self, altura, largura):
        self.altura = altura
        self.largura = largura
        self.dados = [0] * largura * altura
    def __getitem__(self, pos):
        return self.dados[pos[0] + pos[1] * self.largura]
    def __setitem__(self, pos, valor):
        self.dados[pos[0] + pos[1] * largura] = valor
    def repr(self):
        return f"Img <{self.largura} x {self.altura}>"
class Img:
    def __init__(self, altura, largura):
        self.altura = altura
        self.largura = largura
        self.dados = [0] * largura * altura
    def __getitem__(self, pos):
        return self.dados[pos[0] + pos[1] * self.largura]
    def __setitem__(self, pos, valor):
        self.dados[pos[0] + pos[1] * largura] = valor
    def __repr__(self):
        return f"Img <{self.largura} x {self.altura}>"
Fonte Link
jsbueno
  • 31,5mil
  • 1
  • 51
  • 70

Algmas considerações

Na teoria o seu código pode estar correto. Mas na prática, para código que realmente funciona, ele está bem longe de ser funcional.

Python é uma linguagem de muito alto-nível - como tal, fica simples escrever código como o que você quer: a linguagem não fica entre você e o problema - você lê os dados de uma imagem, tem eles num objeto que se comporta como uma matriz bidimensional, aí você usa o que aprendeu em programação e faz dois laços com a altura e largura da imagem, e pode acessar os valores de cada pixel. O código equivalente em C exigiria varios passos extras, e não triviais, incluindo escolher uma biblioteca de imagem, e etc...

Só que ele seria executado cerca de cem a mil vezes mais rápido que esse seu código. Possivelmente até mais uma ou duas ordens de grandeza, por conta de algumas especificidades aí.

Então - quando fazemos esses exercícios na lousa, ou numa página do caderno, tudo bem pensar na imagem como uma matriz - ela vai ter 5 x 5 elementos, no máximo 10 x 10, e a teoria fica bem bonita.

Seu código está incorreto em dois níveis bem distintos: O primeiro é quase que só estético: mesmo para algoritmos implementados 100% em Python, incluindo todas as operações, raramente, quase nunca, em Python se usam laços for com valores numéricos obtidos a partir do comprimento de objetos. Isso por que o for do Python, ao contrário de outras linguagens, é especializado em percorrer sequências - os conteúdos das sequências, não os seus itens! (Em programação genéricamente isso é pensado como um "for each"). Quando o índice, além do conteúdo, é necessário, a construção em geral não é for index in range(len(sequencia)): mas sim for index, content in enumerate(sequencia): - essa segunda forma recupera duas variáveis de uma vez em cada passagem do laço: o índice, e o conteúdo correspondente.

Arrumar os seus laços para algo do tipo, mais o estilo de identação para usar 4 espaços em vez de 8, e várias outras coisinhas, poderia deixar seu código, além de mais apresentável, talvez umas 2 vezes mais rápido. (E uma dica final de legibilidade, evite a todos os custos uma variável chamada simplesmente de "l" - é bem difícil distingui-la de "1" em vários contextos - você gasta energia mental nessa distinção que tem melhor uso em outras frentes)

Mas aí entra o segundo nível em que seu programa está pensado de forma errada -

Na linguagem Python, tudo são objetos - inclusive os números inteiros. O que quer dizer que o overhead para construir um número inteiro na linguagem é considerável - o runtime da linguagem tem que alocar memória, inicializar uma área de dados, manter uma contagem de referências para o número, etc... . Mais ainda, Python é uma linguagem que permite que os objetos sejam "refeitos" e aceita sobrecarga dinâmica de operadores. A implicação disso é que qualquer operação em um objeto Python - seja uma soma, seja recuperar um elemento de uma lista, internamente é equivalente a chamar uma função. Pode ser uma função em Python, ou uma função altamente otimizada em código nativo, no caso de se obter um elemento de uma lista - mas ainda assim, vai haver uma mudança de contexto na CPU, etc... .

Mas, se é assim, como é que Python é tão popular para manipulação de dados e imagens e etc?

Seguinte: tudo o que envolve processamento e repetição em Python deve ser escrito de forma a usar o máximo de código nativo possível. Para matrizes maiores que "uso em quadro branco" (incluindo imagens reais), se usa a biblioteca NumPy, por exemplo.

Então, para você ter uma ideia, esta linha de código:

 matriz_segmentada = [[0 for x in range(altura)] for y in range(largura)]

Vai chamar a função interna __next__ do objeto devolvido por range(altura) uma vez para cada pixel - e para cada linha da imagem, vai criar um novo objeto do tipo lista. Para uma imagem de 640, 480 o prompt interativo nos deixa calcular o tempo:

In [57]: altura, largura = 640, 480

In [61]: %time matriz_segmentada = [[0 for x in range(altura)] for y in range(largura)]
CPU times: user 34 ms, sys: 903 µs, total: 34.9 ms
Wall time: 34 ms

34 milisegundos - parece pouco, mas se fosse um jogo, por exemplo, seria um framerate sofrível, em uma resolução bem baixa, apenas para apagar toda a tela.

Exemplo de objeto "matriz" em Python "bonitinho":

Se eu crio uma classe especializada que mantenha todos os dados numa lista linear na memória, e me permita acessar os dados individuais customizando o operador de acesso [] implementando o método __getitem__, isso já ficaria consideravelmente melhor. Isso seria o um nível intermediário - e usando Python puro talvez permitisse um ganho de até 5x no tempo do seu código. Se você não conseguir "vetorizar" os algoritmos de que precisa usando Numpy, pode usar uma abordagem como essa e a extensão "cython" que permite otimizar código Python como código nativo - isso poderia de tar um ganho de umas 3 ou 4 ordens de grandeza.

Exemplo em Python puro, ainda usando listas e inteiros normais:

class Img:
    def __init__(self, altura, largura):
        self.altura = altura
        self.largura = largura
        self.dados = [0] * largura * altura
    def __getitem__(self, pos):
        return self.dados[pos[0] + pos[1] * self.largura]
    def __setitem__(self, pos, valor):
        self.dados[pos[0] + pos[1] * largura] = valor
    def repr(self):
        return f"Img <{self.largura} x {self.altura}>"

Esse código evita os laços pixel-a-pixel para criar a matriz vazia, simplesmente multplicando pelo número de pixels uma lista criada com um elemento "0" inicial. O tempo para criação do mesmo objeto passa a:

In [64]: %time Img(640, 480)
CPU times: user 2.54 ms, sys: 0 ns, total: 2.54 ms
Wall time: 2.59 ms
Out[64]: <__main__.Img at 0x7f35c8f81668>

3 ms - um ganho de uma ordem de grandeza e código que pode ficar muito mais sintético do que o que você usou:

In [65]: img = Img(640, 480)

In [66]: img[100, 100] = 255

In [67]: img[99,100]
Out[67]: 0

In [68]: img[100, 100]
Out[68]: 255

Ok, mas isso é perfumaria - infelizmente, apesar da elegância que Python permite para esse tipo de objetos com classes personalizadas, esse código não teria um ganho de velocidade tão grande comparado com o seu.

Exemplo usando NumPy

O que realmente se faz em programas "para produção" é: criar os dados como uma matriz do Numpy - além de ter funcionalidade otimizada para processar elemento-a-elemento num laço interno, usando código nativo, os valores em cada célula de uma matriz do Numpy podem ser escolhidos dentre os tipos de dados nativos da máquina. Então a economia de memória e tempo para criação e manipulação dos dados passa a ser ordens de grandeza maior:

In [69]: import numpy as np

In [70]: %time img_numpy = np.zeros((640, 480), dtype=np.float64)
CPU times: user 232 µs, sys: 31 µs, total: 263 µs
Wall time: 196 µs

In [71]: img_numpy[100,100]
Out[71]: 0.0

O tempo anterior de 3ms da minha classe customizada agora é de 0.2ms (196 µs). Uma outra ordem de grandeza de ganho - mais outra ordem de grandeza no uso de memória, uma vez que números "float" do Python sendo objetos Python ocupam cerca de 80 bytes cada (o valor "0" inteiro dos exemplos acima no entanto é reutilizado - medir a memória usada por essas estruturas não é tão trivial). O numpy, nesse caso, usa valores em ponto flutuante de 64bit: 8 bytes por pixel. Se os seus algoritmos vão usar apenas inteiros entre 0 e 255, é só usar dtype=np.uint8 acima, e uso de memória cai mais uma ordem de grandeza, para 1byte/pixel

Mas mais que o tempo de criação - vamos para a lista-de-listas, classe especializada,e matriz no numpy, aplicar uma operação que some "1" ao valor de cada pixel. Observe os tempos:

matriz usando lista de listas:

In [72]: img_lista = [[0 for x in range(altura)] for y in range(largura)]

In [73]: def add_1(img_lista):
    ...:     for x, col in enumerate(img_lista):
    ...:         for y, value in enumerate(img_lista):
    ...:             col[y] += 1
    ...:             

In [74]: %time add_1(img_lista)
CPU times: user 43.5 ms, sys: 3.91 ms, total: 47.4 ms
Wall time: 43.5 ms

In [75]: img_lista[100][100]
Out[75]: 1

Usando a classe especializada 'Img' acima:

In [76]: img = Img(640, 480)

In [77]: %time for index, value in enumerate(img.dados): img.dados[index] += 1
CPU times: user 70.2 ms, sys: 4.72 ms, total: 74.9 ms
Wall time: 71.6 ms

Observe que ficou na verdade mais lento que a lista de listas - por conta de detalhes de implementação de como o acesso a atributos é implementado.

# Usando o numpy:

In [78]: img_numpy = np.zeros((640, 480), dtype=np.float64)

In [79]: %time img_numpy += 1
CPU times: user 1.44 ms, sys: 4.81 ms, total: 6.25 ms
Wall time: 4.88 ms

In [80]: img_numpy[100, 100]
Out[80]: 1.0

Pronto - o Numpy faz uma sobrecarga do operador += para seus tipos matrizes (a documentação sempre chama de 'arrays'), de forma que todos os laços são executados em tipo nativo - a operação que altera todos os pixels agora é executada em menos de 5 milisegundos.

esse tipo de operação do Numpy, onde se evita um for explícito em Python é chamado de "broadcast" na docuemtnação do Numpy - o ideal é conseguir re-escrever o máximo de seus algoritmos para fazer uso disso. É praticamente uma "super-linguagem" a ser aprendida por cima da linguagem Python, mas vale a pena.

Praticamente todo o uso de Python nos domínios de ciência, análise de dados (big data) e aprendizagem de máquina tem como base o NumPy - então não é "só mais uma biblioteca" - é praticamente parte da linguagem.

A documentação está no site oficial do NumPy - dúvidas amis específicas que você venha a ter ao converter o seu programa podem ser melhor esclarecidas em novas perguntas.