Obtendo o número de elementos em um iterador no Python

138

Existe uma maneira eficiente de saber quantos elementos há em um iterador no Python, em geral, sem iterar cada um e contar?

Tomasz Wysocki
fonte
relacionado: Comprimento de um gerador finito
jfs 23/06

Respostas:

101

Não. Não é possível.

Exemplo:

import random

def gen(n):
    for i in xrange(n):
        if random.randint(0, 1) == 0:
            yield i

iterator = gen(10)

O comprimento de iteratoré desconhecido até você iterá-lo.

Tomasz Wysocki
fonte
14
Como alternativa, def gen(): yield random.randint(0, 1)é infinito; portanto, você nunca será capaz de encontrar um comprimento iterando através dele.
tgray
1
Portanto, para validar o óbvio: a melhor maneira de obter o "tamanho" de um iterador é simplesmente contar o número de vezes que você passou pela iteração, certo? Nesse caso, seria numIters = 0 ; while iterator: numIters +=1?
Mike Williamson
Interessante, por isso é o problema da parada
Akababa
231

Este código deve funcionar:

>>> iter = (i for i in range(50))
>>> sum(1 for _ in iter)
50

Embora ele itere através de cada item e conte-os, é a maneira mais rápida de fazer isso.

Também funciona para quando o iterador não possui nenhum item:

>>> sum(1 for _ in range(0))
0

Obviamente, ele funciona para sempre para uma entrada infinita; lembre-se de que os iteradores podem ser infinitos:

>>> sum(1 for _ in itertools.count())
[nothing happens, forever]

Além disso, lembre-se de que o iterador se esgotará fazendo isso e outras tentativas de usá-lo não verão elementos . Essa é uma consequência inevitável do design do iterador Python. Se você deseja manter os elementos, precisará armazená-los em uma lista ou algo assim.

John Howard
fonte
10
Parece-me que isso faz exatamente o que o OP não quer: iterar pelo iterador e contar.
Adam Crossland
36
Esta é uma forma eficiente de espaço de contar os elementos num iteráveis
Capitão Lepton
9
Embora isso não seja o que o OP deseja, dado que sua pergunta não tem resposta, ela evita a instanciação de uma lista e é empiricamente mais rápida por uma constante do que o método de redução listado acima.
Phillip Nordwall
5
Não posso ajudar: a _referência é do Perl $_? :)
Alois Mahdal
17
@AloisMahdal Não. É convencional no Python usar o nome _de uma variável dummy cujo valor você não se importa.
Taymon
67

Não, qualquer método exigirá que você resolva todos os resultados. Você pode fazer

iter_length = len(list(iterable))

mas executar isso em um iterador infinito certamente nunca voltará. Ele também consumirá o iterador e precisará ser redefinido se você quiser usar o conteúdo.

Nos dizer qual é o verdadeiro problema que você está tentando resolver pode ajudar a encontrar uma maneira melhor de atingir seu objetivo real.

Editar: O uso list()lê todo o iterável na memória de uma só vez, o que pode ser indesejável. Outra maneira é fazer

sum(1 for _ in iterable)

como outra pessoa postada. Isso evitará mantê-lo na memória.

Daenyth
fonte
o problema é que estou lendo um arquivo com "pysam" que possui milhões de entradas. Pysam retorna um iterador. Para calcular uma certa quantidade, preciso saber quantas leituras existem no arquivo, mas não preciso ler cada uma ... essa é a questão.
6
Eu não sou usuário de pysam, mas provavelmente está lendo o arquivo "preguiçoso". Faz sentido porque você não deseja ter um arquivo grande na memória. Então, se você deve saber não. de registros antes da iteração, a única maneira é criar dois iteradores e usar o primeiro para contar elementos e o segundo para ler o arquivo. Entre. Não use, len(list(iterable))ele carregará todos os dados na memória. Você pode usar: reduce(lambda x, _: x+1, iterable, 0). Edit: Código Zonda333 com soma também é bom.
Tomasz Wysocki
1
@ user248237: por que você diz que precisa saber quantas entradas estão disponíveis para calcular uma determinada quantidade? Você pode apenas ler uma quantidade fixa deles e gerenciar o caso quando houver menos do que esse valor fixo (realmente simples de usar usando o iterslice). Existe outro motivo para você ler todas as entradas?
kriss
1
@ Tomasz Observe que a redução foi descontinuada e desapareceu no Python 3 e acima.
Wilduck 27/07
7
@Wilduck: Não se foi, apenas foi movido parafunctools.reduce
Daenyth
33

Você não pode (exceto que o tipo de um iterador específico implementa alguns métodos específicos que o tornam possíveis).

Geralmente, você pode contar itens do iterador apenas consumindo o iterador. Uma das maneiras provavelmente mais eficientes:

import itertools
from collections import deque

def count_iter_items(iterable):
    """
    Consume an iterable not reading it into memory; return the number of items.
    """
    counter = itertools.count()
    deque(itertools.izip(iterable, counter), maxlen=0)  # (consume at C speed)
    return next(counter)

(Para Python 3.x, substitua itertools.izippor zip).

zuo
fonte
3
+1: em comparação com o tempo sum(1 for _ in iterator), isso foi quase duas vezes mais rápido.
Aug
1
É mais preciso dizer que ele consome um iterável lendo cada item na memória e descartando-o imediatamente.
Rockallite 22/02/19
É importante notar (que eu ignorei) que a ordem dos argumentos é zipimportante : se você passar zip(counter, iterable), você receberá 1 a mais do que a contagem iterável!
Kye W Shi
resposta muito boa. daria recompensa por isso.
Reut Sharabani
18

Meio. Você pode verificar o __length_hint__método, mas esteja avisado de que (pelo menos até Python 3.4, como os gsnedders apontam úteis), é um detalhe de implementação não documentado ( mensagem a seguir no thread ), que pode muito bem desaparecer ou convocar demônios nasais.

Caso contrário, não. Iteradores são apenas um objeto que apenas expõe o next()método. Você pode chamá-lo quantas vezes for necessário e elas podem ou não aumentar StopIteration. Felizmente, esse comportamento é na maioria das vezes transparente para o codificador. :)

badp
fonte
5
Este não é mais o caso, como no PEP 424 e Python 3.4. __length_hint__agora está documentado, mas é uma dica e não garante a precisão.
gsnedders
12

Gosto do pacote de cardinalidade para isso, é muito leve e tenta usar a implementação mais rápida possível, dependendo do iterável.

Uso:

>>> import cardinality
>>> cardinality.count([1, 2, 3])
3
>>> cardinality.count(i for i in range(500))
500
>>> def gen():
...     yield 'hello'
...     yield 'world'
>>> cardinality.count(gen())
2

A count()implementação real é a seguinte:

def count(iterable):
    if hasattr(iterable, '__len__'):
        return len(iterable)

    d = collections.deque(enumerate(iterable, 1), maxlen=1)
    return d[0][0] if d else 0
Erwin Mayer
fonte
Eu suponho que você ainda pode iterar sobre o iterador se você usar essa função, sim?
Jcollum
12

Então, para aqueles que gostariam de conhecer o resumo dessa discussão. As melhores pontuações finais para contar uma expressão de gerador de 50 milhões de comprimento usando:

  • len(list(gen)),
  • len([_ for _ in gen]),
  • sum(1 for _ in gen),
  • ilen(gen)(de more_itertool ),
  • reduce(lambda c, i: c + 1, gen, 0),

classificados pelo desempenho da execução (incluindo consumo de memória), você ficará surpreso:

`` ``

1: test_list.py:8: 0,492 KiB

gen = (i for i in data*1000); t0 = monotonic(); len(list(gen))

('lista, sec', 1.9684218849870376)

2: test_list_compr.py:8: 0.867 KiB

gen = (i for i in data*1000); t0 = monotonic(); len([i for i in gen])

('list_compr, sec', 2.5885991149989422)

3: test_sum.py:8: 0.859 KiB

gen = (i for i in data*1000); t0 = monotonic(); sum(1 for i in gen); t1 = monotonic()

