python: listas, deques, dicionarios e outros monstros mitologicos
DESCRIPTION
Uma visita no que esta debaixo do capô de quando usamos listas, dicionarios e tal em pythonTRANSCRIPT
Listas, Dicionários, Sets
e outras Bestas Mitológicas --- Adriano Petrich
O(n)?
Listas
Prós:Fantásticas
Listas
l = []
L.append(foo) é O(1)
L.pop() é O(1)
TáIsso não é tão fantástico
L[foo] = bar, L[foo] O(1)
Isso sim é fantástico
meh
ListasSe comportam como RAM porque sãomodeladas da mesma forma
CriaçãoUsa 20 bytes de overhead (classe, len,tamanho da alocação e posição)
masUma lista vazia não tem memória alocadapara os dados.
Quando
l.append(1)
Acontece a AlocaçãoAloca espaço para 4 elementos
Quando chega em 4 aloca espaço para 8 ecopia os 4
Depois 16
E assim por diante
Ou Quase25, 35, 46, 58, 72, 88
L.append(foo) é O(1)
Here be monsters
Cons
L.pop(0) é O(n)
L.pop(0) é O(n)-ish
Alternativa
from collections import dequedeque()
DequesDouble Ended QUEue
Internamente é uma lista ligada dupla
PrósFilas FIFO e não muito mais
De volta aslistas
foo in L é O(n)
Alternativas
set()
Dicionários
Dicionários?
>>> d = {}>>> d['a'] = 1
Interlúdio>>> hash('a')12416037344>>> bin(hash('a')'0b1011100100000011011011000111100000'
Hashtable
Hash 'a'
>>> hash('a')12416037344>>> bin(hash('a')'...000'
Hashtable
Hash 'b'
>>> d['b'] = 2>>> hash('b')12544037731>>> bin(hash('b')'...011'
Hashtable
Hash 'c'
>>> d['c'] = 3>>> hash('c')12672038114>>> bin(hash('c')'...010'
Hashtable
Hash 'j'
>>> d['j'] = 4>>> hash('j')13568040811>>> bin(hash('j')'...011'
Enquanto isso naHashtable
Outra vez na Hashtable
Duas coisas
>>> d1 = {'a':1, 'j':4, 'b':2}>>> d2 = {'a':1, 'b':2, 'j':4}>>> d1{'a': 1, 'j': 4, 'b': 2}>>> d2{'a': 1, 'b': 2, 'j': 4}>>> d1 == d2True
Dicionários não temordemTem sim! A ordem da hashtable
>>> {'a':1, 'j':4, 'b':2}.keys()['a', 'j', 'b']>>> {'a':1, 'j':4, 'b':2}.values()[1, 4, 2]
Existem bem maissutilezasVídeo da pycon 2010: the might dictionary
Sets
SetsImplementação igual dos dicionários sóque sem o valor.
Então:
foo in s é O(1)
Grafos
A B
C D
A B
C D
Duas formas
a,b,c,d = range(4)n = [[0,1,1,0], [0,0,1,0], [0,0,0,1], [0,0,0,0]]
>>> n[a][b]1
Ou
n = { 'a': set('bc'), 'b': set('c'), 'c': set('d'), 'd': set()}
Python Patterns implementing graphs--Guido van Rossum
A B
C D
2
3 4
5
passe para dicionários
n = { 'a': {'b':2, 'c':3}, 'b': {'c':4}, 'c': {'d':5}, 'd': {}}
Créditoshttp://www.flickr.com/photos/autumn_bliss/414160195http://www.flickr.com/photos/autumn_bliss/414160148
Dúvidas?@fractal
+Adriano Petrich
[codando.com.br, sfp.adrianopetrich.com,blog.adrianopetrich.com]