Yield in Mathematica

Question

Can you do something like Python's yield statement in Mathematica, in order to create generators? See e.g. here for the concept.

Update Here's an example of what I mean, to iterate over all permutations, using only O(n) space: (algorithm as in Sedgewick's Algorithms book):

gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit},
  visit[k_] := Module[{t},
    id++; If[k != 0, val[[k]] = id];
    If[id == n, f[val]];
    Do[If[val[[t]] == Null, visit[t]], {t, 1, n}];
    id--; val[[k]] = Null;];
  visit[0];
  ]

Then call it it like:

gen[Print,3], printing all 6 permutations of length 3.

FWIW, Python's way of doing iterators / generators is rather unusual. As long as you have some sort of abstraction over state (closures, classes), you can implement them in any langauge. — jrockway, Jul 22 '09 at 14:37
Ah, nice. Maybe add that as an answer to your own question (it's considered quite kosher to do that). Or is there still a question unanswered here? — dreeves, Jul 30 '09 at 17:45
Well, you need to explicitly pass your functions around, while the Python yield thing kind of figures it out for you, and makes it fit into the framework. So, it isn't quite perfect. But good enough, indeed, I use it now. — nes1983, Jul 30 '09 at 19:54
The code quoted from the book is fine, but being written in top-level Mathematica, it is not the most efficient, will run slow for larger n. You might want to write nextPermutation in Compile, and then loop through permutations. Added benefit, you can compile it into C in v8 to improve performance about 10 times. — Sasha, Mar 03 '11 at 15:50

score 5 · Accepted Answer · answered Apr 18 '11 at 16:03

5

As I have previously stated, using Compile will given faster code. Using an algorithm from fxtbook, the following code generates a next partition in lexicographic ordering:

PermutationIterator[f_, n_Integer?Positive, nextFunc_] := 
 Module[{this = Range[n]},
  While[this =!= {-1}, f[this]; this = nextFunc[n, this]];]

The following code assumes we run version 8:

ClearAll[cfNextPartition];
cfNextPartition[target : "MVM" | "C"] := 
  cfNextPartition[target] = 
   Compile[{{n, _Integer}, {this, _Integer, 1}},
    Module[{i = n, j = n, ni, next = this, r, s},
     While[Part[next, --i] > Part[next, i + 1], 
      If[i == 1, i = 0; Break[]]];
     If[i == 0, {-1}, ni = Part[next, i]; 
      While[ni > Part[next, j], --j];
      next[[i]] = Part[next, j]; next[[j]] = ni;
      r = n; s = i + 1;
      While[r > s, ni = Part[next, r]; next[[r]] = Part[next, s]; 
       next[[s]] = ni; --r; ++s];
      next
      ]], RuntimeOptions -> "Speed", CompilationTarget -> target
    ];

Then

In[75]:= Reap[PermutationIterator[Sow, 4, cfNextPartition["C"]]][[2, 
   1]] === Permutations[Range[4]]

Out[75]= True

This is clearly better in performance than the original gen function.

In[83]:= gen[dummy, 9] // Timing

Out[83]= {26.067, Null}

In[84]:= PermutationIterator[dummy, 9, cfNextPartition["C"]] // Timing

Out[84]= {1.03, Null}

Using Mathematica's virtual machine is not much slower:

In[85]:= PermutationIterator[dummy, 9, 
  cfNextPartition["MVM"]] // Timing

Out[85]= {1.154, Null}

Of course this is nowhere near C code implementation, yet provides a substantial speed-up over pure top-level code.

answered Apr 18 '11 at 16:03

Sasha

5,935
1
25
33

You can get C speed by using the trick I was exposing in this post: http://stackoverflow.com/questions/5246330/delete-repeating-list-elements-preserving-order-of-appearance/5251034#5251034. If you create a generator for a compiled function `PermutationIterator`, like so: `PermutationIteratorGen[f_, nextFunc_] := Compile[{{n, _Integer}}, Module[{this = Range[n]}, While[this =!= {-1}, f[this]; this = nextFunc[n, this]];], RuntimeOptions -> "Speed", CompilationTarget -> "C", CompilationOptions -> {"InlineCompiledFunctions" -> True, "InlineExternalDefinitions" -> True}]`, contd.. – Leonid Shifrin Apr 22 '11 at 07:41
Continuing.. Then, assuming that your *dummy* function can be `Compiled`, you get another order of magnitude speedup: `fn = PermutationIteratorGen[# &, cfNextPartition["C"]]; fn[9] // Timing`. The trick above effectively allows the variables of the enclosing Compiled function to live in the compiled code and be modified by the caller compiled function, because at the end we do inlining and get just a single large Compiled function, but for us it looks more modular. But using `Sow` or other uncompilable function will greatly degrade the performance, thus almost no difference between C and MVM. – Leonid Shifrin Apr 22 '11 at 07:48
@Leonid Yes this a good point, and the iterator also can be custom written to perform some predetermined operations, thus forgoing passing the function altogether. What I meant by not C-speed is that it is far from 130 millions permutations generated per second quote made in fxtbook. `fn[11]` takes 9.86 seconds on my machine amounting to 4 million permutations per second. A look at `CompilePrint[fn]` is instructive and will indicate why that happened. – Sasha Apr 22 '11 at 16:02
@Sasha Thanks, I should have looked at `CompilePrint` indeed. I do that in other cases but here I somehow believed that there would be no calls to the main evaluator and did not check, The same is true for the code I referred to, as you commented there. – Leonid Shifrin Apr 22 '11 at 16:59
@Sasha Strange: I actually looked at `CompilePrint[fn]`, and did not find there the calls to the main evaluator. There were, however, multiple calls to `CopyTensor`, but I assume that `CopyTensor` is some Wolfram Runtime Library function linked to the generated C code, so it should be fast enough. So, I still don't see what could account for such dramatic speed difference between the timings you quote from the book and the ones that `fn` evaluation gives. I could only guess that, since there is a lot of small array memory allocatiion-deallocation involved, this could be the major factor. – Leonid Shifrin Apr 22 '11 at 17:44
@Leonid The code in the book performs a in-place operations, while `CopyTensor` creates a new array and copies elements. I think this is the performance killer, additionally there is a library function calls overhead. This is not at all surprising. The goal of my post was to offer something better than top-level, and `Compile` encapsulation takes it to the next level. – Sasha Apr 22 '11 at 17:57
@Sasha I see. The inlining technique also allows to use `this` directly in the `cfNextPartition` function without copying it to `next` and then back, and therefore modify in place. This may additionally speed things up. – Leonid Shifrin Apr 22 '11 at 18:58

score 2 · Answer 2 · answered Jul 24 '09 at 19:34

2

You probably mean the question to be more general but the example of iterating over permutations as given on the page you link to happens to be built in to Mathematica:

Scan[Print, Permutations[{1, 2, 3}]]

The Print there can be replaced with any function.

answered Jul 24 '09 at 19:34

dreeves

26,430
45
154
229

2

Well, what I mean by a generator is this more like the following, which works in O(n) memory, where you need O(n!). gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit}, visit[k_] := Module[{t}, id++; If[k != 0, val[[k]] = id]; If[id == n, f[val]]; Do[If[val[[t]] == Null, visit[t]], {t, 1, n}]; id--; val[[k]] = Null;]; visit[0]; ] You run it like this: gen[Print,3] – nes1983 Jul 30 '09 at 13:26

Yield in Mathematica

2 Answers2