在Mathematica中,有许多函数不仅返回最终结果或单个匹配项,还返回所有结果。这些函数称为*List
。展示:
我缺少的是MapList函数。
例如,我想要:
MapList[f, {1, 2, 3, 4}]
{{f[1], 2, 3, 4}, {1, f[2], 3, 4}, {1, 2, f[3], 4}, {1, 2, 3, f[4]}}
I want a list element for each application of the function:
MapList[
f,
{h[1, 2], {4, Sin[x]}},
{2}
] // Column
{h[f[1], 2], {4, Sin[x]}} {h[1, f[2]], {4, Sin[x]}} {h[1, 2], {f[4], Sin[x]}} {h[1, 2], {4, f[Sin[x]]}}
One may implement this as:
MapList[f_, expr_, level_: 1] :=
MapAt[f, expr, #] & /@
Position[expr, _, level, Heads -> False]
但是,它效率很低。考虑这个简单的情况,并比较以下timings:a = Range@1000;
#^2 & /@ a // timeAvg
MapList[#^2 &, a] // timeAvg
ConstantArray[#^2 & /@ a, 1000] // timeAvg
0.00005088
0.01436
0.0003744
这说明,与将函数映射到列表中的每个元素并创建1000x1000数组的总和相比,MapList
平均要慢38倍。因此,如何最有效地实现MapList?
最佳答案
我怀疑MapList
对执行结构修改的任何转换都接近性能极限。现有的目标基准并不是真正的公平比较。 Map
示例正在创建一个简单的整数向量。 ConstantArray
示例创建一个简单的向量,该向量包含对同一列表的共享引用。 MapList
在这些示例中显示得很差,因为它正在创建一个向量,其中每个元素都是一个新生成的,非共享的数据结构。
我在下面又添加了两个基准。在这两种情况下,结果的每个元素都是一个压缩数组。 Array
案例通过对Listable
执行a
加法来生成新元素。 Module
情况通过替换a
副本中的单个值来生成新元素。这些结果如下:
In[8]:= a = Range@1000;
#^2 & /@ a // timeAvg
MapList[#^2 &, a] // timeAvg
ConstantArray[#^2 & /@ a, 1000] // timeAvg
Array[a+# &, 1000] // timeAvg
Module[{c}, Table[c = a; c[[i]] = c[[i]]^2; c, {i, 1000}]] // timeAvg
Out[9]= 0.0005504
Out[10]= 0.0966
Out[11]= 0.003624
Out[12]= 0.0156
Out[13]= 0.02308
注意新的基准测试如何表现得更像
MapList
而不太像Map
或ConstantArray
示例。这似乎表明,如果没有一些深层的内核魔术,就没有很大的空间可以显着提高MapList
的性能。因此,我们可以从MapList
中节省一些时间:MapListWR4[f_, expr_, level_: {1}] :=
Module[{positions, replacements}
, positions = Position[expr, _, level, Heads -> False]
; replacements = # -> f[Extract[expr, #]] & /@ positions
; ReplacePart[expr, #] & /@ replacements
]
产生这些时间的时间:
In[15]:= a = Range@1000;
#^2 & /@ a // timeAvg
MapListWR4[#^2 &, a] // timeAvg
ConstantArray[#^2 & /@ a, 1000] // timeAvg
Array[a+# &, 1000] // timeAvg
Module[{c}, Table[c = a; c[[i]] = c[[i]]^2; c, {i, 1000}]] // timeAvg
Out[16]= 0.0005488
Out[17]= 0.04056
Out[18]= 0.003
Out[19]= 0.015
Out[20]= 0.02372
这属于
Module
情况的因素2,我希望进一步的微优化可以进一步缩小差距。但是,我热切期盼与您一起等待答案,这个答案将进一步提高十倍。