Esteemed Monks,
I was looking at
The On-Line Encyclopedia of Integer Sequences (OEIS) (you
know, as one does), and on the Welcome page
I found a list of Some
Famous Sequences, of which the first is Recamán’s
sequence, defined as follows:
R(0) = 0;
for n > 0,
R(n) = R(n-1) - n if positive and not already in the sequence, oth
+erwise
R(n) = R(n-1) + n.
What makes this sequence interesting is N. J. A. Sloane’s conjecture
that every number eventually appears.
Coding the sequence is simplicity itself; the challenge is to test Sloane’s
conjecture by keeping track of the numbers that have not yet appeared in the
series. My initial, naïve approach was to use a sieve, à la
Eratosthenes:
But this turned out to be far too memory-hungry: for values of MAX of
the order of twenty million, RAM usage on my 3GB system approaches 100%,
thrashing sets in, and the script (along with the rest of Windows) grinds to a
shuddering halt.
Surely, I thought, there must be a memory-efficient way to represent a sieve?
And of course there is, and of course it was already implemented on CPAN.
A little searching led to the Set::IntSpan module which stores runs
of consecutive integers as spans, allowing large (even infinite)
collections of integers to be represented very economically.
Calculation of successive terms in the Recamán sequence is noticeably slower
using Set::IntSpan for lookup than it is using a hash. But, as the
adage says, it’s
better to be late than be dead on time. (This was the slogan of an
Australian safe driving ad campaign some years ago.) For the record: I also
looked at Set::IntSpan::Fast and Set::IntSpan::Fast::XS.
The latter failed to install on my system, and the former actually ran slower
than Set::IntSpan for this use-case.
Turns out that Set::IntSpan not only solves the memory problem, it also makes
it possible to dispense with an upper bound for the sieve. How, then, to display
progressive results? Well, the OEIS has a couple of additional series related to
Recamán’s:
- A064228: values of R(n) that take a record
number of steps to appear: 1, 2, 4, 19, ...
- A064227: the values of n corresponding to the
values in A064228: 1, 4, 131, 99734, ...
So I recast the script to output successive values of these two series:
14:20 >perl recaman.pl
1 <-- 1
2 <-- 4
4 <-- 131
19 <-- 99734
...
Here is the new script:
use strict;
use warnings;
use sigtrap handler => \&int_handler, 'INT',
handler => \&break_handler, 'BREAK';
use Set::IntSpan;
use Time::HiRes qw(gettimeofday tv_interval);
$| = 1;
my $t0 = [gettimeofday];
my $min0 = 1;
my $n = 0;
my $r0 = 0;
my $missing = Set::IntSpan->new( '1-)' );
print "$min0 <-- ";
while (++$n)
{
my $r = $r0 - $n;
$r = $r0 + $n if $r < 0 || !$missing->member($r);
$missing->remove($r);
if ((my $min1 = $missing->min) > $min0)
{
print "$n\n$min1 <-- ";
$min0 = $min1;
}
$r0 = $r;
}
sub int_handler
{
printf "\nn = %d, elapsed time: %.1fs\n", $n, tv_interval($t0);
}
sub break_handler
{
int_handler();
exit 0;
}
This script was developed under Windows 8.1, 64-bit, using Strawberry Perl:
14:20 >perl -v
This is perl 5, version 22, subversion 0 (v5.22.0) built for MSWin32-x
+64-multi-thread
The two signal handlers allow the script to be interrupted as follows:
- Control-C causes the script to display the current value of $n
and the total running time of the script so far.
- Control-Break causes the script to display the same information and
then exit.
My takeaways from this meditation?
First, we all know that micro-optimisation is pointless
until you have first selected the best algorithm(s). But optimising an algorithm may actually consist in optimising its underlying
data structures. Obvious? Yes, but still worth a reminder now and then.
Second, CPAN is awesome! But you knew that already. :-)
Cheers,
|
Noël, Noël
in Perl Poetry
2 direct replies — Read more / Contribute
|
by Athanasius
on Dec 25, 2014 at 01:03
|
It’s Christmas! Ring the Monastery bell,
As we with joy recall that first Noël
When shepherds, watching through the lonely night,
Were over-awed by heaven’s glorious light.
With cheer, we’ll greet our brother monks, and sisters,
And amnesty extend to Pythonistas,
And other erring souls; foreach, today,
We wish bright blessings in a long @array.
And tho’ at times, alas!, we make a %hash
Of our Monastic Rule, with insults rash
And words unkind: today we start anew
And map our way with kinder goals in view.
A maid needs help with syntax? We’ll not fail ’er.
A hill of bugs is in our way? We’ll $scalar.
Tho’ all the year in Perl we script — and well, —
Today it’s “Per”, in honour of Noël.
© 2014
Merry Christmas!
|
Happy Monkday!!
You’ve been here 1 thrilling year.
Is it really a whole year since I joined the Monastery? I’m so glad I did, and so very grateful to all the monks whose enthusiasm and dedication make PerlMonks the special place it is.
So this seems like a good opportunity to post a rather long poem I wrote to meet the challenge of finding rhymes for all the monastic levels, from Initiate to Pope.
Enjoy! :-)
Cheers,
|
5 Perlimericks
|
A team of aspiring Perlistas
Would type till their fingers got blisters.
But without their espresso,
The code was a mess, so
They had to take turns as baristas.
|
|
A Perl coder sheepdog named Shep,
As a herder acquired a rep —
An array he did keep
Full of cows, goats, and sheep,
Then he gathered the sheep using grep.
|
|
Said the Scribe, as his postings increased,
“An obsession? No, not in the least!
With my time I’m restrictive.
I know it’s addictive.”
At the last report, he was a Priest...
|
|
An old coder’s wit (not a flash of it!)
Rejected my Perl (the whole stash of it).
He’d been coding all day
An associative array,
So I said, “Well, you’ve sure made a hash of it!”
|
|
Said the boss, “Java’s pure and sublime;
To use anything else is a crime.”
But a rebel named Earl
Said “I much prefer Perl” —
And his project was finished on time.
|
© 2012
Athanasius <°(((>< contra mundum
|
5 Rhyming Haikus
|
|
Newcomer puzzled
By de-refs; but quickly copes
With lexical scopes.
|
|
Seeker of wisdom
Finds that reputation lags
For want of <code> tags.
|
Fresh-minted Friar
Learning Consideration
In Moderation.
|
Tricky answer found—
Dancing and cries of “Whoopie!”
As in rolls XP.
|
|
Newbies, scholars, saints,
Together in the cloisters
Opening oysters.
|
|
© 2012
Athanasius <°(((>< contra mundum
|