Я ищу предложения по ускорению моего кода Бойера-Мура-Хорспула - PullRequest
Новая
       25

Я ищу предложения по ускорению моего кода Бойера-Мура-Хорспула

0 голосов
/ 23 января 2019

Я написал следующий код на Фортране (мой язык выбора), думая, что это будет очень быстро.Оказывается, это довольно быстро, но значительно медленнее встроенного (индекса) FORTRAN для поиска подстрок.В качестве примера, если я ищу строку «5 000 000 символов» для строки «Луна - воздушный шар», которая расположена в 1000 символов от конца строки, я получаю следующие значения времени (в среднем по 10 прогонам насток Intel HM370 (Cannon Lake-H)).Я использую Windows 10, использую GCC Fortan только с флагами оптимизации -O3 и -fno-check);Мой код (ниже) ~ 0,09 секунды Внутренний ~ 0,03 секунды Я ищу какие-либо предложения по рефакторингу кода для его дальнейшего ускорения. 

  INTEGER FUNCTION BOYERMOORE(Text,Pat,Siztext,Sizpat) RESULT(SEARCH)
  IMPLICIT NONE
!
! Dummy arguments
!
  CHARACTER(*)  ::  Pat
  INTEGER  ::  Sizpat
  INTEGER  ::  Siztext
  CHARACTER(*)  ::  Text
  INTENT (IN) Pat, Sizpat, Siztext, Text
!
! Local variables
!
  LOGICAL  ::  found
  INTEGER  ::  i
  INTEGER  ::  j
  INTEGER  ::  k
  INTEGER  ::  maxchar
  INTEGER, DIMENSION(0:Siztext)  ::  skip

!Code starts here
  maxchar = Siztext
  found = .FALSE.
  SEARCH = 0
  IF(Sizpat==0)THEN                             ! Nothing to search for
     SEARCH = 1
     found = .TRUE.
  ENDIF
  skip(0:maxchar) = Sizpat
  DO k = 1, Sizpat - 1                          ! Setup the shift sizes
     skip(IACHAR(Pat(k:k))) = Sizpat - k
  ENDDO
  k = Sizpat
  DO WHILE ((.NOT.found) .AND. (k<=Siztext))    ! Scan
     i = k
     j = Sizpat
     DO WHILE (j>=1)                            ! Match the characters in substring
        IF(Text(i:i)/=Pat(j:j))THEN
           j = -1
        ELSE
           j = j - 1
           i = i - 1
        ENDIF
        IF(j==0)THEN                            ! Found 
           SEARCH = i + 1
           found = .TRUE.
        ENDIF
        k = k + skip(IACHAR(Text(k:k)))         ! Slide window right
     ENDDO
  ENDDO
  RETURN
  END FUNCTION BOYERMOORE
...