Сортировка хешей по длине значения при сохранении порядка - PullRequest
Новая
       19

Сортировка хешей по длине значения при сохранении порядка

0 голосов
/ 17 сентября 2018

В настоящее время я пишу Perl-скрипт для сортировки строк из stdin и печати строк в порядке длины строки, сохраняя при этом порядок одинаковых.Мой код сортировки состоит из следующего: 

while (my $curr_line = <STDIN>) {
    chomp($curr_line);
    $lines{$curr_line} = length $curr_line;
}

for my $line (sort{ $lines{$a} <=> $lines{$b} } keys %lines){
    print $line, "\n";
}

Например, мой стандартный ввод состоит из следующего: 

tiny line
medium line
big line
huge line
rand line
megahugegigantic line

Я бы получил следующий вывод: 

big line
rand line
tiny line
huge line
medium line
megahugegigantic line

Есть ли способ, которым я могу сохранить порядок для линий равной длины, чтобы крошечные предшествовали огромным, что предшествует ранду?Кроме того, кажется, что порядок меняется каждый раз, когда я запускаю скрипт.

Заранее спасибо

Ответы [ 4 ]

0 голосов
/ 17 сентября 2018

Как было объяснено, случайность исходит от использования хеш-ключей для хранения строк.Нет необходимости в этом или в чем-то более сложном, например, преобразование Шварца , чтобы сделать эту работу

Все версии Perl, начиная с версии 5.8, использовали stable sort, который будет сохранять значения, которые сортируются одинаково в том же порядке.Но вы можете настаивать на том, что оператор sort, который вы получаете, является стабильным оператором, использующим прагму sort с 

use sort 'stable'

Вот как я написал бы вашу программу.Он прекращает чтение ввода в конце файла или, когда видит пустую строку, если вы хотите ввести данные с клавиатуры 

use strict;
use warnings 'all';
use feature 'say';
use sort 'stable';

my @list;

while ( <> ) {
    last unless /\S/;
    chomp;
    push @list, $_;
}

say for sort { length $a <=> length $b } @list;

При использовании того же ввода, что и в вопросе, получается

выход 

big line
tiny line
huge line
rand line
medium line
megahugegigantic line
0 голосов
/ 17 сентября 2018

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

Ваша проблема в том, чтовы храните строки в хэше.Хеш - это неупорядоченный набор пар ключ-значение, поэтому добавление строк в хэш и последующая их распечатка без сортировки даст вам строки в случайном порядке.

Вам нужно прочитать все строкив массив и затем сортировать их по длине, самый быстрый способ - использовать преобразование Шварца , см. ниже. 

my  @lines = <STDIN>;
chomp(@lines);

my @sorted = # This is the clever bit and needs to be red from the last map up
    map { $_->[0] } # Get the lines
    sort { $a->[1] <=> $b->[1] }  # Sort on length
    map { [$_, length $_] } # Create a list of array refs containing
        # the line and the length of the line
    @lines;

print join "\n", @sorted; # print out the sorted lines
0 голосов
/ 17 сентября 2018

Нигде вы не храните исходный заказ, так что вы не можете его отсортировать.Самое простое решение - сохранить строки в массиве и убедиться, что Perl использует стабильную сортировку. 

use sort 'stable';

my @lines = <>;
chomp(@lines);

for my $line ( sort { length($a) <=> length($b) } @lines) {
   say $line;
}

[ ST для этого излишне.Это настолько излишне, что это, вероятно, даже замедляет ход событий! ]

0 голосов
/ 17 сентября 2018

Одно из возможных решений

Вы можете сохранить положение строки в дескрипторе входного файла, а также length.Волшебная переменная $. ( номер строки ввода ) обеспечивает это.Затем вы можете отсортировать оба значения. 

use strict;
use warnings;

my %lines;
while ( my $curr_line = <DATA> ) {
  chomp($curr_line);
  $lines{$curr_line} = [ length $curr_line, $. ];
}

for my $line (
  sort {
       $lines{$a}->[0] <=> $lines{$b}->[0]
    || $lines{$a}->[1] <=> $lines{$b}->[1]
  } keys %lines
) {
  print $line, "\n";
}

__DATA__
tiny lin1
medium line
big line
huge lin2
rand lin3
megahugegigantic line

Это всегда будет выводить 

big line
tiny lin1
huge lin2
rand lin3
medium line
megahugegigantic line

Конечно, вы также можете использовать хеш, чтобы сделать код более читабельным. 

$lines{$curr_line} = { 
  length   => length $curr_line, 
  position => $., 
};

Объяснение вашей реализации

Ваши результаты каждый раз меняли свой порядок из-за случайного упорядочивания хешей.Способ keys возвращает список ключей случайным образом из-за способа, которым Perl реализует хеши.Это по замыслу и функция безопасности.Поскольку существует несколько ключей с одинаковым значением, сортировка иногда будет возвращать разные результаты, в зависимости от того, какой из ключей с равным значением был первым.

Вы можете уменьшить это, вставив еще один sort передВаш keys звонок.Это позволит отсортировать ключи по имени, по крайней мере, чтобы порядок нежелательного результата был согласованным. 

#                                               vvvv
for my $line (sort{ $lines{$a} <=> $lines{$b} } sort keys %lines) { ... }

Обратите внимание, что вам не нужно chompвведите, если вы положили \n обратно, когда вы print.В любом случае, она всегда одинаковой длины.Если вы это сделаете, вам следует print a $/, который является разделителем входных записей , который chomp удален, или вы фальсифицируете свои данные.

...