rovf has asked for the wisdom of the Perl Monks concerning the following question:
Assuming: @arr is an array, $n is a number greater than zero and less than the number of elements in the array. Problem: Rotate the array left by $n positions.
Example:
@arr=(1,2,3,4,5,6,7);
$n=3;
# @arr afterwards:
# (4,5,6,7,1,2,3)
For the special case $n==1, I think the best solution would be
push @arr,(shift @arr);
For the general case, I came up with two possible solutions:
- Apply the shifting $n times
- Use array slices, i.e. @arr=(@arr[$index..$#arr],@arr[0..($index-1)])
Any ideas about better solutions? ("Better" in the sense of: more compact, or more readable, or faster for large arrays, etc.).
--
Ronald Fischer <ynnor@mm.st>
Re: Rotating an array
by moritz (Cardinal) on Jun 17, 2011 at 11:38 UTC
|
push @arr, splice @arr, 0, $idx
In the end you'll have to benchmark to find which of the solutions is the fastest for you.
| [reply] [d/l] |
Re: Rotating an array
by BrowserUk (Patriarch) on Jun 17, 2011 at 12:19 UTC
|
Why physically move anything?
If you want to use the values in rotated order en-masse, then do the slice in-situ.
If the array is large, then write an iterator sub that returns the indices in the appropriate order.
Physically (electronically) moving the data, when you can use math to map the indices is silly. Especially for large arrays.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
|
#!/usr/bin/perl --
use Benchmark qw( cmpthese );
@ARGV = ( 3,4,5,6 ) unless @ARGV;
# 7 is too much for me :)
for my $pow ( @ARGV ){
our $max = 10 ** $pow ;
our $index = $max/10;
print "\npow = $pow max = $max index = $index \$] = $]\n
+";
cmpthese(
-3,
{
pushShift => \&pushShift,
slice => \&slice,
pushSplice => \&pushSplice,
splice => \&SPLICE,
}
);
}
sub pushShift {
my @arr = ( 1 .. $max );
push @arr,(shift @arr) for 1 .. $index;
undef @arr;
return;
}
sub slice {
my @arr = ( 1 .. $max );
@arr=(@arr[$index..$#arr],@arr[0..($index-1)]);
undef @arr;
return;
}
sub pushSplice {
my @arr = ( 1 .. $max );
push @arr, splice @arr,0,$index;
undef @arr;
return;
}
sub SPLICE {
my @arr = ( 1 .. $max );
splice @arr,@arr,$index, splice @arr,0,$index;
undef @arr;
return;
}
__END__
pow = 3 max = 1000 index = 100 $] = 5.012002
Rate slice pushShift splice pushSplice
slice 2422/s -- -53% -57% -60%
pushShift 5144/s 112% -- -9% -15%
splice 5659/s 134% 10% -- -6%
pushSplice 6038/s 149% 17% 7% --
pow = 4 max = 10000 index = 1000 $] = 5.012002
Rate slice pushShift splice pushSplice
slice 229/s -- -49% -53% -57%
pushShift 446/s 95% -- -8% -17%
splice 484/s 111% 8% -- -10%
pushSplice 536/s 134% 20% 11% --
pow = 5 max = 100000 index = 10000 $] = 5.012002
Rate slice pushShift splice pushSplice
slice 20.6/s -- -49% -55% -58%
pushShift 40.3/s 95% -- -12% -18%
splice 45.7/s 122% 13% -- -7%
pushSplice 49.0/s 137% 22% 7% --
pow = 6 max = 1000000 index = 100000 $] = 5.012002
Rate slice pushShift splice pushSplice
slice 2.05/s -- -53% -54% -59%
pushShift 4.31/s 111% -- -3% -13%
splice 4.46/s 118% 3% -- -10%
pushSplice 4.98/s 143% 15% 12% --
| [reply] [d/l] |
|
| [reply] |
|
|
| [reply] [d/l] |
|
Because the array is passed on to another function
As a list or an array ref?
If the former, then you can again avoid physically moving the data by slicing it to produce the list.
Of course, if you are only rotating the array once per program run, then it doesn't much matter. But if you need several different rotations during the program run, then it might make sense to avoid moving everything multiple times, if possible.
Silly example code:
#! perl -slw
use strict;
sub rotateAll{
my( $aref, $n ) = @_;
$n = $n % @{$aref};
return ( $n .. $#{$aref}, 0 .. $n-1 );
}
sub rotateOne {
my( $aref, $n, $i ) = @_;
return ( $i + $n ) % @{$aref};
}
my @a = 1 .. 5;
print "Sliced";
printf "% 3d: %s\n", $_,
join ' ', @a[ rotateAll( \@a, $_ ) ]
for -7 .. 7;
print "\nDiced";
for my $rot ( -7 .. 7 ) {
printf "% 3d: ", $rot;
print join ' ', map $a[ rotateOne( \@a, $rot, $_ ) ], 0 .. $#a;
}
__END__
C:\test>910117
Sliced
-7: 4 5 1 2 3
-6: 5 1 2 3 4
-5: 1 2 3 4 5
-4: 2 3 4 5 1
-3: 3 4 5 1 2
-2: 4 5 1 2 3
-1: 5 1 2 3 4
0: 1 2 3 4 5
1: 2 3 4 5 1
2: 3 4 5 1 2
3: 4 5 1 2 3
4: 5 1 2 3 4
5: 1 2 3 4 5
6: 2 3 4 5 1
7: 3 4 5 1 2
Diced
-7: 4 5 1 2 3
-6: 5 1 2 3 4
-5: 1 2 3 4 5
-4: 2 3 4 5 1
-3: 3 4 5 1 2
-2: 4 5 1 2 3
-1: 5 1 2 3 4
0: 1 2 3 4 5
1: 2 3 4 5 1
2: 3 4 5 1 2
3: 4 5 1 2 3
4: 5 1 2 3 4
5: 1 2 3 4 5
6: 2 3 4 5 1
7: 3 4 5 1 2
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] [d/l] |
|
Re: Rotating an array
by zentara (Archbishop) on Jun 17, 2011 at 11:40 UTC
|
I guess you would have to benchmark them to see which is better.
#!/usr/bin/perl
use warnings;
use strict;
#4.47: How do I handle circular lists?
# Circular lists could be handled in the traditional fashion with l
+inked
# lists, or you could just do something like this with an array:
# unshift(@array, pop(@array)); # the last shall be first
# push(@array, shift(@array)); # and vice versa
# You can also use "Tie::Cycle":
use Tie::Cycle;
tie my $cycle, 'Tie::Cycle', [ qw( FFFFFF 000000 FFFF00 ) ];
print $cycle; # FFFFFF
print $cycle; # 000000
print $cycle; # FFFF00
print $cycle; # FFFFFF
print $cycle; # 000000
print $cycle; # FFFF00
| [reply] [d/l] |
|
IMO Tie::Cycle has two disadvantages: It always rotates the list by only one position (hence is not better than the push(...,pop...) variant), and it rearranges the list every time I access the tie'd variable. No surprise: Tie::Cycle was made for a completely different purpose than I'm going to use it: I want to rotate the array only once, but then by a certain number of positions.
However, the solution using splice, which moritz proposed, looks better than those I came up with. I thiink I will use it.
--
Ronald Fischer <ynnor@mm.st>
| [reply] [d/l] [select] |
Re: Rotating an array
by Anonymous Monk on Jun 17, 2011 at 12:59 UTC
|
What I would do is to define a class which owns the array data and which will return any element that you want. Behind the scenes, it applies a numeric offset (default: 0) to the requested coordinate, modulo the size.
Thus, you do not "move" the data at all. | [reply] |
|
|