我有两个数组(a和b),其中n个整数元素在范围(0,n)内。
输入错误:数组中有2^n个整数,其中最大的整数取n=3^n
我想计算a和b中每个元素组合的和(sum_ij_u=a_I_u+b_j_u,for allI,j)。然后取模N(sum_ij_u=sum_ij_uu%N),最后计算不同和的频率。
为了在没有任何循环的情况下快速使用numpy,我尝试使用meshgrid和bincount函数。
A,B = numpy.meshgrid(a,b)
A = A + B
A = A % N
A = numpy.reshape(A,A.size)
result = numpy.bincount(A)
现在,问题是我的输入数组太长了。当我使用包含2^13个元素的输入时,meshgrid会给我内存错误。我想为2^15-2^20个元素的数组计算这个值。
在15到20之间的n
有没有什么聪明的把戏来对付努比?
任何帮助都将不胜感激。
-- 乔恩
检查你的数学,这是你要的空间的一个块:
2^20*2^20=2^40=1099 511 627 776
如果每个元素只有一个字节,那已经是一个太字节的内存了。
加一两个圈。这个问题不适合于最大化内存和最小化计算。
针对jonalm的评论进行编辑:
n是~2^20。如果N是~3^N,则N是~3^(2^20)>;10^(500207)。 科学家估计宇宙中只有大约10^87个粒子。因此,计算机无法(天真地)处理10^(500207)大小的整数。
pv是我为调试变量值而编写的一个小助手函数。它工作起来像 print()除了当您说pv(x)时,它同时打印文本变量名(或表达式字符串)、冒号和变量值。
如果你把
在剧本里你应该得到
与打印相比,使用pv的适度优势在于它可以节省您的打字时间。而不是不得不 写
你可以拍下来
当有多个变量要跟踪时,标记这些变量会很有帮助。 我只是厌倦了写出来。
pv函数通过使用回溯模块查看代码行来工作 用于调用pv函数本身。(参见http://docs.python.org/library/traceback.html#module-traceback)这行代码作为字符串存储在变量文本中。 find()是对常用字符串方法find()的调用。例如,如果
那么
我假设n~3^n,和n~2**20
我们的想法是让模块N工作,这样可以减少数组的大小。 第二个想法(n很大时很重要)是使用“object”类型的numpy ndarrays,因为如果使用整数类型,则可能会溢出所允许的最大整数的大小。
你可以将n改为2**20,但下面我将展示小n的情况 所以输出更容易阅读。
wa在a中包含0、1、2、3的数字 wb保存b中0、1、2、3的数目
把0当作一个代币或筹码。对于1,2,3也一样。
把wa=[24 28 28 20]看作是一个包,里面有24个0片,28个1片,28个2片,20个3片。
你有一个wa包和一个wb包。当你从每个袋子里抽出一个芯片时,你把它们“加”在一起,形成一个新的芯片。你“修改”答案(模N)。
想象一下从wb包中取出一个芯片,并将其与wa包中的每个芯片一起添加。
由于wb包中有34个1-芯片,当您将它们与wa=[24 28 28 20]包中的所有芯片相加时,您将得到
这只是34个1芯片的部分计数。你还得处理另一个 wb袋中的芯片类型,但这向您展示了以下使用的方法:
这是最终结果:24440s,25041s,25202s,25323s
试着把它分块。你的网格是一个NxN矩阵,块高达10x10n/10xN/10,只需计算100个箱子,在最后加起来。这只占用大约1%的内存。
相关问题 更多 >
编程相关推荐