13
$\begingroup$

Is there a way to directly build a list of elements that satisfy a certain property? More precisely, I am looking for a function IncludeIf (this is a placeholder name) that should work like Table but direcly drops all the unwanted elements. E.g.

IncludeIf[i, PrimePowerQ, {i, 1, 1000}]

should create a list of all prime powers among the numbers $\{1,...,1000\}$. The result should be the same as for

Select[Table[i, {i, 1, 1000}], PrimePowerQ]

but without the overhead of first creating a list of maybe far to many elements, and then dropping most of them.

A built-in-function would be preferred, but a work-around is welcome too.

$\endgroup$
11
$\begingroup$

You can use Do together with Reap-Sow:

Reap[Do[If[EvenQ[i], Sow[i]], {i, 100}]][[2, 1]] // Short
(*{2, 4, 6, 8, 10, <<40>>, 92, 94, 96, 98, 100}*)

EDIT

It is interesting to compare the Reap-Sow approach with the linked lists approach.

Reap-Sow approach:

ClearAll[ReapSow];
SetAttributes[ReapSow, HoldAll];
ReapSow[expr_, cond_, spec_] := Reap[
  Do[If[cond, Sow[expr]], spec]
][[2, 1]];

Linked lists approach

ClearAll[LinkedLists];
SetAttributes[LinkedLists, HoldAll];
LinkedLists[expr_, cond_, spec_] := CompoundExpression[
 $temp = f[],
 Do[
   If[cond, $temp = f[$temp, expr]],
   spec
  ],
  List @@ Flatten[$temp]
];

here I intentionally do not introduce local variables not to fool RepeatedTiming by, e.g. Module overhead.

Internal`Bag cheat:

ClearAll[ReapSowCompiled];
SetAttributes[ReapSowCompiled, HoldAll];
ReapSowCompiled[expr_, cond_, spec_] := Compile[
  {},
  Module[
   {bag = Internal`Bag[{0}]},
   Do[If[cond, Internal`StuffBag[bag, expr]], spec];
   Internal`BagPart[bag, All]
  ],
  CompilationTarget -> "C"
];
cf = ReapSowCompiled[i, EvenQ[i], {i, 10^4}];

Tests in a fresh kernel:

(*A fresh kernel*)
mem1 = MemoryInUse[];
a = ReapSow[i, EvenQ[i], {i, 10^4}]; // RepeatedTiming // First
MemoryInUse[] - mem1
(*0.01*)
(*58992*)

(*A fresh kernel*)
mem1 = MemoryInUse[];
b = LinkedLists[i, EvenQ[i], {i, 10^4}]; // RepeatedTiming // First
MemoryInUse[] - mem1
(*0.01*)
(*410696*)

(*A fresh kernel*)
mem1 = MemoryInUse[];
c = cf[] // Rest; // AbsoluteTiming// First
MemoryInUse[] - mem1
(*0.000326986*)
(*47184*)

So, a complex tree structure of pointers seems to involve a bigger memory overhead then an optimized Reap-Sow or Compiled cheat.

$\endgroup$
11
$\begingroup$

As compiled variant of Sow and Reap, you can use the undocumented Internal`Bag:

cf = Compile[{{n, _Integer}},
   Module[{bag = Internal`Bag[{0}]},
    Do[If[EvenQ[i], Internal`StuffBag[bag, i]], {i, n}];
    Internal`BagPart[bag, All]
    ],
    CompilationTarget -> "C"
   ];

n = 10000000;
a = Reap[Do[If[EvenQ[i], Sow[i]], {i, n}]][[2, 1]]; // AbsoluteTiming // First
b = Rest[cf[n]]; // AbsoluteTiming // First
a == b

5.39257

0.214701

True

$\endgroup$
  • $\begingroup$ I wonder, is there a specific advantage of using these undocumented "bags" instead of normal lists and AppendTo? Is there a difference in the grwoth behavior of lists and bags? Does Reap and Sow use bags internally? $\endgroup$ – M. Winter Sep 7 '18 at 11:54
  • 2
    $\begingroup$ @M.Winter, AppendTo will lead to quadratic complexity instead of linear, I would not recommend using AppendTo to build lists element-by-element. $\endgroup$ – Anton.Sakovich Sep 7 '18 at 12:01
  • 3
    $\begingroup$ @HenrikSchumacher cheater :) definitely +1. Maybe it is worth including a link to a SE question where Internal``Bag is explained in some more details, since it is undocumented functionality? Like this one mathematica.stackexchange.com/q/845/59438 $\endgroup$ – Anton.Sakovich Sep 7 '18 at 12:10
  • 1
    $\begingroup$ @M.Winter, in general, the idea is very simple: AppendTo makes a completely new expression and copies all elements form the original expression plus the new element, while Sow just marks an expression to be collected (filling some stack, I suppose), which are collected by Reap only once, at the end. Regarding Bags, I myself have discovered them only recently, I would recommend searching SE. SE can be called "The Documentation Centre for undocumented functions" :) $\endgroup$ – Anton.Sakovich Sep 7 '18 at 12:16
  • 1
    $\begingroup$ @M.Winter The main advantage of Bag is that it is compilable. Repeatedly appending to a list has quadratic complexity, but there are easy ways around this, e.g. using a linked list (which I can show you in another answer if you request it). However, these solutions are not Compileable, while Bag is. $\endgroup$ – Szabolcs Sep 7 '18 at 12:22

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.