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?

  • $\begingroup$ You could use Sow[]/Reap[] with Do[]; e.g. Reap[Do[If[EvenQ[k], Sow[k]], {k, 10}]][[-1, 1]]. $\endgroup$ – J. M.'s torpor Mar 23 '13 at 13:13
  • $\begingroup$ 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 ...) $\endgroup$ – Noon Silk Mar 23 '13 at 13:27
  • 1
    $\begingroup$ It's Scylla and Charybdis, I think: you could have it fast, but at the expense of memory, or memory-conserving, but rather slow... $\endgroup$ – J. M.'s torpor Mar 23 '13 at 13:29
  • $\begingroup$ 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! $\endgroup$ – J. M.'s torpor Mar 23 '13 at 13:32
  • 1
    $\begingroup$ Can you maybe include you actual problem? As I said, there might be structure in your problem that can allow a different solution... $\endgroup$ – J. M.'s torpor 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:


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.

  • $\begingroup$ Thanks; I think your block approach is turning out to be perhaps what I'm after. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Mr.Wizard Mar 23 '13 at 23:36
  • $\begingroup$ Fair enough - I was responding to the "alternatives to Append" element to the question. Your answer is clearly better, but mine is simpler. $\endgroup$ – Verbeia Mar 24 '13 at 1:16
  • $\begingroup$ Sorry, I didn't mean to be a jerk; I really figured I was missing something (I often am). $\endgroup$ – Mr.Wizard Mar 24 '13 at 1:26
  • $\begingroup$ You weren't being a jerk, don't worry. $\endgroup$ – Verbeia Mar 24 '13 at 10:30

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.