in reply to Rotating an array

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.

Replies are listed 'Best First'.
Re^2: Rotating an array
by Anonymous Monk on Jun 17, 2011 at 12:24 UTC
    Silly and slow 
    #!/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%         --

    [download]
[reply]
[d/l]

      What do you think you are comparing here? All of those move the original data, so they are all slow.

      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]
        What do you think you are comparing here?

        Nothing important, different ways to move

        All of those move the original data, so they are all slow.

        Acknowledged

[reply]
Re^2: Rotating an array
by rovf (Priest) on Jun 17, 2011 at 12:53 UTC
    Why physically move anything?
    Because the array is passed on to another function, and the interface to that functions says that it processes the list from the first element to the last. An iterator would makes sense if I process the array myself.

    -- 
    Ronald Fischer <ynnor@mm.st>
[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

      [download]
      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]
        It is passed as a list; and, for a given input data set, rotation is done only once.

        Thank you very much for your examples!

        -- 
        Ronald Fischer <ynnor@mm.st>
[reply]
[d/l]

In Section Seekers of Perl Wisdom