Por que as matrizes do Python são lentas?

153

Eu esperava array.arrayser mais rápido que as listas, pois as matrizes parecem estar fora da caixa.

No entanto, recebo o seguinte resultado:

In [1]: import array

In [2]: L = list(range(100000000))

In [3]: A = array.array('l', range(100000000))

In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop

In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop

In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop

In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop

Qual poderia ser a causa dessa diferença?

Valentin Lorentz
fonte
4
ferramentas numpy pode explorar eficazmente a sua matriz:% timeit np.sum (A): 100 malhas, melhor de 3: 8,87 ms por ciclo
BM
6
Nunca me deparei com uma situação em que precisei usar o arraypacote. Se você deseja fazer quantidades significativas de matemática, o Numpy opera na velocidade da luz (ou seja, C), e geralmente melhor do que implementações ingênuas de coisas como sum()).
Nick T
40
Eleitores próximos: Por que exatamente isso é baseado em opiniões? O OP parece estar fazendo uma pergunta técnica específica sobre um fenômeno mensurável e repetível.
22416 Kevin
5
@NickT Read Uma anedota de otimização . Acontece que arrayé muito rápido na conversão de uma sequência de números inteiros (representando bytes ASCII) em um strobjeto. O próprio Guido só conseguiu isso depois de muitas outras soluções e ficou bastante surpreso com o desempenho. Enfim, este é o único lugar em que me lembro de vê-lo sendo útil. numpyé muito melhor para lidar com matrizes, mas é uma dependência de terceiros.
Bakuriu

Respostas:

220

O armazenamento está "fora da caixa", mas toda vez que você acessa um elemento, o Python precisa "encaixotá-lo" (incorporá-lo em um objeto Python comum) para fazer qualquer coisa com ele. Por exemplo, você sum(A)itera sobre a matriz e encaixa cada número inteiro, um de cada vez, em um intobjeto Python comum . Isso custa tempo. No seu sum(L), todo o boxe foi feito no momento em que a lista foi criada.

Portanto, no final, uma matriz geralmente é mais lenta, mas requer substancialmente menos memória.


Aqui está o código relevante de uma versão recente do Python 3, mas as mesmas idéias básicas se aplicam a todas as implementações do CPython desde que o Python foi lançado.

Aqui está o código para acessar um item da lista:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

Há muito pouco: somelist[i]apenas retorna o i'ésimo objeto na lista (e todos os objetos Python no CPython são ponteiros para uma estrutura cujo segmento inicial está em conformidade com o layout de a struct PyObject).

E aqui está a __getitem__implementação para um arraycódigo de tipo l:

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

A memória bruta é tratada como um vetor de C longnúmeros inteiros nativos da plataforma ; o ith C longé lido; e então PyLong_FromLong()é chamado para quebrar ("box") o nativo C longem um longobjeto Python (que, no Python 3, que elimina a distinção do Python 2 entre inte long, é realmente mostrado como tipo int).

Esse boxe precisa alocar nova memória para um intobjeto Python e pulverizar os C longbits do nativo nele. No contexto do exemplo original, a vida útil desse objeto é muito curta (apenas o tempo suficiente para sum()adicionar o conteúdo a um total em execução) e, em seguida, é necessário mais tempo para desalocar o novo intobjeto.

É daí que a diferença de velocidade vem, sempre veio e sempre virá na implementação do CPython.

Tim Peters
fonte
87

Para adicionar à excelente resposta de Tim Peters, as matrizes implementam o protocolo de buffer , enquanto as listas não. Isso significa que, se você estiver escrevendo uma extensão C (ou o equivalente moral, como escrever um módulo Cython ), poderá acessar e trabalhar com os elementos de uma matriz muito mais rapidamente do que qualquer coisa que o Python possa fazer. Isso fornecerá melhorias consideráveis ​​na velocidade, possivelmente bem acima de uma ordem de magnitude. No entanto, ele tem várias desvantagens:

  1. Agora você está escrevendo C em vez de Python. Cython é uma maneira de melhorar isso, mas não elimina muitas diferenças fundamentais entre os idiomas; você precisa estar familiarizado com a semântica C e entender o que está fazendo.
  2. A API C do PyPy funciona até certo ponto , mas não é muito rápida. Se você está direcionando o PyPy, provavelmente deve escrever um código simples com listas regulares e deixar o JITter otimizá-lo para você.
  3. As extensões C são mais difíceis de distribuir do que o código Python puro, porque precisam ser compiladas. A compilação tende a depender da arquitetura e do sistema operacional; portanto, você precisará garantir que está compilando para sua plataforma de destino.

Indo direto para extensões C pode estar usando uma marreta para golpear uma mosca, dependendo do seu caso de uso. Você deve primeiro investigar o NumPy e verificar se ele é poderoso o suficiente para fazer qualquer matemática que você esteja tentando fazer. Também será muito mais rápido que o Python nativo, se usado corretamente.

Kevin
fonte
10

Tim Peters respondeu por que isso é lento, mas vamos ver como melhorá- lo.

Seguindo o seu exemplo de sum(range(...))(fator 10 menor que o seu exemplo para caber na memória aqui):

import numpy
import array
L = list(range(10**7))
A = array.array('l', L)
N = numpy.array(L)

%timeit sum(L)
10 loops, best of 3: 101 ms per loop

%timeit sum(A)
1 loop, best of 3: 237 ms per loop

%timeit sum(N)
1 loop, best of 3: 743 ms per loop

Dessa forma, o numpy também precisa encaixotar / descompactar, o que tem sobrecarga adicional. Para torná-lo mais rápido, é necessário permanecer dentro do código c numpy:

%timeit N.sum()
100 loops, best of 3: 6.27 ms per loop

Portanto, da solução da lista para a versão numpy, esse é um fator 16 no tempo de execução.

Vamos também verificar quanto tempo a criação dessas estruturas de dados leva

%timeit list(range(10**7))
1 loop, best of 3: 283 ms per loop

%timeit array.array('l', range(10**7))
1 loop, best of 3: 884 ms per loop

%timeit numpy.array(range(10**7))
1 loop, best of 3: 1.49 s per loop

%timeit numpy.arange(10**7)
10 loops, best of 3: 21.7 ms per loop

Vencedor claro: Numpy

Observe também que a criação da estrutura de dados leva tanto tempo quanto a soma, se não mais. A alocação de memória está lenta.

Uso de memória daqueles:

sys.getsizeof(L)
90000112
sys.getsizeof(A)
81940352
sys.getsizeof(N)
80000096

Portanto, esses dados levam 8 bytes por número, com sobrecarga variável. Para o intervalo que usamos, as entradas de 32 bits são suficientes, para que possamos guardar alguma memória.

N=numpy.arange(10**7, dtype=numpy.int32)

sys.getsizeof(N)
40000096

%timeit N.sum()
100 loops, best of 3: 8.35 ms per loop

Mas acontece que a adição de ints de 64 bits é mais rápida que a de 32 bits na minha máquina, então isso só vale a pena se você estiver limitado pela memória / largura de banda.

Robin Roth
fonte
-1

observe que 100000000é igual a 10^8não 10^7, e meus resultados são os seguintes:

100000000 == 10**8

# my test results on a Linux virtual machine:
#<L = list(range(100000000))> Time: 0:00:03.263585
#<A = array.array('l', range(100000000))> Time: 0:00:16.728709
#<L = list(range(10**8))> Time: 0:00:03.119379
#<A = array.array('l', range(10**8))> Time: 0:00:18.042187
#<A = array.array('l', L)> Time: 0:00:07.524478
#<sum(L)> Time: 0:00:01.640671
#<np.sum(L)> Time: 0:00:20.762153
S. Cheraghifar
fonte