Алгоритмическая проблема: определение "пользовательских сеансов"

У меня есть очень мало интересная (по крайней мере для меня) проблема для решения (и, нет, это не домашнее задание). Это эквивалентно этому: вам нужно определить "сеансы" и "время начала и окончания сеанса", на котором пользователь находился перед своим компьютером.

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

В основном вход, который я получаю, это (входы не сортируются, и я бы не сортировал их до определения сеансов):

И, скажем, период бездействия 30 минут.

Затем мне нужно найти три сеанса:

[06:17...07:12]
[07:37...09:00]
[09:51...09:51]

Если период бездействия установлен на 12 часов, я бы просто нашел один большой сеанс:

[06:17...09:51]

Как я могу решить это просто?

Там минимальный допустимый период бездействия, который должен составлять около 15 минут.

Я предпочел бы не сортировать заранее, так это то, что я получу много данных, и только их хранение в памяти будет проблематичным. Однако большинство этих данных должны быть частью одних и тех же сеансов (должно быть относительно немного сеансов по сравнению с объемом данных, возможно, что-то вроде тысяч до 1 [тысяч пользовательских входов за сеанс]).

До сих пор я думаю о чтении ввода (например, 06:38) и определении интервала [data-max_inactivity... data + max_inactivity], и для каждого нового ввода используйте дихотомический (log n) поиск, чтобы увидеть если он попадает в известный интервал или создает новый интервал.

Я бы повторил это для каждого ввода, сделав решение n log n AFAICT. Кроме того, хорошо, что он не будет использовать слишком много памяти, поскольку он будет создавать только интервалы (и большинство входов будет падать в известном интервале).

Кроме того, каждый раз, если попадает в известный интервал, мне придется изменить нижний или верхний предел интервала, а затем посмотреть, нужно ли мне "сливаться" со следующим интервалом. Например (для максимального периода бездействия 30 минут):

[06:00...07:00]  (because I got 06:30)
[06:00...07:00][07:45...08:45]   (because I later got 08:15)
[06:00...08:45] (because I just received 07:20)

Я не знаю, является ли описание очень ясным, но это то, что мне нужно сделать.

Есть ли такая проблема с именем? Как бы вы решили его решить?

ИЗМЕНИТЬ

Мне очень интересно знать, какую структуру данных я должен использовать, если планирую решить ее так, как планирую. Мне нужна функция поиска и вставки/слияния log n.

Ответ 1

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

Что касается выбора структуры данных для текущего набора сеансов, вы можете использовать сбалансированное двоичное дерево поиска. Каждая сессия представлена парой (start,end) времени начала и окончания. Узлы дерева поиска упорядочены по времени start. Поскольку ваши сеансы разделены не менее чем на max_inactivity, т.е. Никакие два сеанса не перекрываются, это гарантирует, что время end будет упорядочено. Другими словами, упорядочение по времени начала будет уже упорядочивать сеансы последовательно.

Вот некоторый псевдокод для вставки. Для удобства обозначения мы делаем вид, что sessions - это массив, хотя он фактически является двоичным деревом поиска.

insert(time,sessions) = do
    i <- find index such that
         sessions[i].start <= time && time < session[i+1].start

    if (sessions[i].start + max_inactivity >= time)
        merge  time  into  session[i]
    else if (time >= sessions[i+1].start - max_inactivity)
        merge  time  into  sessions[i+1]
    else
        insert  (time,time)  into  sessions

    if (session[i] and session[i+1] overlap)
        merge  session[i] and session[i+1]

Операция merge может быть реализована путем удаления и вставки элементов в двоичное дерево поиска.

Этот алгоритм займет время O (n log m), где m - максимальное количество сеансов, которое вы сказали довольно мало.

Конечно, реализация сбалансированного двоичного дерева поиска - непростая задача, в зависимости от языка программирования. Ключевым моментом здесь является то, что вам нужно разделить дерево в соответствии с ключом, и не каждая готовая библиотека поддерживает эту операцию. Для Java я бы использовал класс TreeSet<E>; как сказано, тип элемента E представляет собой один сеанс, заданный начальным и конечным временем. Его методы floor() и ceiling() будут извлекать сеансы, которые я обозначил с помощью sessions[i] и sessions[i+1] в моем псевдокоде.

Ответ 2

Максимальная задержка
Если записи журнала имеют "максимальную задержку" (например, с максимальной задержкой в 2 часа, событие 8:12 никогда не будет указано после события 10:12), вы можете смотреть вперед и сортировать.

Сортировка
В качестве альтернативы, я бы сначала попробовал сортировку - по крайней мере, чтобы убедиться, что она не работает. Временная метка может быть разумно сохранена в 8 байтах (4 даже для ваших целей, вы можете поставить 250 миллионов в то время в гигабайт). Quicksort, возможно, не самый лучший выбор здесь, так как он имеет низкую локальность, сортировка вставки почти идеальна для почти отсортированных данных (хотя и у нее плохая локальность), альтернативно, быстро сортировка по кусочкам, а затем слияние кусков с слиянием sort должен делать, даже если он увеличивает требования к памяти.

Сквош и побеждать
Кроме того, вы можете использовать следующую стратегию:

преобразует каждое событие в "сеанс продолжительности 0"
Разделите список сеансов на куски (например, значения 1K/кусок)
Внутри каждого фрагмента сортировка по началу сеанса
Объединить все сеансы, которые могут быть объединены (сортировка до этого позволяет уменьшить ваш взгляд вперед).
Компактный список оставшихся сеансов в большом одиночном списке
повторите шаг 2, пока список не станет короче.
сортировать и объединять все

Если ваши файлы журналов имеют вид "временной локальности", о котором идет ваш вопрос, уже один проход должен уменьшить данные, чтобы обеспечить "полный" вид.

[ изменить] [Этот сайт] 1 демонстрирует "оптимизированную быстродействующую сортировку с вставкой сортировки", что вполне хорошо на почти отсортированных данных. Как это ребята std:: sort

Ответ 3

Мне неизвестно имя для вашей проблемы или имя найденного решения. Но ваше решение - это (более или менее) решение, которое я бы предложил. Я думаю, что это лучшее решение для этой проблемы.

Если ваши данные хотя бы несколько упорядочены, вы можете найти немного лучшее решение, учитывая это упорядочение. Например. ваши данные могут быть заказаны по дате, но не по времени. Затем вы будете разделять отдельные даты.

Ответ 4

Ваше решение, использующее дерево поиска интервалов, похоже, было бы достаточно эффективным.

Вы не говорите, являются ли данные, которые вы предоставили (состоящие исключительно из временных меток без даты), являются фактическими данными, которые вы обрабатываете. Если да, считайте, что есть только 24 * 60 = 1440 минут в день. Поскольку это относительно небольшое значение, создание битового вектора (упакованного или нет - на самом деле не имеет значения) похоже, что это обеспечит как эффективное, так и простое решение.

Бит-вектор (один раз заполненный) мог бы либо:

ответ на запрос "Был ли пользователь обнаружен во время T?" в O (1), если вы решите установить поле вектора в true только тогда, когда соответствующее время отобразилось на ваших входных данных (мы можем назвать этот метод "консервативным добавлением" ) или
отвечая на запрос "Был ли сеанс активным в момент времени T?" в O (1), но с большей константой, если вы решите установить поле вектора в значение true, если сеанс был активным в это время - под этим я подразумеваю, что когда вы добавляете время T, вы также установите следующие 29 полей в true.

Я хотел бы отметить, что, используя консервативное дополнение, вы не ограничиваете себя интервалами сеанса 30 минут: действительно, вы можете изменить это значение онлайн в любое время, поскольку структура не экстраполирует какую-либо информацию, но это просто практический способ хранения/просмотра записей присутствия.