R 코드가있는 HackerRank의 The Grid Search

Question

HackerRank의 pretty simple problem에서 며칠 동안 일해 왔지만 시간 초과 문제가있어 더 이상 코드를 최적화 할 수 없습니다.

문제는 다음과 같습니다. 숫자의 2D 배열 (R * C 치수)이 주어지면 주어진 2D 패턴 (차원 * * c)의 발생을 찾으십시오. 여기

당신은 변수의 재현 예를 들면 다음과 같습니다

pattern <- c("11111", "11111", "11110") 
text <- c("111111111111111", 
"111111111111111", 
"111111011111111", 
"111111111111111", 
"111111111111111") 
R <- 5 
C <- 15 
r <- 3 
c <- 5 

그것은 정규식 문제의 일종이지만, 2D, 그리고 이것이 내가 즉시 사용 가능한 기능으로 어디서나 찾을 수있는 일입니다 in R. 내가 대처할 수 있었던 몇 가지 모서리 사례가 있습니다. 위의 버전은 일반적인 경우 '정규식'이 비참하게 패턴을 찾지 못하는 경우 중 하나입니다. .

아래 코드는 15 개 중 13 개가 완벽하게 작동하지만 일부 테스트 (예 : R * C = 500 * 500 및 r * c = 236)와 비교하여 시간 초과로 인해 실패합니다. * 208.

RW <- c() 
    pattern2 <- paste0(pattern, collapse = "") 
    RW <- c(rep(NA,(C-c+1)*(R-r+1))) 
    for (v in 1:(C-c+1)) 
    { 
     for (y in 1:(R-r+1)) 
     { 
     RW[(C-c+1)*(y-1)+v] <- paste0(substr(text[y:(y+r-1)],v,c+v-1),collapse="") 
     } 
    } 
    per <- ifelse(pattern %in% RW, result <- "YES",result <- "NO") 
    cat(result, "\n") 

각 시험 5 건까지가 있습니다,이 내 코드가 실패하는 이유입니다하십시오 : 그것은 5 개 부분으로 테스트를 깨는 일 수 있지만,이 경우는 시간 임계 값 전달 큰 R C 및 r 치수와 함께 결합됩니다.

아무도 코드 성능을 향상시키는 방법에 대한 아이디어가 있습니까?

Answer 1

접근 방식을 유지하려는 경우 substr이 아마도 매우 빠르지 않기 때문에 첫 번째 제안은 문자열을 숫자 행렬로 변환하는 것입니다.

Knuth-Morris-Pratt Algorithm과 같은 두 개 이상의 장소에서 위치를 이동시키는보다 정교한 검색 알고리즘을 더 사용할 수 있습니다.

그러나, for 루프는 항상 R에서 매우 느릴 것이므로이 상황에서 가장 좋은 방법은 실제로 정규 표현식이라고 생각합니다. 큰 그리드의 행을 하나의 긴 문자열로 연결하면 패턴의 행 사이의 문자 수가 고정됩니다. 당신의`for` 루프하는 하나 개의 개선 들여 쓰기

grepl(
    paste0(pattern[1], ".{", C - c, ",}", 
      pattern[2], ".{", C - c, "}", 
      pattern[3]), 
    paste0(text, collapse = "") 
    ) 

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm