StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Using a self-reading stream</h2> <p>You can solve this using a self-read stream:</p> <pre><code> ----------- ----------- | pow 2 |------->| | ----------- | | | merge |-------+------------> ----------- | | | .->| x 3 |------->| | | | ----------- ----------- | \_______________________________________/ </code></pre> <p>The first stream produces the powers of two, while the second one ensures all the generated numbers are multiplied by 3 and reinjected into the output. The merge operator ensures that the output is sorted.</p> <p>Note that we must "seed" the output stream with 1, or the first element will try to produce itself when evaluated.</p> <p>Here is the code:</p> <pre><code>(require srfi/41) (define (merge s1 s2) (stream-match s1 ((x . xs) (stream-match s2 ((y . ys) (if (< x y) (stream-cons x (merge xs s2)) (stream-cons y (merge ys s1)))))))) (define (the-stream) (letrec ((s (stream-cons 1 (merge (stream-map (lambda (x) (* 3 x)) s) (stream-iterate (lambda (x) (* 2 x)) 2))))) s)) </code></pre> <p>It's quite simple and fast compared to my other proposal, <strike>because it uses arithmetic properties of the problem besides monotonicity.</strike> <em>I'm wrong, it can be generalized just as well (upcoming)</em></p> <pre><code>$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))' (1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96) $ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))' 161968247347450370721577384417107686788864605658546176 real 0m1.746s user 0m1.344s sys 0m0.156s </code></pre> <h2>Using generators and a queue</h2> <p>We can also implement this with python's generators, but we need to use a queue to store the numbers waiting in the feedback loop:</p> <pre><code># Merge the output of two generators def merge(g1, g2): v1 = g1.next() v2 = g2.next() while 1: if v1 < v2: yield v1 v1 = g1.next() else: yield v2 v2 = g2.next() # Generates the powers of 2, starting with n def pow2(n): while 1: yield n; n *= 2 # Generates values shifted from the given 'q' and multiplied by 3 def mul3(q): while 1: yield q.pop(0) * 3 # The generator we want def pow23(): q = [] v = 1 g = merge(pow2(2), mul3(q)) while 1: yield v q.append(v) v = g.next() g23 = pow23() for i in range(10000): g23.next() print g23.next() </code></pre> <p>This is somewhat less elegant (IMHO), but the generators are much more lightweight:</p> <pre><code>$ time python feedback.py 161968247347450370721577384417107686788864605658546176 real 0m0.150s user 0m0.112s sys 0m0.012s </code></pre> <p>For what is worth, I have done a scheme implementation (using closures as generators) which shows roughly the same performance.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload