Most efficient way to exchange two array values in Perl
I was curious what the most efficient way to exchange two elements in an array in Perl would be.
Let's say I want to switch items at index 3 and 5 respectively, what would be the fastest way to do this?
My thoughts were something like this:
@array[3,5] = @array[5,3];
Is it very effective? I hope it won't have any effect if these two array values contain large amounts of data. I would expect the back-end to change pointers around, without actually copying. It is right?
source to share
What do you mean by "big data"? If you mean referring to large data structures, it doesn't matter how you do it; it will be insanely fast. (Less than one nanosecond per swap.) So, I assume you meant "big strings".
Before 5.20, the code you posted will copy lines. You can avoid this by using Data :: Alias .
use Data::Alias;
alias @array[3,5] = @array[5,3];
Or you can do the same with a small XS if you want to avoid the magic of the Data :: Alias syntax:
void swap_array_elements(AV * av, IV ix1, IV ix2) {
SV ** p_ele1 = av_fetch(av, ix1, 1);
SV ** p_ele2 = av_fetch(av, ix2, 1);
SV * sv = *p_ele1;
*p_ele1 = *p_ele2;
*p_ele2 = sv;
}
As of 5.20, copies of strings have been replaced with simple pointer swaps.
$ 5.18t/bin/perl -MDevel::Peek -e'
my @a = qw( a b c d e f );
Dump($a[3]);
Dump($a[5]);
@a[3,5] = @a[5,3];
Dump($a[3]);
Dump($a[5]);
' 2>&1 | grep '^ PV'
PV = 0x353fba0 "d"\0
PV = 0x357abb0 "f"\0
PV = 0x3541ff0 "f"\0
PV = 0x3537940 "d"\0
$ 5.20t/bin/perl -MDevel::Peek -e'
my @a = qw( a b c d e f );
Dump($a[3]);
Dump($a[5]);
@a[3,5] = @a[5,3];
Dump($a[3]);
Dump($a[5]);
' 2>&1 | grep '^ PV'
PV = 0xe9ace0 "d"\0
PV = 0xe8f230 "f"\0
PV = 0xe8f230 "f"\0
PV = 0xe9ace0 "d"\0
source to share
My guess was that simply swapping temp variables would be faster than slicing. Benchmarking
use Benchmark qw(cmpthese);
use Data::Alias;
my @array = ('thing', 'stuff', 'that', 'joe', 'sofa', 'jim');
cmpthese(-2, {
slice => sub {
@array[3,5] = @array[5,3];
},
temp => sub {
my $tmp = $array[3];
$array[3] = $array[5];
$array[5] = $tmp;
},
alias => sub {
alias @array[3,5] = @array[5,3];
}
});
seems to confirm that:
Rate slice alias temp
slice 940155/s -- -70% -73%
alias 3151934/s 235% -- -9%
temp 3472932/s 269% 10% --
Edit: After I saw ikegami's comment changed to lines and also added alias
. It still looks like a temporary variable.
source to share
In a special case, to replace the first and last value, you can use:
push @l, shift @l;
Test results:
cmpthese( 10000000, {
tmp => sub{
my @l = ( 1, 2 );
my $tmp = $l[0];
$l[0] = $l[1];
$l[1] = $tmp;
},
shift => sub{ #
my @l = ( 1, 2 );
push @l, shift @l;
},
slice => sub{
my @l = ( 1, 2 );
@l[0,1] = @l[1,0];
},
});
Rate slice tmp shift
slice 2544529/s -- -4% -38%
tmp 2645503/s 4% -- -36%
shift 4115226/s 62% 56% --
source to share