Início / coding / Perguntas / 77589188
Accepted
scribe
Asked: 2023-12-02 12:49:54 +0800 CST

Classificando inteiros não negativos em tempo linear usando quebras Numba

  • 772

Estou tentando classificar uma matriz/lista de números inteiros não negativos em tempo linear. Também mantemos apenas os elementos únicos. Aqui está um exemplo,

Sort: [7, 7, 0, 3, 2, 1, 9, 1]

7: 10000000
7: 10000000
0: 10000001
3: 10001001
2: 10001101
1: 10001111
9: 1010001111
1: 1010001111

1010001111: []
101000111: [0]
10100011: [0, 1]
1010001: [0, 1, 2]
101000: [0, 1, 2, 3]
10100: [0, 1, 2, 3]
1010: [0, 1, 2, 3]
101: [0, 1, 2, 3]
10: [0, 1, 2, 3, 7]
1: [0, 1, 2, 3, 7]
: [0, 1, 2, 3, 7, 9]

Essencialmente, estou implementando np.unique([7, 7, 0, 3, 2, 1, 9, 1])em tempo linear. Aqui está meu Python,

import numpy as np
from time import perf_counter
from numba import njit

# @njit
def count(ls):
    ret = []
    m = 0
    for x in ls:
        m = m | (1 << int(x))
    i = 0
    while m > 0:
        if (m & 1):
            ret.append(i)
        m = m >> 1
        i += 1
    return ret

RNG = np.random.default_rng(0)

x = RNG.integers(2**16, size=2**17)
start = perf_counter()
y1 = np.unique(x)
print(perf_counter() - start)
start = perf_counter()
y2 = count(x)
print(perf_counter() - start)
print((y1 == y2).all())

Minha classificação "O (n)" não superou a função exclusiva do Numpy. Eu esperava que, como o Python fosse mais lento que o C (que é onde np.uniqueé implementado, suponho). Para remediar isso, tentei usar o decorador JIT do Numba. Mas - se eu descomentar o decorador, de alguma forma a função quebra e retorna uma lista vazia. Funciona sem o decorador.

Alguém pode apontar meu descuido?

python

2 respostas

  1. Best Answer

    Python usa inteiros de precisão arbitrária para representar todos os inteiros. Isso geralmente é útil, mas tem a desvantagem de ser lento. Para tornar isso mais rápido, o Numba usa inteiros assinados de 64 bits.

    Uma das consequências disso é que 1 << 63 é um número negativo em Numba.

    O programa de teste a seguir mostrará isso.

    from numba import njit


@njit
def shift(amount):
    return 1 << amount


for i in range(66):
    print(i, hex(shift(i)))

    Então, while m > 0:sai imediatamente. É por isso que a versão numba fornece uma lista vazia e também porque isso não funciona corretamente em geral se você tiver mais de 64 números.

    • 0

  2. Lembre-se de que a melhoria de desempenho nem sempre é significativa, pois a função exclusiva do NumPy é altamente otimizada e escrita em C.

    • 0

relate perguntas