Preservando a ordem de sequências ao remover duplicatas

Imagine que você tenha uma lista com as URLs extraídas de uma página web e queira eliminar as duplicatas da mesma.

Transformar a lista em um conjunto (set) talvez seja a forma mais comum de se fazer isso. Tipo assim:

>>> urls = [
    'http://api.example.com/b',
    'http://api.example.com/a',
    'http://api.example.com/c',
    'http://api.example.com/b'
]
>>> set(urls)
{'http://api.example.com/a',
 'http://api.example.com/b',
 'http://api.example.com/c'}

Porém, observe que perdemos a ordem original dos elementos. Esse é um efeito colateral indesejado da eliminação de duplicatas através da transformação em um conjunto.

Um jeito de preservar a ordem dos elementos após a remoção das duplicatas é utilizar este macete com collections.OrderedDict:

>>> from colllections import OrderedDict
>>> OrderedDict.fromkeys(urls).keys()
['http://api.example.com/b',
 'http://api.example.com/a',
 'http://api.example.com/c']

Legal né? Agora vamos entender o que o código acima fez.

Antes de mais nada, é preciso saber que OrderedDict é uma estrutura de dados muito similar a um dicionário. A grande diferença é que o OrderedDict guarda internamente a ordem de inserção dos elementos. Assim, quando iteramos sobre um objeto desse tipo, ele irá retornar seus elementos na ordem em que foram inseridos.

Agora vamos quebrar as operações em partes para entender melhor o que aconteceu:

>>> odict = OrderedDict.fromkeys(urls)

O método fromkeys() cria um dicionário usando como chaves os valores passados como primeiro parâmetro e como valor o que for passado como segundo parâmetro (ou None, caso não passemos nada).

Como resultado, temos:

>>> odict
OrderedDict([('http://api.example.com/b', None),
('http://api.example.com/a', None),
('http://api.example.com/c', None)])

Agora que temos um dicionário com as chaves mantidas em ordem de inserção, podemos chamar o método keys() para obter somente as chaves que, neste caso, são as nossas URLs:

>>> odict.keys()
['http://api.example.com/b',
'http://api.example.com/a',
'http://api.example.com/c']

Obs.: em Python 3, o método keys() retorna uma view ao invés de uma lista. Esse tipo de objeto suporta iteração e teste de pertinência, assim como a lista. Caso você realmente precise de uma lista, basta construir uma usando o resultado de keys():

>>> list(odict.keys())

A eliminação de duplicatas é só uma consequência do design de dicionários, já que a unicidade das chaves é uma das propriedades fundamentais dessa estrutura de dados.

Caso queira entender melhor os princípios por trás de um dicionário, leia sobre tabelas hash: https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-hash.html

Anúncios

Um comentário sobre “Preservando a ordem de sequências ao remover duplicatas

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s