bearbeiten als Antwort auf jonalm Kommentar:
jonalm: N ~ 3^n nicht n ~ 3^N. N ist ein maximales Element in a und n ist eine Anzahl von Elementen in a.
n ist ~ 2^20. Wenn N ~ 3^n ist, dann ist N ~ 3^(2^20)> 10^(500207). Wissenschaftler schätzen (http://www.stormloader.com/ajy/reallife.html), dass es im Universum nur etwa 10^87 Teilchen gibt. Es gibt also keine (naive) Art, wie ein Computer ein int der Größe 10^(500207) verarbeiten kann.
jonalm: Ich bin jedoch ein wenig neugierig über die pv() -Funktion, die Sie definieren. (I nicht verwalten, um es als text.find() ist nicht definiert (erraten Sie es in einem anderen Modul )). Wie funktioniert diese Funktion und was ist ihr Vorteil?
pv ist eine kleine Hilfsfunktion, die ich schrieb, um den Wert von Variablen zu debuggen. Es funktioniert wie print(), außer wenn Sie pv (x) sagen, druckt es sowohl den Namen der Literalvariablen (oder Ausdruckszeichenfolge), einen Doppelpunkt und dann den Wert der Variablen.
Wenn Sie
#!/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)
in einem Skript setzen sollten Sie
x: 1
Der bescheidene Vorteil pv Over-Print ist, dass es erspart Ihnen die Eingabe.Statt
print('x: %s'%x)
schreiben zu müssen können Sie einfach hinknallen
pv(x)
Wenn mehrere Variablen zu verfolgen, ist es hilfreich, die Variablen zu beschriften. Ich war es einfach leid, alles zu schreiben.
Die pv-Funktion arbeitet mit dem Traceback-Modul, um die Codezeile zu betrachten, die zum Aufruf der pv-Funktion verwendet wird. (Siehe http://docs.python.org/library/traceback.html#module-traceback) Diese Codezeile wird als Zeichenfolge im variablen Text gespeichert. text.find() ist ein Aufruf der üblichen String-Methode find(). Zum Beispiel, wenn
text='pv(x)'
dann
text.find('(') == 2 # The index of the '(' in string text
text[text.find('(')+1:-1] == 'x' # Everything in between the parentheses
Ich gehe davon aus n ~ 3^N und n ~ 2 ** 20
Die Idee ist es, diese Schnitte Modul N. zu arbeiten unten auf die Größe der Arrays. Die zweite Idee (wichtig, wenn n sehr groß ist) besteht darin, numpy nDarrays vom Typ 'object' zu verwenden, da bei Verwendung eines ganzzahligen dtype das Risiko besteht, dass die maximal zulässige ganze Zahl überschritten wird.
#!/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))
können Sie n ändern zu 2 ** 20, aber unter ich zeigen, was mit kleinen n geschieht so dass der Ausgang ist leichter zu lesen.
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]
wa die Anzahl der 0s, 1s, 2s, 3s in einem wb hält hält die Anzahl der 0s, 1s, 2s, 3s in b
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')
Denken Sie an eine 0 als ein Zeichen oder Chip. Ähnlich für 1,2,3.
Denken Sie an wa = [24 28 28 20], was bedeutet, dass es eine Tüte mit 24 0-Chips, 28 1-Chips, 28 2-Chips, 20 3-Chips gibt.
Sie haben eine Wa- und eine WB-Tasche. Wenn Sie aus jeder Tasche einen Chip ziehen, "addieren" Sie sie und bilden einen neuen Chip. Sie "mod" die Antwort (modulo N).
Stellen Sie sich vor, Sie nehmen einen 1-Chip aus der WB-Tasche und fügen ihn mit jedem Chip in die Wa- Tasche ein.
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)
Da es 34 1-Chips in der wb Tasche sind, wenn man sie gegen alle Chips in der wa hinzufügen = [24 28 28 20] Tasche, Sie erhalten
34*24 1-chips
34*28 2-chips
34*28 3-chips
34*20 0-chips
Dies ist nur die Teilzählung aufgrund der 34 1-Chips. Sie haben auch die anderen Arten von Chips in der wb-Tasche zu handhaben, aber dies zeigt Ihnen die folgende Methode verwendet:
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]
Dies ist das Endergebnis: 2444 0s, 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]
Und wie groß ist N? – unutbu
Wird Numpy wirklich so effizient sein? Ich nehme an, Sie wären besser dran in C++, schreiben Sie Ihre eigenen Funktionen und optimieren Sie, wie Sie können. Von was es klingt wie numpy kann Array nicht so groß handhaben. Obwohl ich sagen muss, wenn Sie zwei Arrays mit 2^15 bis 2^20 Elemente haben, dann wenn Sie sich alle ihre verschiedenen Summen betrachten, dann werden Sie mit einem Array von 2^30 bis 2^40 Elemente enden. Was ist viel .. – JSchlather
@unutbu: N ~ 3^n @liberalkid: Ich denke, du hast Recht. Tho meine C++ Fähigkeiten sind nicht so gut. – jonalm