Что такое однострочник с низкой вычислительной сложностью для возврата двух самых больших значений массива?

Question

Это скорее вопрос «мне интересно, если это возможно», чем вопрос «мне это действительно нужно», но в любом случае: я знаю, что если я хочу наименьшее значение в списке, используя сравнение пользовательских функций, я могу это сделатьлегко с List::Util::reduce.

my $biggest = reduce {comparison($a, $b) ? $b:$a} @myArray;

Но если я хочу, чтобы два самых больших значения в этом массиве?Опять же, с помощью всего лишь одного обхода массива.

Я могу сделать это, написав цикл for, но мне бы очень хотелось более преликтный однострочный.

---

Редактировать* Под только одним обходом массива я имел в виду, что вычислительная сложность не будет больше O(n).Сортировка всех статей не так эффективна, поскольку мне не нужно сортировать все , только два самых больших значения.

Но я, вероятно, слишком много спрашиваю:)

Answer 1

Чтобы найти максимум два значения в списке, вы можете перебрать значения с двумя переменными для хранения максимумов:

my @list = qw(3 1 2 5 9 7 8 6 4);

my ($x, $y) = (0, 0);

($x, $y) = $_ > $x ? ($_, $x) :
           $_ > $y ? ($x, $_) : next for @list;

say "$x $y";  # '9 8'

или вы можете использовать сгиб, чтобы уменьшить список:

use List::Util 'reduce';

my $max = reduce {
    $b > $$a[0] ? [$b, $$a[0]] : 
    $b > $$a[1] ? [$$a[0], $b] : $a
} [0, 0], @list;

say "@$max"; # '9 8'

Два решения эквивалентны, первое носит процедурный характер и требует внешнего состояния, второе - функционально и не требует. Первый, вероятно, быстрее, поскольку он не создает никаких внутренних массивов для хранения. Каждый из них зацикливается на списке только один раз, поэтому оба значения O(n)

Answer 2

Всегда есть (sort { compare($b, $a) } @array)[0 .. 1] - который работает для любого количества выходов, которое вы хотите, при условии, что вы стараетесь не брать больше элементов, чем существует в @array.Недостатком является то, что он выполняет больше работы по сортировке всего массива, чем на самом деле.

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

Answer 3

my @biggest_two = ( sort { $b <=> $a } @myArray )[0..1]

Answer 4

Я долго думал об этом. Я думаю, что логически мы можем доказать, что это невозможно сделать для общей функции сравнения comparison($a,$b).

При тестировании некоторой простой функции сравнения, скажем, например, >, можно использовать переходное свойство, которое, если a > b и b > c, то a > c, и, следовательно, можно каскадно искать наибольшее значение в одном проходить. Если вы хотите использовать это, чтобы найти два наивысших значения, вы можете сделать это тоже, но уже вы добавили сложность. Проверяемое число может быть больше обоих ИЛИ оно может быть только больше одного и меньше другого ИЛИ оно может быть меньше обоих. Тем не менее, это может быть учтено, как показано в этом простом сценарии.

#!/usr/bin/perl

use strict;
use warnings;

use List::Util 'shuffle';

my @array = shuffle (1..10);
my @out = (0,0); #(max, second)

map { $_>$out[0] ? ( unshift @out, $_ and pop @out) : $_>$out[1] ? $out[1] = $_ : () } @array;

print "$_\n" for @out;

Для действительно общего сравнения необходимо учитывать возможность того, что комбинация двух сравниваемых значений имеет значение, и в этом случае должна приниматься каждая парная комбинация. Фактически это НЕОБХОДИМО сделано выше, однако большинство тестов пропускаются, потому что благодаря переходному свойству мы знаем, что это безопасно.

Так что у вас это есть. Если ваш тест имеет переходные отношения, вы можете сделать что-то вроде того, что я делаю выше. Если нет, то sort придется сделать. Парни из Perl тратят много времени на то, чтобы сделать это быстро, так что, возможно, это не так уж и плохо.