Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > classic loop to controlled iterator

Reply
Thread Tools

classic loop to controlled iterator

 
 
George Mpouras
Guest
Posts: n/a
 
      03-10-2013
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
}
}

 
Reply With Quote
 
 
 
 
Peter Makholm
Guest
Posts: n/a
 
      03-10-2013
"George Mpouras"
<(E-Mail Removed) m.com.nospam> 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
 
Reply With Quote
 
 
 
 
Tim McDaniel
Guest
Posts: n/a
 
      03-16-2013
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/Attr...e/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, http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
Rainer Weikusat
Guest
Posts: n/a
 
      03-17-2013
(E-Mail Removed) (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/Attr...e/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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Triple nested loop python (While loop insde of for loop inside ofwhile loop) Isaac Won Python 9 03-04-2013 10:08 AM
What makes an iterator an iterator? Steven D'Aprano Python 28 04-20-2007 03:34 AM
Difference between Java iterator and iterator in Gang of Four Hendrik Maryns Java 18 12-22-2005 05:14 AM
How to convert from std::list<T*>::iterator to std::list<const T*>::iterator? PengYu.UT@gmail.com C++ 6 10-30-2005 03:31 AM
Iterator doubts, Decision on Iterator usage greg C++ 6 07-17-2003 01:26 PM



Advertisments