# 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 ...) –  Noon Silk 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. –  Noon Silk 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? –  Mr.Wizard 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. –  Verbeia 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). –  Mr.Wizard Mar 24 '13 at 1:26
You weren't being a jerk, don't worry. –  Verbeia Mar 24 '13 at 10:30