就地对 Perl 数组进行排序

问题描述

我有一个数组的引用(称为 $intervals)，我想对这个数组中的值进行排序.数组中可能有大量值，所以我不想复制这些值.我目前的做法是这样的.

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);

但是，如果我正确理解 Perl，这确实会复制数组中的所有值.那正确吗?如果是这样，有没有办法对数组进行就地排序(使用对该数组的引用)?

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)?

推荐答案

Perl 允许使用习语 @arr = sort @arr 就地排序数组.与赋值运算符的正常行为相反，在这种情况下不会进行复制.但是，这种优化仅限于普通数组变量；它不适用于数组引用:

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:

让我们使用 -MO=Concise 选项深入了解.首先，我们进行正常的就地排序以查看我们期望的结果:

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

有趣:sort lK/INPLACE ->8，这似乎排序就位.现在让我们对引用做同样的事情:

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

我在 <@> 中没有看到就地标志排序 lK -> a.所以优化似乎只在使用相同的变量时有效，在使用相同的数组时无效.但这意味着如果我们将数组变量别名为某个标量引用的数组(使用 数据::别名):

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

... 然后就地标志又出现了 排序 lK/INPLACE ->e :-)

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

这意味着 Eric Strom 的回答不正确.

这篇关于就地对 Perl 数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！