Regroupement des données de points en série

Question

I ont une série de points de données (tuples) dans une liste avec un format tel que:

points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')] 

Le premier élément de chaque tuple est un nombre entier et ils sont assurés d'être triés. La deuxième valeur dans chaque tuple est une chaîne arbitraire.

J'ai besoin d'eux groupés dans les listes par leur première valeur dans une série. Donc, étant donné un intervalle de 3, la liste ci-dessus serait divisé en:

[['a', 'b', 'a', 'd'], ['c']] 

j'ai écrit la fonction suivante, qui fonctionne très bien sur les petits ensembles de données. Cependant, il est inefficace pour les grandes entrées. Des conseils sur la façon de réécrire/optimiser/mininiser cela afin que je puisse traiter de grands ensembles de données?

def split_series(points, interval): 
    series = [] 

    start = points[0][0] 
    finish = points[-1][0] 

    marker = start 
    next = start + interval 
    while marker <= finish: 
     series.append([point[1] for point in points if marker <= point[0] < next]) 
     marker = next 
     next += interval 

    return series 

Answer 1

Pour être complet, voici une solution avec itertools.groupby, mais la solution de dictionnaire sera probablement plus rapide (sans parler beaucoup plus facile à lire).

import itertools 
import operator 

def split_series(points, interval): 
    start = points[0][0] 

    return [[v for k, v in grouper] for group, grouper in 
      itertools.groupby((((n - start) // interval, val) 
           for n, val in points), operator.itemgetter(0))] 

Notez que le ci-dessus suppose que vous avez au moins un élément dans chaque groupe, sinon il va donner des résultats différents de votre script, à savoir:

>>> split_series([(1, 'a'), (2, 'b'), (6, 'a'), (6, 'd'), (11, 'c')], 3) 
[['a', 'b'], ['a', 'd'], ['c']] 

au lieu de

[['a', 'b'], ['a', 'd'], [], ['c']] 

Voici une solution de dictionnaire fixe. À un moment donné, le temps de consultation du dictionnaire commencera à dominer, mais peut-être que c'est assez rapide pour vous comme ça.

from collections import defaultdict 

def split_series(points, interval): 
    offset = points[0][0] 
    maxval = (points[-1][0] - offset) // interval 
    vals = defaultdict(list) 
    for key, value in points: 
     vals[(key - offset) // interval].append(value) 
    return [vals[i] for i in xrange(maxval + 1)] 

Answer 2

Une façon de le faire (pas de promesses sur la vitesse):

cassez votre liste de tuples en deux listes: [1,2,2,3,4] et ['a','b','a','d','c']

Depuis la première liste est triée, il vous suffit Continuez à parcourir jusqu'à ce que vous arriviez à un élément hors de portée. Ensuite, vous connaissez les index des éléments de début et de fin afin que vous puissiez simplement découper les chaînes du second tableau. Continuez jusqu'à ce que vous ayez tous les intervalles. Je ne suis pas sûr de l'efficacité avec les listes Python traditionnelles, mais si votre jeu de données est assez grand, vous pouvez essayer d'utiliser un tableau NumPy, qui tranchera très rapidement.

Answer 3

Votre code est O (n). Voici une solution O (n):

def split_series(points, interval): 
    series = [] 
    current_group = [] 
    marker = points[0][0] 
    for value, data in points: 
     if value >= marker + interval: 
      series.append(current_group) 
      current_group = [] 
      marker += interval 
     current_group.append(data) 

    if current_group: 
     series.append(current_group) 

    return series 

points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')] 
print split_series(points, 3) # Prints [['a', 'b', 'a', 'd'], ['c']] 

Answer 4

De votre code, je suppose que mon commentaire précédent est correct. Le problème semble ici être que la performance est O (n^2) - vous répétez la compréhension de la liste (qui répète tous les éléments) plusieurs fois. Je dis, utilisez une simple boucle de boucle pour

Si l'élément actuel appartient au même groupe que le précédent, ajoutez-le à la liste interne existante [["a"], ["b"]] -> [["a"], ["b", "c "]]. Si ce n'est pas le cas, ajoutez-le à une nouvelle liste interne, en ajoutant peut-être d'abord des listes de remplissage vides.

Answer 5

En développant la réponse de Am, utilisez un defaultdict et divisez la clé par intervalle pour les séparer correctement.

from collections import defaultdict 
def split_series(points, interval): 
    vals = defaultdict(list) 
    for key, value in points: 
     vals[(key-1)//interval].append(value) 
    return vals.values() 

Answer 6

Comment utiliser les itérateurs pour une évaluation paresseuse?

Cela devrait être l'équivalent de votre solution initiale:

from itertools import groupby 

def split_series(points, interval): 
    """ 
    >>> points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')] 
    >>> print list(split_series(points, 3)) 
    [['a', 'b', 'a', 'd'], ['c']] 
    """ 

    def interval_key(t): 
     return (t[0] - points[0][0]) // interval 

    groups = groupby(points, interval_key) 

    for group in groups: 
     yield [v for _, v in group[1]] 

Answer 7

est ici une approche paresseuse qui utilise le comportement de l'étape de xrange:

def split_series(points, interval): 
    end_of_chunk = interval 
    chunk = [] 
    for marker, item in points: 
     if marker > end_of_chunk: 
      for end_of_chunk in xrange(end_of_chunk, marker, interval): 
       yield chunk 
       chunk = [] 
      end_of_chunk += interval 
     chunk.append(item) 
    yield chunk