El método más eficiente para obtener claves para valores similares en un dict.

Tengo un diccionario de objetos:

# I have thousands of objects in my real world scenario dic = {'k1':obj1, 'k2':obj2, 'k3':obj3, ...} # keys are string # objs are MyObject 

Edit : Lo siento por dejar la duda en la pregunta. Aquí está la clase exacta y la función like() :

 class MyObject(object): def __init__(self, period, dimensions): self.id = None self.period = period # period is etree.Element self.dimensions = dict() # id -> lxml.XMLElements for dim in dimensions: # there must be only one child: the typed dimension self.dimensions[dim.get('dimension')] = dim[0] self._hash = None def __eq__(self, other): return isinstance(other, MyObject) and self.period == other.period and self.dimensions == other.dimensions def like(self, other): return (other is not None \ and self.period == other.period \ and self.dimensions.keys() == other.dimensions.keys()) 

Me pregunto cómo puedo tener la mejor implementación para encontrar objetos en el diccionario dic que sean similares a un valor val dado. Algo equivalente a:

 def find_keys(dic, val): return [v for v in dic if v.like(val)) 

Sin embargo, este método es demasiado lento, porque tengo miles de iteraciones sobre find-keys() y miles de objetos en el diccionario.

En este momento, he implementado un __hash__(self) en estos objetos, y he agregado la clave como una propiedad:

  def __hash__(self): if self._hash is None: self._hash = hash(self.periodtype) ^ \ hash(tuple(sorted(self.dimensions.values()))) return self._hash 

Entonces, he construido un diccionario de búsqueda que es

 hash_dic = { hash(obj1): [obj1], hash(obj2): [obj2, obj3] } 

Y este nuevo método de búsqueda es mucho más rápido:

 def find_keys_fast(dic, val): prefetched=hash_dic[hash(val)] return [x.key for x in prefetched if x.like(val)] 

Dado que __hash__ es una función nativa utilizada internamente por los Conjuntos y Diccionarios, ¿hay algo más rápido o más elegante que pueda hacer?

Ahora que podemos ver la implementación de “me like , parece factible un enfoque bastante simple, mucho más simple que mi otra respuesta, por like . Defina un nuevo método de signature en MyObject :

 def signature(self): return (self.period, frozenset(self.dimensions.keys())) 

Y luego iterar a través de los objetos:

 import collections sig_keys = collections.defaultdict(set) for k, obj in dic.iteritems(): sig_keys[obj.signature()].add(k) 

Con eso, sig_keys.values() proporciona todos los conjuntos de identificadores para objetos que son iguales. Las listas de objetos podrían construirse directamente, si eso fuera mejor:

 sig_objs = collections.defaultdict(list) for obj in dic.itervalues(): sig_objs[obj.signature()].append(obj) 

Si lo desea, puede definir __hash__ para return hash(self.signature()) o su equivalente.

Dado que no conozco la estructura de sus datos o la naturaleza de la similitud que está buscando, solo puedo adivinar qué podría funcionar. Pero quizás podrías construir algún tipo de árbol de prefijos usando diccionarios. Como en:

 trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}} 

Estos se utilizan más comúnmente para buscar cadenas con prefijos comunes, pero quizás haya algún sentido en el que los datos de sus objetos se puedan representar como una cadena. Esto parece que funcionaría especialmente bien si hay algún orden en que se pueden poner los datos de tal manera que los datos anteriores en la cadena deben compararse como == . Creo que incluso puedo imaginar las hojas del trie incluyendo todos los objetos similares, en lugar de todos estrictamente equivalentes.

Un pequeño ejemplo de juguete de cómo trabajar con un trie:

 >>> trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}} >>> def rec_print(trie, accum=''): ... if trie: ... for k in trie: ... rec_print(trie[k], accum + k) ... else: ... print accum ... >>> rec_print(trie) ack act abs abe 

Su enfoque me parece bastante bueno si solo desea los objetos similares de algunos objetos.

Tampoco hay nada de malo en definir __hash__() para tu propia clase.

Si desea agrupar todos sus objetos en clases de objetos “similares”, entonces hay un enfoque más rápido: puede utilizar la transitividad de su método like() . De hecho, si like(obj0, obj1) y like(obj1, obj2) son verdaderos, entonces like(obj0, obj2) es automáticamente verdadero, sin necesidad de cálculos adicionales. Esto significa que puede agrupar directamente todos sus objetos en clases con el eficiente

 signature = lambda obj: (obj.period, obj.typed_dimensions.keys()) sorted_objs = sorted(dic.values(), key=signature) objs_in_like_classes = [list(group) for (_, group) in itertools.groupby(sorted_objs, key=signature)] 

Esto agrupa a los objetos juntos, automáticamente. Esto es más simple, y probablemente sea más rápido que definir __hash__() y __eq__() y hacer la búsqueda groupby() por usted mismo, porque groupby() usa la transitividad de == .

( PD : Prefiero el “diccionario de objetos similares agrupados por la firma de hashable” de Michael J. Barber para esta solución, porque es probablemente un poco más rápido y también es más general, ya que no es necesario clasificarlos).

Si necesita mantener su enfoque actual, puede hacerlo de una manera un poco más limpia: puede verificar si realmente necesita alguno de estos if other is not None examen if other is not None . Si desea manejar las comparaciones ( __eq__ ) correctamente, también debe manejar el caso de other ser de una clase diferente (en lugar de verificar solo la identidad con None ); un isinstance() haría. like() puede ser diferente, si solo compara objetos de la clase MyObject . En este caso, su código debería verse como:

 def __eq__(self, other): if isinstance(other, MyObject): return (self.period == other.period and self.typed_dimensions == other.typed_dimensions) else: return False def like(self, other): return (self.period == other.period # No need for a backslash and self.typed_dimensions.keys() == other.typed_dimensions.keys()) 

Esto haría que el código sea más limpio (pero no realmente más rápido).

Podría hacer que su __hash__() funcione un poco más rápido al no hacer self._hash = None en __init__() y al escribir:

 def __hash__(self): try: return self._hash except AttributeError: self._hash = (hash(self.periodtype) ^ hash(tuple(sorted(self.dimensions.values())))) return self._hash 

De hecho, try es rápido cuando no se genera ninguna excepción (que es el caso más común con diferencia, en su caso).

En cuanto a tu hash_dict , se puede construir de manera bastante eficiente con:

 hash_dict = dict(itertools.groupby(dic.values(), key=hash)) 

(tal vez eso es lo que ya estás haciendo).

No sigo exactamente tu paso de captación previa, ya que no lo explicaste en detalle, pero ¿quizás podrías también calcular el resultado completo?

Otra posibilidad, que habría hecho, si el método like realmente se parece a eso es la indexación sobre los valores y .

Algo así como index = { 10 : [obj1], 12 : [obj2, obj3] ,... } donde las claves son el atributo y los objetos. Por lo tanto, terminas con:

 def find_keys_in_constant_time(dic, val): precomputed = index[val.y] return precomputed 

Por supuesto, también devuelve el objeto val original, pero también lo hace su método original.

Es difícil responder a esta pregunta, ya que no tengo idea de cuáles son sus requisitos. Lo que haría sería crear algún tipo de clase relacionada y rellenar sus elementos con él. La forma de implementarlo depende principalmente de las propiedades de tu función. Si su relación es simétrica (es decir, a es como b si y solo si b es como a), entonces puede agrupar elementos relacionados y, en lugar de iterar elementos, puede iterar grupos y compararlos con cualquier elemento dentro de ella; si coincide, todos los elementos dentro del clúster están en relación con su elemento.

Sin embargo, la relación de su ejemplo no es simétrica, por lo que probablemente necesite otro enfoque. Todavía podría agrupar por y y z , y al buscar el elemento tomando la intersección del cluster_y correspondiente con la unión de cluster_z sosteniendo z’s mayor o igual al elemento que se está buscando. Sin embargo, podría agregar una sobrecarga de memoria significativa si los valores difieren mucho.

Y podrías hacer otra cosa examinando las propiedades de tu relación. Podríamos ayudarte si nos proporcionas más detalles.

NOTA Después de ver la implementación de “me like , el método descrito es más complicado de lo necesario. Lo dejo aquí, ya que el enfoque puede generalizarse a medidas de similitud más difusas, por ejemplo, al menos el 50% de las dimensiones deben ser las mismas.

Lo que estás haciendo se parece mucho a un índice invertido , aunque es imposible decirlo sin saber realmente cómo se implementa. Para un índice invertido, utiliza valores de objetos posibles como las claves del diccionario, la asignación a listas (u otras colecciones) de objetos que toman esos valores. Con varias propiedades, puede hacer varios diccionarios, manejando los diferentes tipos de valores de objeto. A continuación, busque todas las propiedades del objeto en el índice invertido, determinando una similitud agregada para cada objeto en función de todas las propiedades.

Para aprovechar al máximo el índice invertido, es mejor pensar en devolver todos los objetos similares de una función. Esto le ayuda a manejar cada posible “me gusta” objetos solo una vez. Como ejemplo extremo, puede tener un objeto como otro solo si todas las propiedades son iguales; los objetos similares son aquellos objetos que se encuentran en todas las listas correspondientes del índice invertido. Para obtener todos los objetos similares, simplemente puede convertir las listas en conjuntos y tomar la intersección.

Esto es lo que podría parecer en Python, ligeramente abreviado para centrarse en las dimensiones: la extensión para incluir el period debería ser fácil. Hay una asignación de cadenas de identificador de objeto a los objetos en dic . Por lo tanto, puede crear un índice invertido asignando las dimensiones a los conjuntos de los identificadores de objetos que tienen esa dimensión. Se podría hacer así:

 import collections invind = collections.defaultdict(set) for k, obj in dic.iteritems(): for d in obj.dimensions: invind[d].add(k) 

Ahora diga que desea buscar todos los objetos que tienen dimensiones idénticas a un objeto específico test_obj . Simplemente busque los conjuntos de identificadores de objetos con al menos una de las dimensiones y tome la intersección de todos esos conjuntos. Una forma concisa de escribir una consulta de este tipo es:

 import operator similar_keys = reduce(operator.and_, [invind[d] for d in test_ojb.dimensions]) similar_objects = [dic[k] for k in similar_keys] 

La operate.and_ calculará las intersecciones del conjunto, reduce extiende a toda la lista de conjuntos. Este no es generalmente el enfoque más rápido para implementar las intersecciones; en su lugar, puede manipular un conjunto de resultados en el lugar con el método intersection_update de conjuntos, deteniéndose pronto una vez que el conjunto esté vacío. Dejaré los detalles, ya que son fáciles pero detallados.

La ventaja de este enfoque es que cualquier objeto que no tenga dimensiones en común no se comparará en absoluto . Dependiendo de cómo ocurran sus dimensiones, podría ser una reducción dramática en el número de pruebas realizadas. Puede continuar con la idea, por ejemplo, utilizando pares de dimensiones de co-ocurrencia como las claves en el índice invertido. Esto es más caro para generar las claves, pero generalmente reduce el tamaño de los conjuntos de identificadores de objetos: un poco de experimentación, o simplemente una buena comprensión de las dimensiones, debería ayudar a hacer el intercambio correcto.

Para incluir los períodos en las comparaciones, solo agregue otros períodos de mapeo de índice invertido a los conjuntos de identificadores de objetos. Extender la consulta para objetos similares debería ser sencillo.