3
$\begingroup$

To optimize a brute force algorithm on graphs I want to compile dynamically a list of functions for a list of graphs.
(The representation I'm using for a graph is a list of pairs of integers: integers are nodes, pairs are edges.)

To create one function I need:

  • the graph representation
  • a displacement list.

displacement is constant between all the functions of graphs with $n$ nodes, but since my program operates on various $n$ and also because I don't know displacement in advance and I will actually evaluate it, I'd like to pass displacement too as a parameter for my "pure compilator function".

Here's an example of one single graph and its relative compiled function

displacement = {1, 2, 4, 8, 13, 21, 31};
graph = {{1, 2}, {2, 3}, {2, 4}};

tergetFun = Compile[{{a, _Integer, 1}}, With[{p = {1, 2, 4, 8, 13, 21, 31}}, {p[[a[[1]]]] + p[[a[[2]]]], p[[a[[2]]]] + p[[a[[3]]]], p[[a[[2]]]] + p[[a[[4]]]]}]];

It's not hard to dynamically generate the expression for the function

(p[[a[[#1]]]] + p[[a[[#2]]]]) & @@@ graph
Part::partd: Part specification a[[1]] is longer than depth of object.
Part::pkspec1: The expression a[[1]] cannot be used as a part specification.
Part::partd: Part specification a[[2]] is longer than depth of object.
(* the entire list of errors *)
(* {p[[a[[1]]]] + p[[a[[2]]]], p[[a[[2]]]] + p[[a[[3]]]], p[[a[[2]]]] + p[[a[[4]]]]} *)

Done in this way Mathematica attempts to evaluate Part, failing. Nonetheless the output is exactly the one I need.
I've tried any kind of evaluation control but this most direct and wrong(?) way of doing it is the only one actually working when I use it as argument in Compile

Compile[{{a, _Integer, 1}}, With[{p = #1}, #2]] & @@ {#1, ((p[[a[[#1]]]] + p[[a[[#2]]]]) & @@@ #2)} & @@ {displacement, graph}
(* list of errors *)
(* targetFun *)

Should I use Quiet or some form of evaluation control actually works?

$\endgroup$

1 Answer 1

5
$\begingroup$

Just use Compile`GetElement or Indexed instead of Part:

part = Compile`GetElement;
With[{p = #1}, Compile[{{a, _Integer, 1}},
       #2
       ]
      ] & @@ {#1, ((
         part[p, part[a, #1]] +part[p, part[a, #2]]
         ) & @@@ #2)
     } & @@ {displacement, graph}

But I do not see any reason why you want to recompile the function that many times when you can simply use this:

cf = With[{part = Compile`GetElement},
   Compile[{{a, _Integer, 1}, {p, _Integer, 1}, {edges, _Integer, 2}},
    Table[
     part[p, part[a, part[edges, k, 1]]] + part[p, part[a, part[edges, k, 2]]],
     {k, 1, Length[edges]}
     ],
    CompilationTarget -> "C",
    RuntimeAttributes -> {Listable},
    Parallelization -> True,
    RuntimeOptions -> "Speed"
    ]
   ];

and call it by cf[a, displacement, graph]. If you have a list of many a, then you can call this in a listable and parallelized way as follows:

displacement = {1, 2, 4, 8, 13, 21, 31};
graph = {{1, 2}, {2, 3}, {2, 4}};
n = 10;
alist = Permutations@Range@n;
result = cf[alist, displacement, graph];

This maybe copies displacement and graph to every thread, but it does certainly not make Length[alist] copies of them.

$\endgroup$
6
  • $\begingroup$ Thanks! Where I could have found documentations of Compile`GetElement? By the way I recompile the function many times because I use it in a brute force search where I map it on a Permutation@Range@n list (So the function is listable and parallelizable)... Passing to the function this many time a constant displacement and a constant graph wouldn't be detrimental to speed? (Also I don't know how to make this general version listable) $\endgroup$ Commented Feb 16, 2022 at 18:20
  • $\begingroup$ Compiling an array is certainly more expensive than passing the array as an argument... $\endgroup$ Commented Feb 16, 2022 at 18:23
  • 1
    $\begingroup$ And no, Compile`GetElement is undocumented. You have to look around on this site to find more details about it. $\endgroup$ Commented Feb 16, 2022 at 18:28
  • 1
    $\begingroup$ You're right on your second point, I had give up on making a CompilationTarget -> "C" for each graph I had, because looking at the improvement it seemed it wasn't worth the extra time of compilation. Now this meta-function is clearly faster than one specific non- CompilationTarget -> "C" function and at keeps pace with a specific CompilationTarget -> "C" one, thanks $\endgroup$ Commented Feb 16, 2022 at 18:45
  • 1
    $\begingroup$ Have also a look at this: https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others Generating the permutations one at the time might save you shoving around a lot of memory. $\endgroup$ Commented Feb 16, 2022 at 18:48

Your Answer

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

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