How do I replace a missing value in a column with the value immediately above throughout a table?

Question

I have a large table (7000 rows × 17 columns) of terse textual data. In many of the columns, empty entries have been replaced with "." as a marker. Working from the top of the columns downward, I want to replace each successive "." with the data value (non-".") from above until the next data value is found; at which time I want to replace the next sequence of "." with the new data value etc. E.g.

x     -->  x  
"."   -->  x  
y     -->  y  
"."   -->  y  
"."   -->  y  
z     -->  z  
"."   -->  z  

I need to do this for all rows of data. Any help would be greatly appreciated. -k-

Answer 1

How about

f[_, y_] := y
f[x_, "."] := x

fill[data_] := Transpose[FoldList[f, First[#], Rest[#]] & /@ Transpose[data]]

Answer 2

Map approach:

g["."] := last;    g[x_] := x;
Map[(last = g[#]) &, Transpose[data], {2}]\[Transpose]

Latest ideas, quite important remarks (in my opinion)

I have asked Keith about gaps in first row. ...and no one have paid atenttion (me too). It is crucial, this is what makes significant difference between this problem and problem linked by Mr. Wizard.

Why?, because this information allows us to effectively use ParallelMap.

First I thought, let Transpose->Map->Transpose, what a big deal. Parallel Map will also help each method, so result will be qualitatively the same but... it is not true.

Conclusions:

1. I am not able to help Simon's ListFold method with ParralelMap (separate question)
2. Methods's relative efficiency depends on "." density.
3. Methods's relative efficiency depends on data type.

It should depend of number_of_columns/avalible_threads but I haven't checked that. I have 2 cores.

Each method contains now ParallelMap (exept red one). 0x4A4D's works faster without parallelization so I left it too. Maybe implementation could have been better, codes are below plots.

Codes with methods upgraded with ParallelMap:

(*Simon with and without parallelmap*)
f[_, y_] := y;f[x_, "."] := x;
fill[data_] :=  Transpose[FoldList[f, First[#], Rest[#]] & /@ Transpose[data]]

fillP[data_] := Transpose[ParallelMap[
        FoldList[f, First[#], Rest[#]] &,
        Transpose[data]]]
(*mine*)
g["."] := last;g[x_] := x;
ParallelMap[(last = g[#]) &, Transpose[data], {2}]\[Transpose];
(*0x4A4D's*)
fillblanks[list_, dummy_: "."] := Flatten[
  Map[
     ConstantArray[First[#], Length[#]] &,
     Split[list, MatchQ[#2, dummy] &]]]
(*Michael's*)
filldown2 = Transpose@ParallelMap[
 Module[{last = First[#]}, Function[{entry}, last = entry /. "." -> last] /@ #] &, 
 Transpose[#]] &;

Testing procedure:

time = {};
Do[(
k = 10^i;
data = Table[RandomChoice[{"1","."}], {k}, {4}]~Prepend~(Range@4);
AppendTo[time,
 {fill@data; // Timing // First,
  fillP@data; // Timing // First,
  ParallelMap[(last = g[#]) &, Transpose[data], {2}]\[Transpose]; //Timing // First,
  Transpose[fillblanks /@ Transpose[data]]; // Timing // First,
  filldown2@data; // Timing // First
}]
), {i, 3, 6, .5}]

In order to switch % of "." I have simply used RandomChoice[{"1","."}] (for 50%) and RandomChoice[{"1","1","1","1","1","1","1","1","1","."}] for 10% :).

---

First, single thread ideas

Old There was no MapIndexed way, so now it is:

f[d_, {x_, y_}] := If[d == ".", f[data[[x - 1, y]], {x - 1, y}], d]

MapIndexed[f, data, {2}]

New Map approach:

g["."] := last
g[x_] := x
Map[(last = g[#]) &, Transpose[data], {2}]\[Transpose]

And version which needs only [[1,1]] element to be different from ".":

Partition[
   (last = g[#]) & /@ Flatten[Transpose[data]]
, Length@data]\[Transpose]

33 sec for k=10^6, faster but not fast enough. I'll update plots later.

methods comparison:

tested on 7-column k-row matrix, where k = 10^1, 10^2... Elements are strings.

data=Table[RandomChoice[{"1", "2", "3", "."}], {k}, {7}]~Prepend~(ToString /@Range@7);

Answer 3

This question is arguably a duplicate of: Fill out blanks with a upcoming number in a list?
There the filling is requested in reverse and for a single list, but the principle is the same.

Simon Woods already posted what is IMHO the most natural approach: FoldList, but as we are already restating earlier answers I'd like to share my own variations.

For each method I'll show application to a single list v; application to columns is easily accomplished with a double Transpose.

Heike's method using FoldList and /.:

v = {8, 3, ".", 1, ".", ".", 7, ".", 9, ".", ".", ".", ".", ".", ".", ".", 2, ".", 2, 6};

Rest @ FoldList[#2 /. "." -> # &, ".", v]

{8, 3, 3, 1, 1, 1, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 2, 2, 2, 6}

Also of interest is Leonid's method with Split. Here in a different style:

Join @@ (Table[#, {Length@{##}}] & @@@ Split[v, #2 === "." &])

{8, 3, 3, 1, 1, 1, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 2, 2, 2, 6}

Simon's code is faster than either of these on unpacked (mixed) data:

SeedRandom[3]
v = Clip[RandomInteger[{-7, 9}, 350000], {1, ∞}, {".", 1}];

Rest@FoldList[#2 /. "." -> # &, ".", v]                        // Timing // First
Join @@ (Table[#, {Length@{##}}] & @@@ Split[v, #2 === "." &]) // Timing // First
f[_, y_] := y; f[x_, "."] := x; FoldList[f, First[v], Rest[v]] // Timing // First

0.2872

0.327

0.0936

However if the problem can be recast to packable data then a form that complies will be faster. I'll use zero to represent fields that should be filled.

v = {8, 3, 0, 1, 0, 0, 7, 0, 9, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 6};

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

{8, 3, 3, 1, 1, 1, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 2, 2, 2, 6}

SeedRandom[3]
v = Clip[RandomInteger[{-7, 9}, 350000], {1, ∞}, {0, 1}];

ClearAll[f];

f[_, y_] := y; f[x_, 0] := x; FoldList[f, First[v], Rest[v]]  // Timing // First
Rest @ FoldList[If[#2 == 0, ##] &, 0, v]                      // Timing // First

0.0936

0.0212

I like the compact and self-contained nature of this code as well.

Answer 4

Maybe there's a more efficient approach, but here's what I came up with:

data = {{"foo", "foo", "blah", "blah", "foo", "blah", "argh"},
        {"pfft", ".", ".", ".", ".", ".", "foo"},
        {"foo", ".", "foo", ".", "pfft", "blah", "."},
        {".", ".", "pfft", ".", ".", ".", "blah"},
        {".", "pfft", "blah", ".", ".", ".", "."},
        {"blah", ".", ".", ".", "argh", ".", "."},
        {"blah", "foo", "foo", "argh", ".", ".", "pfft"},
        {".", ".", "pfft", ".", "argh", ".", "."},
        {"foo", ".", "blah", ".", "argh", ".", "."},
        {"blah", "pfft", ".", "pfft", "foo", "argh", "."}};

fillblanks[list_, dummy_: "."] := 
    Flatten[ConstantArray[First[#], Length[#]] & /@ Split[list, StringMatchQ[#2, dummy] &]]

Transpose[fillblanks /@ Transpose[data]]

which yields

{{"foo", "foo", "blah", "blah", "foo", "blah", "argh"},
 {"pfft", "foo", "blah", "blah", "foo", "blah", "foo"},
 {"foo", "foo", "foo", "blah", "pfft", "blah", "foo"},
 {"foo", "foo", "pfft", "blah", "pfft", "blah", "blah"},
 {"foo", "pfft", "blah", "blah", "pfft", "blah", "blah"},
 {"blah", "pfft", "blah", "blah", "argh", "blah", "blah"},
 {"blah", "foo", "foo", "argh", "argh", "blah", "pfft"},
 {"blah", "foo", "pfft", "argh", "argh", "blah", "pfft"},
 {"foo", "foo", "blah", "argh", "argh", "blah", "pfft"},
 {"blah", "pfft", "blah", "pfft", "foo", "argh", "pfft"}}

Answer 5

Row by row:

Clear[datum];
SeedRandom[1];
datum[] := RandomInteger[{0, 9}];
tab = {RandomInteger[{0, 9}, 5]} ~Join~ RandomChoice[{8, 1} -> {".", x}, {9, 5}] /. x :> datum[]

filldown@tab

{{ 1,   4,   0,   7,   0},
 {".", ".", ".",  8,  "."},
 {".", ".", ".", ".",  5},
 {".", ".", ".", ".", "."},
 {".",  7,   6,  ".", "."},
 {".",  7,  ".", ".", "."},
 {".", ".",  0,  ".",  1},
 {".", ".", ".", ".", "."},
 {".", ".",  0,  ".", "."},
 {".", ".", ".", ".", "."}}

filldown = Module[{last = First[#]},
   Function[{row}, 
     last = ReplacePart[last, # -> Extract[row, #] & /@ Position[row, Except["."]]]] /@ #] &

{{1, 4, 0, 7, 0},
 {1, 4, 0, 8, 0},
 {1, 4, 0, 8, 5},
 {1, 4, 0, 8, 5},
 {1, 7, 6, 8, 5},
 {1, 7, 6, 8, 5},
 {1, 7, 0, 8, 1},
 {1, 7, 0, 8, 1},
 {1, 7, 0, 8, 1},
 {1, 7, 0, 8, 1}}

---

Down each column:

filldown2 = Transpose@Map[Module[{last = First[#]},
      Function[{entry}, last = entry /. "." -> last] /@ #] &, Transpose[#]] &

filldown2@tab

Same as above.

Answer 6

Caution: This answer is just for fun. ReplaceRepeated is constantly slow.

Using 0x4A4D's data:

#//.{pre___,a_,b:Longest["."..],post___}:>{pre,a,Sequence@@({b}/."."->a),post}&/@
  (data\[Transpose])\[Transpose]

Or,

Flatten[#//.{pre___,a_,b:Longest["."..],post___}:>{pre,a,{b}/."."->a,post}]&/@
  (data\[Transpose])\[Transpose]