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

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?

• You could use Sow[]/Reap[] with Do[]; e.g. Reap[Do[If[EvenQ[k], Sow[k]], {k, 10}]][[-1, 1]]. Mar 23 '13 at 13:13
• Yeah; that's basically what I had in mind. Interestingly, it doesn't appear to be particularly fast (though at least it probably doesn't waste memory like the Select option would do ...) Mar 23 '13 at 13:27
• It's Scylla and Charybdis, I think: you could have it fast, but at the expense of memory, or memory-conserving, but rather slow... Mar 23 '13 at 13:29
• Of course, sometimes problems have a pattern/structure that allow you to do these things more cleverly. In this simple case, you could do Table[2 i, {i, 1, 5}] or Table[i, {i, 2, 10, 2}] for instance; so, exploit patterns when you can! Mar 23 '13 at 13:32
• Can you maybe include you actual problem? As I said, there might be structure in your problem that can allow a different solution... Mar 23 '13 at 13:35

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.

• Thanks; I think your block approach is turning out to be perhaps what I'm after. Mar 24 '13 at 1:07

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.

• I don't understand this answer. Is this supposed to be faster than Select? On my system at least it is slower. It also does not save memory over Select that I can see. What am I missing? Mar 23 '13 at 23:36
• Fair enough - I was responding to the "alternatives to Append" element to the question. Your answer is clearly better, but mine is simpler. Mar 24 '13 at 1:16
• Sorry, I didn't mean to be a jerk; I really figured I was missing something (I often am). Mar 24 '13 at 1:26
• You weren't being a jerk, don't worry. Mar 24 '13 at 10:30