Python pt-br:Estruturas de Dados

[edit] Introdução

Estruturas de dados são basicamente isso - são estruturas que podem conter alguns dados juntos. Em outras palavras, elas são utilizadas para guardar uma coleção de dados relacionados entre si.

Existem quatro estruturas de dados internas (built-in) em Python - lista, tupla, dicionário e conjunto (set). Nós veremos como usar cada uma delas e de que modo elas nos facilitam a vida.

[edit] Lista

Uma list (lista) é uma estrutura de dados que contém uma coleção ordenada de itens, ou seja, você pode guardar uma sequência de itens em uma lista. Isso é fácil de imaginar se você pensar em uma lista de compras na qual você tem uma lista de itens para comprar, exceto que você provavelmente terá cada item em uma linha separada, ao passo que Python coloca uma vírgula entre eles.

A lista de itens deverá estar dentro de colchetes (square brackets), de modo que Python entende que você está especificando uma lista. Uma vez que você criou a lista, pode adicionar, remover ou fazer buscas por itens dela. Desde que nós podemos adicionar e remover itens, dizemos que uma lista é um tipo mutável de dados, ous seja, este tipo pode ser alterado.

[edit] Rápida Introdução a Objetos e Classes

Embora eu tenha retardado a discussão sobre objetos e classes até agora, uma pequena explanação torna-se imediatamente necessária, tal que você possa entender melhor as listas. Exploraremos esse tópico em mais detalhes em seu próprio capítulo.

Uma lista é um exemplo de utilização de objetos e classes. Quando nós usamos a variável i e atribuímos um valor, digamos, inteiro 5 a ela, você pode raciocinar como se criasse um objeto (isto é uma instância) i de uma classe (ou seja tipo) int. De fato, você pode ler help(int) para melhor entender isso.

Uma classe pode ter métodos ou seja funções definidas para uso com respeito unicamente àquela classe. Você pode usar essas peças de funcionalidade apenas quando tem um objeto daquela classe. Por exemplo, Python fornece um método append para a classe list, o que permite a você adicionar um item ao final da lista. Por exemplo, minhalista.append('um item') adicionará aquela string ao final da lista minhalista. Note o emprego da notação dos pontos para acessar métodos dos objetos.

Uma classe pode também possuir campos que não são nada mais do que variáveis definidas para uso com respeito unicamente àquela classe. Você pode utilizar aquelas variáveis/nomes apenas quando tem um objeto daquela classe. Campos são também acessados com a notação dos pontos, por exemplo, minhalista.campo.

Exemplo:

#!/usr/bin/python
# Nome do arquivo: using_list.py
 
# Esta é a minha lista de compras
shoplista = ['maçã', 'manga', 'cenoura', 'banana']
 
print('Eu tenho', len(shoplista), 'itens para comprar.')
 
print('Estes itens são:', fim=' ')
for item in shoplista:
    print(item, fim=' ')
 
print('\nTambém tenho que comprar arroz.')
shoplista.append('arroz')
print('Minha lista de compras é agora', shoplista)
 
print('Vou colocar a minha lista em ordem agora')
shoplist.sort()
print('A minha lista ordenada é', shoplista)
 
print('O primeiro item que comprarei é', shoplista[0])
olditem = shoplista[0]
del shoplista[0]
print('Eu comprei o', olditem)
print('Minha lista de compras é agora', shoplist)

Saída:

   $ python using_list.py
   Eu tenho 4 itens para comprar.
   Estes itens são: maçã manga cenoura banana
   Também tenho que comprar arroz.
   Minha lista de compras é agora ['maçã', 'manga', 'cenoura', 'banana', 'arroz']
   Vou colocar a minha lista em ordem agora
   A minha lista ordenada é ['arroz', 'banana', 'cenoura', 'maçã', 'manga' ]
   O primeiro item que comprarei é arroz
   Eu comprei o arroz
   Minha lista de compras é agora 'banana', 'cenoura', 'maçã', 'manga' ]

Como Funciona:

A variável shoplista é uma lista de compras para alguém que está indo ao mercado. Em shoplista nós guardamos strings do nomes dos itens a serem comprados, mas você pode adicionar qualquer espécie de objeto a uma lista, incluindo números e até mesmo outras listas.

Nós também empregamos o laço for..in para iterar sobre os itens da lista. Agora você deve ter percebido que uma lista é também uma sequência. A especialidade das sequências será discutida em uma seção posterior.

