定义查询速度：性能问题

我需要建立一个非常大的数字的定义（*），如

f[{1,0,0,0}] = 1 
f[{0,1,0,0}] = 2 
f[{0,0,1,0}] = 3 
f[{0,0,0,1}] = 2 
... 
f[{2,3,1,2}] = 4 
... 
f[{n1,n2,n3,n4}] = some integer 
...

这仅仅是一个例子。参数列表的长度不一定是4，但可以是任何值。我意识到，当参数列表的长度增加时，每个值的查找会以指数复杂度减慢。也许这并不奇怪，因为很明显，原则上Mathematica需要存储多少定义的组合爆炸。尽管如此，我期望Mathematica很聪明，价值提取应该是不变的时间复杂度。显然它不是。

有什么办法可以加快查找时间吗？这可能与Mathematica内部处理符号定义查找的方式有关。它是否会在列表中找到匹配项？它似乎是这样做的。

所有建议非常感谢。祝你好运卓然

（*）我正在研究随机模拟软件，它可以生成系统的所有配置，并且需要存储每次配置发生的次数。在这个意义上，列表{n1，n2，...，nT}描述了系统的一个特定配置，表明有类型1的n1个粒子，类型2的n2个粒子，类型为T的nT个粒子。可以是指数级的许多这样的配置。

来源

2011-08-30 zorank

无模式DownValue查找使用哈希，并分摊和适当的内存限制，恒定的时间。不管是什么导致你的速度问题，它本身不可能是单独的查找时间。 –

您能否详细说明您是如何计算查找时间的指数？

如果它确实是指数的，也许你可以加快速度通过在你的钥匙（配置）使用Hash，然后存储键值对像{{key1,value1},{key2,value2}}列表，不停地通过key排序，然后使用二进制搜索（这应该记录时间）。这应该是非常快速的编码，但在速度方面不是最佳的。

如果这还不够快，可以考虑设置一个合适的哈希表实现（我认为这是f[{0,1,0,1}]=3方法做的，没有检查）。

但放缓的一些玩具例子是进一步进行有益的......

编辑：我只是想

test[length_] := Block[{f}, 
    Do[ 
    f[RandomInteger[{0, 10}, 100]] = RandomInteger[0, 10];, 
    {i, 1, length} 
    ]; 
    f[{0, 0, 0, 0, 1, 7, 0, 3, 7, 8, 0, 4, 5, 8, 0, 8, 6, 7, 7, 0, 1, 6, 
     3, 9, 6, 9, 2, 7, 2, 8, 1, 1, 8, 4, 0, 5, 2, 9, 9, 10, 6, 3, 6, 
    8, 10, 0, 7, 1, 2, 8, 4, 4, 9, 5, 1, 10, 4, 1, 1, 3, 0, 3, 6, 5, 
    4, 0, 9, 5, 4, 6, 9, 6, 10, 6, 2, 4, 9, 2, 9, 8, 10, 0, 8, 4, 9, 
    5, 5, 9, 7, 2, 7, 4, 0, 2, 0, 10, 2, 4, 10, 1}] // timeIt 
    ]

与timeIt定义以准确的时间，即使短期运行如下：

timeIt::usage = "timeIt[expr] gives the time taken to execute expr, 
    repeating as many times as necessary to achieve a total time of \ 
1s"; 

SetAttributes[timeIt, HoldAll] 
timeIt[expr_] := Module[{t = Timing[expr;][[1]], tries = 1}, 
    While[t < 1., 
    tries *= 2; 
    t = Timing[Do[expr, {tries}];][[1]]; 
    ]; 
    Return[t/tries]]

然后

out = {#, test[#]} & /@ {10, 100, 1000, 10000, 100000, 100000}; 
[email protected]

enter image description here

（也适用于较大的运行）。所以在这里似乎不变。

来源

2011-08-30 12:26:44 acl

假设你输入你的信息不喜欢

f[{1,0,0,0}] = 1 
f[{0,1,0,0}] = 2

但到N1 N2 X N3 X N4 X矩阵m像

m[[2,1,1,1]] = 1 
m[[1,2,1,1]] = 2

等

（你甚至可以输入值不是f[{1,0,0,0}]=1，而是f[{1,0,0,0},1]与

f[li_List, i_Integer] := Part[m, Apply[Sequence, li + 1]] = i; 
    f[li_List] := Part[m, Apply[Sequence, li + 1]];

你必须初始化m例如通过m = ConstantArray[0, {4, 4, 4, 4}];）

让我们比较计时：

testf[z_] := 
    (
    Do[ f[{n1, n2, n3, n4}] = RandomInteger[{1,100}], {n1,z}, {n2,z}, {n3,z},{n4,z}]; 
    First[ Timing[ Do[ f[{n2, n4, n1, n3}], {n1, z}, {n2, z}, {n3, z}, {n4, z} ] ] ] 
); 
Framed[ 
    ListLinePlot[ 
     Table[{z, testf[z]}, {z, 22, 36, 2}], 
     PlotLabel -> Row[{"DownValue approach: ", 
          Round[MemoryInUse[]/1024.^2], 
          " MB needed" 
         }], 
     AxesLabel -> {"n1,n2,n3,n4", "time/s"},ImageSize -> 500 
    ] 
] 
Clear[f]; 
testf2[z_] := 
    (
    m = RandomInteger[{1, 100}, {z, z, z, z}]; 
    f2[ni__Integer] := m[[Sequence @@ ({ni} + 1)]]; 
    First[ Timing[ Do[ f2[{n2, n4, n1, n3}], {n1, z}, {n2, z}, {n3, z}, {n4, z}] ] ] 
) 
Framed[ 
    ListLinePlot[ 
     Table[{z, testf2[z]}, {z, 22, 36, 2}], 
     PlotLabel -> Row[{"Matrix approach: ", 
         Round[MemoryInUse[]/1024.^2], 
         " MB needed" 
         }], 
     AxesLabel -> {"n1,n2,n3,n4", "time/s"}, ImageSize -> 500 
    ] 
]

给

DownValues approach Matrix approach

因此，对于较大的设置信息的矩阵方法似乎清楚preferrable。

当然，如果你有真正的大数据，比如说你的RAM有更多的GB，那么你只需要就必须使用数据库和DatabaseLink。

来源

2011-08-30 22:22:23

对于大型配置空间，这会产生问题：如果配置长度为n，每个位置都有m个状态，那么预先分配的矩阵大小为n^m;所以即使是1d经典的伊辛模型也只限于30个网站。如果配置空间是稀疏采样的（我认为这是首先进行随机模拟的要点），那么基于“基于DownValues”的方法是可以的。这可以通过使用稀疏矩阵的方法来处理，并且了解他们在速度方面的表现会很有趣。 – acl

定义查询速度：性能问题

回答

相关问题