O(n) Тяжеловесы с O(1/ эпсилон) пробелом?

Question

Я знаю о следующем алгоритме для тяжеловесов:

Algorithm findHeavyHitters(epsilon, inputStream)
    integer k = ceiling(1 / epsilon) - 1
    initialize hashmap H of size k

    while an item i from the input stream arrives:
        if H[i] exists
            increment the value associated with H[i]
        elsif number of items in H < k
            put H[i] into map with value of 1
        elseif there exists an entry j with a value of 0
            remove j and put H[i] into map with value of 1
        else
            decrement all values in H by 1
    endwhile

    return H

Поправьте меня, если я ошибаюсь, но этот алгоритм не работает в O(n). Можно ли изменить этот алгоритм так, чтобы он работал в O (n), сохраняя при этом использование пространства O(1/epsilon)?

Для потока данных смысл алгоритма состоит в том, чтобы вернуть самые верхние элементы epsilon*t. Эпсилон задается в процентах (например, ввод 0,1 для данных, которые происходят не менее 10% времени).

Answer 1

Алгоритм выполняется в среднем времени O(n), исходя из того, что поиск хеша в среднем равен O(1).

Есть две детали реализации. Во-первых, последний шаг, который включает в себя касание каждого значения в H:

• уменьшить все значения в H на 1

Чтобы сделать это O(1), мы добавим еще одну ячейку памяти, которая называется base, который инициализируется в 0. Затем мы модифицируем алгоритм следующим образом:

while an item i from the input stream arrives:
    if H[i] exists
        increment the value associated with H[i]
    elsif number of items in H < k
        put H[i] into map with value of base + 1
    elseif there exists an entry j with a value of base 
        remove j and put H[i] into map with value of base + 1
    else
        increment base
endwhile

Вторая проблема - найти запись со значением base (или 0) в O(1). Это можно сделать, сохранив элементы в "гребне": связанном списке двухсвязных списков. Каждый внутренний связанный список содержит записи с определенным количеством. Внешний связанный список содержит списки счетчиков в порядке их количества, причем заголовок указывает на список с наименьшим количеством. Если вы рисуете эту структуру данных, она выглядит как гребень:

[  base    ] -> entry a -> entry b -> entry c
    |
[ base + i ] -> entry d
    |
[ base + j ] -> entry e -> entry f
    |
   etc.

Хеш-таблица теперь указывает на записи, а не содержит их. Чтобы увеличить количество отдельной записи, запись удаляется из ее списка (если список содержит более одного элемента) и либо вставляется в следующий список, либо помещается в список из одного элемента, который вставляется после списка, в котором он находился. в зависимости от количества, связанного со следующим списком. Эта операция O(1).

Структура данных гребня по-прежнему равна O(k), где k - количество элементов в хэше, поскольку не может быть более различного количества элементов, чем элементов.

Вместо двусвязных списков вы можете использовать простой массив и список индексов первой записи с каждым счетчиком. Чтобы переместить запись в следующий сегмент подсчета, вы начинаете с того, что заменяете ее последней записью с этим счетом, а затем либо продвигаете начало следующего списка подсчета, либо вставляете новую запись списка подсчета, в зависимости от того, является ли отсчет следующего списка подсчета. один больше или больше чем один больше. Чтобы выполнить перестановку, необходимо обновить расположение двух поменяемых записей в хэше, но это все равно O(1).