Observe o uso da palavra-chave end como argumento na função print, para indicar que nós queremos terminar a saída com um espaço, ao invés da costumeira quebra-de-linha.

Em seguida, nós adicionamos um item à lista usando o método append do objeto lista, como já foi discutido antes. Então, nós verificamos que o item foi efetivamente acrescentado à lista através da impressão do conteúdo da lista, obtida simplesmente passando a lista ao comando print, que a imprime sem problemas.

Daí nós ordenamos a lista por meio do método sort do objeto lista. É importante compreender que este método afeta a a própria lista e que não retorna uma lista modificada - isso é diferente da maneira pela qual a string funciona. É o que nós queremos salientar quando dizemos que as listas são mutáveis e as strings são imutáveis.

A seguir, quando nós terminamos de comprar um item no mercado, queremos retirá-lo da lista. Alcançamos isso por meio do comando del. Aqui nós mencionamos qual o item da lista que desejamos suprimir e o comando del o remove da lista para nós. Especificamos que queremos remover o primeiro item da lista então usamos del shoplist[0] (lembre-se que Python começa a contagem a partir do 0.)

Se você quiser conhecer todos os métodos definidos para o objeto lista, veja help(list) para os detalhes.

[edit] Tupla

Tuplas (tuples) são exatamente como listas, exceto que são imutáveis, como as strings, isto é, você não pode modificar tuplas. Tuplas são definidas especificando itens separados por vírgulas dentro de um par de parênteses. As tuplas são costumeiramente usadas em casos em que um comando ou uma função definida pelo usuário pode seguramente assumir que uma coleção de valores, ou seja, a tupla de valores não será alterada.

Exemplo:

#!/usr/bin/python
# Nome do arquivo: using_tuple.py
 
zoo = ('lobo', 'elefante', 'pinguim')
print('O Número de animais no zoo é', len(zoo))
 
novo_zoo = ('macaco', 'golfinho', zoo)
print('O Número de animais no novo zoo é', len(novo_zoo))
print('Todos os animais no novo zoo são', novo_zoo)
print('Os animais trazidos do antigo zoo são', novo_zoo[2])
print('O último animal trazido do antigo zoo é', novo_zoo[2][2])

Output:

   $ python using_tuple.py
   O Número de animais no zoo é 3
   O Número de animais no novo zoo é 3
   Todos os animais no novo zoo são ('macaco', 'golfinho', ('lobo', 'elefante', 'pinguim'))
   Os animais trazidos do antigo zoo são ('lobo', 'elefante', 'pinguim')
   O último animal trazido do antigo zoo é pinguim

Como Funciona:

A variável zoo refere-se a uma tupla de itens. Nós vemos que a função zoo pode ser utilizada para se obter o comprimento da tupla. Isso também indica que a tupla também é uma sequência.

Nós estamos mudando aqueles animais para um novo zoo, uma vez que o antigo está para ser fechado. Dessa forma, a tupla novo_zoo contém alguns animais que já estavam lá, juntamente com aqueles trazidos do velho zoo. De volta a realidade, observe que uma tupla dentro de outra tupla não perde a sua indentidade.

Podemos acessar os itens em uma tupla especificando a posição do item dentro de um par de colchetes exatamente como nós fizemos para listas. Esse é chamado operador de indexação. Nós acessamos o terceiro item em novo_zoo pela especificação novo_zoo[2] e acessamos o terceiro item dentro do terceiro item na tupla novo_zoo especificando novo_zoo[2][2]. É muito simples uma vez que você domine o jeito.

Tuplas com 0 ou 1 item

Uma tupla vazia é construída com um par de parênteses como vazia = (). Entretanto, com um único item já não é tão simples. Você deve especificar usando uma vírgula em seguida ao primeiro (e único) item, tal que Python possa diferenciar entre uma tupla e um par de parênteses que cercam uma expressão, ou seja, você tem que especificar singleton = (2 , ), se quiser uma tupla contendo o item 2.

Nota para programadores em Perl

Uma lista dentro de uma lista não perde sua identidade, listas não são "achatadas", como em Perl. O mesmo se aplica a uma tupla dentro de uma tupla, ou uma tupla em uma lista, ou uma lista em uma tupla, etc. Do ponto de vista de Python, são apenas objetos alocados usando um outro objeto, apenas isso.

[edit] Dicionário

