直接質問に答えるユニーク

Question

私はこの問題を好転多くの質問を発見したが、誰にも負けないFORTRAN同等：

-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を削除....）。私はウィキペディアに基づいて緩やかにマージソートアルゴリズムと "ユニークな"関数を結合しました。ガッツが@HighPerformanceMarkの提案でモジュール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 

に含まれる、関数は単に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 

は（unique_indices）あなたの例では、上記（unique_sort）間の比較をタイミングのthis gistを参照してください、そして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についてはgistを参照してください）。まったく）。

一方、unique_sortは、約2倍の時間がかかりますが、ソートされていない入力を処理するように設計されています。また、8 LOC（var宣言を引いたもの）でソートされた順序で値を返します。それは公正なトレードオフのようです。 Anywho、私は確信しているunique_sortは、マスキングステートメントのいくつかの並べ替えを使用して高速化のために最適化することができますが、それは別の日です。上に示した

---

更新 タイミングは、各サブルーチンがモジュールに入れ、プロシージャ・コールを介して実行されたテストプログラムから入手しました。しかし、unique_sortがメインプログラムに直接置かれ、100万回の実行で〜0.08秒しか完了しなかった場合、パフォーマンスが驚くほど大きく改善されました。プロシージャを使わないだけで〜25倍の高速化は私にとっては奇妙に思えます - 通常、コンパイラはプロシージャコールのコストを最適化すると仮定します。たとえば、remove_dupまたはunique_indicesのパフォーマンスの違いが、プロシージャを介して実行されたのか、メインプログラムに直接置かれたのかには違いがないことがわかりました。