Получение максимального числа из постоянно обновляемого списка

Question

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

Допустим, у нас есть набор пар k, v, ключи являются строками, а значения являются целыми числами.Мы можем предположить, что есть фиксированный набор ключей (например, k1, k2, ..., kn).Есть какой-то агент, который непрерывно выталкивает эти пары k, v в систему, как поток.И все, что нам нужно сделать, это добавить текущее значение к старому значению для всех входящих пар.

Давайте рассмотрим пример.Во время t0 давайте предположим, что у нас есть следующие пары kv.

k1: 100
k3: 200

Во время t1 есть две входящие пары.k2: 50, k3: 150.Таким образом, на t1 состояние системы:

k1: 100
k2: 50
k3: 350

Цель состоит в том, чтобы выдать ключ, который имеет максимальное значение через периодический интервал.Я не могу придумать ни одного алгоритма, который дал бы лучшее время выполнения, чем max-heapify.Я думал о создании максимальной кучи, а затем обновлять ее по мере поступления новых данных.Для каждого обновления heapify() будет занимать максимум log(n) времени.При каждом вызове мы можем затем вернуть корень кучи.Но есть ли лучшее решение, чем это?

Answer 1

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

Answer 2

Доказательство реализации концепции Perl.Очевидно, что операторы отладки не должны учитываться во времени!

#!/usr/bin/perl -T

$maxv = undef;
%maxk = ();
%pairs = ();

sub updatekeys {
    my %newpairs = @_;
    warn "updating\n";
    while ( my ($k,$v) = each %newpairs ) {
        warn "testing $k:$v\n";
        my $newmax = $pairs{$k} += $v;
        if ( $newmax == $maxv ) {
            warn "appending $k\n";
            $maxk{$k}++;
        }
        elsif ( $newmax > $maxv ) {
            warn "new max ($newmax); overwriting $k\n";
            $maxv = $newmax;
            %maxk = ( $k=>1 );
        }
    }
    warn sprintf "max=$maxv; k=( %s ); pairs=( %s )\n",
        ( join ',', sort keys %maxk ),
        ( join " ", map {"${_}:$pairs{$_}"} sort keys %pairs );

}

updatekeys ( k1=>100, k2=>200 );
updatekeys ( k2=>50, k3=>150 );

Если v может быть отрицательным, это не сработает.

Answer 3

Это зависит (1), являются ли все обновления монотонными (2) от вашей модели вычислений.

Если значения только когда-либо увеличиваются (монотонные обновления), то, очевидно, вы можете просто поддерживать максимум всехзначения, которые когда-либо существовали в памяти в постоянное время.

В противном случае, если значения являются маленькими целыми числами, вы можете использовать Y-быстрый три * , чтобы улучшить время выполнения до O(log log M) где M - максимальное значение.

Если разрешены только сравнения, тогда Theta(log n) - лучшее, что вы можете сделать, потому что эту структуру можно адаптивно использовать для сортировки и сортировки n элементов.требует O(n log n) сравнения.Учитывая несортированный массив, вставьте каждый элемент под другим ключом.Запросите максимум, установите его ключ в минус бесконечность (или какое-то значение меньше, чем элемент min) и повторите, чтобы считывать элементы в порядке убывания.