performance - “MapList”函数

Question

在Mathematica中，有许多函数不仅返回最终结果或单个匹配项，还返回所有结果。这些函数称为*List。展示:

FoldList

NestList

ReplaceList

ComposeList

我缺少的是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？

Answer 1

我怀疑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，我希望进一步的微优化可以进一步缩小差距。但是，我热切期盼与您一起等待答案，这个答案将进一步提高十倍。