Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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-

share|improve this question
4  
Is there an assumption that there are no "." in a first row? –  Kuba Jun 9 '13 at 19:51
    
To Kuba -- In my case all first row entries contain no ".". –  Keith Jun 9 '13 at 20:54
    
To All Respondees -your efforts are truly appreciated. Not only for their efficacy but for their pedagogical value as well. Thanks very much! –  Keith Jun 9 '13 at 20:56
    
One further question re Simon Wood's blazingly fast solution: is the function 'f' doubly defined? I don't understand the usage. Can anyone point me to description? -k- –  Keith Jun 9 '13 at 22:49
1  
@Keith Each definition matches a different pattern of input; together they define a single function. This tutorial may help. –  Michael E2 Jun 10 '13 at 2:38

6 Answers 6

up vote 24 down vote accepted

How about

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

fill[data_] := Transpose[FoldList[f, First[#], Rest[#]] & /@ Transpose[data]]
share|improve this answer
1  
+1. I think this one is going to be my favorite. –  Michael E2 Jun 9 '13 at 19:40
    
It is so fast :). +1 –  Kuba Jun 9 '13 at 21:49
    
Fold is such a natural solution to this problem -- I'm embarrassed I didn't think to try it. It works row-by-row, too, if f is Listable and the data contain no lists: fill[data_] := FoldList[f, First[data], Rest[data]]. –  Michael E2 Jun 9 '13 at 22:44
    
@MichaelE2, that's a neat alternative. –  Simon Woods Jun 10 '13 at 9:41
    
Just happened across this. Quite nice. My final attempt similar, you might get a chuckle from a prior (impractical, but kind of pretty in a way): FixedPoint[ ReplacePart[#, {r_, c_} /; (#[[r, c]] == ".") :> #[[r - 1, c]]] &, data] ... +1, of course! –  rasher May 2 at 6:11

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"}}
share|improve this answer

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.

share|improve this answer

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.

enter image description here enter image description here enter image description here

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);

enter image description here

share|improve this answer
    
I'm a bit heartened that my proposal is at least second best... :D –  J. M. Jun 10 '13 at 2:08
    
@0x4A4D I've thought mine would be :( but reference to data inside function have killed it :) –  Kuba Jun 10 '13 at 5:10
    
@0x4A4D I wasn't able to apply ParallelMap to Your solution, now Michael took Your place. Help me to improve the code :) –  Kuba Jun 10 '13 at 21:09

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]
share|improve this answer
    
I like everything based on patterns (+1) but it seems very slow for bigger tables :/ –  Kuba Jun 9 '13 at 21:50
    
@Kuba ReplaceRepeated is always VERY slow.. This is just an answer for fun :) –  Silvia Jun 9 '13 at 22:00
    
I suspected it was just for fun but I was not aware how slow it would be. :) Nevertheless I still like it :) –  Kuba Jun 9 '13 at 22:27
1  
@Kuba Be careful! ReplaceRepeated is a honey trap! :) –  Silvia Jun 9 '13 at 22:44
    
@Michael -- Thank you for your reference to other material. –  Keith Jun 10 '13 at 11:55

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.

share|improve this answer
2  
I love the use of ## in the If statement! –  Simon Woods Jun 10 '13 at 9:32
    
@Simon Thanks. :-) –  Mr.Wizard Jun 10 '13 at 10:30
    
I have analyzed difference between those two questions, please take a look. –  Kuba Jun 10 '13 at 21:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.