6

在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 ]}}

我想要该函数的每个应用程序的列表元素：

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]]}}

可以将其实现为：

MapList[f_, expr_, level_: 1] :=
 MapAt[f, expr, #] & /@
  Position[expr, _, level, Heads -> False]

但是，它的效率很低。考虑这个简单的案例，并比较这些时间：

a = Range@1000;
#^2 & /@ a // timeAvg
MapList[#^2 &, a] // timeAvg
ConstantArray[#^2 & /@ a, 1000] // timeAvg

0.00005088

0.01436

0.0003744

这说明平均而言MapList，比将函数映射到列表中的每个元素并创建 1000x1000 数组的总和慢约 38 倍。

因此，如何最有效地实现 MapList？

4

3 回答 3

6

（更新了我的功能）

我想我可以在 WReach 的尝试之上再提供 2 倍的提升。

Remove[MapListTelefunken];
MapListTelefunken[f_, dims_] :=
 With[{a = Range[dims], fun = f[[1]]},
  With[{replace = ({#, #} -> fun) & /@ a},
   ReplacePart[ConstantArray[a, {dims}], replace]
   ]
  ]

以下是我机器上的时间（Sony Z 笔记本电脑；i7、8GB 内存、Raid 0 中的 256 SSD）：

a = Range@1000;
#^2 & /@ a; // timeAvg
MapList[#^2 &, a]; // timeAvg
MapListWR4[#^2 &, a]; // timeAvg
MapListTelefunken[#^2 &, 1000]; // timeAvg

0.0000296 (* just Mapping the function over a Range[1000] for baseline *)
0.0297 (* the original MapList proposed by Mr.Wizard *)
0.00936 (* MapListWR4 from WReach *)
0.00468 (* my attempt *)
于 2011-10-31T23:51:18.267 回答
6

我怀疑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程度和程度不同。这似乎表明，如果没有一些深层内核魔法，显着提高性能的空间不大。我们可以节省一些时间：MapConstantArrayMapListMapList

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案例的第二个因素，我希望进一步的微优化可以进一步缩小差距。但怀着热切的期待，我和你们一起等待一个显示进一步十倍改进的答案。

于 2011-10-30T20:06:38.027 回答
3

I think you'd still need to create the 1000x1000 array, and I don't think there's any cleverer way than a constant array. More to the point, your examples are better served with the following definition, although I admit that it lacks the finesse of levels.

MapList[f_, list_] := (Table[MapAt[f, #, i], {i, Length@#}] &)@list;

The culprit in your own definition is the Position[] call, which creates a complex auxiliary structure.

Provide a more complex use case, that will better cover your intentions.

于 2011-10-30T12:10:23.107 回答