Кодирование: отслеживать последние N дней записей для каждого пользователя.
Я решаю интересную проблему, в которой для каждого пользователя я хотел бы сохранить его последние N дней активности. Это может быть применено ко многим сценариям использования, и один из таких простых:
Для каждого пользователя - пользователь может приходить в тренажерный зал в произвольный день - я хочу узнать общее количество раз, когда он посещал тренажерный зал за последние 90 дней.
Это сложно для меня.
Мои мысли: я думал о сохранении вектора, в котором каждая запись будет определять день, а затем логическое значение может представлять его посещение. Для подсчета достаточно просто линейной обработки этого раздела в массиве.
Какой самый лучший способ?
4 ответа
Сделайте для каждого клиента структуру данных Queue, содержащую элементы с датой посещения. Когда клиент посещает тренажерный зал, просто добавьте текущую дату
Q[ClientIdx].Add(Today)
Когда вам нужно получить трек для него:
while (not Q[ClientIdx].Empty) and (Today - Q[ClientIdx].Peek > 90)
Q[ClientIdx].Remove //dequeue too old records
VisitCount = Q.Count
Вы можете использовать стандартные реализации Queue на многих языках или простую собственную реализацию на основе массива / списка, если стандартная версия недоступна.
Обратите внимание, что каждая запись добавляется и удаляется один раз, поэтому амортизируемая сложность составляет O(1) на операцию добавления / подсчета
В зависимости от того, насколько сложным он должен быть, достаточно простого массива, в котором хранятся посещения каждого клиента.
При каждом посещении добавляйте новую запись, содержащую дату / время. Каждый день запускайте проверку, чтобы увидеть, есть ли на клиентах записи о посещениях старше 90 дней. Первая запись, которая недостаточно старая, означает, что больше нет записей для проверки, поэтому вы можете безопасно перейти к следующему клиенту.
Надеюсь, это поможет вам!
Ваша идея будет работать, но действительно ли она эффективна в космосе?
Ваша структура данных будет выглядеть примерно так: булевский 2D-вектор (вы можете представить его в виде матрицы), где каждая строка - это пользователь, а каждый столбец - день (отсортированный), так что он будет состоять из:
матрица размера
U x N
где U - количество пользователей.
Чтобы ответить на вопрос, который я изначально задал, нужно подумать, насколько плотной будет эта матрица. Если это будет много, тогда вы сделали правильный выбор, если нет, то вы потратили (много) места. Вы можете увидеть компромисс здесь.
Конечно, вы должны подумать о вашем случае использования. В примере с тренажерным залом я не думаю, что это было бы эффективным с точки зрения пространства, поскольку большинство людей не ходят в тренажерный зал каждый день (я думаю), что приведет к разреженной матрице, что означает, что мы потратили впустую пространство.
Другая идея состоит в том, чтобы иметь один размер вектора OS N где дни отсортированы. Каждая запись будет представлять собой один связанный список, где каждый узел будет пользователем.
Если пользователь найден в списке дня, это означает, что он пошел в спортзал в тот день.
При таком подходе мы выделяем ровно столько места, сколько необходимо, поэтому оно оптимально по размеру независимо от плотности, которую я упоминал в случае матрицы.
Но так ли это? Нет, конечно нет! Я говорил о космосе, но как насчет эффективности времени? Например, поиск - это, как правило, частый метод, который мы хотим, чтобы наша структура данных поддерживала, и если мы хотим, чтобы это было быстро!
В случае матрицы поиск был бы операцией O(1), что приятно, так как доступ к матрице является постоянной операцией.
Однако в случае вектора + списка поиск занял бы O(L), где L это средний размер списков, которые наш вектор имеет в общей сложности.
Так какой? Это зависит от вашего приложения!
Я бы также попробовал хеш-таблицу, которая не требует сортировки и занимает мало места ( какова сложность пространства хеш-таблицы?).
Как насчет того, чтобы иметь очередь с фиксированным размером (90) сведений о посещении для каждого пользователя? Вы можете обобщить его для нескольких пользователей, и ключевым преимуществом является то, что вам не нужно беспокоиться о сохранении данных за последние 90 дней.
Вы можете вывести очередь в список или массив и сохранить ее при необходимости в O(n). И, как вы упомянули, проверка на отсутствие присутствия также будет O(n).