¿Cómo reemplazar cada 0 con el elemento precedente en una lista de manera idiomática en Mathematica?

Question

Este es un pequeño problema divertido, y quería consultar con los expertos aquí si hay una mejor manera funcional/Mathematica para abordar la solución de lo que hice. No estoy muy contento con mi solución ya que utilizar grandes si entonces si no en ella, pero no pudo encontrar un comando Mathematica para utilizar fácilmente para hacerlo (como Select, Cases, Sow/Reap, Map .. etc ...)

Este es el problema, dados los valores de una lista (números o símbolos), pero por simplicidad, supongamos una lista de números por el momento. La lista puede contener ceros y el objetivo es reemplazar cada cero con el elemento visto antes.

Al final, la lista no debe contener ceros.

Aquí es un ejemplo, dado

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

el resultado debe ser

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

Se debe por supuesto ser hecho de la manera más eficiente.

Esto es lo que podría llegar a

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

quería ver si puedo usar Sow/Reap con esto, pero no sabía cómo.

pregunta: ¿esto se puede resolver de una manera más funcional/Mathematica? Cuanto más corto sea el mejor por supuesto :)

actualización 1 Gracias a todos por la respuesta, todos son muy buenos para aprender. Este es el resultado de la prueba de velocidad, en V 8.04, utilizando Windows 7, 4 GB de RAM, Intel 930 @ 2,8 Ghz:

He probado los métodos dados para n de 100,000 a 4 million. El método ReplaceRepeated no funciona bien para listas grandes.

actualización 2

Eliminado resultado anterior que se muestra arriba en Update1 debido a mi error en la copia de una de las pruebas.

Los resultados actualizados están por debajo. El método Leonid es el más rápido. Felicidades Leonid. Un método muy rápido.

El programa de prueba es el siguiente:

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

para ejecutar las pruebas de longitud 1000 del comando es:

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

Gracias a todos por las respuestas.

Answer 1

Mucho (orden de magnitud) más rápido que otras soluciones fijas:

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

La aceleración se debe a la autocompilación Fold. No será tan dramático para arreglos no empaquetados. Puntos de referencia:

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

Su pregunta es exactamente igual a una tarea para la función ReplaceRepeated.Lo que hace básicamente es que aplica el mismo conjunto de reglas a la expresión hasta que no se apliquen más reglas. En su caso, la expresión es una lista, y la regla es reemplazar 0 con su predecesor cada vez que aparece en una lista. Así que aquí está la solución:

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

El patrón de la regla aquí es la siguiente:

• x___ - cualquier símbolo, cero o más repeticiones, el principio de la lista
• y_ - exactamente un elemento cero antes
• 0 - cero en sí, este elemento será reemplazado con y tarde
• z___ - cualquier símbolo, cero o más repeticiones, al final de la lista

Answer 3

Esto parece ser un factor 4 más rápido en mi máquina:

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

Los tiempos que recibo son

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 4

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

es de alrededor de 10 y 2 veces más rápido que las soluciones de Heike pero más lento que Leonid.