Perl: числовая сортировка массивов в хеше 2 (преобразование Шварца)

На самом деле это продолжение этой темы: Perl: числовая сортировка массивов в хеше

Я не мог отредактировать исходный вопрос, потому что мой текущий код немного отличается, поэтому я просто задаю это как еще один вопрос.

Хорошо, после использования преобразования Шварца у меня есть это:

my @mylines =("0.899 0.92 cat", 
            "9.999 0.001 dog",
            "-0.52 0.3 humpty", 
            "13.52 0.09 bumbo",
            "-1.52 0.98 nanny",
            "3.52 0.34 lala");

my @sorted = map { join ' ', @$_ }
             reverse sort { $a->[0] cmp $b->[0] or $a->[1] <=> $b->[1] }
             map { [ split ] } (@mylines);

print "$_\n" for @sorted;

Я ожидал, что вывод будет отсортирован сначала по первому столбцу, затем по второму, но получается так:

9.999 0.001 dog
3.52 0.34 lala
13.52 0.09 bumbo
0.899 0.92 cat
-1.52 0.98 nanny
-0.52 0.3 humpty

Я полагаю, это потому, что он выполняет сортировку символов... но мне нужна численная сортировка. Нужно ли мне помещать java-подобный «parseInt ()» где-нибудь в функцию сортировки?


arrays sorting perl numerical
person user961627    schedule 31.10.2011    source источник
comment
Нет, вам нужно прочитать perldoc perlop и отметить разницу между cmp и <=>.   -  person Dave Cross    schedule 31.10.2011
comment
Я подозреваю, что вы обнаружите, что в этом случае ST действительно замедляет работу. Просто чтобы вы знали.   -  person ikegami    schedule 31.10.2011

Ответы (1)


arrow_upward
3
arrow_downward

Вы делаете cmp в первом столбце. Это означает, что он сортирует его как текст. Ваша функция сортировки должна быть:

sort { $a->[0] <=> $b->[0] or $a->[1] <=> $b->[1] } ...

Что делает вывод:

13.52 0.09 bumbo
9.999 0.001 dog
3.52 0.34 lala
0.899 0.92 cat
-0.52 0.3 humpty
-1.52 0.98 nanny

Однако вам никогда не нужно ставить reverse перед сортировкой, потому что вы всегда можете поменять местами условия:

sort { $b->[0] <=> $a->[0] or $b->[1] <=> $a->[1] } ...
person Axeman    schedule 31.10.2011
comment
Можно также утверждать, что лучше всегда использовать reverse, так как это делает более очевидным, что вы выполняете обратную сортировку. Кроме того, использование reverse означает, что во многих случаях вам не нужно указывать выражение для сортировки. - person jamessan; 31.10.2011
comment
@Jamessan - хотя удобочитаемость является очень серьезной проблемой, в этом случае добавление операций O (N) для обращения массива может быть слишком высокой стоимостью, чтобы платить за это. Лучше добавить комментарий, поясняющий, что b‹=›a — это реверс). - person DVK; 31.10.2011
comment
@DVK: Согласно hobbs оптимизатор понимает, что reverse sort { $a <=> $b} эквивалентен sort { $a <=> $b }. Я думаю, это означает, что никаких дополнительных накладных расходов не возникает - person Zaid; 31.10.2011
comment
@jamessan, поскольку каждое поле сортируется индивидуально, наличие одного reverse впереди не добавляет удобочитаемости. - person ikegami; 31.10.2011
comment
@DVK, если вы собираетесь использовать анализ Big-Oh, O (N) + O (N log N) по-прежнему равно O (N log N). - person ikegami; 31.10.2011
comment
@ Zaid, sort { $a <=> $b } и reverse sort { $a <=> $b } действительно являются особыми случаями, но здесь они не используются. reverse sort { f($a) <=> f($b) } тоже немного оптимизирован, но не до такой же степени. (sort быстро меняет порядок элементов в самом стеке перед возвратом вместо использования reverse операции для этого.) Возникают накладные расходы. - person ikegami; 31.10.2011
comment
Мой предыдущий комментарий должен был читаться как reverse sort { $a <=> $b} эквивалентно sort { $b <=> $a} - person Zaid; 31.10.2011
comment
@Zaid, верно, но мой ответ все еще актуален. - person ikegami; 31.10.2011
comment
@ikegami: мне любопытно, где задокументировано это поведение. Никогда не сталкивался с этим в perldoc. Кажется, это хороший вопрос. - person Zaid; 31.10.2011
comment
@ Zaid, это оптимизация, и она не задокументирована. См. OPpSORT_REVERSE в pp_sort.c. - person ikegami; 31.10.2011
comment
@ikegami, вот почему я сказал во многих случаях, а не во всех случаях. Люди, очевидно, должны оценить, какие компромиссы есть в коде, который они пишут, например, профилирование, чтобы увидеть, действительно ли накладные расходы на явный реверс имеют значение в более крупной схеме конкретной кодовой базы. Ни один из ответов не является правильным во всех случаях, что я и пытался показать, дойдя до противоположной крайности: никогда не использовать reverse. - person jamessan; 31.10.2011
comment
@Zaid - пожалуйста, спросите, или я украду идею и спрошу :)))) Отличное замечание @ikegami! - person DVK; 31.10.2011
comment
@jamessan сравните, никогда не нужно ставить реверс, чтобы никогда не использовать реверс. - person Axeman; 31.10.2011
comment
@jamessan, это неправда, вы сказали, что некоторые утверждают, что это всегда лучше: можно также утверждать, что лучше всегда использовать reverse, так как это делает более очевидным, что вы Делаем обратную сортировку. Во многих случаях применяется к чему-то еще, что вы сказали. - person ikegami; 01.11.2011
comment
@jamessan, мне кажется, то, что я помещаю в блок сортировки, - это спецификация того, как я хочу, чтобы он был отсортирован. Я думаю, что более запутанно сказать ... и принять обратное, а не просто указать это. Я был бы более склонен использовать reverse sort @array, зная базовое поведение. - person Axeman; 01.11.2011