Estoy tratando de tener una búsqueda en tiempo constante de valores asociados con los subconjuntos de un conjunto dado, donde el orden no está garantizado.

Trabajaré activamente con el conjunto original, eliminando / agregando elementos, y me gustaría buscar valores asociados de los elementos restantes a medida que avanzo.

Por ejemplo, si mi conjunto dado es given = {1, 2, 3}, tal vez construiría un dict que se ve así ...

{
    frozenset([]): 'apple',
    frozenset([1]): 'orange',
    frozenset([2]): 'ice bear',
    frozenset([3]): 'peach',
    frozenset([1, 2]): 'grizzly',
    frozenset([2, 3]): 'pear',
    frozenset([1, 3]): 'panda',
    frozenset([1, 2, 3]): 'banana',
}

Supongamos que elimino un elemento del conjunto dado a través de given.remove(2), dejándome con {1, 3}, y quería ver el valor asociado. Tendría que obligar a mi conjunto a congelar para poder buscarlo en el dict y recuperar el valor 'panda'. En consecuencia, si vuelvo a agregar el elemento a través de given.add(2), restaurando el {1, 2, 3} original, nuevamente tendré que forzar el congelamiento antes de recuperar banana del dict.

Siento que tener que coaccionar a un grupo congelado es una operación O (n) que anula el propósito de una búsqueda O (1).

¿Hay alguna manera de implementar más eficientemente este tipo de búsqueda en Python? ¿O hay alguna estructura de datos que pueda ayudarme aquí?

Estoy en Py2.7 pero si Py3 es mejor para esto, hágamelo saber. ¡Gracias!

1
the_lrner 14 may. 2016 a las 01:02

3 respuestas

La mejor respuesta

Siento que tener que coaccionar a un grupo congelado es una operación O (n) que anula el propósito de una búsqueda O (1).

Es lineal en el tamaño de given, no en el tamaño del dict. En comparación, tomar el hash también es lineal en el tamaño de given, por lo que incluso si no tuviera que construir un conjunto congelado, todavía tendría la misma complejidad asintótica.

Si este costo es demasiado costoso para usted, puede intentar escribir su propia clase de contenedor de conjuntos con una función hash que permita actualizaciones incrementales y romper la condición habitual de que los objetos hash no sean mutables de manera que afecten su valor hash. Personalmente, he tenido buenos resultados con un esquema basado en Zobrist hashing, donde los elementos del conjunto son códigos hash asignados generados al azar que persisten durante la vida útil del programa, y el hash del conjunto es el XOR de todos los hashes de elementos. Cuando se agrega o elimina un elemento, el hash del conjunto se puede actualizar haciendo XOR con el hash del elemento.

1
user2357112 supports Monica 13 may. 2016 a las 22:26

Basado en la respuesta del usuario2357112. No probado porque perdí el interés.

from random import Random

class FastRehashableSet(set):
    _initial_hash = 12345

    def __init__(self, seq=()):
        super(FastRehashableSet, self).__init__(seq)
        self._hash = self._initial_hash
        for x in seq:
            self._hash_single_value(x)

    def _hash_single_value(self, val):
        # Introduce extra randomness since the intended elements are ints
        # which just return themselves when hashed
        self._hash ^= Random(hash(val)).randrange(4294967296)

    def __hash__(self):
        return self._hash

    def add(self, elem):
        super(FastRehashableSet, self).add(elem)
        self._hash_single_value(elem)

    def remove(self, elem):
        super(FastRehashableSet, self).remove(elem)
        self._hash_single_value(elem)

    def discard(self, elem):
        change = elem in self
        super(FastRehashableSet, self).discard(elem)
        if change:
            self._hash_single_value(elem)

    def pop(self):
        val = super(FastRehashableSet, self).pop()
        self._hash_single_value(val)
        return val

    def clear(self):
        super(FastRehashableSet, self).clear()
        self._hash = self._initial_hash

    # You get the idea, I'm not doing these

    def update(self):
        raise NotImplemented

    def intersection_update(self):
        raise NotImplemented

    def difference_update(self):
        raise NotImplemented

    def symmetric_difference_update(self):
        raise NotImplemented
0
Alex Hall 13 may. 2016 a las 22:52

¿Qué pasa con la codificación del índice de las palabras en una lista en binario de la lista de elementos:

words = ["apple","orange","ice bear","peach","grizzly","panda","pear","banana"]

def get_indice(L):
    return sum(2**(i-1) for i in L)

# initial serie of elements
serie = [1,2,3]

# first computation of indice
ind = get_indice([1,2,3])

print serie,words[ind]

# remove the 2
val = 2
serie.remove(val)
ind -= 2**(val-1)

print serie,words[ind]

# add the 2
val = 2
serie.append(val)
serie = sorted(serie)
ind += 2**(val-1)

print serie,words[ind]

Salida:

[1, 2, 3] banana
[1, 3] panda
[1, 2, 3] banana

Tenga en cuenta que el primer cálculo cuesta N operaciones donde N es el número de elementos en serie que es mejor que el número de elementos en palabras. Las siguientes operaciones de agregar y quitar son directas y cuestan O (1).

Como la eliminación del elemento en serie puede costar algo de acuerdo con https://wiki.python.org/moin/ TimeComplexity. Quizás sea mejor invocar directamente get_indices de todos modos.

0
Vince 14 may. 2016 a las 20:13