Поиск блоков временных меток с большей скоростью, чем 1 в минуту с пробелами

Question

У меня есть таблица журнала активности, которая отслеживает метку времени действия пользователя. Мне нужно иметь возможность идентифицировать пользователей, которые выполняют больше действий в данный период времени, чем минут за этот период, по крайней мере 10 действий, необходимых для идентификации "блока действий".

Например

Помеченные

• 11 занятий за 10 минут
• 25 занятий за 20 минут

Не помечен

• 9 занятий за 5 минут
• 23 занятия за 30 минут

Мне нужно иметь возможность идентифицировать самый большой блок, который удовлетворяет этим условиям, например, если пользователь выполняет следующие действия:

Minutes    Action_Count
   1         3
   2         0
   3         0
   4         3
   5         0
   6         3
   7         0
   8         1
   9         0
   10        0
   11        0
   12        1
   13        3

Несмотря на то, что действия с минут 1-8 будут помечены, как 10 в "периоде менее 10 минут", действия с минут 12 и 13 также должны быть включены, поскольку они составляют 14 действий за 13 минут, даже если действие в 12 минут вернулся в порог.

Набор данных для каждого пользователя, вероятно, будет иметь приблизительно 100 временных отметок в течение 7-дневного периода, поэтому, вероятно, будет несколько блоков действий для пользователя, соответствующих тому, когда они активны.

Я могу идентифицировать блоки действий, которые происходят в течение одной минуты, с помощью следующего:

$timestamps = array(1392700382,1392700458,1392700486,1392700612,1392700619,1392700636,1392700648,1392700671,1392700679,1392700701,1392700860,1392815451,1392815486,1392815499,1392815532,1392815539,1392815680,1392815699,1392815763,1392815851,1392815972,1392816075,1392903882,1392903950,1392904029,1392904181,1392904259,1392904377,1392904402,1392904411,1392904437,1392904445,1392904469,1392904638,1392904735,1392988830,1392988858,1392988889,1392988917,1392988980,1392989016,1392989078,1392989108,1392989140,1392989167,1392989203,1392989251,1392989393,1392989401,1392989408,1392989415,1392989511,1393065019,1393065352,1393065448,1393066105,1393066110,1393066114,1393066136,1393066139,1393066144,1393066148,1393066203,1393114548,1393114563,1393114696,1393114697,1393114717,1393114723,1393114742,1393114748,1393114753,1393114785,1393114824,1393204378,1393204383,1393204387,1393204391,1393204408,1393204414,1393204419,1393204424,1393204474);
$elements = array();

foreach ($timestamps as $timestamp) {

    $oneMinuteAgo = $timestamp - 60;

    $elements[] = $timestamp;

    $postsInLastMinute = array_filter($elements, function ($value) use ($oneMinuteAgo) {
        return $value > $oneMinuteAgo;
    });

    echo implode(', ', $postsInLastMinute)."\n";
}

(см. вывод здесь: http://pastebin.com/LDEQWMxn)

Хотя я не уверен, как эта информация помогает мне, и даже если это правильный способ решения проблем.

Answer 1

Geobits уже упомянул наивный подход, и если вы имеете дело с около 100 отметками времени, это кажется достаточно быстрым. Я бы не стал ставить марки сначала в одну минуту. Рассчитать ставку activities / time_span и найдите самый длинный отрезок, основанный на количестве действий или промежутке времени, когда показатель превышает 1/60. (Или просто выясните, существует ли такой промежуток времени.)

В данных вашего примера (те, что в примере кода) действия выполняются порциями не более 20 минут в течение недели. Эти куски имеют большие промежутки между ними. Вы можете использовать характер данных для улучшения наивного алгоритма, просматривая свои временные метки в разрезе. Это дает то преимущество, что вы можете сразу исключать последовательности с менее чем 10 временными метками. Кроме того, наивность подхода менее доминирующая, потому что ваш внутренний цикл должен делать только n - 10 итерации, где n редко превышает 20

Вот подход в псевдокоде. (Я не знаком с PHP.)

flag_piecewise(time[])
    gap = 60 * 60           # choose approriate minimum gap, e.g. 1h
    start = 0
    curr = 1

    while true
        if (curr == len(time) || time[curr] - time[curr - 1] > gap)
            if (flag_range(time[start:curr]) return true            
            if (curr == len(time)) break
            start = curr
        curr++

return false

Вот flag_range это реализация наивного подхода. При быстром тестировании ваших выборочных данных я получил ускорение примерно на 20. (Я думаю, что наивный подход был достаточно быстрым, но вы получаете ускорение без особых сложностей).