3
$\begingroup$

I defined a function

getCell[sp_, i_, j_, x_] := Block[{target, n, m, k, l, k2, l2, cells},
  n = Dimensions[sp][[1]];
  m = Dimensions[sp][[2]];
  cells = {};
  Do[
   Do[
    (* This is one neighbor *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
     AppendTo[cells, {k2, l2}]],
    {l, -1, 1}],
   {k, -1, 1}];
  If[Dimensions[cells][[1]] != 0,
   target = RandomSample[cells, 1][[1]],
   (* The default, if none was found, is to return the cell itself, 
   just for convenience *)
   target = {i, j}
   ];
  Return[target];
  ]

getCell given a square matrix sp filled with Integers attempts to find a cell neighboring [[i,j]] that contains a value equal to x. If it finds such a cell, it returns the coordinates of that cell; if not, it returns the input coordinates {i,j}.

I now wanted to compile getCell to try to speed it up, but when I do so by putting Compile around the function and inserting type definitions, I get several error messages:

Compile::cset: Variable cells of type {_Integer,1} encountered in assignment of type {_Integer,2}. >>

Compile::cpts: The result after evaluating Insert[cells,{k2,l2},-1] should be a tensor. Nontensor lists are not supported at present; evaluation will proceed with the uncompiled function. >>

Compile::cset: Variable target of type {_Integer,2} encountered in assignment of type {_Integer,0}. >>

Compile::cset: Variable target of type {_Integer,2} encountered in assignment of type {_Integer,1}. >>

Does anyone know what I might be doing wrong, and how I could get this simple function compiled?

$\endgroup$
2
  • 1
    $\begingroup$ What code are you feeding to Compile? $\endgroup$ Nov 16, 2012 at 20:47
  • 1
    $\begingroup$ Tom, you substantially changed the question after it was answered: please don't do that! Feel free to follow up with a new question in a new thread. Consult our faq for more guidance. $\endgroup$
    – whuber
    Nov 16, 2012 at 23:16

1 Answer 1

14
$\begingroup$

Note: instead of picking random element I just pick the first it runs into, random version at the end

getCell = 
 Compile[{{sp, _Integer, 2}, {i, _Integer}, {j, _Integer}, {x, _Integer}}, 
  Block[{ n, m, k2, l2, cell},

   {n, m} = Dimensions[sp];
   cell = {i, j};
   Do[(*This is the neighborhood *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, cell = {k2, l2}; 
     Break[]]
    , {l, -1, 1}, {k, -1, 1}];
   cell
   ]]

When you get that type of errors about tensor sizes not matching think about what shapes your data has and if Mathematica knows about it. If it's not an argument that you need to specify shape of you can do that by putting the specification as the last Compile argument, see the docs for details.

Often the easiest is to explicitly assign the variable a value(see below)

What I changed:

  • Explicitly added {sp,_Integer,2} so Mathematica knows what it is. This is the one that matters.
  • Merged the Do loops into one
  • Removed k and l from Block variables since Do localizes them automatically
  • Assigned {m,n} simultaneously
  • There is no need to explicitly state Return what the last function returned gets returned (unless it is suppressed with a ; in which case it gives Null

An example, finding neighboring 0:

m = 5;
r = RandomInteger[{0, 1}, {m, m}];
pos = RandomInteger[{1, m}, 2];
cell = getCell[r, pos[[1]], pos[[2]], 0];

s = Grid[r, 
  ItemStyle -> {Automatic, Automatic, {pos -> Red, cell -> Blue}}]

Output grid

To actually get a random one you can make sure that cells is treated correctly by initializing as a nx2 value:

getCell = 
 Compile[{{sp, _Integer, 2}, {i, _Integer}, {j, _Integer}, {x, _Integer}}, 
  Block[{n, m, k2, l2, cells},

   {n, m} = Dimensions[sp];

   cells = {{i, j}};

   Do[(*This is the neighborhood *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
     AppendTo[cells, {k2, l2}]]
    , {l, -1, 1}, {k, -1, 1}];

   If[Length[cells] == 1, {i, j}, RandomChoice[Rest[cells]]]
   ]] 

Here I do that by just starting with {i,j} in it and appending the positions it finds, at the end I pick randomly out of everything but the first value.

Since you are compiling it in the first place I guess you will be running the function a lot and want speed, there are some easy ways to get a nice speedup, the first is compiling to C and the second is to make the function listable.

Say for a given matrix you want to find the nearest 0 neighbor for a list of positions.

getCellListableC = 
  Compile[{{sp, _Integer, 2}, {pos, _Integer, 1}, {x, _Integer}}, 
   Block[{n, m, k2, l2, cells, i, j},

    {n, m} = Dimensions[sp];
    {i, j} = pos;
    cells = {{i, j}};

    Do[(*This is the neighborhood *)
     k2 = Mod[i + k, n, 1];
     l2 = Mod[j + l, m, 1];
     If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
      AppendTo[cells, {k2, l2}]]
     , {l, -1, 1}, {k, -1, 1}];

    If[Length[cells] == 1, {i, j}, RandomChoice[Rest[cells]]]
    ],
   CompilationTarget -> "C",
   RuntimeOptions -> "Speed",
   RuntimeAttributes -> Listable];

m = 5000;
n = 1000;
r = RandomInteger[{0, 2}, {m, m}];
pos = RandomInteger[{1, m}, {n, 2}];

(* Functions i compare to are as the ones above with different Compile options *)
(* Compiled, but not CompilationTarget->"C" *)
AbsoluteTiming[getCell[r, #[[1]], #[[2]], 0] & /@ r;]
(* {0.085699, Null} *)

AbsoluteTiming[getCellC[r, #[[1]], #[[2]], 0] & /@ r;]
(* {0.077503, Null} *)

(* Take advantage of Listability *)
AbsoluteTiming[getCellListable[r, pos, 0];]
(* {0.008890, Null} *)

AbsoluteTiming[getCellListableC[r, pos, 0];]
(* {0.004517, Null} *)

Note especially how Listable improves speed.

Another thing is to always look at after compiling is:

<< CompiledFunctionTools`
CompilePrint[getCellListableC]

If you see MainEvaluate that means that part isn't compiled, and figure out how to avoid that. Another thing is CopyTensor wherever that occurs a list is copied, you will see that in this code due to the Append (among others).

$\endgroup$
5
  • $\begingroup$ Thanks so much for this! That's great! I'm new to Compiling functions, so sorry for asking this probably rather trivial question... $\endgroup$ Nov 16, 2012 at 21:08
  • $\begingroup$ @TomWenseleers I find that making sure Mathematica knows the shape of all variables can be quite non-trivial, but usually worth it to get a factor 10-100 faster code :) $\endgroup$
    – ssch
    Nov 16, 2012 at 21:44
  • $\begingroup$ @TomWenseleers I added a few other things that I think is good to know about when getting started with Compile $\endgroup$
    – ssch
    Nov 16, 2012 at 22:25
  • 2
    $\begingroup$ Good answer (+1), but just thought I ought to point out that Internal`Bag is highly preferable to AppendTo whenever the $O(n^2)$ behaviour of the latter might represent a performance issue. $\endgroup$ Nov 16, 2012 at 22:32
  • $\begingroup$ Ha that's really great - that's already quite a speed increase! But indeed very tricky to properly tell Mathematica what variable types you are using. $\endgroup$ Nov 16, 2012 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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