jonalm की टिप्पणी के जवाब में संपादित करें:
jonalm: लागू नहीं ~ 3^n नहीं n ~ 3^एन। एन में अधिकतम तत्व है और n तत्वों में से एक है।
एन ~ 2^20 है। यदि एन ~ 3^एन है तो एन ~ 3^(2^20)> 10^(500207) है। वैज्ञानिकों का अनुमान है (http://www.stormloader.com/ajy/reallife.html) कि ब्रह्मांड में केवल 10^87 कण हैं। तो कोई कंप्यूटर नहीं है (बेवकूफ) जिस तरह से कंप्यूटर आकार 10^(500207) के अंतर को संभाल सकता है।
जोनलम: हालांकि मैं परिभाषित पीवी() फ़ंक्शन के बारे में थोड़ा सा curios हूं। (I इसे text.find() परिभाषित नहीं किया गया है (इसे अन्य मॉड्यूल में अनुमान लगाएं))। यह कार्य कैसे काम करता है और इसका क्या फायदा है?
पीवी एक छोटा सा सहायक कार्य है जिसे मैंने चर के मूल्य को डीबग करने के लिए लिखा है। यह प्रिंट() जैसा काम करता है जब आप कहते हैं कि पीवी (एक्स) यह शाब्दिक चर नाम (या अभिव्यक्ति स्ट्रिंग), एक कोलन, और उसके बाद वैरिएबल का मान दोनों प्रिंट करता है।
आप एक स्क्रिप्ट में
#!/usr/bin/env python
import traceback
def pv(var):
(filename,line_number,function_name,text)=traceback.extract_stack()[-2]
print('%s: %s'%(text[text.find('(')+1:-1],var))
x=1
pv(x)
डालें, तो आप मिलना चाहिए
x: 1
प्रिंट से अधिक पीवी का उपयोग करने का मामूली लाभ यह आप टाइप बचाता है।इसके बजाय करने की लिखना
print('x: %s'%x)
तुम सिर्फ नीचे
pv(x)
जब ट्रैक करने के लिए कई चर देखते हैं तमाचा सकते हैं, यह चर लेबल करने के लिए उपयोगी है। मैं इसे सब लिखने के थक गया था।
पीवी फ़ंक्शन पीवी फ़ंक्शन को कॉल करने के लिए उपयोग किए गए कोड की रेखा पर देखने के लिए ट्रेसबैक मॉड्यूल का उपयोग करके काम करता है। (http://docs.python.org/library/traceback.html#module-traceback देखें) कोड की उस पंक्ति को परिवर्तनीय पाठ में एक स्ट्रिंग के रूप में संग्रहीत किया जाता है। text.find() सामान्य स्ट्रिंग विधि खोजने के लिए एक कॉल है()। उदाहरण के लिए, यदि
text='pv(x)'
तो
text.find('(') == 2 # The index of the '(' in string text
text[text.find('(')+1:-1] == 'x' # Everything in between the parentheses
मैं यह सोचते हैं रहा हूँ n ~ 3^N, और n ~ 2 ** 20
विचार मॉड्यूल एन काम करने के लिए यह कटौती है सरणी के आकार पर नीचे। दूसरा विचार (महत्वपूर्ण है जब एन बड़ा है) 'ऑब्जेक्ट' प्रकार के numpy ndarrays का उपयोग करना है क्योंकि यदि आप एक पूर्णांक प्रकार का उपयोग करते हैं तो आप अधिकतम पूर्णांक के आकार को बहने का जोखिम चलाते हैं।
#!/usr/bin/env python
import traceback
import numpy as np
def pv(var):
(filename,line_number,function_name,text)=traceback.extract_stack()[-2]
print('%s: %s'%(text[text.find('(')+1:-1],var))
आप 2 ** 20 होने के लिए n बदल सकते हैं, लेकिन नीचे मैं दिखाती हैं, जो छोटे n तो उत्पादन पढ़ने में आसान है के साथ होता है।
n=100
N=int(np.exp(1./3*np.log(n)))
pv(N)
# N: 4
a=np.random.randint(N,size=n)
b=np.random.randint(N,size=n)
pv(a)
pv(b)
# a: [1 0 3 0 1 0 1 2 0 2 1 3 1 0 1 2 2 0 2 3 3 3 1 0 1 1 2 0 1 2 3 1 2 1 0 0 3
# 1 3 2 3 2 1 1 2 2 0 3 0 2 0 0 2 2 1 3 0 2 1 0 2 3 1 0 1 1 0 1 3 0 2 2 0 2
# 0 2 3 0 2 0 1 1 3 2 2 3 2 0 3 1 1 1 1 2 3 3 2 2 3 1]
# b: [1 3 2 1 1 2 1 1 1 3 0 3 0 2 2 3 2 0 1 3 1 0 0 3 3 2 1 1 2 0 1 2 0 3 3 1 0
# 3 3 3 1 1 3 3 3 1 1 0 2 1 0 0 3 0 2 1 0 2 2 0 0 0 1 1 3 1 1 1 2 1 1 3 2 3
# 3 1 2 1 0 0 2 3 1 0 2 1 1 1 1 3 3 0 2 2 3 2 0 1 3 1]
वा 0, 1s, 2s की संख्या रखती, एक पश्चिम बंगाल में 3s निशानी के रूप में एक 0 की
wa=np.bincount(a)
wb=np.bincount(b)
pv(wa)
pv(wb)
# wa: [24 28 28 20]
# wb: [21 34 20 25]
result=np.zeros(N,dtype='object')
Think ख में 0, 1s, 2s, 3s की संख्या रखती या चिप। इसी प्रकार 1,2,3 के लिए।
वा = [24 28 28 20] के बारे में सोचें, जिसका मतलब है कि 24 0-चिप्स, 28 1-चिप्स, 28 2-चिप्स, 20 3-चिप्स के साथ एक बैग है।
आपके पास वा-बैग और एक डब्ल्यूबी बैग है। जब आप प्रत्येक बैग से एक चिप खींचते हैं, तो आप उन्हें एक साथ जोड़ते हैं और एक नई चिप बनाते हैं। आप जवाब "mod" (मॉड्यूलो एन)।
कल्पना करें कि डब्ल्यूबी-बैग से 1-चिप लेना और वा-बैग में प्रत्येक चिप के साथ जोड़ना।
1-chip + 0-chip = 1-chip
1-chip + 1-chip = 2-chip
1-chip + 2-chip = 3-chip
1-chip + 3-chip = 4-chip = 0-chip (we are mod'ing by N=4)
चूंकि पश्चिम बंगाल की थैली में 34 1-चिप्स कर रहे हैं, जब आप उन्हें वा में सभी चिप्स के खिलाफ जोड़ने = [24 28 28 20] बैग, आप मिल
34*24 1-chips
34*28 2-chips
34*28 3-chips
34*20 0-chips
यह वह जगह है 34 1-चिप्स के कारण आंशिक गिनती। तुम भी पश्चिम बंगाल-बैग में चिप्स के अन्य प्रकारों को प्रबंधित करने के लिए है, लेकिन यह आप विधि नीचे इस्तेमाल किया दिखाता है:
for i,count in enumerate(wb):
partial_count=count*wa
pv(partial_count)
shifted_partial_count=np.roll(partial_count,i)
pv(shifted_partial_count)
result+=shifted_partial_count
# partial_count: [504 588 588 420]
# shifted_partial_count: [504 588 588 420]
# partial_count: [816 952 952 680]
# shifted_partial_count: [680 816 952 952]
# partial_count: [480 560 560 400]
# shifted_partial_count: [560 400 480 560]
# partial_count: [600 700 700 500]
# shifted_partial_count: [700 700 500 600]
pv(result)
# result: [2444 2504 2520 2532]
यह अंतिम परिणाम है: 2444 0, 2504 1s, 2520 2s, 2532 3s ।
# This is a test to make sure the result is correct.
# This uses a very memory intensive method.
# c is too huge when n is large.
if n>1000:
print('n is too large to run the check')
else:
c=(a[:]+b[:,np.newaxis])
c=c.ravel()
c=c%N
result2=np.bincount(c)
pv(result2)
assert(all(r1==r2 for r1,r2 in zip(result,result2)))
# result2: [2444 2504 2520 2532]
और एन कितना बड़ा है? – unutbu
क्या यह वास्तव में कुशल है? मुझे लगता है कि आप सी ++ में बेहतर होंगे, अपने कार्यों को लिखेंगे और अनुकूलित कर सकते हैं। जो numpy की तरह लगता है उससे बड़े पैमाने पर सरणी संभाल नहीं सकता है। हालांकि मुझे यह कहना होगा कि यदि आपके पास 2^15 से 2^20 तत्वों के साथ दो सरणी हैं, तो यदि आप उनके सभी अलग-अलग रकम देखते हैं तो आप 2^30 से 2^40 तत्वों की सरणी के साथ समाप्त हो जाएंगे। जो बहुत है .. – JSchlather
@unutbu: एन ~ 3^एन @ लाइबेरकीड: मुझे लगता है कि आप सही हैं। मेरे सी ++ कौशल अच्छे नहीं हैं। – jonalm