encontrar o comprimento de sequências de valores idênticos em uma matriz numpy (codificação de comprimento de percurso)

Question

Em um programa Pylab (que provavelmente poderia ser um programa Matlab também) Eu tenho uma matriz numpy de números que representam distâncias: d[t] é a distância em tempo de t (e do período de tempo dos meus dados é unidades de tempo len(d)).

Os eventos que eu estou interessado em se quando a distância for inferior a um determinado limite, e eu quero calcular a duração desses eventos. É fácil obter uma matriz de booleanos com b = d<threshold, eo problema se resume a calcular a seqüência dos comprimentos das palavras True-somente em b. Mas eu não sei como fazer isso de forma eficiente (ou seja, utilizando primitivas numpy), e eu recorreu a andar a matriz e para fazer a detecção de mudança manual (ou seja initialize contador quando o valor passa de falso para verdadeiro, aumentar balcão, desde que o valor é True , e a saída do contador para a sequência quando valor remonta a Falso). Mas isso é tremendamente lento.

Como detectar efficienly esse tipo de seqüências em matrizes numpy?

Abaixo está algum código Python que ilustra o meu problema: o quarto ponto leva muito tempo para aparecer (se não, aumente o tamanho da 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

Enquanto primitivos não numpy, funções itertools são frequentemente muito rápido, por isso, dar um presente uma tentativa (e os tempos de medida para várias soluções, incluindo este, é claro):

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

Se você precisar os valores em uma lista, apenas pode utilizar a lista (runs_of_ones (bits)), é claro; mas talvez uma compreensão da lista pode ser marginalmente mais rápido ainda:

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

Mover-se para possibilidades "numpy nativo", o que acontece:

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

Mais uma vez: certifique-se de soluções de referência uns contra os outros em exemplos realistas para-as-you

Answer 2

Totalmente Numpy vetorizado e RLE genérico para qualquer matriz (obras com cordas, booleans etc também).

saídas tuplo de comprimentos de percurso, iniciar posições, e 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])

Pretty rápido (i7):

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

Vários tipos de dados:

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

mesmos resultados que Alex Martelli acima:

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

Um pouco mais lento do que Alex (mas ainda muito rápido), e muito mais flexível.

Answer 3

Aqui é uma solução usando apenas matrizes: leva uma matriz que contém uma sequência de bools e contagens o comprimento das transições

.

>>> 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 contém um verdadeiro onde há um interruptor, isw converte-os em índices. Os itens de ISW são então subtraído pares em lens.

Observe que, se a sequência de passos com um 1 seria contar o comprimento das sequências 0s: esta pode ser fixa na indexação a lente de computação. Além disso, não foram testados casos de canto tais sequências de comprimento 1.

---

Full função que retorna começar posições e comprimentos de todos os 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

Testado para diferentes bool 1D-matrizes (matriz vazia; único / múltiplas elementos, mesmo / comprimentos ímpares; iniciado com True / False; com apenas True elementos / False).

Answer 4

Apenas no caso de alguém é curioso (e desde que você mencionou MATLAB de passagem), aqui está uma maneira de resolvê-lo em MATLAB:

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

Eu não estou muito familiarizado com o Python, mas talvez isso poderia ajudar a dar-lhe algumas ideias. =)

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)