Um dicionário (dictionary) é como uma agenda de endereços na qual você pode encontrar ou endereço ou detalhes de contato de uma pessoa, conhecendo apenas o nome dela, isto é, associamos as keys (chaves) (nome) com values (valores) (detalhes). Note que a key deve ser única, da mesma forma que você não poderá encontrar a informação correta se houverem duas pessoas com exatamente o mesmo nome.

Observe que você pode utilizar somente objetos imutáveis (como strings) como keys de um dicionário, mas pode usar objetos imutáveis e mutáveis como values do dicionário. Isso basicamente se traduz em que você deve usar apenas objetos simples como keys.

Pares de keys e values são especificados em um dicionário pela notação d = {key1 : value1, key2 : value2 }. Observe que os pares key/value estão separados por uma vírgula e todo o conjunto está dentro de um par de chaves.

Lembre-se que os pares key/value em um dicionário não estão de forma alguma ordenados. Se quiser um ordem particular, você mesmo terá que ordená-los antes de usá-los.

Os dicionários que você utilizará são instâncias/objetos da classe dict.

Exemplo:

#!/usr/bin/python
# Nome do arquivo: using_dict.py
 
# 'ab' é diminutivo para 'a'ddress'b'ook
 
ab = {  'Swaroop'   : 'swaroop@swaroopch.com',
        'Larry'     : 'larry@wall.org',
        'Matsumoto' : 'matz@ruby-lang.org',
        'Spammer'   : 'spammer@hotmail.com'
    }
 
print("Swaroop's address is", ab['Swaroop'])
 
# Deletando um par key/value
del ab['Spammer']
 
print('\nThere are {0} contacts in the address-book\n'.format(len(ab)))
 
for name, address in ab.items():
    print('Contact {0} at {1}'.format(name, address))
 
# Adiconando um par key/value
ab['Guido'] = 'guido@python.org'
 
if 'Guido' in ab: # OU ab.has_key('Guido')
    print("\nGuido's address is", ab['Guido'])

Saída:

   $ python using_dict.py
   Swaroop's address is swaroop@swaroopch.com
   
   There are 3 contacts in the address-book
   
   Contact Swaroop at swaroop@swaroopch.com
   Contact Matsumoto at matz@ruby-lang.org
   Contact Larry at larry@wall.org
   
   Guido's address is guido@python.org

Como Funciona:

Nós criamos um dicionário ab usando a notação já discutida. Então acessamos os pares key/value especificando a key usando o operador de indexação como discutido no contexto de listas e tuplas. Observe a sintaxe simples.

Nós podemos deletar os pares key/value usando nosso velho amigo - o comando del. Simplesmente especificamos o dicionário o operador de indexação para a key a ser removida e passamos tudo ao comando del. Não há a necessidade de conhecer o value correspondente à key para esta operação.

Em seguida, nós acessamos cada par key/value usando o método items do dicionário, o qual retorna uma lista de tuplas, em que cada tupla contém um par de itens - a key seguida por um value. Nós recuperamos esse par e o atribuímos as variáveis name e address correspondentemente para cada par, usando o laço de for..in e então imprimimos esses valores no bloco de for.

Podemos adicionar novos pares key/value, simplesmente empregando o operador de indexação para acessar a key e atribuirmos aquele value, como fizemos para Guido no caso acima.

Nó podemos verificar se um par key/value existe, usando o operador in ou mesmo o método has_key da classe dict. Você pode ver a documentação para a lista completa de métodos da classe dict, usando help(dict).

Argumentos em Keyword (palavras-chave) e Dicionários

Em um tópico distinto, se você tiver empregado argumentos em keywords em suas funções, você já usou dicionários! Pense um pouco sobre isso - o par key/value é especificado por você na lista de parâmetros da definição da função e quando você acessa variáveis dentro de sua função, trata-se apenas de uma acesso a key de um dicionário (que é chamado de tabela de símbolos em terminologia de compiladores).

[edit] Sequências

Listas, tuplas, strings e arquivos são exemplos de sequências, mas o que as sequências tem de tão especial? Duas das principais características de uma sequência são a operação de indexação'que nos permite recuperarmos diretamente um item particular e a operação de slicing (fatiamento) que nos permite recuperarmos uma fatia de uma sequência, ou seja, uma parte da sequência.

Exemplo:

#!/usr/bin/python
# Nome do arquivo: seq.py
 
