python - palabra - ¿Cómo recuperar un elemento de un conjunto sin eliminarlo?

conjuntos en python

Question

Supongamos lo siguiente:

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

¿Cómo obtengo un valor (cualquier valor) de s sin hacer s.pop() ? Quiero dejar el elemento en el conjunto hasta que esté seguro de poder eliminarlo, algo de lo que solo puedo estar seguro después de una llamada asíncrona a otro host.

Rápido y sucio:

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

¿Pero sabes de una manera mejor? Idealmente en tiempo constante.

Answer 1

tl; dr

for first_item in muh_set: break sigue siendo el enfoque óptimo en Python 3.x. ^{Maldito seas, guido.}

haces esto

Bienvenido a otro conjunto de tiempos de Python 3.x, extrapolados de La excelente respuesta específica de Python 2.x. A diferencia de la respuesta específica de Python 3.x, igualmente útil de AChampion , los tiempos a continuación también son soluciones atípicas sugeridas anteriormente, que incluyen:

• list(s)[0] , la novedosa solución basada en secuencia de .
• random.sample(s, 1) , dF. Solución ecléctica basada en RNG .

Fragmentos de código para Great Joy

Encender, sintonizar, cronometrarlo:

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

Tiempos atemporales rápidamente obsoletos

¡Mirad! Ordenado por los más rápidos a los fragmentos más 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 faciales para toda la familia.

Como era de esperar, la iteración manual sigue siendo al menos el doble de rápida que la siguiente solución más rápida. Aunque la brecha ha disminuido desde los días de Bad Old Python 2.x (en los cuales la iteración manual fue al menos cuatro veces más rápida), decepciona al fanático de PEP 20 en mí de que la solución más detallada es la mejor. Al menos convertir un conjunto en una lista solo para extraer el primer elemento del conjunto es tan horrible como se esperaba. Gracias Guido, que su luz siga guiándonos.

Sorprendentemente, la solución basada en RNG es absolutamente horrible. La conversión de listas es mala, pero al random realmente toma la torta de salsa horrible. Tanto para el Dios de los números aleatorios .

Solo deseo que los amorfos PEP a un método set.get_first() para nosotros ya. Si estás leyendo esto, ellos: "Por favor. Haz algo".

Answer 2

¿Qué hay de s.copy().pop() ? No lo he cronometrado, pero debería funcionar y es simple. Sin embargo, funciona mejor para conjuntos pequeños, ya que copia todo el conjunto.

Answer 3

Aparentemente la forma más compacta (6 símbolos) aunque muy lenta de obtener un elemento establecido (hecho posible por PEP 3132 ):

e,*_=s

Con Python 3.5+ también puedes usar esta expresión de 7 símbolos (gracias a PEP 448 ):

[*s][0]

Ambas opciones son aproximadamente 1000 veces más lentas en mi máquina que el método for-loop.

Answer 4

Como quieres un elemento aleatorio, esto también funcionará:

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

La documentación no parece mencionar el rendimiento de random.sample . De una prueba empírica realmente rápida con una lista enorme y un conjunto enorme, parece ser un tiempo constante para una lista pero no para el conjunto. Además, la iteración sobre un conjunto no es aleatoria; el orden es indefinido pero predecible:

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

Si la aleatoriedad es importante y necesitas un montón de elementos en tiempo constante (conjuntos grandes), usaría random.sample y convertiría primero a una lista:

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

Answer 5

Dos opciones que no requieren copiar todo el conjunto:

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

O...

e = next(iter(s))

Pero, en general, los conjuntos no admiten la indexación o el corte.

Answer 6

El código mínimo sería:

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

Obviamente, esto creará una nueva lista que contiene cada miembro del conjunto, por lo que no es muy bueno si su conjunto es muy grande.

Answer 7

Me pregunté cómo funcionarán las funciones para diferentes conjuntos, así que hice un punto de referencia:

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

Esta gráfica muestra claramente que algunos enfoques ( RandomSample , SetUnpacking y ListIndex ) dependen del tamaño del conjunto y deben evitarse en el caso general (al menos si el rendimiento puede ser importante). Como ya se mostró en las otras respuestas, la forma más rápida es ForLoop .

Sin embargo, mientras se utilice uno de los enfoques de tiempo constante, la diferencia de rendimiento será despreciable.

iteration_utilities (Descargo de responsabilidad: Soy el autor) contiene una función de conveniencia para este caso de uso: first :

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

También lo incluí en el punto de referencia anterior. Puede competir con las otras dos soluciones "rápidas", pero la diferencia no es mucho de ninguna manera.

Answer 8

Otra opción es usar un diccionario con valores que no le interesan. P.ej,

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

Puedes tratar las claves como un conjunto, excepto que son solo una matriz:

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

Un efecto secundario de esta elección es que su código será compatible con versiones anteriores de Python. Quizás no sea la mejor respuesta pero es otra opción.

Editar: Incluso puede hacer algo como esto para ocultar el hecho de que usó un dict en lugar de una matriz o 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()

Answer 9

Para proporcionar algunas cifras de tiempo detrás de los diferentes enfoques, considere el siguiente código. El get () es mi adición personalizada al setobject.c de Python, siendo solo un pop () sin quitar el 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()

La salida es:

$ ./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

Esto significa que la solución for / break es la más rápida (a veces más rápida que la solución personalizada get ()).

Answer 10

Siguiendo a @wr. Publicar, obtengo resultados similares (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()

Salida:

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

Sin embargo, al cambiar el conjunto subyacente (por ejemplo, la llamada a remove() ), las cosas van mal para los ejemplos iterables ( 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()

Resultados en:

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

Answer 11

Yo uso una función de utilidad que escribí. Su nombre es un tanto engañoso porque implica que podría ser un elemento aleatorio o algo así.

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