performance - 我正在寻找有关加快 Boyer-Moore-Horspool 代码的建议

Question

我用 Fortran（我选择的语言）编写了以下代码，认为它会非常快。事实证明，它相当快，但比 FORTRAN 内在（索引）查找子字符串要慢得多。举个例子，如果我在一个完全随机的 5,000,000 个字符的字符串中搜索距离字符串末尾 1,000 个字符的字符串“月亮是气球”，我得到以下时间（平均超过 10 次运行在库存英特尔 HM370（Cannon Lake-H））。我正在运行 Windows 10，仅使用带有 -O3 和 -fno-checking 优化标志的 GCC Fortan）；我的代码（如下）~ 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

标签： performancefortranboyer-moore