11

Em Python qualquer tipo de array é do tipo da classe list, veja:

array = ['Gato', 'Jake', 'Finn']
print(type(array))

Saída:

<class 'list'>

Ou seja, todo array é um objeto de list. No entanto, há uma questão que eu sempre tive na minha mente, que seria a forma que o Python trata um array internamente, e qual seria o tipo de estrutura de dados que a classe list usa para guardar os valores do array.

Sendo assim, eu gostaria de ter minhas dúvidas esclarecidas.

Dúvidas

  1. Como um array é representado internamente no Python?
  2. Qual estrutura de dados é usada internamente para representar e possibilitar a manipulação do array, lista-encadeada, tabela hash ou um array simples com alocação dinâmica?

3 Respostas 3

12

Primeiro, array é diferente de lista.

Em muitos casos, comumente mais informações, o erro de nomenclatura não será um agravante e não prejudicará a comunicação, mas dado que estaremos analisando o funcionamento interno da linguagem julgo ser interessante se ater aos termos corretos. Dadas as perguntas, ficou claro que a dúvida é sobre o funcionamento de listas, não de arrays.

O tipo list é nativo do Python e foi implementado em C sob a estrutura PyListObject.

typedef struct {
    PyVarObject ob_base;
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

Onde temos:

  • ob_base, um objeto que representa estruturas de tamanho variável, implementa o campo ob_size;
  • ob_item, um ponteiro para ponteiro de PyObject;
  • allocated, um objeto Py_ssize_t que representa o tamanho alocado;

Como pode ver - inclusive comentado no código - os itens que compõem a lista no Python serão gerenciados a partir de ob_item. Ele, por ser um ponteiro, possui a dinamicidade de ser realocado conforme a necessidade de crescimento da lista, em que cada posição apontará para um outro ponteiro PyObject que representa o item da lista. Vale lembrar aqui que todas as estruturas que o Python implementa herdam de PyObject, então não haverá restrições do tipo que poderá ser armazenado na lista.

Sempre que o tamanho de uma lista precisa ser alterado, a função list_resize é invocada; ela que é responsável pela implementação do algoritmo de realocação de uma lista.

O código fonte desta função é:

/* Ensure ob_item has room for at least newsize elements, and set
 * ob_size to newsize.  If newsize > ob_size on entry, the content
 * of the new slots at exit is undefined heap trash; it's the caller's
 * responsibility to overwrite them with sane values.
 * The number of allocated elements may grow, shrink, or stay the same.
 * Failure is impossible if newsize <= self.allocated on entry, although
 * that partly relies on an assumption that the system realloc() never
 * fails when passed a number of bytes <= the number of bytes last
 * allocated (the C standard doesn't guarantee this, but it's hard to
 * imagine a realloc implementation where it wouldn't be true).
 * Note that self->ob_item may change, and even if newsize is less
 * than ob_size on entry.
 */
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

Assim como o Maniero comentou em sua resposta, basicamente o Python aloca um novo espaço de memória já considerando o novo tamanho da lista e considerando espaços de sobra para depois copiar o conteúdo para esse espaço na memória. Perceba que o espaço adicionado ao tamanho da lista será proporcional ao tamanho atual e é feito isso justamente para buscar uma amortização linear no tempo de realocação. Isto é, é mais fácil realocar um espaço maior uma vez e inserir vários elementos do que realocar sempre que for inserir. Perceba também que toda a realocação é feita sobre o objeto items e não diretamente sobre self->ob_item:

items = self->ob_item;

if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
    PyMem_RESIZE(items, PyObject *, new_allocated);
else
    items = NULL;

if (items == NULL) {
    PyErr_NoMemory();
    return -1;
}

self->ob_item = items;

PyMem_RESIZE é uma macro definida por:

#define PyMem_RESIZE(p, type, n) \
  ( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL :        \
        (type *) PyMem_REALLOC((p), (n) * sizeof(type)) )

Que basicamente faz a realocação de memória no ponteiro especificado.

10

Antes de mais nada entenda que Python é uma linguagem de tipagem dinâmica e precisa de estruturas de dados para lidar com esta necessidade. Você não acessa o dado de forma direta como em linguagens estáticas. Se quiser saber mais sobre essa questão de tipagem leia Como funciona internamente os arrays do PHP?.

Assim como em PHP, Python tem uma struct com uma union (ambas linguagens são escritas em C) com o dado e seu tipo, sendo que o dado pode ser um ponteiro.

A lista tem uma estrutura com um cabeçalho, o que seria mais ou menos o normal se escrito em C mesmo em algo mais sofisticado e um objeto com uma sequência de dados. Estes dados serão etas estruturas que citei no parágrafo anterior. Em C um array é justamente uma sequência de dados acessado por um ponteiro. Então a lista do Python não é diferente do array do C e é tão eficiente quanto se olharmos só para a lista em si. A ineficiência viria só ao acesso ao dado que tem um controle interno. Pode-se dizer que que Python precisa desse cabeçalho, mas mesmo em C para usar o array de forma conveniente e correta em código real você precisa de algo assim.

Este cabeçalho tem basicamente o tamanho da lista, o ponteiro para o objeto lista em si e um objeto que é o início da lista (ainda preciso entendê-lo). Pode mudar de versão para versão.

A diferença clara entre uma lista e um array é que o segundo costuma ser definido como uma estrutura fixa e não pode mudar de tamanho e a lista pode. Internamente só tem duas formas de mudar o tamanho de uma coleção, ou faz uma lista ligada (ou algo parecido) que permite adicionar elementos novos de forma simples e sob demanda, porém o acesso ao dado fica trágico ou faz como um array com sobra de capacidade (aloca mais que precisa) e quando estourar a capacidade você cria outro array e copia tudo para este novo e descarta o antigo. Isso é o normal em praticamente todas as linguagens e costuma ser chamado de array dinâmico. O nome não tem a ver com a alocação que por acaso é feita dinamicamente com malloc() (mesmo que indiretamente).

Note que isto vale para CPython que é a implementação padrão, outras implementações podem fazer de forma muito diferente, mas como elas devem funcionar de forma compatível e não poderá ser tão diferente assim. Fonte. Por exemplo Jython pode usar o própria ArrayList da JVM que tem a mesma semântica.

Já um dict é bem diferente porque aí é usada uma forma de hashtable.

Coloquei no GitHub para referência futura.

1

Como um array é representado internamente no Python?

Array é representado como uma lista no python. existe a biblioteca do array exemplo:

from array import *

x = array('i', [10,20,30,40,50])
print(type(x))

mas array nao suporta string apenas:

'b' signed char
'B' unsigned char 'u' Py_UNICODE 'h' signed short
'H' unsigned short
... Ver mais em Array Tipos

existe uma biblioteca de array com mais recursos chamada NumPy, exemplo de uso:

import numpy as np

a = np.array(['Gato', 'Jake', 'Finn'])
print(type(a))

Qual estrutura de dados é usada internamente para representar e possibilitar a manipulação do array, lista-encadeada, tabela hash ou um array simples com alocação dinâmica?

Nao consigo informar ao certo pela falta de informacao na documentacao do python.

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

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .