Jak zamienić każdy 0 na poprzedni element na liście w sposób idiomatyczny w Mathematica?

Question

To jest mały, zabawny problem i chciałem sprawdzić u ekspertów, czy istnieje lepszy, funkcjonalny/matematyczny sposób podejścia do rozwiązania problemu niż to, co zrobiłem. Nie jestem zbyt zadowolony z mojego rozwiązania, ponieważ używam dużego IF THEN ELSE, ale nie mogę znaleźć polecenia Mathematica, które można z łatwością użyć (np. Select, Cases, Sow/Reap, Map .. itd ...)

Oto problem, biorąc pod uwagę wartości list (liczby lub symbole), ale dla uproszczenia, pozwala założyć listę liczb na razie. Lista może zawierać zera, a celem jest zastąpienie każdego zera elementem widzianym przed nim.

Na końcu, lista nie powinna zawierać zer:.

Oto przykład, biorąc pod uwagę

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

wynik powinien być

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

powinno oczywiście być wykonane w najbardziej efektywny sposób.

To co mogłem wymyślić

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

Chciałem zobaczyć, czy mogę użyć Sow/Reap na ten temat, ale nie wiem jak.

pytanie: czy można to rozwiązać w bardziej funkcjonalny/matematyczny sposób? Im krótszy, tym lepiej oczywiście :)

Update 1 Dzięki wszystkim za odpowiedzi, wszystkie są bardzo dobre do nauki. Jest to wynik testu prędkości o 8,04 V, przy użyciu szyby 7, 4 PL Ram Intel 930 @ 2,8 GHz:

I przetestowaniu wszystkich metod n z 100,000 do 4 million. Metoda ReplaceRepeated nie sprawdza się w przypadku dużych list.

Aktualizacja 2

Usunięto wcześniej wynik, który został przedstawiony powyżej w update1 powodu mojego błędu w kopiowaniu jednego z testów.

Zaktualizowane wyniki znajdują się poniżej. Metoda Leonida jest najszybsza. Gratulacje Leonid. Bardzo szybka metoda.

Program badań jest następujący:

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

Aby uruchomić testy dla długości 1000 komenda brzmi:

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

Dzięki wszystkim za odpowiedzi.

Answer 1

dużo (rząd wielkości) szybciej niż inne rozwiązania nieruchomych:

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

Przyspieszenie jest spowodowane automatycznym kompilowaniem Fold. Nie będzie tak dramatyczny dla niezapakowanych tablic. Benchmarki:

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

Pytanie wygląda dokładnie tak, jak zadanie dla funkcji ReplaceRepeated.Zasadniczo polega na tym, że stosuje on ten sam zestaw reguł do wyrażenia, dopóki nie będą obowiązywać żadne reguły. W twoim przypadku wyrażenie jest listą, a reguła ma zastąpić 0 swoim poprzednikiem, ilekroć pojawi się na liście. Więc tutaj jest rozwiązanie:

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

Wzór dla reguły jest tu następujący:

• x___ - dowolny symbol, zero lub więcej powtórzeń, początek listy
• y_ - dokładnie jeden element przed zerem
• 0 - samo zero, ten element zostanie zastąpiony przez y późniejszy
• z___ - dowolny symbol, zero lub więcej powtórzeń, koniec listy

Answer 3

To wydaje się być czynnikiem 4 szybciej na moim komputerze:

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

synchronizacją dostaję są

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] 

wynosi około 10 i 2 razy szybciej niż rozwiązania Heike, ale wolniej niż Leonid użytkownika.