Usunąć wiersze z danych: nakładające się interwały czasowe?

Question

Edytuj: Szukam rozwiązania dla tego pytania teraz również z innymi językami programowania.

Na podstawie other question I asked, mam zestaw danych tak (dla użytkowników R, dput o tym poniżej), która reprezentuje użytkowników sesje komputera:

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 
> 

może być kilka jednoczesnych (nakładające się na podstawie czasu) sesje dla tej samej nazwy użytkownika z tego samego komputera. Jak mogę usunąć te wiersze, aby dla tych danych pozostawiono tylko jedną sesję ? Oryginalny zestaw danych ma ok. 500 000 wierszy.

Oczekiwany wyjściowy (wiersze 2, 15 usuwa)

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 
> 

tutaj jest zestaw danych:

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

Spróbuj pakiet intervals:

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)) 

z próbką danych zmniejsza to 15 rzędów na następujących 13 rzędów (poprzez łączenie rzędów 1 i 2 i rzędy 12 i 13 w pierwotnej ramce danych)

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

Jednym rozwiązaniem jest najpierw rozdzielić odstępach czasu, tak, że są one czasami równe, ale nigdy częściowo się nie nakładają, a oni usuwają duplikaty. Problem polega na tym, że pozostaje nam wiele małych interwałów, a ich scalanie nie wygląda prosto.

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 
}) 

Edycja: Innym koncepcyjnie roztworu czyszczącego, który poprawia non seryjnej oporową przedziałów problemu jest zliczanie liczby otwartych sesji dla każdego użytkownika i urządzenia: gdy przestaje być równa zero, użytkownik ma zalogowany (z jedną lub kilkoma sesjami), gdy spadnie do zera, użytkownik zamknął wszystkie swoje sesje.

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 
}) 

Answer 3

Alternatywne rozwiązanie wykorzystujące klasę interval z lubridate.

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

Teraz potrzebujemy funkcji do testowania na zakładki. Zobacz Determine Whether Two Date Ranges Overlap.

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

Teraz wywołaj to we wszystkich parach interwałów.

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

Zachodzące rzędy:

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

a wiersze, aby usunąć po prostu index[2, overlaps].

Answer 4

Rozwiązanie Pseudokod: O (n log n), O (n), jeśli dane są już znane, aby posortować je prawidłowo.

Rozpocznij od posortowania danych według użytkownika, maszyny i czasu rozpoczęcia (tak, że wszystkie wiersze dla danego użytkownika na danym komputerze są zgrupowane razem, a wiersze w obrębie każdej grupy są w kolejności rosnącej od początku czas).

1. Inicjalizuj "interwał pracy" na null/nil/undef/etc.

2. Dla każdego wiersza w celu:

   • Jeśli czas pracy istnieje i należący do innego użytkownika lub innej maszynie niż prąd rzędu, wyjście i usunąć odstęp roboczy.
   • Jeśli istnieje przerwa robocza, a czas jej zakończenia jest ściśle przed czasem rozpoczęcia bieżącego wiersza, wypisz i wyczyść przerwę roboczą.
   • Jeśli odstęp czasu roboczego istnieje, to musi należeć do tego samego użytkownika i komputera, a także pokrywać się lub przerywać interwał bieżącego wiersza, dlatego należy ustawić czas zakończenia działania na czas zakończenia bieżącego wiersza.
   • W przeciwnym razie interwał roboczy nie istnieje, dlatego ustaw interwał roboczy na bieżący wiersz.

3. Wreszcie, jeśli istnieje przerwa robocza, należy ją wyprowadzić.

Answer 5

Nie wiem, czy to jest to, czego szukasz, czy nie, lub czy zadziałałoby lepiej niż to, co już masz. Jest to rozwiązanie typu powershell, które używa tabeli mieszania z kluczami, które są kombinacją nazwy użytkownika i nazwy komputera. Wartości są skrótem czasu początkowego i końcowego.

Jeśli klucz (sesja) już istnieje, aktualizuje czas zakończenia. Jeśli nie, tworzy jeden i ustawia czas rozpoczęcia i początkowy czas zakończenia. Gdy napotka w rekordzie nowe rekordy sesji dla tego użytkownika/komputera, aktualizuje czas zakończenia klucza sesji.

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

Po zakończeniu pracy trzeba rozdzielić nazwy użytkowników i komputerów z powrotem na klawisze.