如何以任意顺序对Perl列表进行排序？

Question

我有一个字符串的列表，其值来自一个固定的集合。我需要按任意顺序对此列表进行排序。

该集合的顺序由另一个所有可能的字符串列表指定，按照数组顺序排列。

下面是一个例子：

my @all_possible_strings_in_order = ('name', 'street', 'city','state', 'postalcode'); 

my @list_that_needs_to_be_sorted = ('city', 'state', 'name'); 

我在Perl的工作。我认为我最好的选择是自动创建一个将字符串与序号相关联的散列，然后通过引用这些序号进行排序。

该集合中有大约300个可能的字符串。典型的列表将有30个需要排序的字符串。这不会在紧密的循环中被调用，但它也不会很慢。由于程序的结构，无法提前完成自动构建序号散列。

我很乐意提供更好的方法来解决这个问题。谢谢！

编辑：你们真棒。今晚我再也不能抬头了，但明天早上我会花时间去真正理解你的建议......现在是我熟练使用map（）和grep（）的时候了。

Answer 1

设置字符串和各自的岗位之间的关联与

# Define your custom order of all possible strings. 
my @custom_order = qw/ name street city state postalcode /; 

my %order = map +($custom_order[$_] => $_), 0 .. $#custom_order; 

现在，您可以创建一个Perl的sort操作者使用的比较功能：

sub by_order { $order{$a} <=> $order{$b} } 

例如：

my @sorted = sort by_order qw/ city state name /; 
print "@sorted\n"; 
# prints: name city state 

Answer 2

这是一个非常简单的想法。

从您的未排序列表中取出您的第一个字符串，在您的主列表中搜索它，在主列表中找到它的索引，然后将它放入列表中，并跟踪索引。

把你的第二个字符串，在主列表中找到它的索引。如果该指数大于第一个，则将其放在第一个后面的新列表中，否则放在前面。

保留所有剩余的字符串，维护所有索引的列表，以便您始终知道将下一个字符串放置在哪里，重新排序已排序的字符串。

希望这是明确的足以帮助。

约翰·多纳

Answer 3

如果你有Perl 5.10，你可以使用这个（简称为清楚起见名）：

use feature 'state'; 

sub bylist { 
    state %hash = map { $all_possible[$_] => $_ } 0 .. $#all_possible; 
    $hash{$_[0]} cmp $hash{$_[1]}; 
} 

my @sorted = sort bylist @list_to_sort; 

的state关键字创建用C被称为一个static变量 - 这是本地到bylist子例程，但不会重新初始化。这样，您不必事先设置任何东西，但不必每次重新计算值就可以使用它。

我相信在老版本的Perl中有这种情况发生，但我不会使用它。如果你没有5.10，只需使用gbacon's想法，他无耻地偷了我的大脑，而我打字这一点：P

Answer 4

最天真的方式来做到这一点将是基于比较函数进行排序，其中比较如果我理解正确，函数comp（a，b）=“a和b中的哪一个在主列表中首先出现？”。

所以是的，你的想法看起来是正确的。如果您需要对@all_possible_strings_in_order进行更改，那么您应该构建整个地图一次。如果订单列表发生了各种变化，您可以通过一些聪明的懒惰搜索获得一些速度，但也许不会。

my %order; 
my $i = 0; 
foreach my $s (@all_possible_strings_in_order) { 
    $order{$s} = $i++; 
} 

my @sorted = sort {$order{$a} <=> $order{$b}} @list_that_needs_to_be_sorted; 

我想这应该是相当快的。

Answer 5

一种不同的方法（之一，如果要排序的列表可以有需要保留复制将无法工作）：

my %set; 
@set{ @list_that_needs_to_be_sorted } =(); 
my @sorted = grep exists $set{$_}, @all_possible_strings_in_order; 

Answer 6

你可以去接管主列表，将任何元素发生在结果列表的未排序列表中，同时将它从未排序列表中删除。如果你的未排序列表很短（从你的例子来看，我估计大约有5个元素），这应该比每次构建散列表更快更小（你说你事先不能做到这一点）。

优化可能是从未排序列表中创建一个特里结构，但是这是否更好取决于每个列表的大小。

Answer 7

Sort::ByExample使这很容易，还让我们指定后备排序，以防未预料到的值最终在您的列表中。为了保持简单，我会在这里留下一些回退。

use Sort::ByExample qw(sbe); 

my @all_possible_strings_in_order 
    = ('name', 'street', 'city', 'state', 'postalcode'); 

my @list_that_needs_to_be_sorted = ('city', 'state', 'name'); 
my $sorter = sbe(\@all_possible_strings_in_order); 

my @sorted = $sorter->(@list_that_needs_to_be_sorted);