定义查询速度：性能问题

我有以下问题。

我需要构建大量的定义（*），如

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个粒子。可以是指数级的许多这样的配置。

---

你能详细说明你的工作方式，查找时间是指数级的吗？

如果它确实是指数级的，也许你可以通过在你的密钥（配置）上使用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};
ListLogLogPlot@out

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

---

假设你输入的信息不像

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

但成N1 X N2 N3 X X N4矩阵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 = ConstantArray[0, {4, 4, 4, 4}];来初始化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
  ]
]

给

因此，对于更大的信息来说，矩阵方法似乎显然是可取的。

当然，如果你有真正的大数据，比你拥有更多的GB，那么你只需要使用一个数据库和DatabaseLink。

链接地址: http://www.djcxy.com/p/35501.html

上一篇: Definition lookup speed: a performance issue

下一篇: (MathLink) Correct handling of Messages generated by slave kernel