Numpy, проблема с долгими массивами

Проверьте свои математические расчеты, это много места, которое вы просите:

2 ^ 20 * 2 ^ 20 = 2 ^ 40 = 1 099 511 627 776

Если каждый из ваших элементов был всего одним байтом, это уже один терабайт памяти.

Добавьте один или два цикла. Эта проблема не подходит для максимального использования памяти и минимизации вычислений.

Редактировать в ответ на комментарий Джональма:

jonalm: N ~ 3 ^ n, а не n ~ 3 ^ N. N - максимальный элемент в a, а n - количество элементов в a.

n составляет ~ 2 ^ 20. Если N равно ~ 3 ^ n, то N равно ~ 3 ^ (2 ^ 20)> 10 ^ (500207). По оценкам ученых ( http://www.stormloader.com/ajy/reallife.html ), во Вселенной всего около 10 ^ 87 частиц. Таким образом, нет (наивного) способа, которым компьютер может обрабатывать int размером 10 ^ (500207).

jonalm: Однако меня немного интересует определяемая вами функция pv (). (Я не удается запустить его, поскольку text.find () не определен (угадайте его в другом модуль)). Как работает эта функция и в чем ее преимущество?

pv - это небольшая вспомогательная функция, которую я написал для отладки значений переменных. Это работает как print (), кроме случаев, когда вы говорите pv (x), он печатает как буквальное имя переменной (или строку выражения), так и двоеточие, а затем значение переменной.

Если вы поместите

#!/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

] Скромным преимуществом использования pv перед печатью является то, что это избавляет вас от набора текста. Вместо того, чтобы напишите

print('x: %s'%x)

, вы можете просто похлопать

pv(x)

Когда есть несколько переменных, которые нужно отслеживать, полезно пометить переменные. Я просто устал все это писать.

Функция pv работает, используя модуль трассировки, чтобы заглянуть в строку кода используется для вызова самой функции pv. (См. http://docs.python.org/library/traceback.html#module-traceback ) Эта строка кода сохраняется в виде строки в тексте переменной. text.find () - это вызов обычного строкового метода 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

Идея состоит в том, чтобы работать с модулем N. Это сокращает размер массивов. Вторая идея (важная, когда n огромное) - использовать numpy ndarrays типа 'object', потому что, если вы используете целочисленный dtype, вы рискуете выйти за пределы размера максимально допустимого целого числа.

#!/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))

Вы можете изменить n на 2 ** 20, но ниже я покажу, что происходит с маленьким 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]

wa содержит количество 0, 1, 2, 3 в wb содержит количество 0, 1, 2, 3 в 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')

Думайте о 0 как о фишке или фишке. Аналогично для 1,2,3.

Думайте о wa = [24 28 28 20] как о сумке с 24 0-фишками, 28 1-фишками, 28 2-фишками, 20 3-фишками.

У вас есть ва-мешок и вб-мешок. Когда вы вынимаете фишку из каждого мешка, вы «складываете» их вместе и формируете новую фишку. Вы "модифицируете" ответ (по модулю N).

Представьте себе, что вы берете 1-фишку из wb-bag и добавляете ее вместе с каждой фишкой в ​​wa-bag.

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)

Поскольку в wb 34 1-фишки. мешок, когда вы добавляете их ко всем фишкам в сумке wa = [24 28 28 20], вы получаете

34*24 1-chips
34*28 2-chips
34*28 3-chips
34*20 0-chips

Это всего лишь частичный счет из-за 34 1-фишек. Вы также должны справиться с другими типы чипов в wb-bag, но здесь показан метод, используемый ниже:

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 1 с, 2520 2 с, 2532 3 с.

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