5
$\begingroup$

How is the function DeleteCases compilable if Compile does not support patterns?

My question refers to this thread here where I want to use an If[] statement without the third argument required. Since my output of the If[] statement within compile always gives a positive real number, I'd like to get rid of the numbers which I invoke with a negative third argument in the If[] statement (the third arguments seems to be necessary so that the If[] statement is compiled at all).

Maybe there now might be even a better solution than this workaround provided by @Mr.Wizard but I do not really understand his suggestion (or is it meant to use DeleteCases outside of Compile?).

$\endgroup$
  • 6
    $\begingroup$ Only a restricted set of forms is supported in Compile. You can e.g. DeleteCases[list, 123]. I think only literal values can be used as the second argument. $\endgroup$ – Szabolcs Nov 21 '18 at 11:03
  • $\begingroup$ Yes, thank you for pointing it out. I think that is what I encountered here. So it is not usable for my purpose, unfortunately. But I like Henrik's way of avoiding this problem in the first place. $\endgroup$ – Display Name Nov 21 '18 at 15:29
9
$\begingroup$

In code for Compile, it might be a better idea not to delete bad cases but to collect only the good ones with Internal`Bag.

If you have a certain but reasonably sized upper bound for the number od items to collect, you can also employ this less expensive way, using a packed array instead of a expandable data structure such as Internal`Bag:

First, preallocate an array a of sufficient size and a counter c, initialized by 0. Then fill the array in a Do or While loop: Each time your If statement evaluates to True, increase the counter c and write the "good" item into a[[c]]. After having collected all items, truncate the array with a[[1;;c]].

Example

Here are two functions that search the first n positive integers for multiples of 3 or 5:

Internal`Bag-based version (using the Most[{0}] hack to initiaize with an empty bag capable of collecting for integers):

cfBag = Compile[{{n, _Integer}},
   Block[{bag},
    bag = Internal`Bag[Most[{0}]];

    Do[
     If[Mod[i, 3] == 0 || Mod[i, 5] == 0,
      Internal`StuffBag[bag, i];
      ],
     {i, 1, n}];
    Internal`BagPart[bag, All]
    ],
   CompilationTarget -> "C"
   ];

And here is the array-based version:

cfArray = Compile[{{n, _Integer}},
   Block[{a, c = 0},
    a = Table[0, {n}];
    c = 0;
    Do[
     If[Mod[i, 3] == 0 || Mod[i, 5] == 0,
      c++;
      a[[c]] = i;
      ],
     {i, 1, n}];
    If[c > 0, a[[1 ;; c]], {}]
    ],
   CompilationTarget -> "C"
   ];

Comparison:

r1 = cfBag[10000000]; // RepeatedTiming // First
r2 = cfArray[10000000]; // RepeatedTiming // First
r1 == r2

0.288

0.313

True

To my own surprise, Internal`Bag is faster. Probably because the task is memory bound and because a is much larger than needed in the end (so, too much memory allocation and a potentially superfluous copy operation in the end). The reason seems to be that a call like a[[c]] = i; always checks whether c is within the bounds of a. Deactivating that with RuntimeOptions -> "Speed" makes the two methods equally fast.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Can you maybe provide me with a minimal working example to see how that works out in practice? I only superficially read sth about InternalBag` so far, but it sounded interesting to me. $\endgroup$ – Display Name Nov 21 '18 at 12:03
  • $\begingroup$ Thank you very much. I will take a look at it as soon as I can :) $\endgroup$ – Display Name Nov 21 '18 at 13:17
  • 1
    $\begingroup$ For some reason the example code with Internal`Bag always seems to be slightly faster than the array based solution. Even with the specification of RuntimeOptions->"Speed". At least on my machine. The difference is about 17% of time. $\endgroup$ – Display Name Nov 21 '18 at 15:23
  • 1
    $\begingroup$ Yes, sry I thought that minor question isn't worth a new question. I also figured out my mistake with the help of your comment. I sloppily used Compiled`GetElement in the a[[c]] += 1 step, instead of using Part. I guess there is no equivalent to Compiled`GetElement for writing operations. As the name suggests Compiled`GetElement can of course only be used for read operations. $\endgroup$ – Display Name Nov 22 '18 at 13:18
  • 1
    $\begingroup$ Just need to be careful when you use the With construct and replace everything with part=Compile`GetElement as you once suggested to me and then not remember the difference between part and Part :D $\endgroup$ – Display Name Nov 22 '18 at 13:34

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.