Le regroupement des points de données en série

Question

J'ai une série de points de données (tuples) dans une liste avec un format comme:

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 de les regrouper dans des 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 inneficient pour les grandes entrées. Des conseils sur la façon de réécrire / optimize / mininize ce que je peux 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, i.e..

>>> 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-up. À un certain moment, le temps de recherche dans le dictionnaire commence à dominer, mais peut-être il 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

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 3

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, vous pouvez juste garder itérer jusqu'à ce que vous arrivez à un élément hors de la plage. , Vous savez alors les indices des éléments de début et de fin de sorte que vous pouvez simplement couper les chaînes de deuxième tableau. Continuez jusqu'à ce que vous avez tous les intervalles.

Je ne sais pas comment ça va être efficace avec des listes Python tradition, mais si votre ensemble de données est assez grand, vous pouvez essayer d'utiliser un tableau numpy, qui tranche très rapidement.

Answer 4

A partir de votre code, je présume que mon commentaire avant est correcte. Le problème semble être ici que la performance est O (n ^ 2) -. Vous répétez la compréhension de la liste (qui itère tous les articles) plusieurs fois

Je dis, utilisez une simple boucle. Si l'élément actuel appartient au même groupe que le précédent, l'ajouter à la liste intérieure existante [[ "a"], [ "b"]] -> [[ "a"], [ "b", « c « ]]. Si elle ne le fait pas, l'ajouter à une nouvelle liste intérieure, peut-être ajouter des listes de remplissage vides en premier.

Answer 5

L'expansion sur la réponse Am, utilisez un defaultdict et sol diviser la clé par l'intervalle de les briser 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

Voici une approche paresseuse qui utilise le comportement é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

Answer 7

Comment l'utilisation itérateurs pour l'é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]]