العثور على طول تسلسل القيم المتطابقة في صفيف numpy (ترميز طول التشغيل)
-
21-08-2019 - |
سؤال
في برنامج 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 '.'
المحلول
بينما لا 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
مرة أخرى:تأكد من مقارنة الحلول ببعضها البعض في أمثلة واقعية تناسبك!
نصائح أخرى
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 (لكنه لا يزال سريعًا جدًا)، وأكثر مرونة.
إليك الحل باستخدام المصفوفات فقط:فهو يأخذ مصفوفة تحتوي على سلسلة من المنطقيات ويحسب طول التحولات.
>>> 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
عناصر).
فقط في حال كان أي شخص فضوليًا (وبما أنك ذكرت MATLAB بشكل عابر)، فإليك طريقة واحدة لحلها في MATLAB:
threshold = 7;
d = 10*rand(1,100000); % Sample data
b = diff([false (d < threshold) false]);
durations = find(b == -1)-find(b == 1);
أنا لست على دراية كبيرة ببايثون، ولكن ربما قد يساعدك هذا في إعطائك بعض الأفكار.=)
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)