定义查找速度:性能问题

Question

我有以下问题.

我需要构建大量的定义(*),如

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

Answer 1

你能详细说明你如何确定查找时间是指数级的吗？

如果它确实是指数级的,也许你可以通过使用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

(也适用于较大的跑步).所以这里似乎是不变的时间.