hallazgo 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 matriz numpy de números que representan distancias: d[t] es la distancia en el momento t (y el intervalo de tiempo de mis datos es len(d) unidades de tiempo).

Los eventos que me interesan son cuando la distancia está por debajo de 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 palabras True-only en b. Pero no sé cómo hacerlo de manera eficiente (es decir, usando primitivas numpy), y recurrí a caminar la matriz y hacer detección manual de cambios (es decir, inicializar el contador cuando el valor pasa de False a True, aumentar el contador siempre que el valor sea True y saca el contador a la secuencia cuando el valor vuelve a False). Pero esto es tremendamente lento.

Cómo detectar eficazmente ese tipo de secuencias en 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

Aunque no numpy primitivas , itertools funciones son a menudo muy rápido, también lo hacen darle 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 necesita los valores en una lista, simplemente puede usar list (runs_of_ones (bits)), por supuesto; pero tal vez una lista por comprensión podría ser marginalmente más rápido aún:

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

Mover a posibilidades "numpy nativo", lo que acerca de:

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 realistic- ejemplos para ti!

Answer 2

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) 

Answer 3

Por si acaso alguien tiene curiosidad (y ya que ha mencionado MATLAB de pasada), aquí es 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 darte algunas ideas =)

Answer 4

Aquí hay una solución que usa solo matrices: toma 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 los índices. Los elementos de isw se restan por pares en lens.

Observe que si la secuencia comenzada con un 1 contará la longitud de las secuencias de 0s: esto se puede corregir en la indexación para calcular el objetivo. Además, no he probado casos de esquina tales secuencias de longitud 1.

---

función completa que devuelve las posiciones de inicio y la duración de todas las True -subarrays.

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 True/False; con sólo True/False elementos).

Answer 5

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

Emite tupla de longitudes de ejecución, 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 

múltiples tipos de datos:

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 anteriores:

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 

ligeramente más lento que Alex (pero aún muy rápido), y mucho más flexible.