2
$\begingroup$

I'm working on a code that runs many (easy) operations on combinations (subsets) of different size (6, 7, 8, 9) taken from a big set of numbers (normally more that 40). So, this means the code has to manage billions of lists. For example a typical case is Subsets[Range[48],{6}], which has Binomial[48, 6] = 12271512 possible subsets.

I guess Compile can help me to speed some parts up, but I have very poor experience with compilation in Mathematica. Here is the question: in a test I have done, the code includes the Subsets[] function and it's compiled but taking a look at the printed compiled function (CompilePrint) I discovered a MainEvaluate wrapper for Subsets. Indeed, running the compiled code I get the message "...proceeding with uncompiled evaluation" Being Subsets not included in the list of "compilable" functions, I would ask if there is any alternative. For instance, is there a fast way to generate subsets with a Map or something else that can be written into the compiled function? Any help is appreciated.

Note: before to think about Compile, as a first attempt, I tried to use ToPackedArray to reduce the amount of needed memory (and speed the runs up), but the functions I call somehow destroy the packed array and, at the end of the computation, I find unpacked arrays. So, I guess there is no advantage to convert inputs in PackedArray. However, any suggestion/help is welcome for this point too. Thanks in advance

EDIT Here is a small excerpt from my code. Here the result has "only" 13650 6-tuples.

IN = Range[20];
A = {1, 2, 3, 4, 5};
Map[Flatten[Outer[Join, {#}, Subsets[Complement[IN, A], {4}], 1], 1]&, Subsets[A, {2}]]

A first try is to compile the function

Outer[Join, {#}, Subsets[Complement[IN, A], {4}], 1], 1]
$\endgroup$
  • 1
    $\begingroup$ You are much more likely to get a response with some short example code that demonstrates what you are trying to do. $\endgroup$ – Andy Ross Nov 24 '14 at 0:36
  • $\begingroup$ Thanks @AndyRoss I added an example. $\endgroup$ – bobknight Nov 24 '14 at 5:59
  • $\begingroup$ Subsets isn't in this list, so Compile isn't likely to speed up your code. In fact, according to my personal experience, though usually not slowing down, even those compilable list-manipulating functions won't benefit from Compile, the reason might be that as an important part of Mathematica core language, most list-manipulating functions have been highly optimized that they can hardly benefit from Compilation. (Join and Complement is compilable, you can try to Compile them and see if the code speeds up.) $\endgroup$ – xzczd Dec 11 '14 at 12:35
  • $\begingroup$ BTW, what creates the unpacked array is actually Outer, so I'm afraid unpacked array is also unavoidable. $\endgroup$ – xzczd Dec 11 '14 at 12:35
  • $\begingroup$ thanks a lot for the comments. Yes, I agree that if a function is not in the list of compiler functions it's useful to force the compilation, the kernel will always run the not compiled code. However, I'm thinking to write my own Subsets function. $\endgroup$ – bobknight Dec 11 '14 at 15:37

Your Answer

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

Browse other questions tagged or ask your own question.