如何以任意順序對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);