How to generate a list from an iterator and some arbitrary function

Question

Suppose I'd like to generate a table of integers:

Table[i, {i, 10}]

Great; now suppose I want only the integers that are even

Select[Table[i, {i, 10}], EvenQ]

This is fine for small things, but if I'd like to iterate over say $2^{n}$ things, only maybe $n$ of which will satisfy the predicate, it's a pretty terrible way to do it.

Is there some good idiomatic way to do it? I could use a Do loop (I guess with Appending?) but there must be a better way, right?

Answer 1

I am assuming that EvenQ is merely an example; clearly if you can generate these values directly, e.g. Range[2, 20, 2] that will always be preferable.

You can do this reasonably efficiently in terms of both syntax and memory by using Sow and Reap:

test = Divisible[#, 1*^6] &;

Reap[Do[If[test @ i, Sow @ i], {i, 1*^6}]][[2, 1]]

(* Out= *)
{1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000, 9000000, 10000000}

Note that only a small amount of memory is used, unlike the Table and Select method:

MaxMemoryUsed[]

15467904

If you need greater performance you might make use of a block-based approach as I did for Iterate until condition is met, e.g.

block = 100000;

Join @@ Table[Select[Range[n block + 1, (n + 1) block], test], {n, 0, 99}]

(* Out= *)
{1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000, 9000000, 10000000}

This a bit faster than the first method on my system.

Answer 2

I would certainly recommend against using Append for this task, as this is a very inefficient way to go.

One alternative would be to use Fold to build up a highly nested list and then Flatten at the very end, like this:

testdata = Range[10000];
Fold[If[Random[] < 0.2, {#1, #2}, #1] &, {}, testdata] // Flatten

Of course you would change the first argument of the If statement to whatever your real predicate is. Timing on my nearly four-year-old MacBook Pro is about 0.02 seconds for 10000 integers.