Como eu estava aprendendo a programar, as listas Python me pareceram totalmente mágicas. Eu as imaginava como sendo implementadas por algum tipo de infraestrutura de dados mágica que era parte de uma lista vinculada, parte de um array que era perfeito para tudo.

Como eu cresci como engenheiro, ocorreu que isso era improvável. Eu adivinhei (corretamente) que ao invés de algum tipo de implementação mágica, ela era apenas apoiada por um array redimensionável. Eu decidi ler o código e descobrir.

Uma das coisas legais sobre o CPython é a implementação legível. Embora o arquivo relevante seja mais de 2000 linhas de C, é principalmente o algoritmo de ordenação, e boilerplate para tornar as funções chamáveis a partir do código Python.1 As operações da lista do núcleo são curtas e simples.

Aqui estão algumas coisas interessantes que encontrei lendo a implementação. Os trechos de código abaixo vêm do código fonte do CPython com comentários explicativos adicionados por me.

List Resizing

Se você anexar a uma lista Python e o array de suporte não for grande o suficiente, o array de suporte deve ser expandido. Quando isto acontece, o backing array é aumentado em aproximadamente 12%. Pessoalmente, eu tinha assumido que este fator de crescimento era muito maior. Em Java ArrayList cresce em 50% quando expandido2 e em Ruby, Array cresce em 100%.3

 // essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6); 

link para código de realocação CPython

Fiz alguns experimentos de performance – pré-alocar matrizes com construções como *500 não parece fazer nenhuma diferença perceptível. No meu não científico benchmark de anexar a uma lista 100 milhões de vezes, Python 3 foi muito mais lento que Python 2 que foi muito mais lento que Ruby, no entanto, muito mais pesquisa é necessária para determinar o impacto (se houver) do fator de crescimento na performance do insert.

Inserir no início da lista

Inserir no início de uma lista leva tempo linear – isto não é tão surpreendente dado o resto da implementação, mas é bom saber que some_list.insert(0,value) raramente é uma boa ideia. Um usuário Reddit me lembrou de Deques que troca tempo constante inserir e remover de ambas as extremidades em troca de indexação de tempo constante.

>

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;>

link para código de inserção de CPython

>

Criar fatias de listagem

>

Tirar uma fatia de uma lista, por exemplo. some_listé também uma operação de tempo linear no tamanho da fatia, portanto, novamente, sem magia. Você poderia imaginar otimizar isso com algum tipo de copy-on-write semântica, mas o código CPython favorece a simplicidade:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}>

link para o código da fatia do CPython

Slice Assignment

Você pode atribuir a uma fatia! Tenho certeza que isso é comumente conhecido entre desenvolvedores profissionais de Python, mas eu nunca me deparei com isso em vários anos de programação python. Eu só descobri quando me deparei com a função list_ass_slice(...) no código. No entanto, cuidado com grandes listas – precisa copiar todos os itens deletados da lista original, o que irá brevemente dobrar o uso da memória.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Sorting

Arrays Python são ordenados com um algoritmo conhecido como “timsort”. É extremamente complicado e descrito em detalhes em um documento lateral na árvore de origem. Grosso modo, ele constrói séries cada vez mais longas de itens sequenciais e os funde. Ao contrário do tipo normal de fusão, ele começa procurando por seções da lista que já estão ordenadas (runs no código). Isto permite-lhe tirar partido dos dados de entrada que já estão parcialmente ordenados, um tidbit interessante: Para ordenar pequenas arrays (ou pequenas seções de um array maior) de até 64 elementos4, o timsort usa “binary sort”. Esta é essencialmente uma ordenação de inserção, mas usando a busca binária para inserir o elemento no local correto. Na verdade é um algoritmo O(n^2)! Um exemplo interessante de desempenho do mundo real ganhando complexidade algorítmica na prática. link

Sinto falta de algo legal sobre as listas CPython? Deixe-me saber nos comentários.

Obrigado a Leah Alpert por dar sugestões neste post.

Quero receber um e-mail sobre novos posts no blog?

Postei cerca de uma vez a cada poucas semanas sobre tópicos como bases de dados, internos de linguagem e algoritmos, e recentemente, um aprendizado profundo. Eu estou disponível para compromissos de 1 semana a alguns meses. Contrate-me!