Finalizando o cálculo do Numpy antecipadamente

O numpy tem uma operação de "rescisão antecipada" que interromperá as operações numpy antecipadamente se elas atingirem uma condição?

Simplificando, não, Numpy não. Na prática, isso é um pouco mais complexo do que isso.

Na verdade, a função allfuncand anyfuncque você propõe é semelhante a np.alland np.any. Essa função faz algum tipo de rescisão antecipada. Aqui está uma prova na minha máquina:

v = np.random.randint(0, 2, 200*1024*1024) > 0

# 2.74 ms ± 61.5 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit -n 10 v.all()

# 3.16 ms ± 46.5 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
v[0:v.size//16] = True
%timeit -n 10 v.all()

# 3.72 ms ± 77.7 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
v[0:v.size//8] = True
%timeit -n 10 v.all()

# 4.64 ms ± 80.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
v[0:v.size//4] = True
%timeit -n 10 v.all()

# 6.67 ms ± 127 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
v[0:v.size//2] = True
%timeit -n 10 v.all()

# 10.5 ms ± 69.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
v[0:v.size] = True
%timeit -n 10 v.all()

O primeiro é tão rápido que não pode iterar por todo o array, já que a taxa de transferência da memória atingiria 71 GiB/s, enquanto minha RAM só pode atingir a largura de banda máxima teórica de 47,7 GiB/s (cerca de 40 GiB/s na prática). Meu cache de CPU está longe de ser grande o suficiente para armazenar uma parte significativa desse array e o array ocupa 200 MiB de RAM, então cada booleano ocupa 1 byte de RAM. Estranhamente, a velocidade alle anyé bastante decepcionante no primeiro caso, pois v[2]é Falsena prática. Numpy certamente executa o cálculo pedaço por pedaço e executa o encerramento antecipado somente após calcular um pedaço (se necessário).

O problema com anye allé que eles exigem uma matriz booleana no parâmetro. Assim, a matriz booleana precisa ser totalmente computada primeiro, anulando o benefício de qualquer encerramento antecipado .

Alternativamente, Numpy fornece ufuncs que são projetados para operar em arrays elemento por elemento. Um exemplo de ufunc é np.ufunc.reduce. Eles poderiam ser usados ​​para compor algoritmos de tal forma que o encerramento antecipado seria teoricamente possível. Esta solução seria significativamente mais rápida do que as operações normais não ufunc quando o encerramento é possível bem cedo. No entanto, quando o encerramento só é possível ultimamente, o ufuncs seria muito mais lento do que as operações não-ufunc. Na verdade, os ufuncs são (atualmente) fundamentalmente ineficientes em comparação com as operações não-ufunc. Isso ocorre porque os ufuncs exigem uma chamada de função cara (nativa) por item. Esta chamada de função, aplicada em itens escalares, evita diversas otimizações críticas como o uso deInstruções SIMD . Ainda assim, ufuncs muitas vezes pode ser mais rápido do que usar código Python puro elemento por elemento, graças a "vectorization" . A maneira atual como os ufuncs podem ser compostos é que o AFAIK não é suficiente, no seu caso de uso, para escrever um código eficiente que se beneficie do encerramento antecipado.

A maneira padrão de encerrar antecipadamente no Numpy é dividir o cálculo em vários pedaços (manualmente). Essa solução geralmente é rápida porque é vetorizada, geralmente compatível com SIMD e eficiente em cache (assumindo que os pedaços sejam pequenos o suficiente). A sobrecarga do Numpy é pequena, desde que os pedaços sejam grandes o suficiente. Aqui está um exemplo:

def compute_by_chunk(A, B):
    chunkSize = 256
    for i in range(0, A.size, chunkSize):
        for j in range(0, B.size, chunkSize):
            C = np.cross(A[i:i+chunkSize,None,:], B[None,j:j+chunkSize,:])
            if not C.all():
                # print(f'Zero found in chunk ({i},{j})')
                return True
    return False

Para o seu exemplo de entrada, são necessários 239 µs na minha máquina, enquanto a implementação ingênua do Numpy leva 234 ms. Isso é cerca de 1000 vezes mais rápido neste caso. Com pedaços menores, como 32x32, o cálculo é ainda mais rápido: 32,3 µs.

Na verdade, pedaços menores são melhores quando há muitos zeros (já que leva tempo para calcular o primeiro pedaço). 256x256 deve ser relativamente bom na maioria das máquinas (bastante amigável ao cache, eficiente em termos de memória e com baixa sobrecarga Numpy).

Uma solução mais simples (que geralmente também é mais rápida) é usar módulos/ferramentas, como Cython ou Numba , compilando seu código para que os loops possam ser rápidos graças à compilação para funções nativas. No entanto, com esta solução, você mesmo precisa reimplementar o produto vetorial. Na verdade, o Numba ainda não oferece suporte e o Cython não será mais rápido (do que um código Python puro usando Numpy) se você apenas chamar funções Numpy em loops.