Dicionários e Conjuntos

em Python

Dicionários

Dicionários

{"chave": "valor"}

Acesso aleatório imediato O(1)

>>> d = {"chave": "valor", "outra": 123}

>>> d["chave"]

'valor'

>>> d["inexistente"]

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

KeyError: 'inexistente'

Dicionários

{"chave": "valor"}

Acesso aleatório imediato O(1)

Inserção e atualização

>>> d

{'chave': 'valor', 'outra': 123}

>>> d["a"] = 1

>>> d

{'chave': 'valor', 'outra': 123, 'a': 1}

>>> d["a"] = 42

>>> d

{'chave': 'valor', 'outra': 123, 'a': 42}

Dicionários

{"chave": "valor"}

Acesso aleatório imediato O(1)

Inserção e atualização

get() para receber default

>>> d

{'chave': 'valor', 'outra': 123, 'a': 42}

>>> d.get("inexistente", "não tem")

'não tem'

​

Dicionários

{"chave": "valor"}

Acesso aleatório imediato O(1)

Inserção e atualização

get() para receber default

keys(), items(), values()

>>> d.keys()

dict_keys(['chave', 'outra', 'a'])

>>> d.items()

dict_items([('chave', 'valor'), ('outra', 123), ('a', 42)])

>>> d.values()

dict_values(['valor', 123, 42])

​

importância do dict para a implementação da própria linguagem

>>> f = Fenwick(8)

>>> ... # preencher com itens

>>> f.__dict__

{'data': [0, 2, 2, 1, 6, -1, 4, -2, 12], 'size': 8}

​

Conjuntos

Conjuntos

Teoria dos conjuntos - Matemática

Elementos sem repetição

>>> s1 = set([1, 2, 1, 2, 3, 4, 1])

>>> s2 = set([1, 3, 5, 6, 7, 8, 2])

>>> s1

{1, 2, 3, 4}

>>> s2

{1, 2, 3, 5, 6, 7, 8}

Conjuntos

Teoria dos conjuntos - Matemática

Elementos sem repetição

Operações de conjunto:

• união
• intersecção
• diferença
• ou exclusivo

>>> s1 & s2

{1, 2, 3}

>>> s1 | s2

{1, 2, 3, 4, 5, 6, 7, 8}

>>> s1 - s2

{4}

>>> s2 - s1

{8, 5, 6, 7}

>>> s1 ^ s2

{4, 5, 6, 7, 8}

Conjuntos

Teoria dos conjuntos - Matemática

Elementos sem repetição

Operações de conjunto:

• união
• intersecção
• diferença
• ou exclusivo

>>> s1 & s2

{1, 2, 3}

>>> s1 | s2

{1, 2, 3, 4, 5, 6, 7, 8}

>>> s1 - s2

{4}

>>> s2 - s1

{8, 5, 6, 7}

>>> s1 ^ s2

{4, 5, 6, 7, 8}

Não é uma lista

O que tá por trás delas?

?

Hash Tables

Hash tables

Estrutura de dados que visa otimizar o acesso aleatório a seus elementos

a posição que o elemento deve ficar é calculada na inserção

o acesso é calculado da mesma forma

calcula a posição

Hash tables

Estrutura de dados que visa otimizar o acesso aleatório a seus elementos

a posição que o elemento deve ficar é calculada na inserção

o acesso é calculado da mesma forma

Esparsa (muito espaço vazio)

Resolver colisão

calcula a posição

Função hash

Características importantes:

• dois elementos iguais, devem ter hash igual
• dois elementos diferentes preferencialmente, devem ter hash diferentes
• o mais uniforme possível
• a probabilidade de cada hash acontecer deve ser o mais parecido possível

Por isso são usados objetos imutáveis

Custo benefício

tempo

memória

Paradoxo do aniversário

Dado um grupo de 23 pessoas escolhidas aleatoriamente, a chance de que duas pessoas terão a mesma data de aniversário é de mais de 50%. Para 57 ou mais pessoas, a probabilidade é maior do que 99%.

Entretanto, ela não pode ser exatamente 100% exceto que se tenha pelo menos 367 pessoas.

Memória

esparsa cheia de espaços vazios

implementação do python ⅔ ele aumenta por conta da prob de colisão

Memória

esparsa cheia de espaços vazios

implementação do python ⅔ ele aumenta por conta da prob de colisão

NamedTuples

Cuidados

Alterar um dicionário enquanto ele é percorrido é problemático

>>> d

{'chave': 'valor', 'outra': 123, 'a': 42}

>>> for i in d:

... d[i + "1"] = 1

...

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

RuntimeError: dictionary changed size during iteration

​

Obrigada!

Hash tables

Dicionários e conjuntos

Objeto dict

brunanayaramlima@gmail.com