trouver une longueur de séquences de valeurs identiques dans un réseau numpy (longueur d'exécution de codage)

Question

Dans un programme de pylab (qui pourrait probablement être un programme Matlab ainsi) J'ai un tableau numpy de chiffres représentant les distances: est la d[t] distance au moment t (et timespan de mes données sont des unités de temps len(d)).

Les événements que je suis intéressé sont lorsque la distance est inférieure à un certain seuil, et je veux calculer la durée de ces événements. Il est facile d'obtenir un tableau de booléens avec b = d<threshold, et le problème se résume à calculer la séquence des longueurs du vrai uniquement mots b. Mais je ne sais pas comment faire efficacement (par exemple en utilisant des primitives de numpy), et j'ai eu recours à marcher le tableau et de faire la détection manuelle de changement (c.-à-initialiser compteur lorsque la valeur passe de faux à vrai augmenter contre tant que la valeur est True et la sortie du compteur à la séquence lorsque la valeur revient à faux). Mais cela est extrêmement lent.

Comment détecter efficienly ce genre de séquences dans les tableaux numpy?

Voici un code python qui illustre mon problème: le quatrième point prend apparaître très longtemps (sinon, augmentez la taille du tableau)

from pylab import *

threshold = 7

print '.'
d = 10*rand(10000000)

print '.'

b = d<threshold

print '.'

durations=[]
for i in xrange(len(b)):
    if b[i] and (i==0 or not b[i-1]):
        counter=1
    if  i>0 and b[i-1] and b[i]:
        counter+=1
    if (b[i-1] and not b[i]) or i==len(b)-1:
        durations.append(counter)

print '.'

Answer 1

Sans primitives numpy, les fonctions sont souvent itertools très rapide, donc ne pas donner l'essayer (et mesurer les temps pour diverses solutions, y compris celui-ci, bien sûr):

def runs_of_ones(bits):
  for bit, group in itertools.groupby(bits):
    if bit: yield sum(group)

Si vous avez besoin des valeurs dans une liste, il suffit peut utiliser la liste (runs_of_ones (bits)), bien sûr; mais peut-être une compréhension de la liste pourrait être légèrement plus rapide encore:

def runs_of_ones_list(bits):
  return [sum(g) for b, g in itertools.groupby(bits) if b]

Déplacement des possibilités "de numpy natif", qu'en est-:

def runs_of_ones_array(bits):
  # make sure all runs of ones are well-bounded
  bounded = numpy.hstack(([0], bits, [0]))
  # get 1 at run starts and -1 at run ends
  difs = numpy.diff(bounded)
  run_starts, = numpy.where(difs > 0)
  run_ends, = numpy.where(difs < 0)
  return run_ends - run_starts

Encore une fois: assurez-vous de solutions de référence les uns contre les autres en réaliste pour vous-exemples

Answer 2

Entièrement numpy RLE vectorisé et générique pour tout tableau (fonctionne avec des cordes, etc booléens trop).

Sorties tuple de longueurs de déroulement, les positions de départ et les valeurs.

import numpy as np

def rle(inarray):
        """ run length encoding. Partial credit to R rle function. 
            Multi datatype arrays catered for including non Numpy
            returns: tuple (runlengths, startpositions, values) """
        ia = np.asarray(inarray)                  # force numpy
        n = len(ia)
        if n == 0: 
            return (None, None, None)
        else:
            y = np.array(ia[1:] != ia[:-1])     # pairwise unequal (string safe)
            i = np.append(np.where(y), n - 1)   # must include last element posi
            z = np.diff(np.append(-1, i))       # run lengths
            p = np.cumsum(np.append(0, z))[:-1] # positions
            return(z, p, ia[i])

assez rapide (Core i7):

xx = np.random.randint(0, 5, 1000000)
%timeit yy = rle(xx)
100 loops, best of 3: 18.6 ms per loop

Plusieurs types de données:

rle([True, True, True, False, True, False, False])
Out[8]: 
(array([3, 1, 1, 2]),
 array([0, 3, 4, 5]),
 array([ True, False,  True, False], dtype=bool))

rle(np.array([5, 4, 4, 4, 4, 0, 0]))
Out[9]: (array([1, 4, 2]), array([0, 1, 5]), array([5, 4, 0]))

rle(["hello", "hello", "my", "friend", "okay", "okay", "bye"])
Out[10]: 
(array([2, 1, 1, 2, 1]),
 array([0, 2, 3, 4, 6]),
 array(['hello', 'my', 'friend', 'okay', 'bye'], 
       dtype='|S6'))

Mêmes résultats que Alex Martelli ci-dessus:

xx = np.random.randint(0, 2, 20)

xx
Out[60]: array([1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1])

am = runs_of_ones_array(xx)

tb = rle(xx)

am
Out[63]: array([4, 5, 2, 5])

tb[0][tb[2] == 1]
Out[64]: array([4, 5, 2, 5])

%timeit runs_of_ones_array(xx)
10000 loops, best of 3: 28.5 µs per loop

%timeit rle(xx)
10000 loops, best of 3: 38.2 µs per loop

Un peu plus lent que Alex (mais toujours très rapide), et beaucoup plus flexible.

Answer 3

Voici une solution en utilisant des réseaux seulement. Il faut environ une matrice contenant une séquence de bools et compte la longueur des transitions

>>> from numpy import array, arange
>>> b = array([0,0,0,1,1,1,0,0,0,1,1,1,1,0,0], dtype=bool)
>>> sw = (b[:-1] ^ b[1:]); print sw
[False False  True False False  True False False  True False False False
  True False]
>>> isw = arange(len(sw))[sw]; print isw
[ 2  5  8 12]
>>> lens = isw[1::2] - isw[::2]; print lens
[3 4]

sw contient un vrai où il y a un interrupteur, les convertit en isw index. Les éléments de isw sont ensuite soustraits par paires à lens.

Notez que si la séquence a commencé avec un 1 il compter la longueur des séquences 0s: ce peut être fixé dans l'indexation pour calculer la lentille. De plus, je ne l'ai pas testé les cas d'angle de telles séquences de longueur 1.

---

Fonction complète qui renvoie les positions et longueurs début de tous les True - sous-tableaux.

import numpy as np

def count_adjacent_true(arr):
    assert len(arr.shape) == 1
    assert arr.dtype == np.bool
    if arr.size == 0:
        return np.empty(0, dtype=int), np.empty(0, dtype=int)
    sw = np.insert(arr[1:] ^ arr[:-1], [0, arr.shape[0]-1], values=True)
    swi = np.arange(sw.shape[0])[sw]
    offset = 0 if arr[0] else 1
    lengths = swi[offset+1::2] - swi[offset:-1:2]
    return swi[offset:-1:2], lengths

Testé pour différentes matrices de 1D-bool (tableau vide; seul / plusieurs éléments, même / longueurs impaires, a commencé avec False / <=>; avec seulement <=> / <=> éléments).

Answer 4

Juste au cas où quelqu'un est curieux (et puisque vous avez mentionné Matlab en passant), voici une façon de le résoudre dans Matlab:

threshold = 7;
d = 10*rand(1,100000);  % Sample data
b = diff([false (d < threshold) false]);
durations = find(b == -1)-find(b == 1);

Je ne suis pas trop familier avec Python, mais peut-être cela pourrait aider à vous donner quelques idées. =)

Answer 5

durations = []
counter   = 0

for bool in b:
    if bool:
        counter += 1
    elif counter > 0:
        durations.append(counter)
        counter = 0

if counter > 0:
    durations.append(counter)