shoplist = ['apple', 'mango', 'carrot', 'banana']
name = 'swaroop'
 
# Operação de Indexação ou 'Subscrição'
print('Item 0 is', shoplist[0])
print('Item 1 is', shoplist[1])
print('Item 2 is', shoplist[2])
print('Item 3 is', shoplist[3])
print('Item -1 is', shoplist[-1])
print('Item -2 is', shoplist[-2])
print('Character 0 is', name[0])
 
# Slicing (fatiamento) sobre uma lista
print('Item 1 to 3 is', shoplist[1:3])
print('Item 2 to end is', shoplist[2:])
print('Item 1 to -1 is', shoplist[1:-1])
print('Item start to end is', shoplist[:])
 
# Slicing (fatiamento) sobre uma string
print('characters 1 to 3 is', name[1:3])
print('characters 2 to end is', name[2:])
print('characters 1 to -1 is', name[1:-1])
print('characters start to end is', name[:])

Saída:

   $ python seq.py
   Item 0 is apple
   Item 1 is mango
   Item 2 is carrot
   Item 3 is banana
   Item -1 is banana
   Item -2 is carrot
   Character 0 is s
   Item 1 to 3 is ['mango', 'carrot']
   Item 2 to end is ['carrot', 'banana']
   Item 1 to -1 is ['mango', 'carrot']
   Item start to end is ['apple', 'mango', 'carrot', 'banana']
   characters 1 to 3 is wa
   characters 2 to end is aroop
   characters 1 to -1 is waroo
   characters start to end is swaroop

Como Funciona:

Primeiramente, nós vemos como utiizar os índices para obter itens individuais de uma sequência. Isso é também conhecido como operação de subscrição. Quando você especifica um número dentro de colchetes a uma sequência, como mostrado acima, Python irá recuperar para você o item correspondente aquela posição na sequência. Lembre-se que Python começa a contagem dos números a partir do 0. Daí, shoplist[0] retorna o primeiro item e shoplist[3] retorna o quarto item na sequência shoplist.

O índice pode também ser um número negativo, em cujo caso, a posição é calculada a partir do fim da sequência. Assim, shoplist[-1] refere-se ao último item da sequência e shoplist[-2] recuoera o penúltimo item da sequência.

A operação de slicing é empregada especificando-se o nome da sequência seguido de um par opcional de números separados por 'dois pontos' dentro de colchetes. Note que isso é bem similar a operação de indexação que você vem usando até agora. Lembre-se que os números são opcionais mas o 'dois pontos' não é.

O primeiro número (antes do 'dois pontos') na operação de slicing refere-se a posição de onde a fatia começa e o segundo número (depois do 'dois pontos') indica onde a fatia terminará. Se o primeiro número não for especificado, Python começará no início da sequência. Se o segundo número não existir, Python terminará no final da sequência. Note que a fatia retornada começa na posição de início e termina imediatamente antes da posição do fim, ou seja, a posição de início é incluída, mas a posição do fim é excluída na fatia da sequência.

Então, shoplist[1:3] retorna uma fatia de uma sequência que começa na posição 1, inclui a posição 2 mas para na posição 3 e assim uma fatia de dois itens é retornada. Similarmente, shoplist[:] retorna uma cópia da sequência toda.

Você pode também efetuar slicing com números negativos. Os números negativos são usados para posições a partir do fim da sequência. Por exemplo, shoplist[:-1] retornará uma fatia da sequência que exclui o último item da sequência mas contém todo o resto dela.

Experimente várias combinações de especificações de slicing usando interativamente o interpretador de Python, ou seja, o prompt, de modo que você possa ver os resultados imediatamente. Uma grande coisa a respeito de sequências e que você pode acessar tuplas, listas e strings todas da mesma maneira!

[edit] Conjuntos

Conjuntos (Sets) são coleções não ordenadas de objetos simples. Eles são usados quando a existência de um objeto em uma coleção é mais importante do que a ordem em que está ou o número de vezes em que ocorre.

Usando sets, você pode testar para pertencimento a um conjunto, verificar se um conjunto é um subconjunto de outro, encontrar a interseção entre dois conjuntos, e assim por diante.

>>> bri = set(['brasil', 'russia', 'india'])
>>> 'india' in bri
True
>>> 'usa' in bri
False
>>> bric = bri.copy()
>>> bric.add('china')
>>> bric.issuperset(bri)
True
>>> bri.remove('russia')
>>> bri & bric # OR bri.intersection(bric)
{'brasil', 'india'}

Como Funciona:

O exemplo é razoavelmente auto-explicativo, pois envolve teoria básica de conjuntos ensinada na escola.

[edit] Referências

Quando você cria um objeto e o atribui a uma variável, esta apenas se refere ao objeto e não representa o objeto em si mesmo! Isto é, o nome da variável aponta para aquela parte da memória do seu computador na qual o objeto está armazenado. Isso é chamado vinculação (binding) do nome ao objeto.

Em geral você não precisa ficar preocupado com isso, mas existe um efeito sutil devido a referências ao qual você precosa ficar atento:

Exemplo:

#!/usr/bin/python
# Nome do arquivo: reference.py
 
print('Atribuição Simples')
shoplist = ['apple', 'mango', 'carrot', 'banana']
mylist = shoplist # mylist é apenas um outro nome apontando para o mesmo objeto!
 
del shoplist[0] # Eu comprei o primeiro item , então eu o removo da lista
 
print('shoplist is', shoplist)
print('mylist is', mylist)
# note como tanto shoplist e mylist ambas imprimem a mesma lista, sem 'apple', confirmando que apontam para o mesmo objeto.
 
print('Copie por meio de uma fatia completa')
mylist = shoplist[:] # efetue uma cópia por meio de uma fatia completa
del mylist[0] # remova o primeiro item
 
print('shoplist is', shoplist)
print('mylist is', mylist)
# note que agora as duas listas são distintas

Saída:

   $ python reference.py
   Atribuição Simples
   shoplist is ['mango', 'carrot', 'banana']
   mylist is ['mango', 'carrot', 'banana']
   Copie por meio de uma fatia completa
   shoplist is ['mango', 'carrot', 'banana']
   mylist is ['carrot', 'banana']

Como Funciona:

A maior parte da explicação está disponível nos próprios comentários.

O que você precisa lembrar é que quiser fazer uma cópia de uma lista ou tais espécies de sequências ou objetos complexos (não objetos simples como inteiros), então você deve utilizar a operação de slicing para efetuar uma cópia. Se você apenas atribuir o nome da variável a outro nome, então ambos se referirão ao mesmo objeto e isso pode ser um problema se você não for cuidadoso.

Nota para programadores em Perl

Lembre-se que um comando de atribuição para listas não cria uma cópia. Você deverá usar a operação de slicing para efetuar uma cópia da sequência.

[edit] Mais Sobre Strings

Nós já discutimos strings em detalhes antes. O que mais há para se conhecer? Bem, você sabia que strings são também objetos e que tem métodos que fazem de tudo, desde verificar partes de uma string até retirar os espaços em branco!

As strings que você usa em seu programa são todas objetos da classe str. Alguns métodos úteis dessa classe são demonstrados no próximo exemplo. Para uma lista completa de tais métodos, veja em help(str).

Exemplo:

#!/usr/bin/python
# Nome do arquivo: str_methods.py
 
name = 'Swaroop' # Este é um objeto string
 
if name.startswith('Swa'):
    print('Sim, a string começa com "Swa"')
 
if 'a' in name:
    print('Sim, ela contém a string "a"')
 
if name.find('war') != -1:
    print('Sim, ela contém a string "war"')
 
delimitador = '_*_'
mylist = ['Brasil', 'Rússia', 'Índia', 'China']
print(delimitador.join(mylist))

Output:

   $ python str_methods.py
   Sim, a string começa com "Swa"
   Sim, ela contém a string "a"
   Sim, ela contém a string "war"
   Brasil_*_Rússia_*_Índia_*_China

Como Funciona:

Aqui, nós vemos um bocado de métodos da string em ação. O método startswith é usado para descobrir se a string começa com uma dada string. O operador in é usado para verificar se uma dada string é uma parte de uma string.

O método find é usado para achar a posição de uma dada string em uma string ou retorna -1 se não for bem sucedido em achar a substring. A classe str tem também um elegante método para join os itens de uma sequência, com a string atuando como delimitador entre cada item da sequência e retorna uma string muito maior produzida com isso.

[edit] Resumo

Nós esxploramos detalhadamente as várias estruturas internas (built-in) de Python. Estas estruturas serão essenciais para escrever programas de um tamanho razoável.

Agora que nós já temos sob controle o básico de Python, veremos a seguir como projetar e escrever programas do mundo real em Python.