如何在Mathematica中以惯用的方式将每个0替换为列表中的前一个元素？

Question

这是一个有趣的小问题,我想与专家一起检查是否有更好的功能/ Mathematica方法来解决它而不是我做的.我不是太高兴我的解决方案,因为我用大IF THEN ELSE在里面,也没有找到一个Mathematica命令使用容易做到这一点(如Select,Cases,Sow/Reap,Map...等...)

给出列表值(数字或符号),这是问题,但为简单起见,我们假设现在有一个数字列表.列表可以包含零,目标是用前面看到的元素替换每个零.

最后,列表中不应包含零.

给出一个例子

a = {1, 0, 0, -1, 0, 0, 5, 0};

结果应该是

a = {1, 1, 1, -1, -1, -1, 5, 5}

它应该以最有效的方式完成.

这就是我能想到的

Scan[(a[[#]] = If[a[[#]] == 0, a[[#-1]], a[[#]]]) &, Range[2, Length[a]]];

我想知道我是否可以使用Sow/Reap,但不知道如何.

问题:这可以用更实用的/ Mathematica方式解决吗？越短越好的当然:)

更新1 感谢大家的回答,所有这些都是非常好的学习.这是速度测试的结果,在V 8.04上,使用Windows 7,4 GB Ram,intel 930 @ 2.8 Ghz:

我已经测试中给出的方法n,从100,000到4 million.该ReplaceRepeated方法对大型列表不适用.

更新2

由于我在复制其中一个测试时出错,删除了上面在update1中显示的结果.

更新的结果如下.列昂尼德方法是最快的.祝贺列昂尼德.一种非常快速的方法.

测试程序如下:

(*version 2.0 *)
runTests[sizeOfList_?(IntegerQ[#] && Positive[#] &)] := 
 Module[{tests, lst, result, nasser, daniel, heike, leonid, andrei, 
   sjoerd, i, names},

  nasser[lst_List] := Module[{a = lst},
    Scan[(a[[#]] = If[a[[#]] == 0, a[[# - 1]], a[[#]]]) &, 
     Range[2, Length[a]]]
    ];

  daniel[lst_List] := Module[{replaceWithPrior},
    replaceWithPrior[ll_, n_: 0] := 
     Module[{prev}, Map[If[# == 0, prev, prev = #] &, ll]
      ];
    replaceWithPrior[lst]
    ];

  heike[lst_List] := Flatten[Accumulate /@ Split[lst, (#2 == 0) &]];

  andrei[lst_List] := Module[{x, y, z},
    ReplaceRepeated[lst, {x___, y_, 0, z___} :> {x, y, y, z}, 
     MaxIterations -> Infinity]
    ];

  leonid[lst_List] := 
   FoldList[If[#2 == 0, #1, #2] &, First@#, Rest@#] & @lst;

  sjoerd[lst_List] := 
   FixedPoint[(1 - Unitize[#]) RotateRight[#] + # &, lst];

  lst = RandomChoice[Join[ConstantArray[0, 10], Range[-1, 5]], 
    sizeOfList];
  tests = {nasser, daniel, heike, leonid, sjoerd};
  names = {"Nasser","Daniel", "Heike", "Leonid", "Sjoerd"};

  result = Table[0, {Length[tests]}, {2}];

  Do[
   result[[i, 1]] = names[[i]];

   Block[{j, r = Table[0, {5}]},
    Do[
     r[[j]] = First@Timing[tests[[i]][lst]], {j, 1, 5}
     ];
    result[[i, 2]] = Mean[r]
    ],

   {i, 1, Length[tests]}
   ];

  result
  ]

要运行长度为1000的测试,命令为:

Grid[runTests[1000], Frame -> All]

谢谢大家的答案.

Answer 1

比其他解决方案还要快很多(数量级):

FoldList[If[#2 == 0, #1, #2] &, First@#, Rest@#] &

加速是由于Fold自动编译.对于非打包数组,不会那么戏剧化.基准:

In[594]:= 
a=b=c=RandomChoice[Join[ConstantArray[0,10],Range[-1,5]],150000];
(b=Flatten[Accumulate/@Split[b,(#2==0)&]]);//Timing
Scan[(a[[#]]=If[a[[#]]==0,a[[#-1]],a[[#]]])&,Range[2,Length[a]]]//Timing
(c=FoldList[If[#2==0,#1,#2]&,First@#,Rest@#]&@c);//Timing

SameQ[a,b,c]

Out[595]= {0.187,Null}
Out[596]= {0.625,Null}
Out[597]= {0.016,Null}
Out[598]= True

Answer 2

这似乎是我机器上的一个因素4:

a = Flatten[Accumulate /@ Split[a, (#2 == 0) &]]

我得到的时间是

a = b = RandomChoice[Join[ConstantArray[0, 10], Range[-1, 5]], 10000];

(b = Flatten[Accumulate /@ Split[b, (#2 == 0) &]]); // Timing

Scan[(a[[#]] = If[a[[#]] == 0, a[[# - 1]], a[[#]]]) &, 
  Range[2, Length[a]]] // Timing

SameQ[a, b]

(* {0.015815, Null} *)
(* {0.061929, Null} *)
(* True *)

Answer 3

FixedPoint[(1 - Unitize[#]) RotateRight[#] + # &, d]

比Heike的解决方案快10倍和2倍,但比Leonid的速度慢.

Answer 4

您的问题看起来与ReplaceRepeated函数的任务完全相同.它的作用基本上是它将相同的规则集应用于表达式,直到不再适用规则为止.在您的情况下,表达式是一个列表,规则是在列表中发生时将其与其前任替换为0.所以这是解决方案:

a = {1, 0, 0, -1, 0, 0, 5, 0};
a //. {x___, y_, 0, z___} -> {x, y, y, z};

此处规则的模式如下:

• x___ - 任何符号,零个或多个重复,列表的开头
• y_ - 零前正好一个元素
• 0- 零本身,此元素将在y以后替换
• z___ - 任何符号,零个或多个重复,列表的结尾