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

https://stackoverflow.com/questions/59825

python
set

09-06-2019
|

Pregunta

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 sólo puedo estar seguro después de una llamada asincrónica a otro host.

Rápido y sucio:

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

¿Pero conoces una forma mejor?Idealmente en tiempo constante.

Solución

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 ni la división.

Otros consejos

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 bueno si su conjunto es muy grande.

Para proporcionar algunas cifras de tiempo detrás de los diferentes enfoques, considere el siguiente código.get() es mi adición personalizada a 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()

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 el para/descanso La solución es la más rápida (a veces más rápida que la solución personalizada get()).

tl; dr

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

tu haces esto

Bienvenido a otro conjunto de tiempos de Python 3.x, extrapolados de wr.es excelente Respuesta específica de Python 2.x.A diferencia de Un campeónes igualmente útil Respuesta específica de Python 3.x, los horarios a continuación también soluciones atípicas de tiempo sugeridas anteriormente, que incluyen:

list(s)[0], Johnla novela solución basada en secuencia.
random.sample(s, 1), dF.es ecléctico Solución basada en RNG.

Fragmentos de código para una gran alegría

Enciéndelo, sintonízalo, cronometralo:

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! Ordenados 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

Plantas faciales para toda la familia

Como era de esperar, la iteración manual sigue siendo al menos dos veces más rápida como 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 que la iteración manual era al menos cuatro veces más rápida), decepciona a los PEPE 20 Soy un fanático de que la solución más detallada es la mejor.Al menos convertir un conjunto en una lista sólo para extraer el primer elemento del conjunto es tan horrible como se esperaba. Gracias Guido, que su luz nos siga guiando.

Sorprendentemente, el La solución basada en RNG es absolutamente horrible. La conversión de listas es mala, pero random en realidad se lleva el pastel de salsa horrible.Hasta aquí el Dios de números aleatorios.

Sólo desearía que los amorfos tuvieran PEP en un set.get_first() método para nosotros ya.Si estás leyendo esto, ellos:"Por favor.Hacer algo."

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.A partir 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 no está definido pero es 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 una lista primero:

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

Me preguntaba cómo funcionarán las funciones para diferentes conjuntos, así que hice una prueba comparativa:

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 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 podría se Importante).Como ya se muestra 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 mucha en ambos sentidos.

Utilizo 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

Aparentemente el más compacto (6 símbolos) aunque muy lento forma de obtener un elemento establecido (posible gracias a 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 del bucle for.

Siguiendo a @wr.publicación, 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()

Producción:

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 (p. ej.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

Qué tal si 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 el conjunto completo.

Otra opción es utilizar un diccionario con valores que no te 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 y anteriores.set Versiones de Python.Quizás no sea la mejor respuesta, pero es otra opción.

Editar:Incluso puedes hacer algo como esto para ocultar el hecho de que usaste 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()

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow