Сортировать массив Perl на месте?

Question

У меня есть ссылка на массив (называемый $intervals), и я хотел бы отсортировать значения в этом массиве.Возможно, что в массиве может быть огромное количество значений, поэтому я бы предпочел не копировать значения.Мой текущий подход заключается в следующем.

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

Однако, если я правильно понимаю Perl, это действительно скопирует все значения в массиве.Это правильно?Если так, есть ли способ, которым я могу сделать массив на месте (используя ссылку на этот массив)?

Answer 1

Perl позволяет сортировать массивы на месте с идиомой @arr = sort @arr.Вопреки нормальному поведению оператора присваивания, в этом случае копии не будут создаваться.Однако эта оптимизация ограничена обычными переменными массива;он не будет работать с ссылками на массивы:

Давайте рассмотрим тайник с помощью опции -MO=Concise.Во-первых, мы делаем обычную сортировку на месте, чтобы увидеть, что мы ожидаем:

$ 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, что, кажется, сортирует на месте.Теперь давайте сделаем то же самое со ссылками:

$ 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

Я не вижу флаг вставки в <@> sort lK ->a.Таким образом, оптимизация работает только при использовании одной и той же переменной, а не при использовании одного и того же массива.Но это означает, что мы можем отсортировать ссылки на массивы на месте, если добавим псевдоним переменной массива к массиву, на который ссылается некоторый скаляр (используя 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

… и местофлаг снова там <@> sort lK/INPLACE ->e: -)

Это означает, что Эрик Стром ответил неверно.

Answer 2

Начиная с Perl 5.8.4, сортировка по месту @a = sort @a оптимизирована. Смотрите ссылки ниже для деталей:

Улучшения производительности в 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 */

Итак, вы должны написать:

@$intervals = sort by_position @$intervals

А в Perl более поздней версии, чем 5.8.3, вы увидите уменьшение использования памяти (и сохранение псевдонимов в тех редких случаях, когда это важно).

Answer 3

Во втором примере будет создана новая ссылка: $x = [ qw( a c b ) ]; say $x; @$x = sort @$x; say $x; $x = [sort @$x]; say $x. Первый пример делает то, что вы хотите. ref .