Блог

Главная - Вопросы по программированию - ETS упорядоченный набор и эффективная разбивка на страницы

ETS упорядоченный набор и эффективная разбивка на страницы

#performance #erlang #pagination #ets

#Производительность #erlang #разбивка на страницы #ets

Вопрос:

Я храню {Key, Value} данные в ETS ordered_set , где Key это дата-время. Довольно легко выбрать все элементы за заданное время внутри [From, To] .

Что-то вроде этого:

 ets:select(Tab, [{{'$1', '$2'}, [{'>=', '$1', From}, {'=<', '$1', To}], ['$2']}])

У нас есть Limit параметр в select() функции, поэтому мы можем ограничить количество выбираемых элементов. Но как я могу указать смещение?

В качестве входных данных мой модуль получает интервал времени и номер страницы. Моя цель — вернуть элементы за указанный интервал времени и страницу. Размер страницы ( Limit ) является константой. Я могу вычислить смещение как 

 Offset = Limit * PageNumber - Limit

Вопрос в том, как я могу эффективно выбирать элементы только для данной страницы?

Я знаю, что select() функция может получать Continuation параметр, но у меня нет состояния из предыдущего выбора. У меня есть только номер страницы.

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

Ответ №1:

Даже ваш первый выбор неэффективен, потому что сопоставление ets недостаточно разумно. Следуйте этому обсуждению.

Комментарии:

1. Существует ли какая-либо альтернативная структура данных для выполнения такого выбора в O (logN)? Может быть, gb_trees?

2. @Stas: Если вы воспользуетесь next lookup советом Роберта, вы получите тот же результат, что и любая другая структура O (logN). Единственным недостатком является то, что вам нужно сохранить последний ключ на странице, чтобы двигаться дальше.

3. @Stas: ordered_set это O(log N), как и gb_trees . Gb_trees позволяет вам перешагивать через таблицу, но вы можете начать только с начала. Насколько велика ваша таблица? Это определит, какие структуры данных вам удобно использовать.