encontrar longitud de las secuencias de valores idénticos en una matriz numpy (codificación de longitud de ejecución)

Question

En un programa pylab (que probablemente podría ser un programa MATLAB también) Tengo una serie de números que representan numpy distancias: d[t] es el Distancia en el momento t (y el intervalo de tiempo de mis datos es len(d) unidades de tiempo).

Los acontecimientos que me interesan son cuando la distancia es inferior a un cierto umbral, y quiero calcular la duración de estos eventos. Es fácil obtener una matriz de booleanos con b = d<threshold, y el problema se reduce a calcular la secuencia de las longitudes de las Verdadero sólo palabras b. Pero no sé cómo hacerlo de manera eficiente (es decir, utilizando las primitivas numpy), y recurrí a recorrer la matriz y para hacer la detección de cambios manual (es decir, inicializar el contador cuando el valor va de falso a verdadero, aumentar el contador, siempre y cuando el valor es True , y la salida del contador a la secuencia cuando el valor se remonta a Falso). Pero esto es tremendamente lento.

¿Cómo detectar efficienly ese tipo de secuencias en las matrices numpy?

A continuación se muestra un código Python que ilustra mi problema: el cuarto punto tarda mucho tiempo en aparecer (si no es así, aumentar el tamaño de la matriz)

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

Si bien no numpy primitivas, itertools funciones son a menudo muy rápido, por lo que dan a éste un intento (y medir el tiempo en varias soluciones incluyendo éste, por supuesto):

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

Si es necesario los valores en una lista, la lista (runs_of_ones (bits)) solo se puede utilizar, por supuesto; pero tal vez una lista por comprensión podría ser marginalmente más rápido sigue:

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

Mover a posibilidades "numpy-nativa", ¿qué pasa con:

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

Una vez más: asegúrese de soluciones de referencia contra los demás en realista-para-usted los ejemplos

Answer 2

Totalmente numpy RLE vectorizado y genérico para cualquier matriz (funciona con cadenas, booleanos, etc también).

Salidas tupla de longitudes de secuencia, las posiciones de inicio y valores.

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

bastante rápido (i7):

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

tipos de datos múltiples:

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

mismos resultados que Alex Martelli arriba:

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 poco más lento que Alex (pero sigue siendo muy rápido), y mucho más flexible.

Answer 3

Aquí está una solución utilizando sólo arrays:. Que se necesita una matriz que contiene una secuencia de Bools y cuenta la longitud de las transiciones

>>> 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 contiene un cierto cuando hay un interruptor, isw los convierte en índices. Los elementos de ISW se restan pairwise en lens.

Observe que si la secuencia comenzó con un 1 sería contar la longitud de las secuencias de 0s: esto se puede solucionar en la indización para calcular lente. Además, no he probado casos de esquina tales secuencias de longitud 1.

---

Función completa que devuelve iniciar posiciones y longitudes de todos los True - submatrices.

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

Probado para diferentes bool 1D-matrices (matriz vacía; elementos individuales / múltiple; incluso / longitudes impares; comenzó con False / <=>; con solamente <=> / <=> elementos).

Answer 4

Por si acaso alguien tiene curiosidad (y ya que ha mencionado de pasada MATLAB), aquí está una manera de resolverlo en MATLAB:

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

No estoy muy familiarizado con Python, pero tal vez esto podría ayudar a darle algunas ideas. =)

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)