Pitone:BTree OOSet, IISet, ecc. di Zope... Efficaci per questo requisito?

Question

Ho fatto un'altra domanda:https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python dove stavo cercando di determinare l'approccio migliore per ordinare 1 milione di record.Nel mio caso devo essere in grado di aggiungere ulteriori elementi alla raccolta e farli ricorrere.Mi è stato suggerito di provare a utilizzare BTrees di Zope per questo compito.Dopo aver letto un po', sono un po' perplesso su quali dati inserirei in un set.

Fondamentalmente, per ogni record ho due dati.1.Un ID univoco associato a un utente e 2.un valore di interesse per l'ordinamento.

Vedo che posso aggiungere gli elementi a un OOSet come tuple, dove il valore per l'ordinamento è nell'indice 0.COSÌ, (200, 'id1'),(120, 'id2'),(400, 'id3') e il set risultante verrebbe ordinato con id2, id1 and id3 al fine.

Tuttavia, parte del requisito è che ciascun ID appaia solo una volta nel set.Aggiungerò periodicamente ulteriori dati al set e i nuovi dati potrebbero includere o meno "ID" duplicati.Se sono duplicati, desidero aggiornare il valore e non aggiungere una voce aggiuntiva.Quindi, in base alle tuple sopra, potrei aggiungere (405, 'id1'),(10, 'id4') al set e vorrei che l'output avesse id4, id2, id3, id1 al fine.

Eventuali suggerimenti su come realizzare questo.Scusate la mia novità sull'argomento.

*MODIFICA - informazioni aggiuntive*

Ecco del codice effettivo dal progetto:

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 sono i dati originali in un dizionario con ciascun ID come chiave e un dizionario dei dati aggiuntivi come valore.data è un dizionario contenente gli elenchi di dati ordinati.

Come nota a margine, man mano che viene eseguita ogni iterazione del campo for in lb_fields, il tempo per l'ordinamento aumenta, non di molto...ma è evidente.Dopo che sono stati ordinati 1 milione di record per ciascuno dei 16 campi, vengono utilizzati circa 4 giga o RAM.Alla fine questo funzionerà su una macchina con 48 Giga.

Answer 1

Non penso che BTrees o altre tradizionali strutture di dati ordinati (alberi rosso-neri, ecc.) ti aiuteranno, perché mantengono l'ordine per chiave, non per valore corrispondente - in altre parole, il campo che garantiscono come unico è lo stesso uno da cui ordinano.Le tue esigenze sono diverse, perché vuoi l'unicità in un campo, ma l'ordinamento nell'altro.

Quali sono i tuoi requisiti prestazionali?Con un'implementazione Python pura piuttosto semplice basata su dict Python per unicità e ordinamenti Python, su un laptop non incredibilmente veloce, ottengo 5 secondi per la costruzione originale (essenzialmente un ordinamento su un milione di elementi, iniziando con loro come dict) , e circa 9 secondi per l'"aggiornamento" con 20.000 nuove coppie id/valore di cui metà "si sovrappongono" (quindi sovrascrivono) un id esistente e metà sono nuove (posso implementare l'aggiornamento in modo più veloce, circa 6,5 ​​secondi, ma quell'implementazione presenta un'anomalia:se una delle "nuove" coppie è esattamente identica a una di quelle "vecchie", sia id che valore, è duplicata - la protezione contro tale "duplicazione di identici" è ciò che mi spinge da 6,5 ​​secondi a 9, e immagino avresti bisogno dello stesso tipo di precauzione).

Quanto distano questi tempi di 5 e 9 secondi dalle tue esigenze (tenendo conto della velocità effettiva della macchina su cui utilizzerai rispetto al Core Duo da 2,4 GHz, 2 GB di RAM e i tipici problemi di prestazioni di questo laptop? sto usando)?IOW, è abbastanza vicino alla "distanza impressionante" per valere la pena armeggiare e provare a spremere gli ultimi cicli o hai bisogno di prestazioni più veloci di ordini di grandezza?

Ho provato diversi altri approcci (con un DB SQL, con C++ e il suo std::sort &c, ...) ma sono tutti più lenti, quindi se hai bisogno di prestazioni molto più elevate non sono sicuro di cosa potresti fare .

Modificare:dal momento che l'OP dice che questa prestazione andrebbe bene ma non riesce a raggiungerla neanche lontanamente, immagino che farei meglio a mostrare lo script che ho usato per misurare questi tempi...:

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()

e questa è una corsa tipica:

$ 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

il tempo complessivo trascorso è di qualche secondo in più rispetto ai totali che sto misurando, ovviamente, perché comprende il tempo necessario per popolare il contenitore con numeri casuali, generare i "nuovi dati" anche in modo casuale, distruggere e raccogliere oggetti alla fine fine di ogni esecuzione e così via.

Questo è con Python 2.5.2 fornito dal sistema su un Macbook con Mac OS X 10.5.7, Intel Core Duo a 2,4 GHz e 2 GB di RAM (i tempi non cambiano molto quando utilizzo versioni diverse di Python).

Answer 2

E 'perfettamente possibile per risolvere il problema. Per questo si deve solo notare che i tipi di contenitori in Python sempre confrontare gli oggetti chiamando i loro metodi. Pertanto si dovrebbe fare qualcosa di simile:

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())

Note:

• a seconda di come viene implementato il tipo di contenitore preferito, potrebbe essere necessario aggiungere metodi per! =, <=,>,> = E
• questo non si rompe il rapporto tra == e <= finché x.unique == y.unique ==> x.sort == y.sort