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

427

Supongamos lo siguiente:

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

¿Cómo obtengo un valor (cualquier valor) ssin hacerlo s.pop()? Quiero dejar el elemento en el conjunto hasta que esté seguro de que puedo eliminarlo, algo de lo que solo puedo estar seguro después de una llamada asincrónica a otro host.

Rápido y sucio:

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

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

Daren Thomas
fuente
8
¿Alguien sabe por qué Python aún no tiene esta función implementada?
hlin117
¿Cuál es el caso de uso? Set no tiene esta habilidad por una razón. Se supone que debe iterar a través de él y realizar operaciones relacionadas con el conjunto, como unionetc., sin tomar elementos de él. Por ejemplo, next(iter({3,2,1}))siempre regresa, 1así que si pensabas que esto devolvería un elemento aleatorio, no lo haría. Entonces, ¿tal vez solo estás usando la estructura de datos incorrecta? ¿Cuál es el caso de uso?
user1685095
1
Relacionado: stackoverflow.com/questions/20625579/… (Lo sé, no es la misma pregunta, pero hay alternativas e ideas valiosas allí).
John Y
@ hlin117 Porque set es una colección desordenada . Como no se espera ningún orden, no tiene sentido recuperar un elemento en una posición dada; se espera que sea aleatorio.
Jeyekomon

Respuestas:

547

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 indexación o segmentación.

Blair Conrad
fuente
44
Esto responde a mi pregunta. Por desgracia, supongo que seguiré usando pop (), ya que la iteración parece ordenar los elementos. Los preferiría en orden aleatorio ...
Daren Thomas
99
No creo que iter () esté ordenando los elementos: cuando creo un conjunto y pop () hasta que esté vacío, obtengo un orden consistente (ordenado, en mi ejemplo), y es lo mismo que el iterador - pop ( ) no promete un orden aleatorio, solo arbitrario, como en "No prometo nada".
Blair Conrad
2
+1 iter(s).next()no es asqueroso pero genial. Completamente general para tomar elementos arbitrarios de cualquier objeto iterable. Sin embargo, puede elegir si desea tener cuidado si la colección está vacía.
u0b34a0f6ae
8
next (iter (s)) también está bien y tiendo a pensar que se lee mejor. Además, puede usar un centinela para manejar el caso cuando s está vacío. Por ejemplo, next (iter (s), set ()).
ja
55
next(iter(your_list or []), None)para manejar conjuntos de Ninguno y conjuntos vacíos
MrE
111

El código mínimo sería:

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

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

Juan
fuente
97
next(iter(s))solo supera list(s)[0]en tres caracteres y, por lo demás, es dramáticamente superior en complejidad de tiempo y espacio. Entonces, aunque la afirmación del "código mínimo" es trivialmente cierta, también es trivialmente cierto que este es el peor enfoque posible. Incluso eliminar manualmente y luego volver a agregar el elemento eliminado al conjunto original es superior a "construir un contenedor completamente nuevo solo para extraer el primer elemento", que es evidentemente una locura. Lo que más me preocupa es que 38 Stackoverflowers realmente votaron por esto. Solo sé que veré esto en el código de producción.
Cecil Curry
19
@augurar: Porque hace el trabajo de una manera relativamente simple. Y a veces eso es todo lo que importa en un guión rápido.
tonysdg
44
@Vicrobot Sí, pero lo hace copiando toda la colección y convirtiendo una operación O (1) en una operación O (n). Esta es una solución terrible que nadie debería usar.
augurar
99
Además, si solo está apuntando al "código mínimo" (que es tonto), entonces min(s)usa incluso menos caracteres y es tan terrible e ineficiente como esto.
augurar
55
+1 para el ganador del código de golf, que tengo un contraejemplo práctico por ser "terrible e ineficiente": min(s)es un poco más rápido que next(iter(s))para los conjuntos de tamaño 1, y llegué a esta respuesta buscando específicamente extraer un único elemento de los conjuntos en caso especial de tamaño 1.
lehiester
52

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

ingrese la descripción de la imagen aquí

Este gráfico muestra claramente que algunos enfoques ( RandomSample, SetUnpackingy 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, siempre que se utilice uno de los enfoques de tiempo constante, la diferencia de rendimiento será insignificante.


iteration_utilities(Descargo de responsabilidad: soy el autor) contiene una función conveniente 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.

MSeifert
fuente
43

tl; dr

for first_item in muh_set: breaksigue siendo el enfoque óptimo en Python 3.x. Te maldigo, Guido.

haces esto

Bienvenido a otro conjunto de temporizaciones de Python 3.x, extrapolado de wr. 's excelente respuesta específica 2.x-Python . A diferencia de la respuesta específica de Python 3.x igualmente útil de AChampion , los tiempos a continuación también presentan soluciones atípicas sugeridas anteriormente, que incluyen:

Fragmentos de código para gran alegría

Enciende, sintoniza, cronometra:

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 intemporales rápidamente obsoletos

¡Mirad! Ordenado por fragmentos más rápidos a 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

Faceplants para toda la familia

Como era de esperar, la iteración manual sigue siendo al menos el doble de rápida que la próxima solución más rápida. Aunque la brecha ha disminuido desde los días Bad Old Python 2.x (en los que la iteración manual fue al menos cuatro veces más rápida), decepciona al fanático de PEP 20 en mí 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 continúe guiándonos.

Sorprendentemente, la solución basada en RNG es absolutamente horrible. La conversión de la lista es mala, pero random realmente toma el pastel de salsa horrible. Esto en cuanto al Dios del número aleatorio .

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

Cecil Curry
fuente
2
Creo que quejarse de que eso next(iter(s)) es dos veces más lento que for x in s: breaken CPythones un poco extraño. Quiero decir que es CPython. Será aproximadamente 50-100 veces (o algo así) más lento que C o Haskell haciendo lo mismo (la mayor parte del tiempo, especialmente en iteración, sin eliminación de llamadas de cola y sin optimizaciones de ningún tipo). Perder algunos microsegundos no hace una diferencia real. ¿No te parece? Y también está PyPy
usuario1685095
39

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

El resultado 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 get () personalizada).

wr.
fuente
¿Alguien tiene una idea de por qué iter (s) .next () es mucho más lento que las otras posibilidades, incluso más lento que s.add (s.pop ())? Para mí se siente como un muy mal diseño de iter () y next () si los tiempos se ven así.
peschü
Bueno, para una esa línea crea un nuevo objeto iter en cada iteración.
Ryan
3
@Ryan: ¿No se crea implícitamente un objeto iterador for x in stambién? "Se crea un iterador para el resultado de la expression_list".
musiphil
2
@musiphil Eso es cierto; Originalmente me perdí el "descanso" en 0.14, eso es realmente contra-intuitivo. Quiero profundizar en esto cuando tenga tiempo.
Ryan
1
Sé que esto es viejo, pero cuando se añade s.remove()a la mezcla de los iterejemplos tanto fory itervoy catastróficamente mal.
AChampion
28

Como desea 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 gran lista y un gran conjunto, 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 necesita un montón de elementos en tiempo constante (conjuntos grandes), random.sampleprimero usaría y convertiría a una lista:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
dF.
fuente
14
Si solo quieres un elemento, random.choice es más sensato.
Gregg Lind el
list (s) .pop () funcionará si no te importa qué elemento tomar.
Evgeny
8
@ Gregg: No puedes usar choice(), porque Python intentará indexar tu conjunto y eso no funciona.
Kevin
3
Si bien es inteligente, esta es realmente la solución más lenta sugerida hasta ahora por un orden de magnitud. Sí, es que lento. Incluso convertir el conjunto en una lista solo para extraer el primer elemento de esa lista es más rápido. Para los no creyentes entre nosotros ( ... ¡hola! ), Vea estos tiempos fabulosos .
Cecil Curry
9

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

e,*_=s

Con Python 3.5+ también puede 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.

skovorodkin
fuente
1
El método for loop (o más exactamente el método iterador) tiene una complejidad de tiempo O (1), mientras que estos métodos son O (N). Sin embargo, son concisos . :)
ForeverWintr
6

Yo uso una función de utilidad que escribí. Su nombre es algo 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
Mella
fuente
2
También puede ir con el siguiente (iter (iterable), Ninguno) para ahorrar tinta :)
1 ''
3

Siguiendo @wr. post, 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, llamar 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
Un campeón
fuente
1

Lo que suelo hacer para colecciones pequeñas es crear un tipo de método analizador / convertidor como este

def convertSetToList(setName):
return list(setName)

Entonces puedo usar la nueva lista y acceder por número de índice

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

Como lista, tendrá todos los otros métodos con los que puede necesitar trabajar

Josué Carvajal
fuente
¿Por qué no usarlo en listlugar de crear un método convertidor?
Daren Thomas
-1

¿Qué tal 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.

Solomon Ucko
fuente
-6

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

Puede tratar las teclas 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 setversiones anteriores de Python anteriores. Tal vez 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()
Pat Notz
fuente
3
Esto no funciona de la manera que espera. En python 2, keys () es una operación O (n), por lo que ya no es un tiempo constante, pero al menos las teclas [0] devolverán el valor que espera. En python 3 keys () es una operación O (1), ¡así que sí! Sin embargo, ya no devuelve un objeto de lista, devuelve un objeto tipo conjunto que no se puede indexar, por lo que las teclas [0] arrojarían TypeError. stackoverflow.com/questions/39219065/…
sage88