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

https://stackoverflow.com/questions/59825

python
set

09-06-2019
|

Pergunta

Suponha o seguinte:

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

Como obtenho um valor (qualquer valor) de s sem 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ê conhece uma maneira melhor?Idealmente em tempo constante.

Solução

Duas opções que não exigem a 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 fatiamento.

Outras dicas

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 é bom se o seu conjunto for muito grande.

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

Isto significa que o para/quebrar solução é a mais rápida (às vezes mais rápida que a solução get() personalizada).

dr.

for first_item in muh_set: break continua sendo a abordagem ideal em Python 3.x. ^{Maldito seja, Guido.}

você faz isso

Bem-vindo a mais um conjunto de tempos do Python 3.x, extrapolados de wr.é excelente Resposta específica do Python 2.x.Diferente Um campeãoé igualmente útil Resposta específica do Python 3.x, os horários abaixo também soluções atípicas de tempo sugeridas acima - incluindo:

list(s)[0], Johnromance de solução baseada em sequência.
random.sample(s, 1), dF.é eclético Solução baseada em RNG.

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()

Tempos atemporais rapidamente obsoletos

Contemplar! Ordenado pelos trechos mais rápidos para os 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

Plantas faciais para toda a família

Sem surpresa, a iteração manual permanece pelo menos duas vezes mais rápida como a próxima solução mais rápida.Embora a diferença tenha diminuído em relação aos dias do Bad Old Python 2.x (nos quais a iteração manual era pelo menos quatro vezes mais rápida), isso decepciona o PEP 20 fanático 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. Obrigado Guido, que sua luz continue nos guiando.

Surpreendentemente, o A solução baseada em RNG é absolutamente horrível. A conversão de lista é ruim, mas random realmente pega o bolo com molho horrível.Tanto para o Deus dos Números Aleatórios.

Eu só queria que o amorfo Eles fizessem PEP um set.get_first() método para nós já.Se você está lendo isso, eles:"Por favor.Faça alguma coisa."

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.A partir de um teste empírico muito rápido com uma lista enorme e um conjunto enorme, parece ser um tempo constante para uma lista, mas não para o conjunto.Além disso, a iteração em um conjunto não é aleatória;a ordem é indefinida, 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.sample e converta para uma lista primeiro:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time

Eu me perguntei como as funções funcionariam 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()

Este gráfico mostra claramente que algumas abordagens (RandomSample, SetUnpacking e ListIndex) dependem do tamanho do conjunto e devem ser evitados no caso geral (pelo menos se o desempenho poder ser importante).Como já mostrado pelas outras respostas, o caminho mais rápido é ForLoop.

Entretanto, 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 conveniente 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 de qualquer maneira.

Eu uso uma função utilitária que escrevi.Seu nome é um tanto enganador porque implica que pode ser um item aleatório ou algo parecido.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None

Aparentemente o mais compacto (6 símbolos) embora muito devagar maneira de obter um elemento de conjunto (tornado possível por PEP 3132):

e,*_=s

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

[*s][0]

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

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()

Saída:

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 ex.ligar para remove()) as coisas vão mal para os 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

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

Outra opção é usar um dicionário com valores que não lhe interessam.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 um array:


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

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

Editar:Você pode até fazer algo assim para esconder o fato de ter usado um dict em vez de um array 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()

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow