在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?

    最佳答案

    我怀疑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而不太像MapConstantArray示例。这似乎表明,如果没有一些深层的内核魔术,就没有很大的空间可以显着提高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,我希望进一步的微优化可以进一步缩小差距。但是,我热切期盼与您一起等待答案,这个答案将进一步提高十倍。

    10-01 15:53