Огромный анализ данных
Скажем, у нас есть о 1e10 строки файла журнала каждый день, каждая из которых содержит: идентификационный номер (целое число длиной менее 15 цифр), время входа в систему и время выхода из системы. Некоторые ID могут входить и выходить из системы несколько раз.
Вопрос 1:
Как подсчитать общее количество идентификаторов, которые вошли в систему? (Мы не должны считать каждый идентификатор дважды или более)
Я попытался использовать хеш-таблицу здесь, но обнаружил, что память, которую мы должны получить, может быть настолько большой.
вопрос 2:
Подсчитайте время, когда население онлайн-пользователей самое большое.
Я думаю, что мы можем разделить время дня на 86400 секунд, а затем для каждой строки файла журнала добавить 1 к каждой секунде в сетевом интервале. Или, может быть, я могу отсортировать файл журнала по времени входа?
Решение
-
использовать сегментное дерево хранить интервалы последовательных идентификаторов.
Сканирование журналов для всех событий входа в систему.
Чтобы вставить идентификатор, сначала выполните поиск сегмента, содержащего идентификатор: если он существует, идентификатор является дубликатом. Если он не ищет сегменты, которые находятся сразу после или перед идентификатором. Если они существуют, удалите их и, при необходимости, объедините новый идентификатор и вставьте новый сегмент. Если они не существуют, вставьте идентификатор как сегмент из 1 элемента.После того, как все идентификаторы были вставлены, посчитайте их количество, суммируя кардиналы всех сегментов в дереве.
-
при условии, что:
- данный идентификатор может быть зарегистрирован только один раз в любой момент времени,
- события хранятся в хронологическом порядке (как правило, это журналы)
Сканирование журнала и ведение счетчика
cот количества вошедших в данный момент пользователей, а также от максимального количестваmнайдено и связанное времяt, Для каждого входа в систему, приращениеcи для каждого выхода уменьшайте его. На каждом шаге обновляйсяmа такжеtеслиmниже чемc,
Другие решения
Вы можете сделать это в оболочке * nix.
cut -f1 logname.log | sort | uniq | wc -lcut -f2 logname.log | sort | uniq -c | sort -r
Чтобы вопрос 2 имел смысл: вам, вероятно, нужно войти в 2 вещи: пользователь входит в систему и пользователь выходит из системы. Два разных действия вместе с идентификатором пользователя. Если этот список отсортирован по времени выполнения действия (вход или выход из системы). Вы просто сканируете счетчиком currentusers: добавьте 1 для каждого входа и -1 для каждого выхода. Максимальное значение, которое достигает число (текущие пользователи), — это значение, которое вас интересует, вам, вероятно, будет интересно также отслеживать, в какое время это произошло.
В вопросе 1 забудьте C ++ и используйте инструменты * nix. Предполагая, что файл журнала разделен пробелом, тогда число уникальных имен входа в данном журнале вычисляется по формуле:
$ awk '{print $1}' foo.log | sort | uniq | wc -l
Gnu sort, с радостью отсортирует файлы больше памяти. Вот что делает каждый кусок:
- AWK извлекает первый разделенный пробелами столбец (идентификационный номер).
- Сортировать сортирует эти идентификационные номера, потому что уник нужен отсортированный ввод.
- уник возвращает только уникальные номера.
- Туалет печатает количество строк, которое будет количеством уникальных чисел.
Для 1 вы можете попробовать работать с фрагментами файла в то время, когда они достаточно малы, чтобы поместиться в память.
то есть вместо
countUnique([1, 2, ... 1000000])
пытаться
countUnique([1, 2, ... 1000]) +
countUnique([1001, 1002, ... 2000]) +
countUnique([2001, 2002, ...]) + ... + countUnique([999000, 999001, ... 1000000])
2 немного сложнее. Разделение работы на управляемые интервалы (как вы и предложили секунду) — хорошая идея. Для каждой секунды найдите количество людей, вошедших в систему в течение секунды, используя следующую проверку (псевдокод):
def loggedIn(loginTime, logoutTime, currentTimeInterval):
return user is logged in during currentTimeInterval
Примените loggedIn ко всем 86400 секундам, а затем разверните список из 86400 отсчетов пользователей, чтобы найти время, когда количество пользователей онлайн является самым большим.
detector