0

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?

11
  • 2
    Se a performance é necessária, seria melhor não usar Python. :P As próprias bibliotecas de Python que exigem isso não são implementadas em Python, mas sim em C, C++, Fortran, etc. O Python fica apenas de "cola". Commented 26/11/2023 às 23:18
  • 1
    A complexidade de tempo desse algoritmo é O(n). Veja pt.stackoverflow.com/q/33319/137387 Commented 27/11/2023 às 1:34
  • 1
    Na pergunta está escrito "...se as operações forem realizadas diretamente no registrador, isto é: em tempo O(1), tal como em C, C++, etc...." O código dentro do laço está condicionado a subtração então mesmo que tente aceleração vetorial SIMD ou uso de GPU o código continuará a iterar. Commented 27/11/2023 às 1:48
  • 1
    Eu pensei assim, em for i in range(10**5): você tem 10**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 linha value -= 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. Commented 27/11/2023 às 2:09
  • 1
    Quanto a demora que percebeu individualmente nas operações em Python com relação ao C/C++ é resultado de como o Python interpreta o loop. Ele interpreta o fonte em bytecode, porém adiciona variáveis de controle para testar a consistência do código interpretado a cada iteração o que o torna mais lento que o equivalente compilado. Commented 27/11/2023 às 2:21

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .