Pitón:BTree OOSet, IISet, etc. de Zope… ¿Eficaz para este requisito?

Question

Hice otra pregunta:https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python donde intentaba determinar el mejor enfoque para ordenar 1 millón de registros.En mi caso, necesito poder agregar elementos adicionales a la colección y recuperarlos.Me sugirieron que intentara usar BTrees de Zope para esta tarea.Después de leer un poco, estoy un poco perplejo en cuanto a qué datos pondría en un conjunto.

Básicamente, para cada registro tengo dos datos.1.Una identificación única que se asigna a un usuario y 2.un valor de interés para clasificar.

Veo que puedo agregar los elementos a un OOSet como tuplas, donde el valor para ordenar está en el índice 0.Entonces, (200, 'id1'),(120, 'id2'),(400, 'id3') y el conjunto resultante se ordenaría con id2, id1 and id3 en orden.

Sin embargo, parte del requisito para esto es que cada identificación aparezca solo una vez en el conjunto.Agregaré datos adicionales al conjunto periódicamente y los nuevos datos pueden incluir o no 'identificadores' duplicados.Si están duplicados, quiero actualizar el valor y no agregar una entrada adicional.Entonces, basándome en las tuplas anteriores, podría agregar (405, 'id1'),(10, 'id4') al conjunto y querría que la salida tuviera id4, id2, id3, id1 en orden.

Alguna sugerencia sobre cómo lograr esto.Perdón por mi novedad en el tema.

* EDITAR - información adicional *

Aquí hay un código real del proyecto:

for field in lb_fields:
        t = time.time()
        self.data[field] = [ (v[field], k) for k, v in self.foreign_keys.iteritems() ]
        self.data[field].sort(reverse=True)
        print "Added %s: %03.5f seconds" %(field, (time.time() - t))

Foreign_keys son los datos originales en un diccionario con cada identificación como clave y un diccionario de datos adicionales como valor.data es un diccionario que contiene listas de datos ordenados.

Como nota al margen, a medida que se ejecuta cada iteración del campo for en lb_fields, el tiempo para ordenar aumenta, no mucho...pero se nota.Después de ordenar 1 millón de registros para cada uno de los 16 campos, se utilizan aproximadamente 4 Gigas o RAM.Con el tiempo, esto se ejecutará en una máquina con 48 Gigas.

Answer 1

No creo que BTrees u otras estructuras de datos ordenadas tradicionales (árboles rojo-negro, etc.) le ayuden, porque mantienen el orden por clave, no por valor correspondiente; en otras palabras, el campo que garantizan como único es el mismo. uno por el que ordenan.Sus requisitos son diferentes, porque desea unicidad en un campo, pero clasificación en el otro.

¿Cuáles son sus requisitos de desempeño?Con una implementación pura de Python bastante simple basada en dictados de Python para unicidad y tipos de Python, en una computadora portátil que no es increíblemente rápida, obtengo 5 segundos para la construcción original (esencialmente una clasificación sobre el millón de elementos, comenzando con ellos como un dictado) , y aproximadamente 9 segundos para la "actualización" con 20.000 nuevos pares de identificación/valor, de los cuales la mitad se "superponen" (por lo tanto, sobrescriben) una identificación existente y la otra mitad son nuevos (puedo implementar la actualización de una manera más rápida, aproximadamente 6,5 segundos, pero esa implementación tiene una anomalía:si uno de los pares "nuevos" es exactamente idéntico a uno de los "antiguos", tanto id como valor, está duplicado; protegerse contra tal "duplicación de idénticos" es lo que me empuja de 6,5 segundos a 9, y me imagino necesitarías el mismo tipo de precaución).

¿Qué tan lejos están estos tiempos de 5 y 9 segundos de sus requisitos (teniendo en cuenta la velocidad real de la máquina que utilizará frente al Core Duo de 2,4 GHz, 2 GB de RAM y los problemas típicos de rendimiento de esta computadora portátil? estoy usando)?OIA, ¿está lo suficientemente cerca de la "distancia de ataque" como para que valga la pena retocarlo e intentar exprimir algunos de los últimos ciclos, o necesita un rendimiento mucho más rápido?

Probé varios otros enfoques (con una base de datos SQL, con C++ y su std::sort &c, ...) pero todos son más lentos, por lo que si necesitas un rendimiento mucho mayor, no estoy seguro de qué podrías hacer. .

Editar:Dado que el OP dice que este rendimiento estaría bien pero no puede lograrlo, supongo que será mejor que muestre el script que utilicé para medir estos tiempos...:

import gc
import operator
import random
import time


nk = 1000

def popcon(d):
  for x in xrange(nk*1000):
    d['id%s' % x] = random.randrange(100*1000)

def sorted_container():
  ctr = dict()
  popcon(ctr)
  start = time.time()
  ctr_sorted = ctr.items()
  ctr_sorted.sort(key=operator.itemgetter(1))
  stend = time.time()
  return stend-start, ctr_sorted

def do_update(ctr, newones):
  start = time.time()
  dicol = dict(ctr)
  ctr.extend((k,v) for (k,v) in newones if v!=dicol.get(k,None))
  dicnu = dict(newones)
  ctr.sort(key=operator.itemgetter(1))
  newctr = [(k,v) for (k,v) in ctr if v==dicnu.get(k,v)]
  stend = time.time()
  return stend-start, newctr

def main():
  random.seed(12345)
  for x in range(3):
    duration, ctr = sorted_container()
    print 'dict-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
    newones = [('id%s' % y, random.randrange(nk*100))
                for y in xrange(nk*990,nk*1010)]
    duration, ctr = do_update(ctr, newones)
    print 'updt-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
    del ctr
    gc.collect()

main()

y esta es una ejecución típica:

$ time python som.py
dict-to-sorted, 0: 5.01 sec, len=1000000
updt-to-sorted, 0: 9.78 sec, len=1010000
dict-to-sorted, 1: 5.02 sec, len=1000000
updt-to-sorted, 1: 9.12 sec, len=1010000
dict-to-sorted, 2: 5.03 sec, len=1000000
updt-to-sorted, 2: 9.12 sec, len=1010000

real    0m54.073s
user    0m52.464s
sys 0m1.258s

el tiempo total transcurrido es unos segundos más que los totales que estoy midiendo, obviamente, porque incluye el tiempo necesario para llenar el contenedor con números aleatorios, generar los "nuevos datos" también de forma aleatoria, destruir y recolectar basura en el final de cada ejecución, etc.

Esto es con Python 2.5.2 suministrado por el sistema en una Macbook con Mac OS X 10.5.7, Intel Core Duo de 2,4 GHz y 2 GB de RAM (los tiempos no cambian mucho cuando uso diferentes versiones de Python).

Answer 2

Es perfectamente posible para resolver su problema. Para ello sólo debe tener en cuenta que los tipos de contenedores en Python siempre comparar objetos llamando a sus métodos. Por lo tanto usted debe hacer algo como:

class Record:
    'Combination of unique part and sort part.'
    def __init__(self, unique, sort):
        self.unique = unique
        self.sort = sort

    def __hash__(self):
        # Hash should be implemented if __eq__ is implemented.
        return hash(self.unique)

    def __eq__(self, other):
        return self.unique == other.unique

    def __lt__(self, other):
        return self.sort < other.sort

 records = btree((Record(u, s) for u, s in zip(unique_data, sort_data)))

 print(records.pop())

Notas:

• dependiendo de cómo se implementa el tipo de contenedor favorito, puede que tenga que añadir métodos para! =, <=,>,> =, Así
• esto no se romperá la relación entre == y <= siempre que x.unique == y.unique ==> x.sort == y.sort