4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Take a look at SparseArray $\endgroup$ – Lukas Lang Jun 18 '18 at 22:00
  • 4
    $\begingroup$ 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. $\endgroup$ – MarcoB Jun 18 '18 at 22:18
  • $\begingroup$ @MarcoB Thank you for this quick fix! $\endgroup$ – Leuven Jun 18 '18 at 22:33
  • 4
    $\begingroup$ As @LukasLang already mentioned, SparseArray does a good job here: SparseArray[positions -> 1, {dimx, dimy}, 0] $\endgroup$ – Henrik Schumacher Jun 18 '18 at 23:03
  • $\begingroup$ @LukasLang and HenrikSchumacher Thank you, your solution instantly does exactly what I needed, so my problem is solved! $\endgroup$ – Leuven Jun 18 '18 at 23:24
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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]. $\endgroup$ – Szabolcs Jun 19 '18 at 15:47
  • $\begingroup$ @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. $\endgroup$ – Daniel Lichtblau Jun 19 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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