# Performance issue using MemberQ inside Table

I have a list of positions that I would like to use in an array. I came up with the following code to fill a Table with 'ones' in these positions, and 'zeros' everywhere else:

positions = RandomInteger[{1, 200}, {2000, 2}];
array = Table[If[MemberQ[positions, {i, j}], 1, 0], {i, 1, 200}, {j, 1, 200}];


Maybe this is not the most efficient way to solve this, but it works fast enough for me (around 0.15 seconds).

My problem arose when I assigned the table dimensions in an earlier statement:

dimx = 200;
dimy = 200;
array = Table[If[MemberQ[positions, {i, j}], 1, 0], {i, 1, dimx}, {j, 1, dimy}];


The code above takes around 22 seconds to execute on my machine, while the only change is that I put dimx and dimy as table dimensions, instead of 200 directly.

I was hoping someone could explain to me why this is happening and if there is a way to solve this.

• Take a look at SparseArray Jun 18, 2018 at 22:00
• To answer the second part of your question, you can force evaluation of the table iterators, i.e. Evaluate@{i, 1, dimx}, Evaluate@{j, 1, dimy}. This will bring the timing in the second piece of code in line with the first. I vaguely suspect that this might have something to do with autocompilation within Table; autocompilation may be triggered when Table, which is a HoldAll function, can "see" the explicit size of the array being produced, but not when the size is "hidden" within the symbols dimx and dimy. Unfortunately I am unable to go into more detail right this moment. Jun 18, 2018 at 22:18
• @MarcoB Thank you for this quick fix! Jun 18, 2018 at 22:33
• As @LukasLang already mentioned, SparseArray does a good job here: SparseArray[positions -> 1, {dimx, dimy}, 0] Jun 18, 2018 at 23:03
• @LukasLang and HenrikSchumacher Thank you, your solution instantly does exactly what I needed, so my problem is solved! Jun 18, 2018 at 23:24

Others have indicated how to redress this but I will point out that one can improve on the MemberQ speed here. The idea is to create a lookup table for the positions of interest, using pattern-free down values. This is fast to create:

positions = RandomInteger[{1, 200}, {2000, 2}];
AbsoluteTiming[Scan[(presentQ[#] = True) &, positions];]

(* Out[44]= {0.005684, Null} *)


And the run time is quite good:

dimx = 200;
dimy = 200;
AbsoluteTiming[
array = Table[
If[MemberQ[positions, {i, j}], 1, 0], {i, 1, dimx}, {j, 1, dimy}];]
AbsoluteTiming[
array2 = Table[
If[TrueQ[presentQ[{i, j}]], 1, 0], {i, 1, dimx}, {j, 1, dimy}];]
array === array2

(* Out[55]= {13.410903, Null}

Out[56]= {0.033746, Null}

Out[57]= True *)


One can also get good efficiency using Dispatch.

AbsoluteTiming[repRules = Dispatch[Thread[positions -> 1]];]

(* Out[62]= {0.002518, Null} *)

AbsoluteTiming[
array3 = Table[{i, j}, {i, 1, dimx}, {j, 1, dimy}] /.
repRules /. {i_Integer, j_Integer} -> 0;]
array3 === array2

(* Out[63]= {0.057041, Null}

Out[64]= True *)


Another possibility, which I did not try, would use Association with the elements in positions as keys.

• "And the run time is quite good". I made a custom set data structure for integers with LibraryLink, with a "memberQ" operation. Pattern-free downvalues are actually faster when testing membership one-by-one. (Of course, for batch testing, the C++ solution will be faster.) Association could be even better because it can do batch processing with Lookup directly in Mathematica, e.g. at = AssociationThread[members -> True] then Lookup[at, elements, False]. Jun 19, 2018 at 15:47
• @Szabolcs One possibility for testing a set quickly is to use Nearest (create if on positions, run the NearestFunction on the full array). Replace exact hits with 1 and all else with 0. Your Association/LookUp method might be better though. Jun 19, 2018 at 16:08