一個FORTRAN相當於獨特

Question

我發現，解決此問題轉了很多問題，但沒有直接回答這個問題：

-in FORTRAN，什麼是（a）速度最快（掛鐘）和（b）從整數

必須有名單消除重複最優雅（簡潔明瞭）的方式比我愚蠢的嘗試更好的辦法：

Program unique 
implicit none 
! find "indices", the list of unique numbers in "list" 
integer(kind = 4) :: kx, list(10) 
integer(kind = 4),allocatable :: indices(:) 
logical :: mask(10) 
!!$ list=(/3,2,5,7,3,1,4,7,3,3/) 
list=(/1,(kx,kx=1,9)/) 
mask(1)=.true. 
do kx=10,2,-1 
    mask(kx)= .not.(any(list(:kx-1)==list(kx))) 
end do 
indices=pack([(kx,kx=1,10)],mask) 
print *,indices 
End Program unique 

我試圖期望列表進行排序，但如果這個要求被解除，那將會更好

Answer 1

@VladimirF指出我過度比較後，發現我可以矢量化我的原始代碼（刪除do循環do kx ....）。我已將鬆散地基於wikipedia的mergesort算法與「unique」功能結合在一起。膽量都包含在模塊SortUnique

Module SortUnique 
contains 
    Recursive Subroutine MergeSort(temp, Begin, Finish, list) 
    ! 1st 3 arguments are input, 4th is output sorted list 
    implicit none 
    integer(kind=4),intent(inout) :: Begin,list(:),temp(:) 
    integer(kind=4),intent(in) :: Finish 
    integer(kind=4) :: Middle 
    if (Finish-Begin<2) then !if run size =1 
     return     !it is sorted 
    else 
     ! split longer runs into halves 
     Middle = (Finish+Begin)/2 
     ! recursively sort both halves from list into temp 
     call MergeSort(list, Begin, Middle, temp) 
     call MergeSort(list, Middle, Finish, temp) 
     ! merge sorted runs from temp into list 
     call Merge(temp, Begin, Middle, Finish, list) 
    endif 
    End Subroutine MergeSort 

    Subroutine Merge(list, Begin, Middle, Finish, temp) 
    implicit none 
    integer(kind=4),intent(inout) :: list(:),temp(:) 
    integer(kind=4),intent(in) ::Begin,Middle,Finish 
    integer(kind=4) :: kx,ky,kz 
    ky=Begin 
    kz=Middle 
    !! While there are elements in the left or right runs... 
    do kx=Begin,Finish-1 
     !! If left run head exists and is <= existing right run head. 
     if (ky.lt.Middle.and.(kz.ge.Finish.or.list(ky).le.list(kz))) then 
      temp(kx)=list(ky) 
      ky=ky+1 
     else 
      temp(kx)=list(kz) 
      kz = kz + 1 
     end if 
    end do 

    End Subroutine Merge 

    Function Unique(list) 
    !! usage sortedlist=Unique(list) 
    implicit none 
    integer(kind=4) :: strt,fin,N 
    integer(kind=4), intent(inout) :: list(:) 
    integer(kind=4), allocatable :: unique(:),work(:) 
    logical,allocatable :: mask(:) 
    ! sort 
    work=list;strt=1;N=size(list);fin=N+1 
    call MergeSort(work,strt,fin,list) 
    ! cull duplicate indices 
    allocate(mask(N)); 
    mask=.false. 
    mask(1:N-1)=list(1:N-1)==list(2:N) 
    unique=pack(list,.not.mask) 

    End Function Unique 

End Module SortUnique 

Program TestUnique 
    use SortUnique 
    implicit none 
    ! find "indices", the list of unique numbers in "list" 
    integer (kind=4),allocatable :: list(:),newlist(:) 
    integer (kind=4) :: kx,N=100000 !N even 
    real (kind=4) :: start,finish,myrandom 

    allocate(list(N)) 
    do kx=1,N 
    call random_number(myrandom) 
    list(kx)=ifix(float(N)/2.*myrandom) 
    end do 

    call cpu_time(start) 

    newlist=unique(list) 

    call cpu_time(finish) 
    print *,"cull duplicates: ",finish-start 
    print *,"size(newlist) ",size(newlist) 

End Program TestUnique 

在@HighPerformanceMark的建議，該功能簡單地援引爲newlist =唯一的（列表）。上述內容當然不是簡明扼要，但似乎很清楚，比我提出的原始解決方案或其他解決方案快200倍。

Answer 2

我只是忍不住自己，所以我寫了一個你可能喜歡的答案。下面的代碼將返回一個唯一值的數組，以升序排列輸入數組的未排序整數。請注意，輸出結果是實際值，而不僅僅是指數。

program unique_sort 
    implicit none 
    integer :: i = 0, min_val, max_val 
    integer, dimension(10) :: val, unique 
    integer, dimension(:), allocatable :: final 

    val = [ 3,2,5,7,3,1,4,7,3,3 ] 
    min_val = minval(val)-1 
    max_val = maxval(val) 
    do while (min_val<max_val) 
     i = i+1 
     min_val = minval(val, mask=val>min_val) 
     unique(i) = min_val 
    enddo 
    allocate(final(i), source=unique(1:i)) !<-- Or, just use unique(1:i) 
    print "(10i5:)", final 
end program unique_sort 
! output: 1 2 3 4 5 7 

對之間的定時的比較見this gist（unique_sort）以上，你的例子（unique_indices）中，在Rosetta Code（remove_dups）的例子，以及一對夫婦的變化。我想測試@High Performance Mark的代碼，但還沒有。

Run program 1,000,000 times, 100 integers 0<=N<=50 
- unique_sort  t~2.1 sec input: unsorted, w/duplicates output: sorted unique values 
- remove_dup  t~1.4  input: unsorted, w/duplicates output: unsorted unique values 
- unique_indices t~1.0  input: sorted, w/duplicates output: unsorted indices for unique values 
- BONUS!(Python) t~4.1  input: unsorted, w/duplicates output: sorted unique values 

底線：我的機器（I7 8GB筆記本電腦）上unique_indices比remove_dups稍快。然而，remove_dups不需要預先排序輸入數組，而是實際返回值而不是索引（請參閱要修改的unique_indices版本的要點，它會返回值，而這看起來並不會使其變慢完全）。

另一方面，unique_sort需要大約兩倍的時間，但被設計爲處理未排序的輸入，並且還以8排序（在減去var聲明）的排序順序返回值。所以這似乎是一個公平的權衡。任何人，我敢肯定unique_sort可以使用某種掩蔽聲明進行優化以獲得更高的速度，但那是另一天。

---

更新 上面所示的定時，從其中每個子程序放置在模塊中並執行經由一個過程調用的測試程序獲得的。但是，當unique_sort直接放在主程序中時，我發現性能出乎意料的大幅提高，在100萬次運行中只完成了約0.08秒。簡單地通過不使用程序加速〜25x對我來說似乎很奇怪 - 通常我認爲編譯器會優化程序調用的開銷。例如，我發現remove_dup或unique_indices的性能沒有區別，無論它們是通過一個過程執行還是直接放在主程序中。