Mam długi zestaw danych z kolumnami reprezentującymi czasy rozpoczęcia i zakończenia i chcę upuścić wiersz, jeśli pokrywa się on z innym i ma wyższy priorytet (np. 1 jest najwyższym priorytetem). Moje przykładowe dane to
library(tidyverse)
library(lubridate)
times_df <- tibble(start = as_datetime(c("2019-10-05 14:05:25",
"2019-10-05 17:30:20",
"2019-10-05 17:37:00",
"2019-10-06 04:43:55",
"2019-10-06 04:53:45")),
stop = as_datetime(c("2019-10-05 14:19:20",
"2019-10-05 17:45:15",
"2019-10-05 17:50:45",
"2019-10-06 04:59:00",
"2019-10-06 05:07:10")), priority = c(5,3,4,3,4))
Sposób, w jaki wpadłem na problem, polega anti_join
na odwróceniu problemu, znajdując nakładki o wyższej wartości priorytetu, a następnie używając znaku an, aby usunąć je z oryginalnej ramki danych. Ten kod nie działa, jeśli trzy kropki pokrywają się z tym samym punktem czasowym i jestem pewien, że istnieje bardziej wydajny i funkcjonalny sposób na zrobienie tego.
dropOverlaps <- function(df) {
drops <- df %>%
filter(stop > lead(start) | lag(stop) > start) %>%
mutate(group = ({seq(1, nrow(.)/2)} %>%
rep(each=2))) %>%
group_by(group) %>%
filter(priority == max(priority))
anti_join(df, drops)
}
dropOverlaps(times_df)
#> Joining, by = c("start", "stop", "priority")
#> # A tibble: 3 x 3
#> start stop priority
#> <dttm> <dttm> <dbl>
#> 1 2019-10-05 14:05:25 2019-10-05 14:19:20 5
#> 2 2019-10-05 17:30:20 2019-10-05 17:45:15 3
#> 3 2019-10-06 04:43:55 2019-10-06 04:59:00 3
Czy ktoś może mi pomóc uzyskać taką samą wydajność, ale z czystszą funkcją? Bonus, jeśli może obsłużyć dane wejściowe z co najmniej trzema okresami, które się pokrywają.
combn
, choć może być drogo, jeśli masz dużo wierszy.times_df %>% mutate(interval = interval(start, stop)) %>% {combn(nrow(.), 2, function(x) if (int_overlaps(.$interval[x[1]], .$interval[x[2]])) x[which.min(.$priority[x])], simplify = FALSE)} %>% unlist() %>% {slice(times_df, -.)}
plyranges
który dostosowuje IRanges / GRanges (używane do znalezienia nakładających się na siebie genomów) dla Tidyverse. Myślę, że możesz przekształcić swoje czasy w zakresy „genomowe”, zamieniając dni + godziny na liczby całkowite godzin („choromosom”), a minuty + sekundy na liczby całkowite sekund („nukleotydy”). Jeśli spojrzałeś na dane wyjściowepair_overlaps
(i użyłeś kolumny identyfikatora do usunięcia nakładania się siebie), możesz zachować swój priorytet i zrobić ładny filtr wyników + wewnętrzna_łącz z oryginalną tabelą. Jest hacky, ale powinien zoptymalizować łatwość kodowania + wydajność.Odpowiedzi:
Oto
data.table
rozwiązanie służącefoverlaps
do wykrywania nakładających się rekordów (jak już wspomniano w @GenesRus). Nakładające się rekordy są przypisywane do grup w celu filtrowania rekordu za pomocą max. priorytet w grupie. Dodałem dwa kolejne rekordy do przykładowych danych, aby pokazać, że ta procedura działa również w przypadku trzech lub więcej pokrywających się rekordów:Edycja: zmodyfikowałem i przetłumaczyłem rozwiązanie @ pgcudahy,
data.table
które daje jeszcze szybszy kod:Aby uzyskać więcej informacji, zobacz
?foverlaps
- Istnieje kilka bardziej użytecznych funkcji zaimplementowanych do kontrolowania tego, co uważa się za nakładanie się, takie jakmaxgap
,minoverlap
lubtype
(dowolne, w obrębie początku, końca, równości).Aktualizacja - nowy test porównawczy
Kod testu porównawczego:
źródło
Mam funkcję pomocniczą, która grupuje nakładające się dane / dane czasowe za pomocą pakietu igraph (może zawierać bufor nakładający się, tzn. Zakończenie jest w ciągu 1 minuty ...)
Użyłem go do grupowania twoich danych w oparciu o interwały w trybie lubridate, a następnie wykonałem pewne przekierowania danych, aby uzyskać tylko najwyższy priorytet z nakładających się czasów.
Nie jestem pewien, jak dobrze się skaluje.
Co daje:
źródło
Poszedłem do dziury królika, patrząc na drzewa interwałów (i implementacje R, takie jak IRanges / plyranges), ale myślę, że ten problem nie wymaga tak zaangażowanej struktury danych, ponieważ czasy rozpoczęcia można łatwo sortować. Rozszerzyłem również zestaw testowy, taki jak @ismirsehregal, aby objąć więcej potencjalnych relacji interwałowych, takich jak interwał rozpoczynający się przed i kończący po swoim sąsiedztwie lub gdy trzy przedziały zachodzą na siebie, ale pierwszy i ostatni nie nakładają się na siebie, lub dwa rozpoczynające się przedziały i zatrzymaj się dokładnie w tym samym czasie.
Następnie wykonuję dwa przejścia przez każdy interwał, aby sprawdzić, czy pokrywa się on ze swoim poprzednikiem lub następcą
stop >= lead(start, default=FALSE)
istart <= lag(stop, default=FALSE))
Podczas każdego przejścia następuje drugie sprawdzenie, czy priorytet przedziału ma wyższą wartość liczbową niż poprzednik lub następca
priority > lead(priority, default=(max(priority) + 1))
. Podczas każdego przejścia, jeśli oba warunki są spełnione, flaga „usuń” jest ustawiana na wartość true w nowej kolumnie za pomocąmutate
. Wszelkie wiersze z flagą usuwania są następnie filtrowane.Pozwala to uniknąć sprawdzania wszystkich potencjalnych kombinacji przedziałów, takich jak odpowiedź @ Paula (porównania 2n i n!), A także akceptuje moją niewiedzę na temat teorii grafów :)
Podobnie odpowiedź @ ismirsehregal zawiera magię data.table, która jest poza moim zrozumieniem.
@ Rozwiązanie MKa wydaje się nie działać z> 2 nakładającymi się okresami
Testowanie rozwiązań daje
Z tego kodu
źródło
tibble
strukturą i wygląda napull()
to, że był przyczyną problemu. Bodataframe()
powinno działać tak, jak jest. Właśnie zaktualizowałem odpowiedź.data.table
dzięki czemu wszystko jest jeszcze szybsze (sprawdź mój nowy test porównawczy).Używając również
igraph
do identyfikowania nakładających się grup, możesz spróbować:źródło