21563

Sort Perl array in place?

I have a reference to an array (called $intervals) and I would like to sort the values in this array. It's possible that there could be a huge number of values in the array, so I would prefer not to copy the values. My current approach is this.

sub by_position { $a->start <=> $b->start || $a->end <=> $b->end } my @sorted_intervals = sort by_position (@$intervals);

However, if I understand Perl correctly this will indeed copy all of the values in the array. Is that right? If so, is there a way that I can do an in-place sort of an array (using a reference to that array)?

Answer1:

Perl allows arrays to be sorted in-place with the idiom @arr = sort @arr. Contrary to the normal behavior of the assignment operator, no copies will be made in this case. However, this optimization is limited to normal array variables; it won't work with array references:

Let's look under the hood by using the -MO=Concise option. First, we do normal in-place sorting to see what we'd expect:

$ perl -E'say $^V' v5.18.2 $ perl -MO=Concise -e'my @arr; @arr = sort @arr' 8 <@> leave[1 ref] vKP/REFC ->(end) 1 <0> enter ->2 2 <;> nextstate(main 1 -e:1) v:{ ->3 3 <0> padav[@arr:1,2] vM/LVINTRO ->4 4 <;> nextstate(main 2 -e:1) v:{ ->5 - <1> ex-aassign vKS/64 ->8 - <1> ex-list lK ->- 5 <0> pushmark s ->6 7 <@> sort lK/INPLACE ->8 6 <0> padrange[@arr:1,2] l/1 ->7 - <0> padav[@arr:1,2] lRM* ->7 - <1> ex-list lK ->- - <0> ex-pushmark s ->- - <0> ex-padav lRM* ->- -e syntax OK

Interesting: <@> sort lK/INPLACE ->8, which seems to sort in place. Now let's do the same thing with references:

$ perl -MO=Concise -e'my $ref; @$ref = sort @$ref' e <@> leave[1 ref] vKP/REFC ->(end) 1 <0> enter ->2 2 <;> nextstate(main 1 -e:1) v:{ ->3 3 <0> padsv[$ref:1,2] vM/LVINTRO ->4 4 <;> nextstate(main 2 -e:1) v:{ ->5 d <2> aassign[t4] vKS/COMMON ->e - <1> ex-list lK ->a 5 <0> pushmark s ->6 9 <@> sort lK ->a 6 <0> pushmark s ->7 8 <1> rv2av[t3] lK/1 ->9 7 <0> padsv[$ref:1,2] s ->8 - <1> ex-list lK ->d a <0> pushmark s ->b c <1> rv2av[t2] lKRM*/1 ->d b <0> padsv[$ref:1,2] sM/DREFAV ->c -e syntax OK

I do not see an inplace flag in <@> sort lK ->a. So the optimization only seems to work when using the same variable, not when using the same array. But this means we can sort array references in place if we alias an array variable to the array referenced by some scalar (using Data::Alias):

perl -MData::Alias -MO=Concise -e'my $ref; alias my @arr = @$ref; @arr = sort @arr' e <@> leave[1 ref] vKP/REFC ->(end) 1 <0> enter ->2 2 <;> nextstate(main 1 -e:1) v:{ ->3 3 <0> padsv[$ref:1,3] vM/LVINTRO ->4 4 <;> nextstate(main 2 -e:1) v:{ ->5 - <1> entersub vKS/INARGS ->a ... a <;> nextstate(main 3 -e:1) v:{ ->b - <1> ex-aassign vKS/64 ->e - <1> ex-list lK ->- b <0> pushmark s ->c d <@> sort lK/INPLACE ->e c <0> padrange[@arr:2,3] l/1 ->d - <0> padav[@arr:2,3] lRM* ->d - <1> ex-list lK ->- - <0> ex-pushmark s ->- - <0> ex-padav lRM* ->- -e syntax OK

… and the inplace-flag is there again <@> sort lK/INPLACE ->e :-)

This means that Eric Strom's answer is incorrect.

Answer2:

Since perl 5.8.4, the in place sort @a = sort @a is optimized. See the links below for details:

Performance Enhancements in perl584delta

http://perl5.git.perl.org/perl.git/commit/fe1bc4cf71e7b04d33e679798964a090d9fa7b46?f=pp_sort.c

+ /* optimiser converts "@a = sort @a" to "sort \@a"; + * in case of tied @a, pessimise: push (@a) onto stack, then assign + * result back to @a at the end of this function */

So you should be able to write:

@$intervals = sort by_position @$intervals

And in perl's later than 5.8.3 you will see reduced memory usage (and preservation of aliasing for the rare times it matters).

Answer3:

The second example will create a new reference: $x = [ qw( a c b ) ]; say $x; @$x = sort @$x; say $x; $x = [sort @$x]; say $x. <strike>The first example does what you wish.</strike> ref.

Recommend

  • R: Random sampling an even number of observations from a range of categories
  • can't add multicast group
  • Special characters in property name
  • How do I tabulate across an entire R data frame?
  • How can I speed up this row-by-row operation in data.table
  • create a cocossharp project in xamarin
  • pure javascript dom dynamic insert, update and delete
  • How to include Web reference endpoint configuration in another project
  • VBA: Extract Top 'x' Entries from each category
  • Bokeh 0.7.1: Dynamically Add Plot to Bokeh-Server Generated Existing Page
  • SEO friendly 301 redirect .htm to .aspx
  • how to translate xml using xslt with complex rules
  • SSRS 2008 - Sorting within a group
  • C++ - Is destructor called when a vector holds objects?
  • Extract data between rows r
  • Why is it still possible to insert a foreign key that doesn't exist?
  • Ant: fileset “dir” attribute with a runtime expanded full path
  • What is Closure Compiler?
  • Pointer vs Reference difference when passing Eigen objects as arguments
  • How to select table rows/complete table?
  • LNK1104: cannot open file 'kernel32.lib'
  • How can I determine which routines MATLAB uses to solve a sparse matrix?
  • Wait for .each() .getJSON request to finish before executing a callback
  • Entity Framework ObjectContext: Concurrency
  • Want to understand iframe breakout code
  • Can my PDF ping my server when it is opened?
  • Monotouch crashes with NullReferenceException on non nullable object
  • Access object instance inside an event handler
  • Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE
  • How to get links to open in the native browser in iOS Meteor apps?
  • Pycharm: Marking a folder as 'sources root' is not recursive for subfolders
  • perl, mysql - fasting way to upload a csv file into mysql?
  • Get specific string
  • Eloquent paginate function in Slim 3 project using twig
  • Is there a perl module to validate passwords stored in “{crypt}hashedpassword” “{ssha}hashedpassword
  • Comma separated Values
  • How to CLICK on IE download dialog box i.e.(Open, Save, Save As…)
  • Bitwise OR returns boolean when one of operands is nil
  • MATLAB: Piecewise function in curve fitting toolbox using fittype
  • How to load view controller without button in storyboard?