एक सरणी, a, सॉर्ट किए गए मानों और श्रेणियों की एक सरणी, bins को देखते हुए, a में कितने मान गिनने का सबसे कारगर तरीका क्या है प्रत्येक श्रेणी में आते हैं, rng, bins में?
वर्तमान में मैं निम्नलिखित कर रहा हूँ:
def sliding_count(a, end, window, start=0, step=1):
bins = [(x, x + window) for x in range(start, (end + 1) - window, step)]
counts = np.zeros(len(bins))
for i, rng in enumerate(bins):
count = len(a[np.where(np.logical_and(a>=rng[0], a<=rng[1]))])
counts[i] = count
return counts
a = np.array([1, 5, 8, 11, 14, 19])
end = 20
window = 10
sliding_count(a, end, window)
जो अपेक्षित सरणी देता है
array([3., 4., 3., 3., 4., 4., 3., 3., 3., 3., 3.])
लेकिन मुझे लगता है कि ऐसा करने का एक और अधिक प्रभावी तरीका होना चाहिए?
3 जवाब
import numpy as np
def alt(a, end, window, start=0, step=1):
bin_starts = np.arange(start, end+1-window, step)
bin_ends = bin_starts + window
last_index = np.searchsorted(a, bin_ends, side='right')
first_index = np.searchsorted(a, bin_starts, side='left')
return last_index - first_index
def sliding_count(a, end, window, start=0, step=1):
bins = [(x, x + window) for x in range(start, (end + 1) - window, step)]
counts = np.zeros(len(bins))
for i, rng in enumerate(bins):
count = len(a[np.where(np.logical_and(a>=rng[0], a<=rng[1]))])
counts[i] = count
return counts
a = np.array([1, 5, 8, 11, 14, 19])
end = 20
window = 10
print(sliding_count(a, end, window))
# [3. 4. 3. 3. 4. 4. 3. 3. 3. 3. 3.]
print(alt(a, end, window))
# [3 4 3 3 4 4 3 3 3 3 3]
ऑल्ट कैसे काम करता है:
डिब्बे के आरंभ और समाप्ति मान उत्पन्न करें:
In [73]: bin_starts = np.arange(start, end+1-window, step); bin_starts
Out[73]: array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
In [74]: bin_ends = bin_starts + window; bin_ends
Out[74]: array([10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])
चूंकि a क्रमबद्ध क्रम में है, आप np.searchsorted पहली और आखिरी अनुक्रमणिका खोजने के लिए bin_starts और bin_ends में जहां a में प्रत्येक मान फिट बैठता है:
In [75]: last_index = np.searchsorted(a, bin_ends, side='right'); last_index
Out[75]: array([3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6])
In [76]: first_index = np.searchsorted(a, bin_starts, side='left'); first_index
Out[76]: array([0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3])
count केवल सूचकांकों में अंतर है:
In [77]: last_index - first_index
Out[77]: array([3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3])
यहां एक perfplot दिया गया है जिसमें alt बनाम sliding_count के प्रदर्शन की तुलना फ़ंक्शन के रूप में की गई है a की लंबाई का:
import perfplot
def make_array(N):
a = np.random.randint(10, size=N)
a = a.cumsum()
return a
def using_sliding(a):
return sliding_count(a, end, window)
def using_alt(a):
return alt(a, end, window)
perfplot.show(
setup=make_array,
kernels=[using_sliding, using_alt],
n_range=[2**k for k in range(22)],
logx=True,
logy=True,
xlabel='len(a)')
Perfplot यह भी जांचता है कि using_sliding द्वारा लौटाया गया मान using_alt द्वारा दिए गए मान के बराबर है।
Matt Timmermans' का विचार, "उस बिन की गिनती से position_in_a घटाएं" इस समाधान को ट्रिगर किया।
एक बिन में तत्वों की संख्या b, तत्वों की संख्या <= b.end घटा तत्वों की संख्या < b.start है।
तो आप शुरुआत के आधार पर छांटे गए डिब्बे की एक starts सरणी बना सकते हैं, और ends अंत तक छांटे गए डिब्बे की सरणी बना सकते हैं। फिर चरण में सभी 3 सरणियों के माध्यम से चलें। जब आप a में प्रत्येक x से आगे बढ़ते हैं, तो उस बिन की गिनती से x < b.start और घटाना position_in_a के साथ शुरुआत से पहले आगे बढ़ें। फिर उस बिन की गिनती में x <= b.end और जोड़ें position_in_a के साथ आगे बढ़ें।
कुल जटिलता ओ (एन लॉग एन) है, जो प्रारंभ और अंत सरणी को क्रमबद्ध करके हावी है। 3 सरणियों के माध्यम से चलना और गणनाओं को समायोजित करना O(N) है।
आपके कोड में आप पहले से छांटे गए डिब्बे की सरणी जनरेट कर रहे हैं, इसलिए यदि आप ऐसा कर सकते हैं तो आप सॉर्टिंग चरण को छोड़ सकते हैं और कुल जटिलता O(a.length+bin_count) है। मैं उस सरणी को उत्पन्न करने की भी जहमत नहीं उठाऊंगा क्योंकि आप आसानी से सूचकांक से प्रारंभ और अंत मूल्यों की गणना कर सकते हैं।
कुछ इस तरह (?):
def sliding_count(a, nx0, nx1, window):
bin0 = np.arange(nx0,nx1,1)
bin1 = bin0 + window
count = np.zeros((nx1-nx0), dtype=int)
for j in range(nx1-nx0):
count[j] = np.sum(a<=bin1[j]) - np.sum(a<bin0[j])
return count
#---- main ---------------
nx0, nx1, window = 0, 11, 10
a = np.array([1, 5, 8, 11, 14, 19])
sliding_count(a, nx0, nx1, window)
array([3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3])
मैंने nx0>0 और चरण>1 के लिए bin0 = np.arange(nx0,nx1,1) में कोड की जांच नहीं की। तो ऐसे मामलों के लिए फॉर-लूप की लंबाई को संशोधित करना होगा।