Jak mogę posortować listę Perla w dowolnej kolejności?

Question

Mam listę ciągów, których wartości pochodzą z ustalonego zestawu. Muszę posortować listę w dowolnej kolejności.

Kolejność zestawu jest określona przez inną listę wszystkich możliwych ciągów, posortowaną w kolejności w tablicy.

Oto przykład:

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

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

pracuję w Perlu. Myślę, że najlepiej jest automatycznie utworzyć mieszanie, które łączy łańcuchy z liczbami porządkowymi, a następnie sortować według tych liczb porządkowych.

Istnieje około 300 możliwych ciągów w zestawie. Typowe listy będą miały 30 ciągów, które należy posortować. Nie będzie to wywoływane w ciasnej pętli, ale nie może też być wolne. Automatyczne budowanie haszu porządkowego nie może być wykonane z wyprzedzeniem ze względu na strukturę programu.

Jestem otwarty na sugestie dotyczące lepszych sposobów na zrobienie tego. Dzięki!

Edytuj: Jesteście niesamowici. Nie mogę dziś więcej wytrzymać, ale jutro rano poświęcam czas, aby naprawdę zrozumieć twoje sugestie ... Najwyższy czas, abym stał się biegły w zakresie map() i grep().

Answer 1

Ustaw stowarzyszenie między ciągi i ich stanowisk z

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

Teraz można utworzyć funkcję porównawczą dla użytku z Perl sort operatora:

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

Na przykład:

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

Answer 2

Oto pomysł, który jest dość prosty.

Weź pierwszy ciąg z nieposortowanej listy, wyszukaj go na głównej liście, znajdź jego indeks na liście głównej, umieść go na liście i śledź indeks.

Weź drugi ciąg, znajdź jego indeks na liście głównej. jeśli ten indeks jest większy niż pierwszy, umieść go na swojej nowej liście za pierwszą, w przeciwnym razie z przodu.

Zachowaj to dla wszystkich pozostałych ciągów, utrzymując listę wszystkich indeksów, aby zawsze wiedzieć, gdzie umieścić następny ciąg na już posortowane struny.

Mam nadzieję, że jest to wystarczająco jasne, aby pomóc.

John Doner

Answer 3

Jeśli masz Perl 5.10, można użyć to (nazwy skrócone dla jasności):

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 kluczowe stwarza to, co w C jest znany jako zmienna static - to lokalny do podprogramu bylist, ale nie zostanie on ponownie zainicjowany. W ten sposób nie musisz niczego wcześniej ustawiać, ale nie musisz ponownie obliczać wartości za każdym razem, gdy chcesz z niej skorzystać.

Wierzę, że jest hack, aby tak się stało w starszych Perls, ale nie użyłbym go. Jeśli nie masz 5.10, po prostu użyj gbacon's idei, którą bezwstydnie ukradł z mojego mózgu, pisząc to: P

Answer 4

Najbardziej naiwnym sposobem na to byłoby sortowanie w oparciu o funkcję porównania, gdzie porównanie function comp (a, b) = "który z aib znajduje się na pierwszym miejscu listy głównej?", jeśli dobrze rozumiem.

Więc tak, twój pomysł wygląda dobrze. Jeśli musisz zrobić wiele rodzajów między zmianami do @all_possible_strings_in_order, powinieneś zbudować całą mapę raz. Jeśli lista zamówień zmieni się w dowolny sposób, możesz uzyskać pewną prędkość dzięki sprytnemu leniwemu wyszukiwaniu, ale może nie.

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; 

Wyobrażam sobie, że powinno to być dość szybkie.

Answer 5

Inne podejście (taki, który nie będzie działać, jeśli lista mają być sortowane może mieć duplikaty, które muszą być zachowane):

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

Answer 6

można po prostu iść na głównej listy i wcisnąć dowolny element, który występuje na nieposortowanej liście na liście wyników, usuwając ją z listy nieposortowanej. Jeśli twoja nieposortowana lista jest krótka (z twojego przykładu, liczę około 5 elementów), to powinno być szybsze i mniejsze niż budowanie tablic mieszających za każdym razem (powiedziałeś, że nie możesz tego zrobić wcześniej).

Optymalizacja może polegać na wylosowaniu listy nieposortowanej, ale to, czy jest to lepsze, zależy od wielkości każdej listy.

Answer 7

czyni to całkiem łatwo, a także pozwala określić sortowanie awaryjne w przypadku, gdy nieprzewidziane wartości znajdą się na liście. Opuszczę tutaj awarie, żeby wszystko było proste.

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