Алгоритмическая проблема: определение “сеансов пользователя”
У меня есть реальное, мало интересное (по крайней мере, мне) проблема для решения (и, нет, это не домашняя работа). Это эквивалентно этому: необходимо решить, что "сессии" и "сессии запускаются, и время окончания" пользователь шло перед его компьютером.
Вы получаете время, в которое любое взаимодействие с пользователем было сделано и максимальный период неактивности. Если время, больше или равное, чем период неактивности, протекло между двумя вводами данных пользователем, то они - часть различных сессий.
В основном вход, который я получаю, является этим (исходные данные не отсортированы, и я не отсортировал бы их прежде, чем определить сессии):
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 [тысячи вводов данных пользователем на сессию]).
До сих пор я думаю о чтении входа (скажите 6:38), и определение интервала [данные-max_inactivity... data+max_inactivity] и, для каждого нового входа, используют дихотомическое (зарегистрируйте n), поиск, чтобы видеть, падает ли это в известном интервале или создает новый интервал.
Я повторил бы это для каждого входа, заставив решение n зарегистрировать 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)
Я не знаю, является ли описание очень четким, но именно это я должен сделать.
Такая проблема имеет имя? Как Вы пошли бы о решении его?
Править
Я очень интересуюсь знанием, какой вид структуры данных я должен использовать, если я планирую решить его способ, к которому я планирую. Я должен и зарегистрировать поиск n и способность к вставке/слиянию.
4 ответа
Вы запрашиваете онлайн-алгоритм , то есть такой, который может постепенно вычислять новый набор сеансов для каждого нового времени ввода.
Что касается выбора структуры данных для текущего набора сеансов, вы можете использовать сбалансированное двоичное дерево поиска. Каждый сеанс представлен парой (начало, конец) времени начала и времени окончания. Узлы дерева поиска упорядочены по их времени начала . Поскольку ваши сеансы разделены как минимум max_inactivity , то есть два сеанса не перекрываются, это гарантирует, что время окончания также будет упорядочено. Другими словами, упорядочивание по времени начала уже упорядочит сеансы последовательно.
Вот какой-то псевдокод для прошивки. Для удобства записи мы делаем вид, что 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]
Операция слияния может быть реализована путем удаления и вставки элементов в двоичное дерево поиска.
Этот алгоритм займет время O (n log m), где m - максимальное количество сеансов, которое, как вы сказали, довольно мало.
Конечно, реализация сбалансированного двоичного дерева поиска - непростая задача, в зависимости от языка программирования. Ключевым моментом здесь является то, что вам нужно разбить дерево в соответствии с ключом, и не каждая готовая библиотека поддерживает эту операцию. Для Java я бы использовал класс TreeSet ; как уже говорилось, тип элемента E - это отдельный сеанс, заданный временем начала и окончания.Его методы floor () и потолок () будут извлекать сеансы, которые я обозначил как sessions [i] и sessions [i + 1] в моем псевдокоде.
Ваше решение, использующее дерево интервального поиска, кажется достаточно эффективным.
Вы не говорите, являются ли предоставленные вами данные (состоящие исключительно из отметок времени без date ) фактическими данными, которые вы обрабатываете. Если это так, считайте, что в сутках всего 24 * 60 = 1440 минут. Поскольку это относительно небольшое значение, создание битового вектора (упакованного или нет --- на самом деле не имеет значения) кажется эффективным и простым решением.
Битовый вектор (после заполнения) мог бы:
отвечать на запрос «Был ли пользователь обнаружен в момент времени T?» в O (1), если вы решите установить для поля вектора значение true только тогда, когда соответствующее время появилось в ваших входных данных (мы можем назвать этот метод «консервативным сложением») или
ответив на запрос «Был сеанс, активный в момент времени T? " в O (1), но с большей константой, если вы решите установить для поля вектора значение true, если сеанс был активен в это время - я имею в виду, что когда вы добавляете время T, вы также установите для следующих 29 полей значение true.
Я хотел бы отметить, что, используя консервативное добавление, вы не ограничиваете себя 30-минутными интервалами сеанса: действительно, вы можете изменить это значение онлайн в любое время, поскольку структура не экстраполирует никакой информации, а это просто практичный способ хранения / просмотра записей присутствия.
Мне неизвестно название вашей проблемы или название решения, которое вы нашли. Но ваше решение - это (более или менее) решение, которое я бы предложил. Я считаю, что это лучшее решение для такого рода проблем.
Если ваши данные хотя бы в некоторой степени упорядочены, вы можете найти немного лучшее решение, приняв во внимание этот порядок. Например. ваши данные могут быть упорядочены по дате, но не по времени. Затем вы разделяете отдельные даты.
Максимальная задержка
Если записи журнала имеют «максимальную задержку» (например, с максимальной задержкой в 2 часа, событие 8:12 никогда не будет указано после события 10:12), вы можете посмотреть вперед и Сортировать.
Выполнить сортировку
В качестве альтернативы я бы сначала попробовал выполнить сортировку - по крайней мере, чтобы убедиться, что это не работает. Временная метка может быть разумно сохранена в 8 байтах (4 даже для ваших целей, вы можете поместить 250 миллионов в гигабайт). Быстрая сортировка здесь может быть не лучшим выбором, поскольку у нее низкая локальность, сортировка вставкой почти идеальна для почти отсортированных данных (хотя у нее тоже плохая локальность), в качестве альтернативы, быстрая сортировка по фрагментам, а затем слияние фрагментов слиянием sort должна работать, даже если она увеличивает требования к памяти.
Сжать и победить
В качестве альтернативы вы можете использовать следующую стратегию:
- преобразовать каждое событие в «сеанс длительностью 0»
- Разделить список сеансов на фрагменты (например, 1К значений на фрагмент)
- В каждом блоке сортировать по началу сеанса
- Объединить все сеансы, которые можно объединить (предварительная сортировка позволяет сократить время ожидания).
- Сожмите список оставшихся сеансов в один большой список
- повторите с шага 2, пока список не станет короче.
- sort-and-merge по всем
Если ваши файлы журналов имеют вид «временного местоположения», о котором говорит ваш вопрос, уже за один проход данные следует уменьшить, чтобы обеспечить «полную» сортировку.
[ редактировать ] [Этот сайт] 1 демонстрирует «оптимизированную быструю сортировку с окончанием сортировки вставкой», которая довольно хороша для почти отсортированных данных.Как и у этого парня std :: sort