('soma, segundo', 3,441088170016883)

4: more_itertools / more.py: 413: 1.266 KiB

d = deque(enumerate(iterable, 1), maxlen=1)

test_ilen.py:10: 0.875 KiB
gen = (i for i in data*1000); t0 = monotonic(); ilen(gen)

('ilen, sec', 9.812256851990242)

5: test_reduce.py:8: 0.859 KiB

gen = (i for i in data*1000); t0 = monotonic(); reduce(lambda counter, i: counter + 1, gen, 0)

('reduzir, seg', 13.436614598002052) `` `

Portanto, len(list(gen))é o consumível mais frequente e com menos memória

Alex-Bogdanov
fonte
Como você mediu o consumo de memória?
normanius 11/11/19
1
Você pode explicar por len(list(gen))que consumir menos memória do que a abordagem baseada em reduzir? O primeiro cria um novo listque envolve alocação de memória, enquanto o último não. Então, eu esperaria que o último fosse mais eficiente em memória. Além disso, o consumo de memória dependerá do tipo de elemento.
Normanius 11/11/19
FYI: Posso reproduzir para python 3.6.8 (em um MacBookPro) que o método 1 supera os outros métodos em termos de tempo de execução (pulei o método 4).
normanius 11/11/19
len(tuple(iterable))pode ser ainda mais eficiente: artigo de Nelson Minar
VMAtm 14/11/19
9

Um iterador é apenas um objeto que possui um ponteiro para o próximo objeto a ser lido por algum tipo de buffer ou fluxo; é como um LinkedList em que você não sabe quantas coisas possui até iterá-las. Os iteradores devem ser eficientes porque tudo o que eles fazem é informar o que vem a seguir por referências, em vez de usar a indexação (mas como você viu, você perde a capacidade de ver quantas entradas são próximas).

Jesus Ramos
fonte
2
Um iterador não é nada como uma lista vinculada. Um objeto retornado de um iterador não aponta para o próximo objeto e esses objetos não são (necessariamente) armazenados na memória. Em vez disso, ele pode produzir um objeto após o outro, com base em qualquer lógica interna (que poderia ser, mas não precisa ser, com base em uma lista armazenada).
Tom
1
@ Tom: Eu estava usando o LinkedList como exemplo, principalmente porque você não sabe quanto tem, pois só sabe o que vem a seguir em certo sentido (se houver algo). Peço desculpas se minhas palavras parecem um pouco erradas ou se eu impliquei que elas são a mesma.
Jesus Ramos
8

Com relação à sua pergunta original, a resposta ainda é que geralmente não há como saber a duração de um iterador no Python.

Dado que sua pergunta é motivada por um aplicativo da biblioteca pysam, posso dar uma resposta mais específica: sou um colaborador do PySAM e a resposta definitiva é que os arquivos SAM / BAM não fornecem uma contagem exata de leituras alinhadas. Essas informações também não estão facilmente disponíveis em um arquivo de índice BAM. O melhor a fazer é estimar o número aproximado de alinhamentos usando o local do ponteiro do arquivo após ler vários alinhamentos e extrapolar com base no tamanho total do arquivo. Isso é suficiente para implementar uma barra de progresso, mas não um método de contar alinhamentos em tempo constante.

Kevin Jacobs
fonte
6

Uma referência rápida:

import collections
import itertools

def count_iter_items(iterable):
    counter = itertools.count()
    collections.deque(itertools.izip(iterable, counter), maxlen=0)
    return next(counter)

def count_lencheck(iterable):
    if hasattr(iterable, '__len__'):
        return len(iterable)

    d = collections.deque(enumerate(iterable, 1), maxlen=1)
    return d[0][0] if d else 0

def count_sum(iterable):           
    return sum(1 for _ in iterable)

iter = lambda y: (x for x in xrange(y))

%timeit count_iter_items(iter(1000))
%timeit count_lencheck(iter(1000))
%timeit count_sum(iter(1000))

Os resultados:

10000 loops, best of 3: 37.2 µs per loop
10000 loops, best of 3: 47.6 µs per loop
10000 loops, best of 3: 61 µs per loop

Ou seja, o simples count_iter_items é o caminho a percorrer.

Ajustando isso para python3:

61.9 µs ± 275 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
74.4 µs ± 190 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
82.6 µs ± 164 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Michael
fonte
Nota: este teste é baseado em python2
normanius 11/11/19
3

Existem duas maneiras de obter o comprimento de "algo" em um computador.

A primeira maneira é armazenar uma contagem - isso requer qualquer coisa que toque o arquivo / dados para modificá-lo (ou uma classe que apenas expõe interfaces - mas tudo se resume à mesma coisa).

A outra maneira é iterar sobre ela e contar quão grande é.

Wayne Werner
fonte
0

É prática comum colocar esse tipo de informação no cabeçalho do arquivo e o pysam fornecer acesso a isso. Não sei o formato, mas você verificou a API?

Como outros já disseram, você não pode saber o tamanho do iterador.

tom10
fonte
0

Isso é contrário à própria definição de um iterador, que é um ponteiro para um objeto, além de informações sobre como chegar ao próximo objeto.

Um iterador não sabe quantas vezes mais ele será capaz de iterar até terminar. Isso pode ser infinito, então o infinito pode ser sua resposta.

FCAlive
fonte
Não está violando nada, e não há nada errado em aplicar conhecimento prévio ao usar um iterador. Existem zilhões de iteradores ao redor, onde você sabe, que o número de elementos é limitado. Pense em simplesmente filtrar uma lista, você pode facilmente fornecer o tamanho máximo, você realmente não sabe quantos elementos realmente se encaixam na sua condição de filtro. Desejar saber o número de elementos correspondentes é um aplicativo válido, não violando nenhuma idéia misteriosa de um iterador.
Michael
0

Embora geralmente não seja possível fazer o que foi solicitado, ainda é útil ter uma contagem de quantos itens foram iterados após iterá-los. Para isso, você pode usar jaraco.itertools.Counter ou similar. Aqui está um exemplo usando Python 3 e rwt para carregar o pacote.

$ rwt -q jaraco.itertools -- -q
>>> import jaraco.itertools
>>> items = jaraco.itertools.Counter(range(100))
>>> _ = list(counted)
>>> items.count
100
>>> import random
>>> def gen(n):
...     for i in range(n):
...         if random.randint(0, 1) == 0:
...             yield i
... 
>>> items = jaraco.itertools.Counter(gen(100))
>>> _ = list(counted)
>>> items.count
48
Jason R. Coombs
fonte
-1
def count_iter(iter):
    sum = 0
    for _ in iter: sum += 1
    return sum
hasen
fonte
-1

Presumivelmente, você deseja contar o número de itens sem fazer iterações, para que o iterador não se esgote e use-o novamente mais tarde. Isso é possível com copyoudeepcopy

import copy

def get_iter_len(iterator):
    return sum(1 for _ in copy.copy(iterator))

###############################################

iterator = range(0, 10)
print(get_iter_len(iterator))

if len(tuple(iterator)) > 1:
    print("Finding the length did not exhaust the iterator!")
else:
    print("oh no! it's all gone")

A saída é " Finding the length did not exhaust the iterator!"

Opcionalmente (e não recomendado), você pode sombrear a lenfunção interna da seguinte maneira:

import copy

def len(obj, *, len=len):
    try:
        if hasattr(obj, "__len__"):
            r = len(obj)
        elif hasattr(obj, "__next__"):
            r = sum(1 for _ in copy.copy(obj))
        else:
            r = len(obj)
    finally:
        pass
    return r
Palito Anêmona
fonte
1
Intervalos não são iteradores. Existem alguns tipos de iteradores que podem ser copiados, mas outros farão com que esse código falhe com um TypeError (por exemplo, geradores), e a iteração através de um iterador copiado pode causar efeitos colaterais duas vezes ou causar interrupções arbitrárias no código que, por exemplo, retornou um mapiterador esperando que as chamadas de função resultantes ocorram apenas uma vez.
User2357112 suporta Monica