Come sostituire ogni 0 con l'elemento precedente in una lista in modo idiomatico in Mathematica?

Question

Questo è un piccolo problema divertente, e volevo verificare con gli esperti qui se c'è un modo migliore/funzionale per affrontare Mathematica rispetto a quello che ho fatto. Non sono molto contento della mia soluzione poiché utilizzo il grande IF THEN ELSE ma non riesco a trovare un comando Mathematica da usare facilmente (come Select, Cases, Sow/Reap, Map .. ecc ...)

Ecco il problema, dati i valori di una lista (numeri o simboli), ma per semplicità, per ora assumiamo una lista di numeri. L'elenco può contenere zeri e l'obiettivo è sostituire ogni zero con l'elemento visto prima.

Alla fine, l'elenco non deve contenere zeri.

Ecco un esempio, dato

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

il risultato dovrebbe essere

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

Si deve naturalmente essere fatto in modo più efficiente.

Questo è ciò che ho potuto venire con

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

Volevo vedere se posso usare Sow/Reap su questo, ma non sapeva come fare.

domanda: può essere risolto in un modo più funzionale/matematico? Più corto è meglio naturalmente :)

aggiornamento 1 Grazie a tutti per la risposta, tutti sono molto buona per imparare. Questo è il risultato di test di velocità, su V 8.04, utilizzando finestre 7, 4 GB RAM, processore Intel 930 @ 2.8 Ghz:

Ho testato metodi da applicare per n da 100,000 a 4 million. Il metodo ReplaceRepeated non funziona bene per elenchi di grandi dimensioni.

aggiornamento 2

Rimosso risultato in precedenza che è stato mostrato in precedenza in Update1 a causa del mio errore nella copia di una delle prove.

I risultati aggiornati sono di seguito. Il metodo Leonid è il più veloce. Congratulazioni Leonid. Un metodo molto veloce.

Il programma di test è la seguente:

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

Per eseguire i test per lunghezza 1000 il comando è:

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

Grazie a tutti per le risposte.

Answer 1

Gran parte (ordine di grandezza) più veloce di altre soluzioni ancora:

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

L'accelerazione è dovuta alla compilazione automatica Fold. Non sarà così drammatico per gli array non imballati. Benchmark:

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

La domanda sembra esattamente come un compito per la funzione ReplaceRepeated.Quello che fa in pratica è che applica lo stesso insieme di regole all'espressione finché non sono più applicabili. Nel tuo caso l'espressione è una lista e la regola è di sostituire 0 con il suo predecessore ogni volta che si verifica in una lista. Quindi, ecco la soluzione:

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

Il modello per la regola qui è il seguente:

• x___ - qualsiasi simbolo, zero o più ripetizioni, l'inizio della lista
• y_ - esattamente un elemento prima dello zero
• 0 - zero stesso, questo elemento verrà sostituito con y in seguito
• z___ - qualsiasi simbolo, zero o più ripetizioni, alla fine della lista

Answer 3

Questo sembra essere un fattore 4 più veloce sulla mia macchina:

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

I tempi che ricevo sono

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] 

è di circa 10 e 2 volte più veloce rispetto alle soluzioni di Heike ma più lento di Leonid di.