Talvez o título da questão não reflita com clareza o problema, mas é o seguinte: eu desenvolvi um algoritmo eficiente para um problema muito específico, que realiza varias operações aritméticas básicas, e que só funciona eficientemente se as operações forem realizadas diretamente no registrador, isto é: em tempo O(1)
, tal como em C, C++, etc... Parte do código de exemplo:
for i in range(10**5):
# Realiza o shift do valor.
value -= data[i - m] * d
value *= base
# Soma o dígito à última casa.
value = round(value + data[i])
Como vocês podem ver, é um código bem simples, nada demais. No momento, estou tentando implementá-lo em Python, contudo ele se apresenta absurdamente lento na linguagem.
Estou utilizando como métrica a comparação do seu tempo de execução com o tempo de um outro algoritmo que possui uma complexidade muito maior.
Abaixo uma amostra dos resultados:
$ meu_algoritmo_em_cpp.exe
Tempo de execução: 0.82s
$ algoritmo_de_maior_complexidade_em_cpp.exe
Tempo de execução: 1.73s
$ python meu_algoritmo_em_python.py
Tempo de execução: 13.71s
$ python algorito_de_maior_complexidade_em_python.py
Tempo de execução: 4.37s
Eu entendo que o motivo dessa lentidão é que Python possui uma camada de implementação por trás dos tipos int
e float
, exemplo: nós podemos gerar números absurdamente grandes com eles. Então certamente não é mais uma opção tentar algo com eles.
Pesquisando por soluções, eu encontrei algumas postagens que sugeriam utilizar Cython. Porém mesmo utilizando os seus tipos, tal como cython.int
e cython.longlong
, não houve diferença. Na verdade, parece que até aumentou o tempo. Exemplo:
# Antes de executar o algoritmo, converti tudo para os tipos do Cython.
# O tempo dessa conversão não foi computado para o resultado final.
value = cython.longlong(value)
base = cython.int(base)
data = [cython.int(v) for v in data]
...
Dito isso, existe alguma forma de realizar operações aritméticas diretamente nos registradores, em Python, ou pelo menos diminuir o tempo das operações?
for i in range(10**5):
você tem10**5
pacotes de operações aritméticas. Para obter algum ganho de processamento você poderia fazer com que a execução de algum desses pacotes de operações aritméticas fossem realizados em paralelo tirando vantagem do hardware, ou com vetoração SIMD ou paralelismo GPU, mas como esses pacotes contém a linhavalue -= data[i - m] * d
a subtração-=
impediria esse tipo de abordagem pois a resolução de qualquer um desses pacotes de operações(exceto o primeiro) é dependente do resultado do pacotes de operações anterior.