Compile `DeleteCases`

Question

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?).

Answer 1

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.