Привет котаны-бротаны.

Очередная пятничная.

Дан поток данных имеющих целочисленные ключи. Поток бесконечный. У него есть точка начала
но нет конца.

Пример ключей.




В любой момент времени пользователь может запросить из него top 1000 элементов ранжированных по ключу.
Пример output:



Язык разработки: C++/Delphi/C# вобщем любой.

Алгоритмы и структуры данных: счетчики, биткарты, хештаблички, деревья... вобщем что угодно.
Единственное пожелание - чтоб были сорцы на для уточнения алгоритма.

Что мы не будем использовать
Базы данных и готовые коробочные продукты.

Физический смысл


P.S. Топик похож на топик Ивана но мы не будем обсуждаеть его тему.

Go-go кодить!!

Не знаю. Я - не азартный.

Пробовал приспособить бинарную кучу (или пирамиду). Но у нее нет строгого доказательства что top 1000 элементов
ляжет в лимитированную пирамиду в правильном порядке. Из гарантий - только максимум. Остальные
(листовые узлы) могут вытеснятся в случайном порядке.

На картинке показан кейс.



Наименьшим элементом является ключ "1" но он не индексируется для быстрого удаления. А если мы добавляем
новый элемент (допустим 101) то он спустит вниз поддерево узлов и вытеснен будет элемент с ключом "3" при
условии что мы сохраняем фиксированный размер кучи равно 9 элементов как показано на картинке.

Если снять ограничение на 9 элементов - тогда открыт вопрос - а сколько вообще надо хранить чтобы поднять top 1000.



По другим структурам.

Можно приспособить красно-черное дерево, но оно избыточно в стационарной фазе когда есть уже 1000 элементов
и нужно будет постоянно добавлять +1 элемент и выбрасывать еще -1. Ненужное число ре-балансов.

fkfka, а как устроен внутри SortedList?

Сортированный список? Неплохо для удаления хвостика. Но не очень быстро для вставки нового элемента.

У меня под рукой нет .Net компиллятора. Ты можешь сделать бенчмарк? Добавь например 1 млрд целых
чисел и скажи сколько времени это займет.

Всегда-ли куча будет хороша?

Возможен-ли кейс, когда красно-черное дерево лучше?

Давай я придумаю здравый смысл. Возможно он пригодится не для этого а для моих будущих топиков.
Потом просто кину ссылку сюда.

Есть приложение которое анализирует события мира ценных бумаг в разрезе одной биржи. Приложение
используют заинтерсованные лица (ЗЛ). Кто эти лица - мы не знаем. События - месседжи. Хотя не всякий
месседж нам интересен.

Здесь я могу немного ошибаться. Но нам может быть интересен например filled ордера. И нам может быть интересно
цена (= произведение цены ценной бумаги (price) на ее количество (quantity)). Заполнение ордера означает что
пакет ценных бумаг куплен.

Пример месседжа (я взял с Вики образец) https://ru.wikipedia.org/wiki/Financial_Information_eXchange.



В данном примере нас в сортировке бы интересовало произведение 15 штук акций * цену акции 15 $ = 225 $.
Только тип события не 35=D (новый ордер) а другой код связанный с заполнением количества штук
(я не помню его точно).

Какие поиски или какие views ЗЛ может заказывать - мы не знаем. Но пока мы собираем топы сделок в разрезе
всего торгового дня или в разреде какого-то конкретного тикера (например Microsoft/Apple/IBM).

Скорость реакции интерфейса - важна и наши заинтересованные не хотят долго ждать выборок из БД.

Наше приложение слушает события в этом формате (TCP/UDP/JMS/...e.t.c) по сетевым и прикладным протоколам
и публикует на экране топчик.

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

Я еще немного поборюсь за кучу (двоичную кучу или пирамиду).

Далее я с вашего позволения буду называть "кучу" пирамидой . Мне так удобнее чтоб не было терминологической
тавтологии с кучей как механизмом аллокации памяти.

Мне нравится пирамида своей компактностью в противоположность дереву.

Моя первая идея была как предложил Зяма выше - использовать мин-пирамиду. Только
я хотел трекать две пирамиды сразу. Мин-пирамиду - для решения собственно задачи. И макс-пирамиду
для показа первых 10-15 значений (типа pagination). Но я уже сомневаюсь что можно доверять макс-пирамиде.
Есть вероятность что она просто станет хуже обычной пирамидальной сортировки (мин-пирамида -> сортировка
по месту -> реверс массива наоборот).

Сами тела месседжей - хранить отдельно от пирамид. В идеале элемент пирамиды должен быть ключом + указателем
на месседж в пуле месседжей.

Это также удобно тем что мы можем сделать несколько views. По цене сделки за день. По заданному типу сделок за день.
И т.п. вариации.

В деревьях - хотелось-бы избежать insert/delete ключей и произвести сразу update минимального на текущий новый
с ребалансировкой как обычно. Это моя наивная попытка избежать операций с new/delete памяти.

fkfka, почему o(n)?

Для пирамиды:

Добавление в хвост O(1) + Перебалансировка O(Log n)
Чтение max (peek) - O(1). Изьятие max (poll) - O(Log n)

Не надо сравнивать с HashSet. Это просто бесполезно т.к. цели не те.

Ну сделай на массиве. Посмотрим.

У нас бесконечность - это опер-день. С утреца - будет снова по нулям.

Начал строить дом с крыши. До 1000 элементов кучу можно наполнять. Или пакетно впихнуть.
А после 1000 делать замены вершинного элемента (там будет минимальный) на новый.

Вот этот метод replaceTopItem() я сделал в целях оптимизации insert/poll. Хотя чорт его знает будет ли дешевле.



Из готовых имплементаций есть в std готовый метод делания пирамиды https://en.cppreference.com/w/cpp/algorithm/make_heap
и кажется он был там уже очень давно.

Я его называю "пирамидизация". Но мне также еще понадобиться метод для проталкивания "бульбы" вверх и вниз
методом пузыря.