Удалить строки из данных: перекрывающиеся интервалы времени?

Question

Редактировать: теперь я ищу решение этого вопроса и с другими языками программирования.

На основании другого вопроса, который я задал , у меня есть такой набор данных (для Rпользователи, для этого ниже приведен dput, представляющий сеансы компьютера пользователя:

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 09:44:18 2011-01-03 09:47:27
2     user1 D5599.domain.com 2011-01-03 09:46:29 2011-01-03 10:09:16
3     user1 D5599.domain.com 2011-01-03 14:07:36 2011-01-03 14:56:17
4     user1 D5599.domain.com 2011-01-05 15:03:17 2011-01-05 15:23:15
5     user1 D5599.domain.com 2011-02-14 14:33:39 2011-02-14 14:40:16
6     user1 D5599.domain.com 2011-02-23 13:54:30 2011-02-23 13:58:23
7     user1 D5599.domain.com 2011-03-21 10:10:18 2011-03-21 10:32:22
8     user1 D5645.domain.com 2011-06-09 10:12:41 2011-06-09 10:58:59
9     user1 D5682.domain.com 2011-01-03 12:03:45 2011-01-03 12:29:43
10    USER2 D5682.domain.com 2011-01-12 14:26:05 2011-01-12 14:32:53
11    USER2 D5682.domain.com 2011-01-17 15:06:19 2011-01-17 15:44:22
12    USER2 D5682.domain.com 2011-01-18 15:07:30 2011-01-18 15:42:43
13    USER2 D5682.domain.com 2011-01-25 15:20:55 2011-01-25 15:24:38
14    USER2 D5682.domain.com 2011-02-14 15:03:00 2011-02-14 15:07:43
15    USER2 D5682.domain.com 2011-02-14 14:59:23 2011-02-14 15:14:47
>

Может быть несколько одновременных (перекрывающихся по времени) сеансов для одного и того же имени пользователя с одного и того же компьютера.Как я могу удалить эти строки, чтобы для этих данных оставался только один сеанс?Исходный набор данных имеет ок.500 000 строк.

Ожидаемый результат (строки 2, 15 удалены)

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 09:44:18 2011-01-03 09:47:27
3     user1 D5599.domain.com 2011-01-03 14:07:36 2011-01-03 14:56:17
4     user1 D5599.domain.com 2011-01-05 15:03:17 2011-01-05 15:23:15
5     user1 D5599.domain.com 2011-02-14 14:33:39 2011-02-14 14:40:16
6     user1 D5599.domain.com 2011-02-23 13:54:30 2011-02-23 13:58:23
7     user1 D5599.domain.com 2011-03-21 10:10:18 2011-03-21 10:32:22
8     user1 D5645.domain.com 2011-06-09 10:12:41 2011-06-09 10:58:59
9     user1 D5682.domain.com 2011-01-03 12:03:45 2011-01-03 12:29:43
10    USER2 D5682.domain.com 2011-01-12 14:26:05 2011-01-12 14:32:53
11    USER2 D5682.domain.com 2011-01-17 15:06:19 2011-01-17 15:44:22
12    USER2 D5682.domain.com 2011-01-18 15:07:30 2011-01-18 15:42:43
13    USER2 D5682.domain.com 2011-01-25 15:20:55 2011-01-25 15:24:38
14    USER2 D5682.domain.com 2011-02-14 15:03:00 2011-02-14 15:07:43
>

Вот набор данных:

structure(list(username = c("user1", "user1", "user1",
"user1", "user1", "user1", "user1", "user1",
"user1", "USER2", "USER2", "USER2", "USER2", "USER2", "USER2"
), machine = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 3L,
3L, 3L, 3L, 3L, 3L, 3L), .Label = c("D5599.domain.com", "D5645.domain.com",
"D5682.domain.com", "D5686.domain.com", "D5694.domain.com", "D5696.domain.com",
"D5772.domain.com", "D5772.domain.com", "D5847.domain.com", "D5855.domain.com",
"D5871.domain.com", "D5927.domain.com", "D5927.domain.com", "D5952.domain.com",
"D5993.domain.com", "D6012.domain.com", "D6048.domain.com", "D6077.domain.com",
"D5688.domain.com", "D5815.domain.com", "D6106.domain.com", "D6128.domain.com"
), class = "factor"), start = structure(c(1294040658, 1294040789,
1294056456, 1294232597, 1297686819, 1298462070, 1300695018, 1307603561,
1294049025, 1294835165, 1295269579, 1295356050, 1295961655, 1297688580,
1297688363), class = c("POSIXct", "POSIXt"), tzone = ""), end =
structure(c(1294040847,
1294042156, 1294059377, 1294233795, 1297687216, 1298462303, 1300696342,
1307606339, 1294050583, 1294835573, 1295271862, 1295358163, 1295961878,
1297688863, 1297689287), class = c("POSIXct", "POSIXt"), tzone = "")),
.Names = c("username",
"machine", "start", "end"), row.names = c(NA, 15L), class = "data.frame")

Answer 1

Попробуйте пакет интервалов :

library(intervals)

f <- function(dd) with(dd, {
    r <- reduce(Intervals(cbind(start, end)))
    data.frame(username = username[1],
         machine = machine[1],
         start = structure(r[, 1], class = class(start)),
         end = structure(r[, 2], class = class(end)))
})

do.call("rbind", by(d, d[1:2], f))

