2009-02-19 10 views
0

Je dois construire un ensemble complet de "séries de nombres" en fonction d'une série de nombres. Je commence par une liste telle que:Construction d'une plage de numéros "complète" sans chevauchements

ID START 
* 0 
a 4 
b 70 
c 700 
d 701 
e 85 
  • où « DEF » est la plage par défaut & devrait « remplir » les lacunes
  • « chevauche » sont la valeur (70, 700, 701) en données à partir

Et besoin le résultat suivant:

ID START END 
*  0 - 39 
a  4 - 49 
*  5 - 69 
c 700 - 7009 
d 701 - 7019 
b 702 - 709 
* 71 - 849 
e 85 - 859 
* 86 - 9 

Ce que je suis en train de comprendre est de savoir s'il y a une sorte d'algorithme là-bas ou un modèle de conception pour y remédier. J'ai quelques idées mais j'ai pensé que je le ferais d'abord par les "experts". J'utilise Python.

Toutes les idées/directions seraient grandement appréciées. Quelques idées initiales j'ai:

  • Construire une liste « plage » w/début & les valeurs de fin rembourrées sur toute la longueur. La valeur par défaut est donc de 0000 à 9999
  • Créer une liste de "splits" construite à la volée
  • Faire une boucle dans la liste "range" en comparant chaque valeur aux valeurs de la liste de divisions.
  • Dans le cas où un chevauchement est trouvé, supprimez la valeur dans la liste des séparations et ajoutez la (les) nouvelle (s) plage (s).

Répondre

0
import operator 

ranges = { 
    '4' : 'a', 
    '70' : 'b', 
    '700': 'c', 
    '701': 'd', 
    '85' : 'e', 
    '87' : 'a', 
} 

def id_for_value(value): 
    possible = '*' 
    for idvalue, id in sorted(ranges.iteritems()): 
     if value.startswith(idvalue): 
      possible = id 
     elif idvalue > value: 
      break 
    return possible 

Cela suffit pour connaître l'identifiant d'une certaine valeur. Tests:

assert id_for_value('10') == '*' 
assert id_for_value('499') == 'a' 
assert id_for_value('703') == 'b' 
assert id_for_value('7007') == 'c' 
assert id_for_value('7017') == 'd' 
assert id_for_value('76') == id_for_value('83') == '*' 
assert id_for_value('857') == 'e' 
assert id_for_value('8716') == 'a' 

Si vous voulez vraiment la plage, vous pouvez utiliser itertools.groupby pour le calculer:

def firstlast(iterator): 
    """ Returns the first and last value of an iterator""" 
    first = last = iterator.next() 
    for value in iterator: 
     last = value 
    return first, last 

maxlen = max(len(x) for x in ranges) + 1 
test_range = ('%0*d' % (maxlen, i) for i in xrange(10 ** maxlen)) 
result = dict((firstlast(gr), id) 
       for id, gr in itertools.groupby(test_range, key=id_for_value)) 

donne:

{('0000', '3999'): '*', 
('4000', '4999'): 'a', 
('5000', '6999'): '*', 
('7000', '7009'): 'c', 
('7010', '7019'): 'd', 
('7020', '7099'): 'b', 
('7100', '8499'): '*', 
('8500', '8599'): 'e', 
('8600', '8699'): '*', 
('8700', '8799'): 'a', 
('8800', '9999'): '*'} 
+0

wow! laissez-moi essayer ceci ..... une complexité que j'ai laissée de côté est le fait que vous pouvez avoir plusieurs gammes pour le même "ID", ce qui affecterait le dictionnaire initial. Merci!! – John

+0

@John: J'ai mis à jour ma réponse pour refléter plusieurs plages pour le même identifiant. J'utilise simplement l'identifiant comme valeur maintenant. – nosklo

+0

@Nosklo - pour une raison quelconque lorsque j'ai une grande plage START (7190000), le processus manque de mémoire. Peu importe si j'ai 3 plages ou 20, une plage de cette taille provoque un problème de mémoire. Pensées? MERCI ENCORE!! – John