fortran66のブログ

fortran について書きます。

しつこくShell sort

Win32で走らせると、4割がたスピードアップします。Quick sortの場合はx64とWin32で速さは変わらないのですが・・

■実行結果

Win32では10**9個のデータを確保できませんでした。

x64の場合の結果

■ソースプログラム

bubble sortの代わりにinsertion sortを使ってみました。速さにはほとんど差がありません。
必要なオプション
/assume:realloc_lhs

MODULE m_sort
  IMPLICIT NONE
 CONTAINS

  PURE FUNCTION ssort(x) ! Shell Sort
    REAL, ALLOCATABLE :: ssort(:)
    REAL, INTENT(IN) :: x(:)
    REAL :: tmp
    INTEGER :: i, j, k, kmax, igap      
    INTEGER, PARAMETER :: igaps(0:25) = [( INT( (9.0 * (9.0/4.0)**i - 4.0) / 5.0 ), i = 0, 25 )] !Tokuda's gap 

    ssort = x
    DO kmax = 0, 24
     IF ( igaps(kmax + 1) > INT(SIZE(x) * 4.0 / 9.0) ) EXIT
    END DO

    DO k = kmax, 0, -1
     igap = igaps(k)
     DO i = igap, SIZE(x)       ! insertion sort
      tmp = ssort(i)
      DO j = i, 1 + igap, -igap
       IF ( ssort(j - igap) > tmp ) THEN 
        ssort(j) = ssort(j - igap)
       ELSE
        EXIT
       END IF
      END DO
      ssort(j) = tmp
     END DO
    END DO

    RETURN
  END FUNCTION ssort

END MODULE m_sort
!========================================================
PROGRAM sort
 USE m_sort
 IMPLICIT NONE
 REAL, ALLOCATABLE :: x(:), y(:)
 REAL :: t0, t1
 INTEGER :: i

 CALL RANDOM_SEED()

 DO i = 0, 8
  ALLOCATE( x(10**i) )
  CALL RANDOM_NUMBER(x)
  CALL CPU_TIME(t0)
  y = ssort(x)
  CALL CPU_TIME(t1)
  PRINT *, i, SIZE(x), t1 - t0
  DEALLOCATE( x, y )
 END DO

 STOP
END PROGRAM sort