fortran - Fortran 等价于 unique

Question

我发现了很多可以解决这个问题的问题，但没有一个能直接回答这个问题:

-在 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

我无法控制自己，所以我写了一个你可能会喜欢的答案。以下代码将为未排序整数的输入数组按升序返回唯一值数组。请注意，输出结果是实际值，而不仅仅是索引。

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 个 LOC 中(减去 var 声明)。所以这似乎是一个公平的权衡。无论如何，我确信可以使用某种屏蔽语句来优化 unique_sort 以获得更高的速度，但那是另一天的事了。

<小时/>

更新上面显示的时序是从测试程序中获得的，其中每个子例程都放置在模块中并通过过程调用执行。然而，当将 unique_sort 直接放置在主程序中时，我发现性能有了惊人的巨大提升，100 万次运行仅需约 0.08 秒即可完成。仅仅通过不使用过程就可以实现约 25 倍的加速，这对我来说似乎很奇怪 - 通常，我假设编译器优化了过程调用的成本。例如，我发现 remove_dup 或 unique_indices 无论是通过过程执行还是直接放置在主程序中，性能都没有差异。