classic loop to controlled iterator

Discussion in 'Perl Misc' started by George Mpouras, Mar 10, 2013.

  1. I think this is a nice trick.
    Lets say we have a loop that will not stop until it finish e.g.

    my $i=5;
    for (1..$i) {
    print "$_\n"
    }
    for (2*$i..4*$i) {
    print "$_\n"
    }
    }


    it is possible to convert it to a contolable iterator like this


    use strict;
    use warnings;

    my $prog = wrapper(5);

    print "first result : ", $prog->() ,"\n";
    print "second result : ", $prog->() ,"\n";
    while ( $_ = $prog->() ) {
    print "*$_*\n";
    }


    sub wrapper {
    my ($i, $last) = ($_[0], 0);

    sub {
    ++$last;
    my $result;
    for ($last .. $i) { $result ||= $_ }
    for ($last .. 4*$i) { $result ||= $_ }
    $result
    }
    }
     
    George Mpouras, Mar 10, 2013
    #1
    1. Advertising

  2. "George Mpouras"
    <> writes:

    > I think this is a nice trick.
    > Lets say we have a loop that will not stop until it finish e.g.
    >
    > my $i=5;
    > for (1..$i) { print "$_\n"
    > }
    > for (2*$i..4*$i) {
    > print "$_\n"
    > }
    > }


    Note that this set of loops performs 3*$i iterations of the loop bodies.

    > sub wrapper {
    > my ($i, $last) = ($_[0], 0);
    >
    > sub {
    > ++$last;
    > my $result; for ($last .. $i) { $result ||= $_ }
    > for ($last .. 4*$i) { $result ||= $_ }
    > $result
    > }
    > }


    This will perform ((3*$i)^2)/2 iterations of the loop body.

    In this specific case the difference might be negligible as the constant
    number of print operations overshadows the other costs. But when
    generalizing this method you need to take very care that the loop bodies
    in the wrapper always has the form '$result ||= expr' which turns into
    almost a no-op in all iterations except the initial.

    You method will also have hard to handle the case where the loop body
    might result in a false value.

    //Makholm
     
    Peter Makholm, Mar 10, 2013
    #2
    1. Advertising

  3. George Mpouras

    Tim McDaniel Guest

    There are general comments I can make: consistent indentation really
    helps in understanding code, I prefer ";" at the end of each block,
    the output for two alternatives should be identical so you can compare
    the output of the two versions, I really prefer "return" for an
    explicit return.

    The biggest problem is that the proposal as written doesn't work. The
    original code outputs 1..5, 10..20, but the replacement outputs 1..20.
    Even if it's a contrived example to illustrate a point, working code
    should be posted.

    I also agree with the comment about inefficiency. It's repeating the
    entire sequence to reach one value, "||" to get a value but continuing
    past the first value. I'm thinking you might not have been aware of
    "return", and it would not work with a zero or null value.

    Here's a working version:

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    #! /usr/bin/perl
    use strict;
    use warnings;

    if (0) {
    my $i=5;
    for (1..$i) {
    print "$_\n"
    }
    for (2*$i..4*$i) {
    print "$_\n"
    }
    } else {
    my $prog = wrapper(5);

    while ( $_ = $prog->() ) {
    print "$_\n";
    }
    }
    exit 0;

    sub wrapper {
    my ($i, $last) = ($_[0], 0);

    return sub {
    ++$last;
    for ($last .. $i) { return $_; }
    $last = 2*$i if $last < 2*$i;
    for ($last .. 4*$i) { return $_; }
    return undef;
    }
    }

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    (After Perl 5.9.4, you could use a "state" declaration, but I've hit
    old versions of perl often enough, on systems that I don't control,
    that a solution that works on older perls is a good notion.)

    In
    for ($last .. $i) { return $_; }
    I believe that "for $i (a..b)" is optimized to "for ($i = a; $i < b; ++$i)".
    Because the loop body returns immediately, the "for" really functions
    as an "if": this works the same:
    return $last if $last <= $i;
    But using "for" makes it perhaps a little more readable, makes it look
    more like the original version.

    This is no longer O(n^2), but roughly as efficient as the original
    version -- sub has no actual loops. But it still goes thru a series
    of implicit if statements on each call. It's a trivial enough thing
    in this case, but in general, it might be highly problematic.

    One solution would be to generate the output stream on the first call
    and parcel them out one at a time:

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    sub wrapper {
    my ($i) = ($_[0]);
    my @results = (1..$i, 2*$i..4*$i);

    return sub {
    return shift @results;
    }
    }

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    It's certainly clear to understand. But that sort of misses the point
    of having a generator. It has to generate all the results at the
    start, but one purpose of a generator is that you can get a few of the
    first results, not bother getting the rest, and only pay the cost of
    getting the ones you got. Also, if the process to get a result
    consumes something or is less trivial than this (e.g., reading from a
    terminal), it could be problematic or impossible to do this. It also
    consumes all the sorage to hold all the results at once, so there are
    two failures if your generator is supposed to, say, return all the
    positive integers.

    In general, what you really want are "generators". The notion is that
    a computation can proceed for a time, but suspend and yield a result
    to the caller. When the caller calls back, the thread of execution
    starts continuing after the point of the last yield.

    From a quick search, looking at only the first few pages of 1292 hits
    in CPAN for
    generator
    http://search.cpan.org/~mlehmann/Coro-6.23/ is the basis of what you
    want. It implements coroutines / continuations, which have the
    stop-and-resume model but don't necessarily yield a result.
    http://search.cpan.org/~rintaro/Attribute-Generator-0.02/lib/Attribute/Generator.pm
    appears to use Coro to implement stop-and-resume plus yielding
    results. I've not used either, so I can't express an opinion about
    how reliable, efficient, and usable they are.

    --
    Tim McDaniel,
     
    Tim McDaniel, Mar 16, 2013
    #3
  4. (Tim McDaniel) writes:

    [...]

    > In general, what you really want are "generators". The notion is that
    > a computation can proceed for a time, but suspend and yield a result
    > to the caller. When the caller calls back, the thread of execution
    > starts continuing after the point of the last yield.
    >
    > From a quick search, looking at only the first few pages of 1292 hits
    > in CPAN for
    > generator
    > http://search.cpan.org/~mlehmann/Coro-6.23/ is the basis of what you
    > want. It implements coroutines / continuations, which have the
    > stop-and-resume model but don't necessarily yield a result.
    > http://search.cpan.org/~rintaro/Attribute-Generator-0.02/lib/Attribute/Generator.pm
    > appears to use Coro to implement stop-and-resume plus yielding
    > results. I've not used either, so I can't express an opinion about
    > how reliable, efficient, and usable they are.


    One of the really 'nice' parts of the Wikipedia page on generators is
    that it states that (paraphrase) "A generator is a kind of coroutine
    except that it isn't coroutine but a subroutine" (which only ever
    returns to the caller). Any 'thing' which can be 'invoked' somehow and
    then returns 'the next value from some set of values' utilizing
    internal state information to keep track of what precisely 'the next
    value' is supposed to be, is 'a generator'. The obvious idea how to
    implement that would be 'some kind of class with a next_value
    method'. Often, it will be more convenient to use a closure instead.
     
    Rainer Weikusat, Mar 17, 2013
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,466
  2. greg
    Replies:
    6
    Views:
    480
    Dietmar Kuehl
    Jul 17, 2003
  3. Replies:
    6
    Views:
    693
    Jim Langston
    Oct 30, 2005
  4. Steven D'Aprano

    What makes an iterator an iterator?

    Steven D'Aprano, Apr 18, 2007, in forum: Python
    Replies:
    28
    Views:
    1,267
    Steven D'Aprano
    Apr 20, 2007
  5. Isaac Won
    Replies:
    9
    Views:
    443
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page