proceso - tiempo de ejecucion python

Rendimiento de pequeños sets en Python

Question

Estoy buscando la manera más eficiente de representar pequeños conjuntos de enteros en un rango dado (digamos 0-10) en Python. En este caso, la eficiencia implica una construcción rápida (de una lista sin clasificar), una consulta rápida (un par de consultas en cada conjunto) y una construcción razonablemente rápida de una versión ordenada (tal vez una vez cada diez conjuntos, más o menos). A priori, los candidatos están usando el tipo de conjunto incorporado de Python (consulta rápida), usando una matriz ordenada (¿quizás más rápida de compilar?), O usando una matriz de bits (todo rápido si estuviese en C ... pero dudo que Python sea ese eficiente (?)). ¿Algún consejo de cuál elegir?

Gracias.

Answer 1

En este caso, puede usar una lista de valores Verdadero / Falso. La tabla hash utilizada por el set hará lo mismo, pero incluirá una sobrecarga para hash, asignación de cubo y detección de colisión.

myset = [False] * 11
for i in values:
    myset[i] = True
mysorted = [i for i in range(11) if myset[i]]

Como siempre, necesita medirlo usted mismo para saber cómo funciona en sus circunstancias.

Answer 2

Mi consejo es seguir con el set() incorporado set() . Será muy difícil escribir código Python que supere el código C incorporado para el rendimiento. La velocidad de construcción y la velocidad de búsqueda serán más rápidas si confía en el código C incorporado.

Para una lista ordenada, la mejor opción es utilizar la función de clasificación incorporada:

x = set(seq) # build set from some sequence
lst = sorted(x)  # get sorted list from set

En general, en Python, cuanto menos código escriba, más rápido será. Mientras más puedas confiar en los fundamentos de C integrados de Python, más rápido. En muchos casos, Python interpretado es 20x a 100 veces más lento que el código C, y es extremadamente difícil ser tan inteligente que salga adelante frente a solo usar las funciones incorporadas como se esperaba.

Si se garantiza que sus conjuntos siempre serán enteros en el rango de [0, 10], y desea asegurarse de que la huella de memoria sea lo más pequeña posible, los indicadores de bits dentro de un número entero serían el camino a seguir.

pow2 = [2**i for i in range(32)]

x = 0  # set with no values
def add_to_int_set(x, n):
    return x | pow2[n]

def in_int_set(x, n):
    return x & pow2[n]

def list_from_int_set(x):
    return [i for i in range(32) if x & pow2[i]]

Apuesto a que esto es realmente más lento que usar las funciones set() incorporadas, pero sabes que cada conjunto será un objeto int : 4 bytes, más la sobrecarga de un objeto Python.

Si literalmente necesitaras miles de millones de ellos, podrías ahorrar espacio usando una array NumPy en lugar de una lista de Python; la array NumPy solo almacenará enteros enteros. De hecho, NumPy tiene un tipo de entero de 16 bits, por lo que si sus conjuntos están realmente solo en el rango de [0, 10], puede obtener el tamaño de almacenamiento de hasta dos bytes cada uno usando una array NumPy.

http://www.scipy.org/FAQ#head-16a621f03792969969e44df8a9eb360918ce9613

Answer 3

Yo usaría un mapa de bits y almacenaría los miembros de un "conjunto" en un int ... que en realidad podría ser más rápido que el tipo de set integrado en este caso, aunque no lo he probado. Definitivamente requerirá menos almacenamiento.

Actualizar

No tengo tiempo ahora mismo para hacer una implementación completa y compararla con la clase incorporada de Python, pero esto es lo que creo que es un ejemplo de trabajo que ilustra mi sugerencia. Como creo que estarían de acuerdo, el código parece bastante rápido y eficiente desde el punto de vista de la memoria.

Dadas las capacidades integer largas "ilimitadas" casi transparentes de Python, lo que se escribe funcionará automáticamente con valores enteros en un rango mucho más grande de lo que necesita, aunque hacerlo podría ralentizar un poco las cosas. ;)

class BitSet(object):
    def __init__(self, *bitlist):
        self._bitmap = 0
        for bitnum in bitlist:
            self._bitmap |= (1 << bitnum)

    def add(self, bitnum):
        self._bitmap |= (1 << bitnum)

    def remove(self, bitnum):
        if self._bitmap & (1 << bitnum):
            self._bitmap &= ~(1 << bitnum)
        else:
            raise KeyError

    def discard(self, bitnum):
       self._bitmap &= ~(1 << bitnum)

    def clear(self):
        self._bitmap = 0

    def __contains__(self, bitnum):
        return bool(self._bitmap & (1 << bitnum))

    def __int__(self):
        return self._bitmap

if __name__ == ''__main__'':

    bs = BitSet()

    print ''28 in bs:'', 28 in bs
    print ''bs.add(28)''
    bs.add(28)
    print ''28 in bs:'', 28 in bs

    print
    print ''5 in bs:'', 5 in bs
    print ''bs.add(5)''
    bs.add(5)
    print ''5 in bs:'', 5 in bs

    print
    print ''bs.remove(28)''
    bs.remove(28)
    print ''28 in bs:'', 28 in bs