Como recuperar um elemento de um conjunto sem removê-lo?

427

Suponha o seguinte:

>>> s = set([1, 2, 3])

Como faço para obter um valor (qualquer valor) ssem fazer s.pop()? Quero deixar o item no conjunto até ter certeza de que posso removê-lo - algo que só posso ter certeza após uma chamada assíncrona para outro host.

Rapido e sujo:

>>> elem = s.pop()
>>> s.add(elem)

Mas você sabe de uma maneira melhor? Idealmente em tempo constante.

Daren Thomas
fonte
8
Alguém sabe por que python ainda não tem essa função implementada?
hlin117
Qual é o caso de uso? Set não tem essa capacidade por um motivo. Você deveria iterar através dele e fazer operações relacionadas ao conjunto, unionetc., sem tirar elementos dele. Por exemplo, next(iter({3,2,1}))sempre retorna, 1portanto, se você pensou que isso retornaria um elemento aleatório - não retornaria. Então, talvez você esteja usando a estrutura de dados errada? Qual é o caso de uso?
User1685095
1
Relacionados: stackoverflow.com/questions/20625579/... (. Eu sei, não é a mesma pergunta, mas existem alternativas válidas e insights lá)
John Y
@ hlin117 Porque set é uma coleção não ordenada . Como nenhuma ordem é esperada, não faz sentido recuperar um elemento em determinada posição - é esperado que seja aleatório.
Jeyekomon 03/12/19

Respostas:

545

Duas opções que não exigem cópia de todo o conjunto:

for e in s:
    break
# e is now an element from s

Ou...

e = next(iter(s))

Mas, em geral, os conjuntos não suportam indexação ou fatia.

Blair Conrad
fonte
4
Isso responde à minha pergunta. Infelizmente, acho que ainda usarei pop (), pois a iteração parece classificar os elementos. Eu preferiria-los em ordem aleatória ...
Daren Thomas
9
Eu não acho que o iter () esteja classificando os elementos - quando eu crio um conjunto e pop () até ficar vazio, fico com a ordem consistente (classificada no meu exemplo), e é o mesmo que o iterador - pop ( ) não promete ordem aleatória, apenas arbitrária, como em "Não prometo nada".
Blair Conrad
2
O +1 iter(s).next()não é nojento, mas ótimo. Completamente geral para obter um elemento arbitrário de qualquer objeto iterável. Sua escolha se você quiser ter cuidado se a coleção estiver vazia.
U0b34a0f6ae 23/10/09
8
next (iter (s)) também está OK e eu costumo pensar que lê melhor. Além disso, você pode usar um sentinela para lidar com o caso quando s estiver vazio. Por exemplo, next (iter (es), set ()).
22412 ja
5
next(iter(your_list or []), None)lidar com nenhum conjunto e conjuntos vazios
MrE
111

O menor código seria:

>>> s = set([1, 2, 3])
>>> list(s)[0]
1

Obviamente, isso criaria uma nova lista que contém cada membro do conjunto, portanto não é ótimo se o seu conjunto for muito grande.

John
fonte
96
next(iter(s))só ultrapassa list(s)[0]por três caracteres e é de outro modo dramaticamente superior em ambos tempo e espaço complexidade. Portanto, embora a alegação de "menos código" seja trivialmente verdadeira, também é trivialmente verdade que esta é a pior abordagem possível. Mesmo remover e adicionar manualmente novamente o elemento removido ao conjunto original é superior a "construir um contêiner totalmente novo apenas para extrair o primeiro elemento", o que é claramente insano. O que mais me preocupa é que 38 Stackoverflowers realmente votaram nisso. Só sei que verei isso no código de produção.
Cecil Curry
19
@augurar: Porque faz o trabalho de uma maneira relativamente simples. E às vezes isso é tudo o que importa em um script rápido.
tonysdg
4
@ Vicrobot Sim, mas faz isso copiando toda a coleção e transformando uma operação O (1) em uma operação O (n). Esta é uma solução terrível que ninguém jamais deve usar.
Augurar
9
Além disso, se você está apenas buscando "menos código" (o que é burro), min(s)usa ainda menos caracteres e é tão terrível e ineficiente quanto isso.
Augurar
5
+1 para o vencedor do código de golfe, que eu tenho um contra-exemplo prático por ser "terrível e ineficiente": min(s)é um pouco mais rápido do que next(iter(s))para conjuntos de tamanho 1, e cheguei a essa resposta procurando especificamente casos especiais que extraem o único elemento de conjuntos do tamanho 1.
lehiester 18/01/19
50

Gostaria de saber como as funções serão executadas para conjuntos diferentes, então fiz um benchmark:

from random import sample

def ForLoop(s):
    for e in s:
        break
    return e

def IterNext(s):
    return next(iter(s))

def ListIndex(s):
    return list(s)[0]

def PopAdd(s):
    e = s.pop()
    s.add(e)
    return e

def RandomSample(s):
    return sample(s, 1)

def SetUnpacking(s):
    e, *_ = s
    return e

from simple_benchmark import benchmark

b = benchmark([ForLoop, IterNext, ListIndex, PopAdd, RandomSample, SetUnpacking],
              {2**i: set(range(2**i)) for i in range(1, 20)},
              argument_name='set size',
              function_aliases={first: 'First'})

b.plot()

insira a descrição da imagem aqui

Este lote mostra claramente que algumas abordagens ( RandomSample, SetUnpackinge ListIndex) dependem do tamanho do conjunto e deve ser evitado no caso geral (pelo menos se o desempenho pode ser importante). Como já mostrado pelas outras respostas, o caminho mais rápido é ForLoop.

No entanto, desde que uma das abordagens de tempo constante seja usada, a diferença de desempenho será insignificante.


iteration_utilities(Isenção de responsabilidade: sou o autor) contém uma função de conveniência para este caso de uso first::

>>> from iteration_utilities import first
>>> first({1,2,3,4})
1

Eu também o incluí no benchmark acima. Ele pode competir com as outras duas soluções "rápidas", mas a diferença não é grande.

MSeifert
fonte
43

tl; dr

for first_item in muh_set: breakcontinua sendo a abordagem ideal no Python 3.x. Maldito seja, Guido.

você faz isso

Bem-vindo a mais um conjunto de horários do Python 3.x, extrapolado de wr. é excelente resposta específica de 2.x do Python . Diferentemente da resposta específica do Python 3.x, igualmente útil, do AChampion , os intervalos abaixo também cronometram as soluções mais extremas sugeridas acima - incluindo:

Trechos de código para grande alegria

Ligue, sintonize, cronometre:

from timeit import Timer

stats = [
    "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
    "for i in range(1000): next(iter(s))",
    "for i in range(1000): s.add(s.pop())",
    "for i in range(1000): list(s)[0]",
    "for i in range(1000): random.sample(s, 1)",
]

for stat in stats:
    t = Timer(stat, setup="import random\ns=set(range(100))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Temporizações atemporais rapidamente obsoletas

Ver! Ordenados pelos snippets mais rápidos e mais lentos:

$ ./test_get.py
Time for for i in range(1000): 
    for x in s: 
        break:   0.249871
Time for for i in range(1000): next(iter(s)):    0.526266
Time for for i in range(1000): s.add(s.pop()):   0.658832
Time for for i in range(1000): list(s)[0]:   4.117106
Time for for i in range(1000): random.sample(s, 1):  21.851104

Faceplants para toda a família

Sem surpresa, a iteração manual permanece pelo menos duas vezes mais rápida que a próxima solução mais rápida. Embora a diferença tenha diminuído nos dias Bad Old Python 2.x (nos quais a iteração manual foi pelo menos quatro vezes mais rápida), decepciona o fanático do PEP 20 em mim, que a solução mais detalhada é a melhor. Pelo menos converter um conjunto em uma lista apenas para extrair o primeiro elemento do conjunto é tão horrível quanto o esperado. Graças a Guido, que sua luz continue a nos guiar.

Surpreendentemente, a solução baseada em RNG é absolutamente horrível. Conversão de lista é ruim, mas random realmente leva o bolo de molho horrível. Tanta coisa para o Deus do Número Aleatório .

Eu só queria que os amorfos já tivessem um set.get_first()método para nós. Se você está lendo isso, eles: "Por favor, faça alguma coisa".

Cecil Curry
fonte
2
Eu acho que reclamar que isso next(iter(s)) é duas vezes mais lento do que for x in s: breakem CPythoné meio estranho. Eu quero dizer que é CPython. Será cerca de 50 a 100 vezes (ou algo parecido) mais lento que C ou Haskell fazendo a mesma coisa (na maior parte do tempo, especialmente na iteração, sem eliminação de chamada de cauda e sem otimizações). Perder alguns microssegundos não faz uma diferença real. Você não acha? E também tem o
PyPy
39

Para fornecer alguns números de tempo por trás das diferentes abordagens, considere o código a seguir. O get () é minha adição personalizada ao setobject.c do Python, sendo apenas um pop () sem remover o elemento.

from timeit import *

stats = ["for i in xrange(1000): iter(s).next()   ",
         "for i in xrange(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in xrange(1000): s.add(s.pop())   ",
         "for i in xrange(1000): s.get()          "]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100))")
    try:
        print "Time for %s:\t %f"%(stat, t.timeit(number=1000))
    except:
        t.print_exc()

A saída é:

$ ./test_get.py
Time for for i in xrange(1000): iter(s).next()   :       0.433080
Time for for i in xrange(1000):
        for x in s:
                break:   0.148695
Time for for i in xrange(1000): s.add(s.pop())   :       0.317418
Time for for i in xrange(1000): s.get()          :       0.146673

Isso significa que a solução for / break é a mais rápida (às vezes mais rápida que a solução get () personalizada).

wr.
fonte
Alguém tem uma idéia de por que iter (s) .next () é muito mais lento que as outras possibilidades, ainda mais lento que s.add (s.pop ())? Para mim, parece um projeto muito ruim de iter () e next () se os tempos forem assim.
peschü 24/06
Bem, para aquele que a linha cria um novo objeto iter a cada iteração.
Ryan
3
@ Ryan: Um objeto iterador não é criado implicitamente for x in stambém? "Um iterador é criado para o resultado do expression_list."
Musiphil
2
@musiphil Isso é verdade; originalmente, eu perdi o "break" de 0,14, o que é realmente contra-intuitivo. Quero mergulhar nisso quando tiver tempo.
Ryan
1
Eu sei que isto é antiga, mas ao adicionar s.remove()ao misturar os iterexemplos tanto fore iterir catastroficamente ruim.
precisa saber é o seguinte
28

Como você deseja um elemento aleatório, isso também funcionará:

>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]

A documentação não parece mencionar o desempenho de random.sample. De um teste empírico muito rápido, com uma lista enorme e um conjunto enorme, parece haver tempo constante para uma lista, mas não para o conjunto. Além disso, a iteração sobre um conjunto não é aleatória; o pedido é indefinido, mas previsível:

>>> list(set(range(10))) == range(10)
True 

Se a aleatoriedade for importante e você precisar de vários elementos em tempo constante (conjuntos grandes), eu usaria random.samplee converteria em uma lista primeiro:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
dF.
fonte
14
Se você quer apenas um elemento, random.choice é mais sensato.
Gregg Lind
list (s) .pop () servirá se você não se importar com qual elemento usar.
Evgeny
8
@ Gregg: Você não pode usar choice(), porque o Python tentará indexar seu conjunto e isso não funciona.
Kevin
3
Embora inteligente, essa é realmente a solução mais lenta já sugerida por uma ordem de magnitude. Sim, é tão lento. Até converter o conjunto em uma lista apenas para extrair o primeiro elemento dessa lista é mais rápido. Para os não crentes entre nós ( ... oi! ), Veja esses horários fabulosos .
Cecil Curry
9

