6

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

関数のアプリケーションごとにリスト要素が必要です。

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

私のマシン（SonyZラップトップ;i7、8GB RAM、RAID0の256SSD）のタイミングは次のとおりです。

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各要素が新しく生成された非共有のデータ構造であるベクトルを作成しているため、これらの例に対しては不十分です。

以下にさらに2つのベンチマークを追加しました。どちらの場合も、結果の各要素はパックされた配列です。ケースは、に加算をArray実行することによって新しい要素を生成します。ケースは、のコピー内の単一の値を置き換えることによって新しい要素を生成します。これらの結果は次のとおりです。ListableaModulea

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ケースの要因2の範囲内であり、さらなるマイクロ最適化によってギャップをさらに埋めることができると私は期待しています。しかし、私があなたに加わって、さらに10倍の改善を示す答えを待っているのは、熱心な期待です。

于 2011-10-30T20:06:38.027 に答える
3

1000x1000配列を作成する必要があると思いますが、定数配列よりも賢い方法はないと思います。もっと要点を言えば、あなたの例は次の定義でよりよく提供されますが、私はそれがレベルの精巧さを欠いていることを認めます。

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

あなた自身の定義の犯人はPosition[]、複雑な補助構造を作成する呼び出しです。

より複雑なユースケースを提供してください。これにより、意図がより適切にカバーされます。

于 2011-10-30T12:10:23.107 に答える