Структура данных для отображения top-#

[begemot_sun]

Добрый день.

Необходима структура наподобии map{} когда можно быстро (за время O(log n)) поменять значение элемента по ключу (cчетчик), но также иметь возможность вывести весь список сортированный по значениям элементов как в прямом, так и в обратном порядке. 

Может есть какая реализация на github? А может это какой-то стандартная структура данных, которую можно погуглить и реализовать на Erlang ?

Скажу, что кол-во элементов будет до 100-200 (и возможно я тут развожу оверинжиниринг и достаточно lists и сортировки по списку), но для меня задача представляет также и чисто академический интерес. Как реализовать такое оптимально при большем кол-ве элементов?

Сразу в голову приходит структура из 2-х gb_trees (maps), но может что уже придумали другого ?

P.S. ETS не предлагать.

Спасибо.

[Yuri Zhloba]

если элементов 100-200, то не важно, будет там O(log n) или O(n^2)

map и sort(map:to_list(M))

26 октября 2015 г., 13:00 пользователь begemot_sun <logu...@gmail.com> написал:

--
Вы получили это сообщение, поскольку подписаны на группу "Erlang по-русски".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес erlang-russia...@googlegroups.com.
Чтобы отправлять сообщения в эту группу, отправьте письмо на электронный адрес erlang-...@googlegroups.com.
Чтобы настроить другие параметры, перейдите по ссылке https://groups.google.com/d/optout.

--

Yuri Zhloba

skype: yzh44yzh
phone: +375 44 793 33 73

[Yuri Zhloba]

Если элементов много, то ets типа ordered_set

26 октября 2015 г., 13:04 пользователь Yuri Zhloba <yzh4...@gmail.com> написал:

[Dmitry Lipovoi]

200 элементов -- это очень мало, можно просто поддерживать отсортированный список.

Но вообще, такую проблему решает любая структура данных, базирующаяся на бинарных деревьях поиска.

--

[Alexander Tchitchigin]

Ну, можно ещё какой-нибудь хип (https://en.wikipedia.org/wiki/Heap_%28data_structure%29) взять...

--

С уважением,
Александр.

[Daniil Churikov]

плюсую heap

[Alexander Zhuravlev]

On Mon, Oct 26, 2015 at 04:00:39AM -0700, begemot_sun wrote:
>
>
> Добрый день.
>
> Необходима структура наподобии map{} когда можно быстро (за время O(log n))
> поменять значение элемента по ключу (cчетчик), но также иметь возможность
> вывести весь список сортированный по значениям элементов как в прямом, так
> и в обратном порядке.
>
> Может есть какая реализация на github? А может это какой-то стандартная
> структура данных, которую можно погуглить и реализовать на Erlang ?
>
> Скажу, что кол-во элементов будет до 100-200 (и возможно я тут развожу
> оверинжиниринг и достаточно lists и сортировки по списку), но для меня
> задача представляет также и чисто академический интерес. Как реализовать
> такое оптимально при большем кол-ве элементов?

Если нужно считать top-k для streaming data, то можно посмотреть на
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.9563
https://github.com/dgryski/go-topk/blob/master/topk.go

>
> Сразу в голову приходит структура из 2-х gb_trees (maps), но может что уже
> придумали другого ?
>
> P.S. ETS не предлагать.
>
> Спасибо.
>

> --
> Вы получили это сообщение, поскольку подписаны на группу Erlang по-русски.
>
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес erlang-russia...@googlegroups.com.

> Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу erlang-...@googlegroups.com.
> Настройки подписки и доставки писем: https://groups.google.com/d/optout.

--
Alexander Zhuravlev

[Sergey Loguntsov]

> Если нужно считать top-k для streaming data, то можно посмотреть на
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.9563
> https://github.com/dgryski/go-topk/blob/master/topk.go

Спасибо добрый человек, буду изучать.

[Dmitry Lipovoi]

Heap тоже можно, но там несколько сложнее выбрать n максимальных элементов.

Нужно делать что-то вроде обхода в ширину, только frontier должен быть не списком, а еще одним heap'ом.

Но по времени это будет n*log(n), а не линейно, как в случае с обходом дерева.

Плюс, если хочется делать как в прямом, так и в обратном порядке (о чем писал ТС), нужно поддерживать два хипа.

[Daniil Churikov]

наверное m * log n, где m это кол-во максимальных/минимальных элементов, которые нужны?
Если m константа, можно сделать что бы верхняя нода состояла и m упорядоченных элементов,
которые при модификации хипа будут перестраиваться, т.о. можно извлечь m min/max элементов за O(1).