العثور على طول تسلسل القيم المتطابقة في صفيف numpy (ترميز طول التشغيل)

Question

في برنامج pylab (والذي من المحتمل أن يكون برنامج matlab أيضًا) لدي مجموعة من الأرقام التي تمثل المسافات: d[t] هل مسافة في الوقت t (والمدة الزمنية لبياناتي هي len(d) الوحدات الزمنية).

الأحداث التي أهتم بها هي عندما تكون المسافة أقل من حد معين، وأريد حساب مدة هذه الأحداث.من السهل الحصول على مجموعة من القيم المنطقية b = d<threshold, ، وتتلخص المشكلة في حساب تسلسل أطوال الكلمات الحقيقية فقط b.لكنني لا أعرف كيفية القيام بذلك بكفاءة (أي.باستخدام الأوليات numpy)، ولجأت إلى السير في المصفوفة والقيام بالكشف عن التغيير يدويًا (أي.تهيئة العداد عندما تنتقل القيمة من False إلى True، وزيادة العداد طالما كانت القيمة True، وإخراج العداد إلى التسلسل عندما تعود القيمة إلى False).ولكن هذا بطيء للغاية.

كيفية اكتشاف هذا النوع من التسلسلات بكفاءة في صفائف numpy؟

يوجد أدناه بعض رموز python التي توضح مشكلتي:النقطة الرابعة تستغرق وقتا طويلا جدا لتظهر (إذا لم تكن كذلك، قم بزيادة حجم المصفوفة)

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

بينما لا numpy البدائيون, itertools غالبًا ما تكون الوظائف سريعة جدًا، لذا جرّب هذه الوظيفة (وقس الأوقات لمختلف الحلول بما في ذلك هذا الحل بالطبع):

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

إذا كنت بحاجة إلى القيم الموجودة في القائمة، فما عليك سوى استخدام القائمة (runs_of_ones(bits)) بالطبع؛ولكن ربما يكون فهم القائمة أسرع بشكل هامشي:

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

الانتقال إلى احتمالات "numpy-native"، ماذا عن:

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

مرة أخرى:تأكد من مقارنة الحلول ببعضها البعض في أمثلة واقعية تناسبك!

Answer 2

RLE عام ومتجه بالكامل لأي صفيف (يعمل مع السلاسل والقيم المنطقية وما إلى ذلك أيضًا).

يُخرج مجموعة من أطوال التشغيل ومواضع البدء والقيم.

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

سريع جدًا (i7):

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

أنواع بيانات متعددة:

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

نفس نتائج Alex Martelli أعلاه:

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

أبطأ قليلاً من Alex (لكنه لا يزال سريعًا جدًا)، وأكثر مرونة.

Answer 3

إليك الحل باستخدام المصفوفات فقط:فهو يأخذ مصفوفة تحتوي على سلسلة من المنطقيات ويحسب طول التحولات.

>>> 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 يحتوي على صحيح حيث يوجد التبديل، isw يحولها إلى الفهارس.يتم بعد ذلك طرح عناصر isw بشكل ثنائي lens.

لاحظ أنه إذا بدأ التسلسل بالرقم 1، فسيتم حساب طول تسلسلات الصفر:ويمكن إصلاح ذلك في الفهرسة لحساب العدسة.أيضًا، لم أختبر حالات الزاوية مثل هذه التسلسلات ذات الطول 1.

---

وظيفة كاملة تقوم بإرجاع مواضع البداية وأطوال الكل True-المصفوفات الفرعية.

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

تم اختباره لمصفوفات منطقية 1D مختلفة (صفيف فارغ؛عناصر مفردة/متعددة؛أطوال زوجية/فردية؛بدأت مع True/False;مع فقط True/False عناصر).

Answer 4

فقط في حال كان أي شخص فضوليًا (وبما أنك ذكرت MATLAB بشكل عابر)، فإليك طريقة واحدة لحلها في MATLAB:

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

أنا لست على دراية كبيرة ببايثون، ولكن ربما قد يساعدك هذا في إعطائك بعض الأفكار.=)

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)