关于使用 Schwartzian 变换的 Perl 排序的建议

Question

我一直在看一篇关于在 Perl 中使用正则表达式对数组进行排序的旧文章 post。原来的post是here

我很难完全理解被选为“正确”答案的脚本。原来的 post 是关于对下面的数组进行排序的：

  my @array = (
  "2014 Computer Monitor 200",
  "2010 Keyboard 30",
  "2012 Keyboard 80",
  "2011 Study Desk 100"
);

问题是如何在 perl 中使用正则表达式按年份、项目名称和价格对整个数组进行排序？例如，如果用户想按价格排序，他们输入 'price' 并且排序如下：

2010 Keyboard 30
2012 Keyboard 80
2011 Study Desk 100
2014 Computer Monitor 200

提出了一个解决方案，它使用施瓦兹变换。我刚刚开始了解这个，这个脚本与我见过的其他例子有点不同。被选为正确答案的脚本如下。我正在寻找有关其工作原理的建议。

   my $order = "price";
   my @array = (
  "2014 Computer Monitor 200",
  "2010 Keyboard 30",
  "2012 Keyboard 80",
  "2011 Study Desk 100"
);

my %sort_by = (
  year  => sub { $a->{year}  <=> $b->{year} },
  price => sub { $a->{price} <=> $b->{price} },
  name  => sub { $a->{name}  cmp $b->{name} },
);
@array = sort {

  local ($a, $b) = map {
    my %h; 
    @h{qw(year name price)} = /(\d+) \s+ (.+) \s+ (\S+)/x;
    \%h;
  } ($a, $b);
  $sort_by{$order}->();

} @array;

# S. transform
# @array =
#  map { $_->{line} }
#  sort { $sort_by{$order}->() }
#  map { 
#    my %h = (line => $_); 
#    @h{qw(year name price)} = /(\d+) \s+ (.+) \s+ (\S+)/x;
#    $h{name} ? \%h : ();
#  } @array;

use Data::Dumper; print Dumper \@array;

我知道脚本使用正则表达式 /(\d+) \s+ (.+) \s+ (\S+)/x 来匹配年份名称和价格。

我认为脚本的其余部分如下所示：

• 第 14 行的初始排序一次从@array 中获取两个项目，一个在 $a 中，一个在 $b 中

• map 函数然后获取项目 $a 和 $b 并将每个项目映射到一个散列 - 每个项目都变成一个具有键 'year'、'price' 和 'name.这是基于正则表达式 /(\d+) \s+ (.+) \s+ (\S+)/x

• 将两个散列映射returns 作为局部变量$a 和$b 的引用

• 我认为有必要使用本地的$a 和$b，否则排序将使用在第17 行排序开始时采用的默认$a 和$b？

• 'price' 排序函数作为代码引用存储在 %sort_by 哈希

中

• 这在 $a 和 $b

的本地版本上由代码 $sort_by{$order}->() 在第 26 行调用

重复此操作，直到第 14 行中的所有项目都返回到@array

任何人都可以告诉我我在这里的路线是否正确，或者纠正任何误解。您还可以建议使用本地 $a 和 $b 变量。

谢谢 J

Answer 1

A Schwartzian 变换 是一种避免多次计算排序键的方法，就像在解决方案中一样 - local ($a,$b)

一个S.tranform的步骤基本上是：

使用 Map 通过计算的排序键丰富列表元素。这里，%h 用作新元素，包含原始行 line
使用 Sort 对此富豪榜进行排序。 sort 有点脏 $a $b 魔法。
使用 Map 提取原始列表元素。这里通过提取line键。

关于$a $b

的注释

非常遗憾，$a 和 $b 在 Perl 中是全局变量。它们通常会在 sort 块内自动分配。喜欢 sort { $a <=> $b } (3,2,1)

这解释了为什么即使比较元素没有作为排序子参数给出，S. 解决方案仍然有效。它还解释了 local 的必要性（另一个假装全局变量是局部变量的 Perl 恐怖），因此天真的解决方案的排序函数在 $a, $b.

中获得正确的值

我强烈建议您忘记这一点并避免隐式使用比排序块本身更深的 $a 和 $b。

一个更容易理解的版本是：

my $order = "price";
my @array = (
  "2014 Computer Monitor 200",
  "2010 Keyboard 30",
  "2012 Keyboard 80",
  "2011 Study Desk 100"
);

my %sort_by = (
  year  => sub { shift->{year}  <=> shift->{year} },
  price => sub { shift->{price} <=> shift->{price} },
  name  => sub { shift->{name}  cmp shift->{name} },
);

my @sorted = 
  map { $_->{line} }
  sort { $sort_by{$order}->($a, $b) }
  map { 
    my %h = (line => $_); # $_ is the array element (the input line)
    @h{qw(year name price)} = ( $_ =~ /(\d+) \s+ (.+) \s+ (\S+)/x );
    # Did the regex capture a name, i.e. did it work?
    if( $h{name} ){
        \%h
    } else{
        (); # Empty array will cause the invalid line to disappear, but you can choose to do something else with it.
    }
  } @array;
  
print(join("\n", @sorted))

关于使用 Schwartzian 变换的 Perl 排序的建议

Advice on Perl sort that uses Schwartzian transform

arrays

sorting

perl