相当于 unique 的 fortran
A fortran equivalent to unique
我发现了很多解决这个问题的问题，但是 none 直接回答了这个问题：
-在 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
我的尝试希望列表是有序的，但如果取消该要求会更好
我就是忍不住，所以我写了一个你可能会喜欢的答案。以下代码将 return 一个由未排序整数输入数组 升序排列的唯一值数组。请注意，输出结果是实际值，而不仅仅是索引。
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 for timing comparisons between (unique_sort) above, your example (unique_indices), and the example at 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 不需要对输入数组进行预排序，实际上 return 是值而不是索引（请参阅 unique_indices 的修改版本的要点 returns 而不是值，这似乎根本不会减慢它的速度）。
另一方面，unique_sort 需要大约两倍的时间，但设计用于处理未排序的输入，并且 returns 按排序顺序排列的值，在 8 LOC 中（减去 var声明）。所以这似乎是一个公平的权衡。任何人，我确信 unique_sort 可以使用某种掩码语句进行优化以提高速度，但那是另一天的事了。
更新
上面显示的时序是从一个测试程序中获得的，其中每个子例程都放在一个模块中并通过过程调用执行。然而，当 unique_sort 直接放在主程序中时，我发现性能有了惊人的巨大改进，运行 100 万次仅需约 0.08 秒。仅仅通过不使用过程来加速约 25 倍对我来说似乎很奇怪 - 通常，我假设编译器优化了过程调用的成本。例如，我发现 remove_dup 或 unique_indices 的性能没有差异，无论它们是通过过程执行还是直接放在主程序中。
在@VladimirF 指出我比较过度后，我发现我可以对我的原始代码进行矢量化（删除 do 循环 do kx....）。我已将 "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=unique(list)。上面当然不简洁，但看起来很清楚，而且比我原来的或其他提出的解决方案快大约 200 倍。
我发现了很多解决这个问题的问题，但是 none 直接回答了这个问题：
-在 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
我的尝试希望列表是有序的，但如果取消该要求会更好
我就是忍不住，所以我写了一个你可能会喜欢的答案。以下代码将 return 一个由未排序整数输入数组 升序排列的唯一值数组。请注意，输出结果是实际值，而不仅仅是索引。
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 for timing comparisons between (unique_sort) above, your example (unique_indices), and the example at 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 不需要对输入数组进行预排序，实际上 return 是值而不是索引（请参阅 unique_indices 的修改版本的要点 returns 而不是值，这似乎根本不会减慢它的速度）。
另一方面，unique_sort 需要大约两倍的时间，但设计用于处理未排序的输入，并且 returns 按排序顺序排列的值，在 8 LOC 中（减去 var声明）。所以这似乎是一个公平的权衡。任何人，我确信 unique_sort 可以使用某种掩码语句进行优化以提高速度，但那是另一天的事了。
更新
上面显示的时序是从一个测试程序中获得的，其中每个子例程都放在一个模块中并通过过程调用执行。然而，当 unique_sort 直接放在主程序中时，我发现性能有了惊人的巨大改进，运行 100 万次仅需约 0.08 秒。仅仅通过不使用过程来加速约 25 倍对我来说似乎很奇怪 - 通常，我假设编译器优化了过程调用的成本。例如，我发现 remove_dup 或 unique_indices 的性能没有差异，无论它们是通过过程执行还是直接放在主程序中。
在@VladimirF 指出我比较过度后，我发现我可以对我的原始代码进行矢量化（删除 do 循环 do kx....）。我已将 "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=unique(list)。上面当然不简洁，但看起来很清楚，而且比我原来的或其他提出的解决方案快大约 200 倍。