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

Question

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

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

По сути, я получаю следующие данные (входные данные не отсортированы, и я бы предпочел не сортировать их до определения сеансов):

06:38
07:12
06:17
09:00
06:49
07:37
08:45
09:51
08:29

И, скажем, период бездействия 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 *) 1025 *) выполните поиск, чтобы определить, попадает ли он в известный интервал, или создайте новый интервал.

Я бы повторял это для каждого ввода, делая решение 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)

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

У такой проблемы есть имя? Как вы решите это?

EDIT

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

Answer 1

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

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

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

1. преобразовать каждое событиев «сеанс продолжительностью 0»
2. Разделить список сеансов на куски (например, значения 1К / блок)
3. Внутри каждого блока сортировать по началу сеанса
4. Объединить всесеансы, которые могут быть объединены (сортировка перед позволяет уменьшить ваш взгляд в будущее).
5. Сжать список оставшихся сеансов в один большой список
6. повторять с шагом 2, пока список не станет короче.
7. сортировать и объединять все

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

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

Answer 2

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

Относительно выбора структура данных для текущего набора сеансов вы можете использовать сбалансированное двоичное дерево поиска.Каждая сессия представлена ​​парой (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] в моем псевдокоде.

Answer 3

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

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

Бит-вектор (после заполнения) будет способен либо:

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

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

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

Answer 4

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

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