С примерами данных это сокращает 15 строк до следующих 13 строк (объединяя строки 1 и 2 и строки 12 и 13 висходный фрейм данных):

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 02:44:18 2011-01-03 03:09:16
2     user1 D5599.domain.com 2011-01-03 07:07:36 2011-01-03 07:56:17
3     user1 D5599.domain.com 2011-01-05 08:03:17 2011-01-05 08:23:15
4     user1 D5599.domain.com 2011-02-14 07:33:39 2011-02-14 07:40:16
5     user1 D5599.domain.com 2011-02-23 06:54:30 2011-02-23 06:58:23
6     user1 D5599.domain.com 2011-03-21 04:10:18 2011-03-21 04:32:22
7     user1 D5645.domain.com 2011-06-09 03:12:41 2011-06-09 03:58:59
8     user1 D5682.domain.com 2011-01-03 05:03:45 2011-01-03 05:29:43
9     USER2 D5682.domain.com 2011-01-12 07:26:05 2011-01-12 07:32:53
10    USER2 D5682.domain.com 2011-01-17 08:06:19 2011-01-17 08:44:22
11    USER2 D5682.domain.com 2011-01-18 08:07:30 2011-01-18 08:42:43
12    USER2 D5682.domain.com 2011-01-25 08:20:55 2011-01-25 08:24:38
13    USER2 D5682.domain.com 2011-02-14 07:59:23 2011-02-14 08:14:47

Answer 2

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

Если ключ (сеанс) уже существует, он обновляет время окончания. Если это не так, он создает и устанавливает время начала и время начала. При обнаружении новых записей сеанса для этого пользователя / компьютера в журнале обновляется время окончания сеансового ключа.

 $ht = @{}
 import-csv <logfile> |
    foreach{
      $key = $_.username + $_.computername
      if ($ht.ContainsKey($key)){$ht.$key.end = $_.end}
      else{$ht.add("$key",@{start=$_.start;end=$_.end}}
       }

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

Answer 3

Решение псевдокода: O (n log n), O (n), если известно, что данные уже отсортированы должным образом.

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

1. Инициализировать «рабочий интервал» как ноль / ноль / undef / и т. Д.

2. Для каждой строки в порядке:

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

3. Наконец, если рабочий интервал существует, выведите его.

Answer 4

Альтернативное решение с использованием класса interval от lubridate.

library(lubridate)
int <- with(d, new_interval(start, end))

Теперь нам нужна функция для проверки перекрытий. См. Определение перекрытия двух диапазонов дат .

int_overlaps <- function(int1, int2)
{
  (int_start(int1) <= int_end(int2)) & 
  (int_start(int2) <= int_end(int1))
}

Теперь вызовите это на всех парах интервалов.

index <- combn(seq_along(int), 2)
overlaps <- int_overlaps(int[index[1, ]], int[index[2, ]])

Пересекающиеся строки:

int[index[1, overlaps]]
int[index[2, overlaps]]

И строки для удаления просто index[2, overlaps].

Answer 5

Одно из решений состоит в том, чтобы сначала разбить интервалы, чтобы они иногда были равны, но никогда не перекрывались частично, и они удаляли дубликаты. Проблема в том, что у нас осталось много небольших интервалов стыковки, и объединение их не выглядит простым.

library(reshape2)
library(sqldf)
d$machine <- as.character( d$machine ) # Duplicated levels...
ddply( d, c("username", "machine"), function (u) {
  # For each username and machine, 
  # compute all the possible non-overlapping intervals
  intervals <- sort(unique( c(u$start, u$end) ))
  intervals <- data.frame( 
    start = intervals[-length(intervals)], 
    end   = intervals[-1] 
  )
  # Only retain those actually in the data
  u <- sqldf( "
    SELECT DISTINCT u.username, u.machine, 
                    intervals.start, intervals.end
    FROM  u, intervals 
    WHERE       u.start <= intervals.start 
    AND   intervals.end <=         u.end
  " )
  # We have non-overlapping, but potentially abutting intervals:
  # ideally, we should merge them, but I do not see an easy 
  # way to do so.
  u
} )

РЕДАКТИРОВАТЬ: Другое, концептуально более чистое решение, которое устраняет проблему не связанных интервалов примыкания, состоит в подсчете количества открытых сеансов для каждого пользователя и машины: когда он перестает быть нулевым, пользователь вошел в систему (с одним или несколькими сеансами), когда он падает до нуля, пользователь закрыл все свои сеансы.

ddply( d, c("username", "machine"), function (u) {
  a <- rbind( 
    data.frame( time = min(u$start) - 1, sessions = 0 ),
    data.frame( time = u$start, sessions = 1 ), 
    data.frame( time = u$end,   sessions = -1 ) 
  )
  a <- a[ order(a$time), ]
  a$sessions <- cumsum(a$sessions)
  a$previous <- c( 0, a$sessions[ - nrow(a) ] )
  a <- a[ a$previous == 0 & a$sessions  > 0 | 
          a$previous  > 0 & a$sessions == 0, ]
  a$previous_time <- a$time
  a$previous_time[-1] <- a$time[ -nrow(a) ]
  a <- a[ a$previous > 0 & a$sessions == 0, ]
  a <- data.frame( 
    username = u$username[1],
    machine  = u$machine[1],
    start = a$previous_time,
    end   = a$time
  )
  a
} )