Aparentemente, a maneira mais compacta (6 símbolos), embora muito lenta , de obter um elemento definido (possibilitado pelo PEP 3132 ):

e,*_=s

Com o Python 3.5+, você também pode usar esta expressão de 7 símbolos (graças ao PEP 448 ):

[*s][0]

Ambas as opções são aproximadamente 1000 vezes mais lentas na minha máquina do que o método for-loop.

skovorodkin
fonte
1
O método do loop for (ou mais precisamente o método do iterador) possui complexidade de tempo O (1), enquanto esses métodos são O (N). Eles são concisos embora. :)
ForeverWintr
6

Eu uso uma função de utilidade que escrevi. Seu nome é um tanto enganador, porque meio que implica que pode ser um item aleatório ou algo assim.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None
usuario
fonte
2
Você também pode ir com o próximo (iterável (iterável), Nenhum) para economizar tinta :)
1 ''
3

Seguindo @wr. post, obtenho resultados semelhantes (para Python3.5)

from timeit import *

stats = ["for i in range(1000): next(iter(s))",
         "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in range(1000): s.add(s.pop())"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Resultado:

Time for for i in range(1000): next(iter(s)):    0.205888
Time for for i in range(1000): 
    for x in s: 
        break:                                   0.083397
Time for for i in range(1000): s.add(s.pop()):   0.226570

No entanto, ao alterar o conjunto subjacente (por exemplo, chamar para remove()), as coisas correm mal nos exemplos iteráveis ​​( for, iter):

from timeit import *

stats = ["while s:\n\ta = next(iter(s))\n\ts.remove(a)",
         "while s:\n\tfor x in s: break\n\ts.remove(x)",
         "while s:\n\tx=s.pop()\n\ts.add(x)\n\ts.remove(x)"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Resulta em:

Time for while s:
    a = next(iter(s))
    s.remove(a):             2.938494
Time for while s:
    for x in s: break
    s.remove(x):             2.728367
Time for while s:
    x=s.pop()
    s.add(x)
    s.remove(x):             0.030272
Um campeão
fonte
1

O que costumo fazer para coleções pequenas é criar um tipo de método analisador / conversor como este

def convertSetToList(setName):
return list(setName)

Então eu posso usar a nova lista e acessar pelo número do índice

userFields = convertSetToList(user)
name = request.json[userFields[0]]

Como lista, você terá todos os outros métodos com os quais pode precisar trabalhar.

Josué Carvajal
fonte
por que não usar em listvez de criar um método conversor?
Daren Thomas
-1

Que tal s.copy().pop()? Ainda não cronometrei, mas deve funcionar e é simples. No entanto, funciona melhor para conjuntos pequenos, pois copia todo o conjunto.

Solomon Ucko
fonte
-6

Outra opção é usar um dicionário com valores dos quais você não se importa. Por exemplo,


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...

Você pode tratar as chaves como um conjunto, exceto que elas são apenas uma matriz:


keys = poor_man_set.keys()
print "Some key = %s" % keys[0]

Um efeito colateral dessa opção é que seu código será compatível com versões anteriores e mais setantigas do Python. Talvez não seja a melhor resposta, mas é outra opção.

Edit: Você pode até fazer algo assim para esconder o fato de que você usou um dict em vez de uma matriz ou conjunto:


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
poor_man_set = poor_man_set.keys()
Pat Notz
fonte
3
Isso não funciona da maneira que você espera. No python 2 keys () é uma operação O (n), então você não fica mais tempo constante, mas pelo menos keys [0] retornará o valor esperado. No python 3 keys () é uma operação O (1), então sim! No entanto, ele não retorna mais um objeto de lista, mas sim um objeto de conjunto que não pode ser indexado; portanto, as teclas [0] lançariam TypeError. stackoverflow.com/questions/39219065/...
sage88