Python: BTree Zope OOSet, IISet, etc ... Efficace pour cette exigence?

Question

Je posé une autre question: https://stackoverflow.com/ Questions / 1180240 / best-way-to-Tri-1m-records-en-python où je tentais de déterminer la meilleure approche pour le tri 1 million d'enregistrements. Dans mon cas, je dois être en mesure d'ajouter des éléments supplémentaires à la collecte et les avoir recours. Il a été suggéré que j'essayer d'utiliser les Zope pour un arbre binaire cette tâche. Après avoir fait un peu de lecture, je suis un peu perplexe quant à ce que les données que je mettrais dans un ensemble.

En fait, pour chaque enregistrement que j'ai deux morceaux de données. 1. Un identifiant unique qui correspond à un utilisateur et 2. une valeur d'intérêt pour le tri sur.

Je vois que je peux ajouter les articles à un OOSet comme tuples, où la valeur de tri sur est à l'index 0. Ainsi, (200, 'id1'),(120, 'id2'),(400, 'id3') et l'ensemble résultant seraient triés par ordre id2, id1 and id3 dans l'ordre.

Cependant, une partie de l'exigence est que chaque id apparaissent une seule fois dans le jeu. Je vais ajouter des données supplémentaires à l'ensemble périodiquement et les nouvelles données peuvent inclure ou non des dupliqué « ids ». Si elles sont dupliquées je veux mettre à jour la valeur et ne pas ajouter une entrée supplémentaire. Ainsi, sur la base des tuples ci-dessus, je pourrais ajouter (405, 'id1'),(10, 'id4') à l'ensemble et je veux la sortie d'avoir id4, id2, id3, id1 dans l'ordre.

Toutes les suggestions sur la façon d'y parvenir. Désolé pour mon newbness sur le sujet.

* EDIT - informations complémentaires *

Voici une partie réelle du projet:

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 sont les données originales dans un dictionnaire avec chaque identifiant comme clé et un dictionnaire des données supplémentaires comme la valeur. données est un dictionnaire contenant les listes de données triées.

Comme une note de côté, chaque itereation du terrain pour dans les courses de lb_fields, le temps de trier les augmentations - pas de beaucoup ... mais il est perceptible. Après 1 million d'enregistrements ont été triés pour chacun des 16 champs qu'il utilise environ 4 Gigs ou RAM. Finalement, ce sera exécuté sur une machine avec 48 Gigs.

Answer 1

Je ne pense pas un arbre binaire ou d'autres structures de données traditionnelles trié (arbres rouge-noir, etc.) va vous aider, parce qu'ils gardent l'ordre de clé, et non par la valeur correspondante - en d'autres termes, le terrain, ils garantissent aussi unique est le même que celui qu'ils commandent par. Vos besoins sont différents, parce que vous voulez unique le long d'un champ, mais sortedness par l'autre.

Quelles sont vos exigences de performance? Avec une implémentation de Python pur assez simple basé sur Python dicts pour sortes d'unicité et de Python, sur un ordinateur portable sans blazingly rapide, je reçois 5 secondes pour la construction d'origine (essentiellement une sorte au cours des millions d'éléments, en commençant par eux comme un dict) , et environ 9 secondes pour la « mise à jour » avec 20.000 nouveaux id / paires de valeurs dont la moitié « chevauchement » (écrasera ainsi) un identifiant et demi existants sont nouveaux (je peux mettre en œuvre la mise à jour d'une manière plus rapide, environ 6,5 secondes, mais que la mise en œuvre a une anomalie: si l'un des « nouveaux » paires est exactement identique à l'un des plus « anciens », à la fois id et de la valeur, il est dupliqué - Warding contre cette « duplication des identicals » est ce qui me pousse de 6,5 secondes à 9, et je suppose que vous auriez besoin du même genre de précaution).

Dans quelle mesure sont ces 5 et-9 secondes fois de vos besoins (en prenant en compte la vitesse réelle de la machine que vous courrez sur vs 2,4 GHz Core Duo, 2 Go de RAM, et les problèmes de performance types d'ordinateur portable de ce portable j'utilise)? OIEau, est-il assez proche de « distance de frappe » à la peine de bricoler et d'essayer de presser un dernier quelques cycles sur, ou avez-vous besoin des ordres de grandeur des performances plus rapides?

J'ai essayé plusieurs autres approches (avec une base de données SQL, C ++ et son std :: sort etc., ...), mais ils sont tous plus lent, donc si vous avez besoin de performances beaucoup plus que je ne suis pas sûr de ce que vous pouvez le faire.

Modifier : depuis l'OP dit que cette performance serait bien, mais il ne peut pas atteindre approcher, je pense que je ferais mieux de montrer le script que je l'habitude de mesurer ces temps ...:

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

et c'est une course typique:

$ 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

le temps total écoulé étant quelques secondes de plus que le total que je mesure, évidemment, car il inclut le temps nécessaire pour remplir le conteneur avec des nombres aléatoires, générer les « nouvelles données » également au hasard, détruire et ramassent les ordures choses à la fin de chaque cycle, et ainsi de suite.

Ceci est le système fourni par Python 2.5.2 sur un Macbook avec Mac OS X 10.5.7, 2,4 GHz Intel Core Duo et 2 Go de RAM (les temps changent pas beaucoup quand j'utilise différentes versions de Python) .

Answer 2

Il est parfaitement possible de résoudre votre problème. Pour cela, vous devez simplement noter que les types de conteneurs en Python toujours comparer des objets en appelant leurs méthodes. Par conséquent, vous devriez faire quelque chose comme:

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

Notes:

• selon la façon dont est mis en œuvre votre type de conteneur préféré, vous devrez peut-être ajouter des méthodes pour! =, <=,>,> = Et
• cela ne cassera pas la relation entre == et <= tant que x.unique == y.unique ==> x.sort == y.sort