3

Estou estudando a respeito de filas no Python e estou usando o objeto deque do módulo collections.

Assim sendo, no Python eu posso acessar os valores de um array pelo índice simplesmente escrevendo:

array = [1, 2, 3]
arra[0] # 1

No entanto, o objeto deque também permite que eu acesse os valores da fila através de um índice, com a mesma notação de array.

Veja:

fila = deque()
fila.append(1)
fila.append(2)
fila.append(3)

fila[0] # 1

Só que o array é da classe list e a fila é da classe deque do módulo collections veja abaixo:

print(type(fila))
print(type(array))

Saída:

<class 'collections.deque'>
<class 'list'>

E isto me deixou com a seguinte dúvida.

Dúvida

  • O tipo list é o que determina a variável como array? Se sim, como que um objeto do tipo de outra classe (i.e. deque) pode ter o mesmo comportamento de um array?
4
  • 1
    Defina "mesmo comportamento de um array".
    – Maniero
    4/09/2018 às 19:18
  • @Maniero a possibilidade de acessar o valor diretamente através de um índice. Claro que deve haver outras definições, mas não sei :)
    – gato
    4/09/2018 às 19:18
  • gato repara que um tuple segundo essa definição (possibilidade de acessar através de um indíce) pode ser também um array, ex: (1,2,3)[0] == 1
    – Miguel
    4/09/2018 às 19:32
  • @Miguel então tupla é um array também, essa eu nem imaginava xD
    – gato
    4/09/2018 às 19:56

2 Respostas 2

6

Em Python o tipo não define nada.

O que define é o contrato do objeto com a função que você executará. Por exemplo, quando você faz obj[x], independente do que obj ou x sejam, o interpretador do Python avaliará o código como sendo uma chamada ao método __getitem__ de obj. Se ele possuir esse método, seu código funcionará, independente se ele é uma lista, uma fila, uma tupla, ou qualquer outro tipo.

Neste caso, a classe deque também implementa o método __getitem__, assim como a list, tuple, str, etc. Por isso funciona fazer fila[0].

>>> import collections
>>> print(dir(collections.deque))
[..., '__getattribute__', '__getitem__', '__gt__', ...]

Por exemplo, você poderia implementar uma classe qualquer com um comportamento bastante característico:

class Tabuada:
    def __init__(self, valor):
        self.valor = valor

    def __getitem__(self, item):
        return item * self.valor

Assim, você pode criar a tabuada do 2, t = Tabuada(2), e verificar seus valores:

>>> print(t[1])  # 2
>>> print(t[2])  # 4
>>> print(t[3])  # 6
>>> print(t[4])  # 8

E assim em diante.

Veja que a classe Tabuada tem relação nenhuma com as listas, nem herda, nem utiliza, mas por definir o método __getitem__, você consegue acessar os índices através da notação com colchetes.

1
  • 2
    Não seria interessante definir este comportamento como Duck Typing na resposta, para que o pessoal conheça o termo? 4/09/2018 às 19:47
6

List é o nome que Python dá pra o que se conhece como array. Na verdade o array puro como conhecemos Python não tem. Ela é uma estrutura de dados que são colocados em sequência e que cada elemento é acessado em tempo O(1) e a adição ou remoção de dados adicionados na pontas pode ser feita, mas com custo O(n), ainda que possa existir algumas otimizações para minimizar isso em alguns casos, garantido mesmo só a complexidade linear, portanto ainda que que permitido pode ser bem lento adicionar ou remover itens da lista.

Um ponto importante a notar que esse array é sempre de ponteiros para os valores, isso permite colocar qualquer dado nele.

Deque é outra estrutura com características diferentes. A adição e remoção nas pontas é O(1) (isso nem é tão verdade assim em todos casos), portanto muito rápido, mas acessar os elementos aleatoriamente não dá rapidamente, o acesso é O(n), embora na média possa ser O(n/2). deque não se comporta como um array e a pergunta parte de uma premissa falsa. Pode acessar pelo índice, mas com um compromisso muito diferente.

Documentação.

Fazer a mesma operação não significa que é igual, complexidades diferentes fazem toda diferença e é a base das otimizações da computação. A forma como o dado é organizado internamente e o algoritmo usado torna impraticável para determinada operação. É muito comum o uso da estrutura errada e a pessoa não entender ou perceber porque algo está lento.

Nada impede qualquer estrutura ter um comportamento idêntico ao da lista, embora provavelmente não faça sentido ter isso, a não ser por uma abstração que faça sentido. Na biblioteca padrão certamente não tem já que ela deve ter apenas mecanismo mais concretos necessários para várias operações. As coleções constantes na documentação acima e as padrões da linguagem tem sempre características diferentes, embora todas possam ser acessadas por um índice. Algumas até são abstrações pata facilitar o uso dos tipos da linguagem, provavelmente porque tenha sido um erro os tipos serem especiais na linguagem, quase todas linguagens usam esses tipos como padrões na biblioteca em vez de fazer o compilador saber como lidar com eles.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .