如何使用运行前的整数替换run中的每个值

Question

使用Mathematica,我有一个列表:

l={0,0,0,1,2,0,0,0,1,0,0,0,2,0,0,0}

我想将一个函数应用于上面的列表以获得以下内容:

{0,0,0,1,2,2,2,2,1,1,1,1,2,2,2,2}

本质上,我想用相同长度的运行替换0值的运行,但是使用每次运行0之前的正整数的值.

我认为我可以使用FoldList轻松完成这项工作,但我无法看到解决方案.

非常感谢.

Answer 1

这是你的测试清单:

tst = {0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0}

以下解决方案将相当有效:

In[31]:= Module[{n = 0}, Replace[tst, {0 :> n, x_ :> (n = x)}, {1}]]

Out[31]= {0, 0, 0, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2}

它的工作方式如下:我们使用的事实是只应用第一个匹配规则.该变量n存储模式匹配器在列表中运行期间遇到的最后一个非零值.最初它设置为零.第一个规则替换0为当前值n.如果匹配,则进行替换并继续进行模式匹配.如果它不匹配,那么我们有一个非零值,第二个规则适用,更新值n.由于Set赋值返回值,因此简单地放回非零元素.解决方案应该具有列表长度的线性复杂性,并且IMO是偶尔使用与规则混合的副作用的一个很好的例子.

编辑

这是一个功能版本:

In[56]:= Module[{n = 0}, Map[If[# != 0, n = #, n] &, tst]]

Out[56]= {0, 0, 0, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2}

可以检查基于规则的版本对于真正大的列表来说快了大约4倍.但是,这种形式的优点是它可以很容易地Compile-d,提供极高的性能:

nzrunsC = 
 Compile[{{l, _Integer, 1}}, 
   Module[{n = 0}, Map[If[# != 0, n = #, n] &, l]], 
   CompilationTarget -> "C"]

In[68]:= tstLarge = RandomInteger[{0,2},{10000000}];

In[69]:= nzrunsC[tstLarge];//Timing
Out[69]= {0.047,Null}

In[70]:= Module[{n = 0},Map[If[#!=0,n = #,n]&,tstLarge]];//Timing
Out[70]= {18.203,Null}

这里的差异是几百倍,比基于规则的解决方案快一百倍.OTOH,基于规则的解决方案也适用于符号列表,不一定是整数列表.

Answer 2

ReplaceRepeated似乎可以正常工作:

l //. {f__, x_ /; x != 0, 0, e___} :> {f, x, x, e}

(*   {0, 0, 0, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2}  *)

Answer 3

您最初使用FoldList的想法产生了以下优雅的解决方案:

In[1]:= tst = {0, 0, 0, 1, 2, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0};

In[2]:= FoldList[If[#2 != 0, #2, #1] &, 0, tst] // Rest                 

Out[2]= {0, 0, 0, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2}

此解决方案在功能上更纯,因为它不需要将辅助变量设置为副作用,如基于规则或基于映射的版本.它也更快:

In[3]:= tstLarge = RandomInteger[{0, 2}, {10000000}];

In[4]:= Module[{n = 0}, Replace[tstLarge, {0 :> n, x_ :> (n = x)}, {1}]]; // Timing

Out[4]= {5.704, Null}

In[5]:= Module[{n = 0}, Map[If[# != 0, n = #, n] &, tstLarge]]; // Timing

Out[5]= {16.5619, Null}

In[6]:= FoldList[If[#2 != 0, #2, #1] &, 0, tstLarge] // Rest; // Timing

Out[6]= {1.25148, Null}