Home > Archive > PERL Beginners > March 2008 > functions: rotate and factorial
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
functions: rotate and factorial
|
|
| Sharan Basappa 2008-03-13, 8:03 am |
| Hi,
I was wondering if perl has support for the following operators or functions:
- rotate: the elements of a given array are shifted such the elements
are shifted right or left
and the last/first element fill the first/last position depending on
whether shift right or shift left is
done.
- factorial
Regards
| |
| Chas. Owens 2008-03-13, 8:03 am |
| On Thu, Mar 13, 2008 at 8:36 AM, Sharan Basappa
<sharan.basappa@gmail.com> wrote:
snip
> - rotate: the elements of a given array are shifted such the elements
> are shifted right or left
> and the last/first element fill the first/last position depending on
> whether shift right or shift left is
> done.
snip
rotate left:
push @a, shift @a;
rotate right:
unshift @a, pop @a
snip
> - factorial
snip
Not that I am aware of, you might want to look on CPAN:
search.cpan.org or Google.
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
| |
| Jenda Krynicky 2008-03-13, 7:08 pm |
| Date sent: Thu, 13 Mar 2008 18:06:27 +0530
From: "Sharan Basappa" <sharan.basappa@gmail.com>
To: beginners@perl.org
Subject: functions: rotate and factorial
> Hi,
>
> I was wondering if perl has support for the following operators or functions:
>
> - rotate: the elements of a given array are shifted such the elements
> are shifted right or left
> and the last/first element fill the first/last position depending on
> whether shift right or shift left is
> done.
right
@a = (pop(@a), @a);
left
@a = (@a[1..$#a], $a[0]);
there's nothing preventing you from moving those to subroutines, eg.
like this:
sub shiftR (\@) {
my ($a) = @_;
@$a = (pop(@$a), @$a);
return;
}
sub shiftL (\@) {
my ($a) = @_;
@$a = (@{$a}[1..$#$a], $a->[0]);
return;
}
@a = (1,2,3,4);
print join(',', @a), "\n";
shiftR @a;
print join(',', @a), "\n";
shiftL @a;
print join(',', @a), "\n";
> - factorial
Looks like it's for example in Math::NumberCruncher
Jenda
===== Jenda@Krynicky.cz === http://Jenda.Krynicky.cz =====
When it comes to wine, women and song, wizards are allowed
to get drunk and croon as much as they like.
-- Terry Pratchett in Sourcery
| |
| Chas. Owens 2008-03-13, 7:08 pm |
| On Thu, Mar 13, 2008 at 9:02 AM, Jenda Krynicky <Jenda@krynicky.cz> wrote:
snip
> right
> @a = (pop(@a), @a);
>
> left
> @a = (@a[1..$#a], $a[0]);
snip
These are O(n) operations and are fine if n is small, but the push/shift and
unshift/pop implementations are O(1). Of course, the push/shift and
unshift/pop versions are destructive, so you may need to use these if you
aren't assigning back to the same array (which would be O(n) anyway so there
wouldn't be a noticeable performance hit).
test with ten elements
left_push_shift [2] [3] [4] [5] [6] [7] [8] [9] [1]
left_slice [2] [3] [4] [5] [6] [7] [8] [9] [1]
right_slice [9] [1] [2] [3] [4] [5] [6] [7] [8]
right_unshift_pop [9] [1] [2] [3] [4] [5] [6] [7] [8]
results for n of 10
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 297890/s -- -36% -92%
-93%
right_slice 463698/s 56% -- -87%
-89%
right_unshift_pop 3574691/s 1100% 671% --
-13%
left_push_shift 4111294/s 1280% 787% 15%
--
results for n of 100
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 36885/s -- -34% -99%
-99%
right_slice 55854/s 51% -- -98%
-99%
right_unshift_pop 3300471/s 8848% 5809% --
-22%
left_push_shift 4249037/s 11420% 7507% 29%
--
results for n of 1000
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 3459/s -- -37% -100%
-100%
right_slice 5493/s 59% -- -100%
-100%
right_unshift_pop 3247802/s 93806% 59024% --
-14%
left_push_shift 3780922/s 109221% 68729% 16%
--
results for n of 10000
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 352/s -- -38% -100%
-100%
right_slice 565/s 61% -- -100%
-100%
right_unshift_pop 3276799/s 931108% 580055% --
-13%
left_push_shift 3776122/s 1073007% 668459% 15%
--
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark;
my @a;
my %subs = (
left_push_shift => sub { push @a, shift @a; return 0 },
left_slice => sub { @a = (@a[1..$#a], $a[0]); return 0 },
right_unshift_pop => sub { unshift @a, pop @a; return 0 },
right_slice => sub { @a = (pop @a, @a); return 0 },
);
print "test with ten elements\n";
for my $sub (sort keys %subs) {
@a = 1 .. 9;
$subs{$sub}->();
printf "%-20s %s\n", $sub, join " ", map {"[$_]"} @a;
}
for my $n (10, 100, 1_000, 10_000) {
@a = 1 .. $n;
print "results for n of $n\n";
Benchmark::cmpthese(-1, \%subs);
}
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
| |
| Obdulio Santana 2008-03-13, 7:08 pm |
| 2008/3/13, Jenda Krynicky <Jenda@krynicky.cz>:
>
> Date sent: Thu, 13 Mar 2008 18:06:27 +0530
> From: "Sharan Basappa" <sharan.basappa@gmail.com>
> To: beginners@perl.org
> Subject: functions: rotate and factorial
>
>
> functions:
>
>
> right
> @a = (pop(@a), @a);
>
> left
> @a = (@a[1..$#a], $a[0]);
>
> there's nothing preventing you from moving those to subroutines, eg.
> like this:
>
> sub shiftR (\@) {
> my ($a) = @_;
> @$a = (pop(@$a), @$a);
> return;
> }
> sub shiftL (\@) {
> my ($a) = @_;
> @$a = (@{$a}[1..$#$a], $a->[0]);
> return;
> }
>
> @a = (1,2,3,4);
> print join(',', @a), "\n";
>
> shiftR @a;
> print join(',', @a), "\n";
>
> shiftL @a;
> print join(',', @a), "\n";
>
>
> Looks like it's for example in Math::NumberCruncher
>
> Jenda
if you don't know or want to use Math::Num.... or similar this may help
sub factorial {
my $n = 1;
$n *= $_ for 2..shift;
return $n;
}
extracted from http://timjoh.com/writing-a-factori...routine-in-perl
I hop this help somebody.
| |
| Sharan Basappa 2008-03-14, 4:12 am |
| Thanks everybody. I need to use these as a part of algo I am working
on. I will get back if I have any comments ..
On Thu, Mar 13, 2008 at 7:19 PM, obdulio santana
<obduliosantana@gmail.com> wrote:
> 2008/3/13, Jenda Krynicky <Jenda@krynicky.cz>:
>
>
>
>
>
> if you don't know or want to use Math::Num.... or similar this may help
>
> sub factorial {
> my $n = 1;
> $n *= $_ for 2..shift;
> return $n;
> }
>
> extracted from http://timjoh.com/writing-a-factori...routine-in-perl
> I hop this help somebody.
>
| |
| Rob Dixon 2008-03-14, 7:13 pm |
| Sharan Basappa wrote:
>
> Thanks everybody. I need to use these as a part of algo I am working
> on. I will get back if I have any comments ..
Rotating an array and calculating a factorial are both likely to absorb
large amounts of processor time unless your problem is trivial. I'm also
intrigued to hear of an algorithm that makes use of factorials. Perhaps
your solution needs looking at before you implement it?
Rob
| |
| Sharan Basappa 2008-03-17, 7:08 pm |
| Rob,
Actually you are correct. I was on my way to implement permutation for
a given set of numbers.
In that context, I had designed my own algo as a part of bigger
problem I am trying to solve.
That algo requires rotate and factorial. Rotate to get different
combinations and factorial to limit for loop.
Today, I happened to go through Steinhaus-Johnson-Trotter's algo for the same.
It looks elegant and should be efficient. I plan to use this.
Question: Does anyone know if perl has inuilt function to implement
Steinhaus-Johnson-Trotter's?
Regards,
Sharan
On Fri, Mar 14, 2008 at 8:33 PM, Rob Dixon <rob.dixon@gmx.com> wrote:
> Sharan Basappa wrote:
>
> Rotating an array and calculating a factorial are both likely to absorb
> large amounts of processor time unless your problem is trivial. I'm also
> intrigued to hear of an algorithm that makes use of factorials. Perhaps
> your solution needs looking at before you implement it?
>
> Rob
>
>
| |
| Chas. Owens 2008-03-17, 7:08 pm |
| On Mon, Mar 17, 2008 at 10:34 AM, Sharan Basappa
<sharan.basappa@gmail.com> wrote:
> Rob,
>
> Actually you are correct. I was on my way to implement permutation for
> a given set of numbers.
> In that context, I had designed my own algo as a part of bigger
> problem I am trying to solve.
> That algo requires rotate and factorial. Rotate to get different
> combinations and factorial to limit for loop.
> Today, I happened to go through Steinhaus-Johnson-Trotter's algo for the same.
> It looks elegant and should be efficient. I plan to use this.
> Question: Does anyone know if perl has inuilt function to implement
> Steinhaus-Johnson-Trotter's?snip
snip
I don't know what algorithm Algorithm::Permute* uses, but it seems fairly fast.
* http://search.cpan.org/dist/Algorit...mute/Permute.pm
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
|
|
|
|
|