# Most efficient searching algorithm in a table

I am completely new in Mathematica (and in data analysis in general) and I find it really useful, although I still do not use it properly.

I have the following question related to data manipulation: I have a huge table (115 * 100000), and I want to make queries of the type "look for the row in TABLE such that its column number 1 has the value 0.124, column number 3 has the value 45345.5 etc.. (if it helps, the row verifying such a conditions is unique). So far, I am doing it through Select in the following way:

Select[TABLE, #[[1]] == value1 && #[[3]] == value2 &]

I suspect that there is a faster way to do it, is it correct?

Thanks!

• If the row is unique you can use SelectFirst to stop looking after you've found the row. – C. E. Dec 5 '14 at 16:27
• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – user9660 Dec 5 '14 at 16:33
• Note that using Select can be slow relative to pattern matching with Cases, however since you are using == to match a specific "Real" number, you should read this thread regarding the difference between exact and approximate numbers. ( mathematica.stackexchange.com/questions/18393/… ). When trying to select Real numbers it's often better to look for the difference. (i.e. Select[MyTable, Chop[#[[1]]-value1) == 0 && Chop[#[[3]]-value2] == 0 &] ) – rivercfd Dec 5 '14 at 17:12
• There are many ways to do this. That said, yours is fine. Whether others might be faster can only be determined by testing. Also this might depend on specifics of the table, such as whether or not it is a packed array of numbers. Given the uniqueness specification, the advice of @Pickett to use SelectFirst is also a good idea (though the improvement might not be huge, it's always good to bail out as soon as possible). – Daniel Lichtblau Dec 5 '14 at 18:36
• Related: (8364804) – Mr.Wizard Dec 6 '14 at 14:38

I think the SelectFirst approach is probably one of the easiest to read but just for fun here are a couple of other solutions. I'll start by generating a sample table t0.

t0 = RandomReal[{0, 1}, {10^5, 151}];
r0 = t0[[50000]];

Applying your method with Select is pretty fast. (Note that SelectFirst is faster for the unique case proportional to the position of the found row in the data so about 2x in this case). I've chosen vanilla Select for generality.

AbsoluteTiming[x1 = Select[t0, (#[[1]] == r0[[1]] && #[[3]] == r0[[3]]) &];]

(*{0.265200, Null}*)

Now I define a new function pickRow that does some trickery to create a mask for picking the proper row(s). Chopping, as suggested by @rivercfd is a good idea since equal tolerances can lead to issues when testing for machine numbers. The Unitize converts all non-zero values to 1 and leaves zero 0. Thus, when I total, there are zeros in the positions of the found rows.

pickRow[data_, index_, values_] :=
Pick[data,
Total[Unitize[Chop[Transpose[data[[All, index]]] - values]]], 0]

AbsoluteTiming[x2 = pickRow[t0, {1, 3}, r0[[{1, 3}]]];]

(* {0.062400, Null} *)

And of course if you can compile it is often worth trying for a speedup. I abandon Pick here because it is not among the list of compilable functions.

pickRowC =
Compile[{{data, _Real, 2}, {index, _Integer, 1}, {values, _Real, 1}},
mask = Total[Unitize[Chop[Transpose[data[[All, index]]] - values]]];
]
];

AbsoluteTiming[x3 = pickRowC[t0, {1, 3}, r0[[{1, 3}]]];]

(* {0.015600, Null} *)

x1 == x2 == x3

(* True *)

The real benefits shine through when we scale the problem up. (Warning: I have 32GB ram so generating a matrix with 10^9 elements is no trouble for me but it might bring your machine down)

t = RandomReal[{0, 1}, {10^6, 1000}];
r = t[[500000]];

AbsoluteTiming[
x1 = Select[
t, (#[[1]] == r[[1]] && #[[3]] == r[[3]] && #[[200]] ==
r[[200]] && #[[888]] == r[[888]]) &];]

(* {8.174414, Null} *)

AbsoluteTiming[
x2 = pickRow[t, {1, 3, 200, 888}, r[[{1, 3, 200, 888}]]];]

(* {1.575603, Null} *)

AbsoluteTiming[
x3 = pickRowC[t, {1, 3, 200, 888}, r[[{1, 3, 200, 888}]]];]

(* {0.140400, Null} *)

x1 == x2 == x3

(* True *)

At the request of @Aisamu here are the timings of the same operation using an algorithm with Cases.

patt =
ReplacePart[ConstantArray[HoldPattern@_, #[[1]]],
Thread[#[[2]] -> #[[3]]]] &@({Length@#, {1, 3, 200,
888}, #[[{1, 3, 200, 888}]]}) &@r; AbsoluteTiming[
x4 = Cases[t, patt];]

(* {9.859217, Null} *)

x1 == x2 == x3 == x4

(* True *)

NOTE

I did some further testing on SelectFirst with my later large data set thinking I might be unfair in my comparison since I picked a value in the middle. What I found surprised me, by setting r to t[[1]] I expected SelectFirst to bail out very quickly but instead it took around 10 seconds to complete. I think this happens because Select unpacks the packed table and with very large data this is time consuming.

• You were right about bringing my machine down... Could you add this to your $10^9$ test? patt = ReplacePart[ConstantArray[HoldPattern@_, #[[1]]], Thread[ #[[2]] -> #[[3]]]] &@({Length@#, {1, 3}, #[[{1, 3}]]}) &@r0; AbsoluteTiming[x4 = Cases[t0, patt];] – Aisamu Dec 6 '14 at 13:57
• You could earn a little bit of time by not extracting r0[[1]] and r0[[3]] every time. There's also this approach to try t0[[t0[[All, {1, 3}]]~FirstPosition~{r0[[1]], r0[[3]]}]]] – Rojo Dec 6 '14 at 14:40
• That was really helpful and instructive! Thanks a lot! – Vazquez Dec 6 '14 at 14:53
• @Rojo that is a very clean and fast solution (though not quite as fast as the compiled function). I didn't even know about FirstPosition so thanks for that! It is worth noting that for machine reals this looks for exact equal, even adding \$MachineEpsilon will cause it to return Missing["NotFound"]. – Andy Ross Dec 7 '14 at 22:25