如何在 Fortran 上提高代码效率？我解决了一个练习，但我对自己的答案不满意

Question

为了一份工作，我正在自学 Fortran，我对此还很陌生。我尝试了以下练习并得到了正确答案。但我相信一定有更多处理高效的方法来解决同样的问题。

练习：用 Fortran 90 开发一个程序，计算并提供一个包含 2 到 1000 之间素数的数组。

我的解决方案：

        subroutine locate_primes(prime_array,count)
            integer(4), parameter               :: n = 1000
            integer                             :: i,j
            integer, allocatable, intent(out)   :: prime_array(:)
            integer, intent(out)                :: count
        
            j = 2
            i = 3
            count = 1
            
            do while (i<n+1) !counts how many prime numbers are there on the set
                do while (j<i)
                    if (mod(i,j) == 0 ) then
                        go to 100
                    end if
                    j = j + 1
                    if (j == i) then
                        count = count + 1
                    end if
                end do
100             i = i+1
                j = 2
            end do
            
            allocate(prime_array(count)) !allocate an array of the right size for the prime numbers
            count = 1
            prime_array(1) = 2
            j = 2
            i = 3

            do while (i<n+1) !add create an array with all the prime numbers
                do while (j<i)
                    if (mod(i,j) == 0 ) then
                        go to 101
                    end if
                    j = j + 1
                    if (j == i) then
                        count = count + 1
                        prime_array(count)=i
                    end if
                end do
101             i = i+1
                j = 2
            end do
        end subroutine

我自己的解决方案的两个主要问题是，我需要检查 3 到 1000 之间的每个数字两次，使其处理效率低下，内存效率低下。

这个想法是用第一个素数（数字 2）创建一个等级为 1、大小为 1 的数组。然后，我会检查数字 3 是否是质数，如果是，我会将数组的大小增加到 2，并将数字 3 添加到第二个位置。我计划对 1000 以内的每个数字重复此过程。

但是，我很快了解到这种方法不可行，因为你不能简单地更改 Fortran 中数组的大小。唯一的选择是取消分配它，这将导致丢失其中已保存的数字。所以，这就是我尝试过的：

我认为最好的方法是有两个数组：一个是可分配的，另一个是排名为 1 且大小为 500 的数组。因为我知道 2 到 1000 之间的数字中有一半不能是素数（因为它们是 2 的倍数） ），500 的大小绝对足以存储 1 到 1000 之间的所有素数。我会将素数保存在大小为 500 的数组中，并在整数变量中保存计数。之后，我可以使用我计算的大小分配新数组，然后用大小为 500 的数组中的数字填充它。最后，我会释放大小为 500 的数组以节省内存。

这是我的新解决方案：

        subroutine locate_primes_2(prime_array_final,count)
            integer(4), parameter               :: n = 1000
            integer                             :: i,j
            integer, allocatable, intent(out)   :: prime_array_final(:)
            integer, allocatable                :: prime_array_500(:)
            integer, intent(out)                :: count
        
            allocate(prime_array_500(n/2)) !creates an temporary array to save the prime numbers
            j = 2
            i = 3
            count = 1
            prime_array_500(1) = 2
            
            do while (i<n+1) !counts how many prime numbers there are on the set and saves them
                do while (j<i)
                    if (mod(i,j) == 0 ) then
                        go to 102
                    end if
                    j = j + 1
                    if (j == i) then
                        count = count + 1
                        prime_array_500(count) = i
                    end if
                end do
102             i = i+1
                j = 2
            end do
            
            allocate(prime_array_final(count))
            prime_array_final = prime_array_500(1:count) !saves the set of the prime numbers
            deallocate(prime_array_500) !deallocate the array that ocupied unnecessary memory
            
        end subroutine

它似乎处理效率更高，因为我不需要两次检查 3 到 1000 之间的每个数字，但在释放它之前我仍然会得到一个大集合，占用不必要的内存空间。尽管我相信我有一个比一开始的更好的解决方案，但我仍然想询问社区应该如何解决此类问题。

我知道样本量这么小，这可能不是问题，但我正在尝试学习如何更有效地编程。

我还没有研究过 Fortran 中的指针，但这是我的下一个主题。欢迎讨论。

未来如何解决处理效率和内存效率问题？有没有我可以学习的参考资料？如何确定新解决方案是否真的比旧解决方案更好？你有比我更好的解决方案吗？

Answer 1

您的问题更多的是关于算法而不是编程。正如其他人提到的，看看“埃拉托色尼筛子”，我不会更多地讨论算法。关于编程：

• 当有简单的替代方案时，不要使用 goto。在您的示例中，请使用

  exit

  语句来退出循环。还有

  cycle

  语句，它会跳过循环中的其余代码并开始下一次迭代。

• do while <expression>

  已弃用。相反，使用带有退出测试的无限循环：

do
    if (.not.<expression>) exit
    ...
end do

• 您的第一个

  do while

  循环可以替换为经典循环，因为上限在迭代过程中不会改变：

  do i = 1, n

• 一维可分配数组可以动态扩展，例如将元素

  x

  附加到现有数组 A(:) 中，您可以编写

  A = [A, x]

  。这是“分配时分配”功能。请注意，这里有一些陷阱，但是当您事先不知道最终大小时，这很方便（尽管通常性能效率不高）。
• Fortran 指针与 C 指针有很大不同，它们是强类型并完整描述所指向的对象。只要有可能，就应该使用可分配项而不是指针，但在某些情况下指针仍然有用。

最后一句话：Stack Overflow 可能不是学习语言的最佳场所，因为有时需要进行扩展讨论。因此，我提请您关注这个论坛，这是 Fortran 社区的一种“非官方官方”论坛，以及相关的网站以获取一些资源。