无论如何检查矩阵一行中的 n 个项在 fortran 中是否相等？
Is there anyway to check if n number of terms in a row of a matrix are equal in fortran?
我想知道是否有一种快速的方法可以让 Fortran 遍历 maxtrix 的行并确定 n 个项是否相等。
我找不到与我类似的问题，也找不到任何在线帮助。
假设我们考虑一个整数矩阵，它的成本为 O(N³)，N 是矩阵的维数。本质上，对于每一行，您需要将每个元素与该行中的其他元素进行比较，这需要 O(N³) 操作。您可能需要自己编写，但这没什么大不了的，循环遍历行并分别检查每个元素，如果某个元素出现 n 次
integer :: M(N, N) ! matrix to check
integer :: n, i, j, k, counter ! flag if a value appears n times
logical :: appears
appears = .false.
do i = 1, N ! loop over the rows
do j = 1, N ! loop over the entries
counter = 1
do k = j + 1, N
! check if the elements are the same, if yes, increase the counter
! exact implementation depends on type of M
if(M(i, k) == M(i, j)) counter = counter + 1
! check if this element appears n times
if(counter == n) appears = .true.
! or even more often?
if(counter > n) appears = .false.
end do
end do
end do
您可以根据需要进行调整，但您也可以这样做。
I was wondering if there was a quick way to have fortran look throughout a maxtrix’s rows and determine if n number of terms are equal.
据我了解你的问题，这就是你想要的：
具有签名的函数：(integer(:), integer) -> logical
此函数接收一维数组 line 并检查是否有任何值出现 至少 n 次在数组
函数是不是应该表示什么或多少 是那些值、它们的位置或重复的确切次数
有很多方法可以实现这一点。 "What is the most efficient?" 这将取决于您的数据、系统、编译器等的具体情况。为了说明这一点，我提出了 3 种不同的解决方案。当然，他们都给出了正确的答案。建议您使用 真实数据 .
的样本对它们中的每一个（或任何其他您提出的）进行测试
天真的解决方案 #1 - 很好的循环
这是默认算法。它遍历 line 并将每个值存储到聚合器列表 packed 中，其中包含到目前为止找到的每个不同值，以及它们出现的次数。在任何值达到 n 次重复的那一刻，功能 returns .true.。如果没有值达到 n 次重复，并且没有更多机会完成谓词，则 returns .false..
我说 defalut 因为它是基于好的 ol' do 循环。如果您对数据、系统甚至编程语言细节的性质的信息为零，这可能是一般情况下的最佳选择。聚合器会在满足条件后立即终止函数，但代价是额外的列表遍历（在其长度上）。如果数据中有许多不同的值并且 n 很大，则聚合器会变得太长并且查找可能成为一项昂贵的操作。此外，几乎没有并行、矢量化和其他优化的空间。
! generic approach, with loops and aggregator
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
integer :: i, j, max_repetitions, qty_distincts
! packed(1,:) -> the distinct integers found so far
! packed(2,:) -> number of repetitions of each distinct integer so far
integer :: packed(2, size(line) - n + 2)
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
packed(:, 1) = [line(1), 1]
qty_distincts = 1
max_repetitions = 1
i = 1
! iterate until there aren't enough elements left to reach n repetitions
outer: do, while(i - max_repetitions <= size(line) - n)
i = i + 1
! test for a match on packed
do j = 1, qty_distincts
if(packed(1, j) == line(i)) then
packed(2, j) = packed(2, j) + 1
if(packed(2, j) == n) then
has_at_least_n_repeated = .true.
return
end if
max_repetitions = max(max_repetitions, packed(2, j))
cycle outer
end if
end do
! add to packed
qty_distincts = qty_distincts + 1
packed(:, qty_distincts) = [line(i), 1]
end do outer
has_at_least_n_repeated = .false.
end if
end
天真的解决方案 #2 - 尝试一些矢量化
这种方法试图利用 Fortran 的 arraysh 特性和内部函数的快速实现。不是内部 do 循环，而是使用数组参数调用内部 count，允许编译器进行一些向量化。此外，如果您有任何并行工具，或者如果您知道如何使用 coarrays（并且您的编译器支持），您可以使用这种方法来实现它们。
这里的缺点是函数会扫描所有元素，即使它们之前出现过。因此，当您的数据中有许多不同的可能值且重复次数很少时，这更适合。虽然，添加包含过去值的缓存列表并使用内部 any，将缓存作为整个数组传递也很容易。
! alternative approach, intrinsic functions without cache
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
Integer :: i
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
! iterate until there aren't enough elements left to reach n repetitions
do i = 1, size(line) - n + 1
if(count(line(i + 1:) == line(i)) + 1 >= n) then
has_at_least_n_repeated = .true.
return
end if
end do
has_at_least_n_repeated = .false.
end if
end
天真的解决方案 #3 - 函数式风格
这是我最喜欢的（个人标准）。我喜欢函数式语言，我喜欢将它的某些方面借用到命令式语言中。这种方法将计算委托给内部辅助递归函数。这里没有 do 循环。在每个函数调用中，只有 line 的一部分作为参数传递：一个较短的数组，其中只有到目前为止未检查的值。也不需要缓存。
老实说，Fortran 对递归的支持远非很好 - 没有尾递归，编译器通常实现低调用堆栈限制，递归阻止了许多自动优化。虽然算法很聪明，但我喜欢它的样子，在进行一些测试和比较之前我不会放弃它。
注意：Fortran 不允许在主程序的contains 部分嵌套过程。要使其按呈现的方式工作，您需要将该函数放入模块、子模块或使其成为外部函数。其他选项是提取嵌套函数并使其成为同一范围内的普通函数。
! functional approach, auxiliar recursive function and no loops
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
has_at_least_n_repeated = aux(line)
end if
contains
! on each iteration removes all entries of an element from array
pure recursive function aux(section) result(out)
integer, intent(in) :: section(:)
logical :: out, mask(size(section))
integer :: left
mask = section /= section(1)
left = count(mask)
if(size(section) - left >= n) then
out = .true.
else if(n > left) then
out = .false.
else
out = aux(pack(section, mask))
end if
end
end
结论
在选择要遵循的路径之前进行测试！我在这里谈了一点我个人对每种方法的感受及其影响，但如果该站点上的某些 Fortran Gurus 加入讨论并提供准确的信息和批评者，那就太好了.
这是@RodrigoRodrigues 已经提供的解决方案的实用 替代方案。在没有任何好的证据（问题严重未明确说明）的情况下，我们需要关注渐近复杂性和所有这些好东西，这里有一个简单直接的函数，我花了大约 5 分钟的时间来设计、编码和测试。
此函数接受一个 rank-1 整数数组并返回一个 rank-1 整数数组，每个元素对应于输入数组中该元素的计数。如果该描述让您感到困惑，请耐心等待并阅读相当简单的代码：
FUNCTION get_counts(arr) RESULT(rslt)
INTEGER, DIMENSION(:), INTENT(in) :: arr
INTEGER, DIMENSION(SIZE(arr)) :: rslt
INTEGER :: ix
DO ix = 1, SIZE(arr)
rslt(ix) = COUNT(arr(ix)==arr)
END DO
END FUNCTION get_counts
对于输入数组[1,1,2,3,4,1,5]它returns[3,3,1,1,1,3,1]。如果 OP 想用它作为函数的基础来查看是否有任何值出现 n 次，那么 OP 可以写
any(get_counts(rank_1_integer_array)==n)
如果 OP 想知道哪些元素出现 n 次，那么使用 get_counts 的结果来引用原始数组以提取该元素是相当简单的。
这个解决方案是实用，因为它节省了我的时间而不是计算机的时间。我的解决方案有点浪费 space，这对于非常大的输入数组来说可能是个问题。 Rodrigo 的任何解决方案在时间和 space 方面都可能优于我的解决方案。
我把这个问题的意思是要确定一行中的任何值是否至少重复了 n 次。为了解决这个问题，我选择使用 C 标准库中的 qsort 对每一行的副本进行排序，然后很容易找到每个 运行 值的长度。
module sortrow
use ISO_C_BINDING
implicit none
interface
subroutine qsort(base, num, size, compar) bind(C,name='qsort')
import
implicit none
integer base(*)
integer(C_SIZE_T), value :: num, size
procedure(icompar) compar
end subroutine qsort
end interface
contains
function icompar(p1, p2) bind(C)
integer(C_INT) icompar
integer p1, p2
select case(p1-p2)
case(:-1)
icompar = -1
case(0)
icompar = 0
case(1:)
icompar = 1
end select
end function icompar
end module sortrow
program main
use sortrow
implicit none
integer, parameter :: M = 3, N = 10
integer i, j
integer array(M,N)
real harvest
integer, allocatable :: row(:)
integer current, maxMatch
call random_seed
do i = 1, M
do j = 1, N
call random_number(harvest)
array(i,j) = harvest*3
end do
end do
do i = 1, M
row = array(i,:)
call qsort(row, int(N,C_SIZE_T), C_SIZEOF(array(1,1)), icompar)
maxMatch = 0
current = 1
do j = 2, N
if(row(j) == row(j-1)) then
current = current+1
else
current = 1
end if
maxMatch = max(maxMatch,current)
end do
write(*,'(*(g0:1x))') array(i,:),'maxMatch =',maxMatch
end do
end program main
样本运行:
0 0 0 2 0 2 1 1 1 0 maxMatch = 5
2 1 2 1 0 1 2 1 2 0 maxMatch = 4
0 0 2 2 2 2 2 0 1 1 maxMatch = 5
我想知道是否有一种快速的方法可以让 Fortran 遍历 maxtrix 的行并确定 n 个项是否相等。 我找不到与我类似的问题，也找不到任何在线帮助。
假设我们考虑一个整数矩阵，它的成本为 O(N³)，N 是矩阵的维数。本质上，对于每一行，您需要将每个元素与该行中的其他元素进行比较，这需要 O(N³) 操作。您可能需要自己编写，但这没什么大不了的，循环遍历行并分别检查每个元素，如果某个元素出现 n 次
integer :: M(N, N) ! matrix to check
integer :: n, i, j, k, counter ! flag if a value appears n times
logical :: appears
appears = .false.
do i = 1, N ! loop over the rows
do j = 1, N ! loop over the entries
counter = 1
do k = j + 1, N
! check if the elements are the same, if yes, increase the counter
! exact implementation depends on type of M
if(M(i, k) == M(i, j)) counter = counter + 1
! check if this element appears n times
if(counter == n) appears = .true.
! or even more often?
if(counter > n) appears = .false.
end do
end do
end do
您可以根据需要进行调整，但您也可以这样做。
I was wondering if there was a quick way to have fortran look throughout a maxtrix’s rows and determine if n number of terms are equal.
据我了解你的问题，这就是你想要的：
具有签名的函数：
(integer(:), integer) -> logical此函数接收一维数组
line并检查是否有任何值出现 至少n次在数组函数是不是应该表示什么或多少 是那些值、它们的位置或重复的确切次数
有很多方法可以实现这一点。 "What is the most efficient?" 这将取决于您的数据、系统、编译器等的具体情况。为了说明这一点，我提出了 3 种不同的解决方案。当然，他们都给出了正确的答案。建议您使用 真实数据 .
的样本对它们中的每一个（或任何其他您提出的）进行测试天真的解决方案 #1 - 很好的循环
这是默认算法。它遍历 line 并将每个值存储到聚合器列表 packed 中，其中包含到目前为止找到的每个不同值，以及它们出现的次数。在任何值达到 n 次重复的那一刻，功能 returns .true.。如果没有值达到 n 次重复，并且没有更多机会完成谓词，则 returns .false..
我说 defalut 因为它是基于好的 ol' do 循环。如果您对数据、系统甚至编程语言细节的性质的信息为零，这可能是一般情况下的最佳选择。聚合器会在满足条件后立即终止函数，但代价是额外的列表遍历（在其长度上）。如果数据中有许多不同的值并且 n 很大，则聚合器会变得太长并且查找可能成为一项昂贵的操作。此外，几乎没有并行、矢量化和其他优化的空间。
! generic approach, with loops and aggregator
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
integer :: i, j, max_repetitions, qty_distincts
! packed(1,:) -> the distinct integers found so far
! packed(2,:) -> number of repetitions of each distinct integer so far
integer :: packed(2, size(line) - n + 2)
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
packed(:, 1) = [line(1), 1]
qty_distincts = 1
max_repetitions = 1
i = 1
! iterate until there aren't enough elements left to reach n repetitions
outer: do, while(i - max_repetitions <= size(line) - n)
i = i + 1
! test for a match on packed
do j = 1, qty_distincts
if(packed(1, j) == line(i)) then
packed(2, j) = packed(2, j) + 1
if(packed(2, j) == n) then
has_at_least_n_repeated = .true.
return
end if
max_repetitions = max(max_repetitions, packed(2, j))
cycle outer
end if
end do
! add to packed
qty_distincts = qty_distincts + 1
packed(:, qty_distincts) = [line(i), 1]
end do outer
has_at_least_n_repeated = .false.
end if
end
天真的解决方案 #2 - 尝试一些矢量化
这种方法试图利用 Fortran 的 arraysh 特性和内部函数的快速实现。不是内部 do 循环，而是使用数组参数调用内部 count，允许编译器进行一些向量化。此外，如果您有任何并行工具，或者如果您知道如何使用 coarrays（并且您的编译器支持），您可以使用这种方法来实现它们。
这里的缺点是函数会扫描所有元素，即使它们之前出现过。因此，当您的数据中有许多不同的可能值且重复次数很少时，这更适合。虽然，添加包含过去值的缓存列表并使用内部 any，将缓存作为整个数组传递也很容易。
! alternative approach, intrinsic functions without cache
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
Integer :: i
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
! iterate until there aren't enough elements left to reach n repetitions
do i = 1, size(line) - n + 1
if(count(line(i + 1:) == line(i)) + 1 >= n) then
has_at_least_n_repeated = .true.
return
end if
end do
has_at_least_n_repeated = .false.
end if
end
天真的解决方案 #3 - 函数式风格
这是我最喜欢的（个人标准）。我喜欢函数式语言，我喜欢将它的某些方面借用到命令式语言中。这种方法将计算委托给内部辅助递归函数。这里没有 do 循环。在每个函数调用中，只有 line 的一部分作为参数传递：一个较短的数组，其中只有到目前为止未检查的值。也不需要缓存。
老实说，Fortran 对递归的支持远非很好 - 没有尾递归，编译器通常实现低调用堆栈限制，递归阻止了许多自动优化。虽然算法很聪明，但我喜欢它的样子，在进行一些测试和比较之前我不会放弃它。
注意：Fortran 不允许在主程序的contains 部分嵌套过程。要使其按呈现的方式工作，您需要将该函数放入模块、子模块或使其成为外部函数。其他选项是提取嵌套函数并使其成为同一范围内的普通函数。
! functional approach, auxiliar recursive function and no loops
pure logical function has_at_least_n_repeated(line, n)
integer, intent(in) :: line(:), n
if(n < 1 .or. size(line) == 0) then
has_at_least_n_repeated = .false.
else if(n == 1) then
has_at_least_n_repeated = .true.
else
has_at_least_n_repeated = aux(line)
end if
contains
! on each iteration removes all entries of an element from array
pure recursive function aux(section) result(out)
integer, intent(in) :: section(:)
logical :: out, mask(size(section))
integer :: left
mask = section /= section(1)
left = count(mask)
if(size(section) - left >= n) then
out = .true.
else if(n > left) then
out = .false.
else
out = aux(pack(section, mask))
end if
end
end
结论
在选择要遵循的路径之前进行测试！我在这里谈了一点我个人对每种方法的感受及其影响，但如果该站点上的某些 Fortran Gurus 加入讨论并提供准确的信息和批评者，那就太好了.
这是@RodrigoRodrigues 已经提供的解决方案的实用 替代方案。在没有任何好的证据（问题严重未明确说明）的情况下，我们需要关注渐近复杂性和所有这些好东西，这里有一个简单直接的函数，我花了大约 5 分钟的时间来设计、编码和测试。
此函数接受一个 rank-1 整数数组并返回一个 rank-1 整数数组，每个元素对应于输入数组中该元素的计数。如果该描述让您感到困惑，请耐心等待并阅读相当简单的代码：
FUNCTION get_counts(arr) RESULT(rslt)
INTEGER, DIMENSION(:), INTENT(in) :: arr
INTEGER, DIMENSION(SIZE(arr)) :: rslt
INTEGER :: ix
DO ix = 1, SIZE(arr)
rslt(ix) = COUNT(arr(ix)==arr)
END DO
END FUNCTION get_counts
对于输入数组[1,1,2,3,4,1,5]它returns[3,3,1,1,1,3,1]。如果 OP 想用它作为函数的基础来查看是否有任何值出现 n 次，那么 OP 可以写
any(get_counts(rank_1_integer_array)==n)
如果 OP 想知道哪些元素出现 n 次，那么使用 get_counts 的结果来引用原始数组以提取该元素是相当简单的。
这个解决方案是实用，因为它节省了我的时间而不是计算机的时间。我的解决方案有点浪费 space，这对于非常大的输入数组来说可能是个问题。 Rodrigo 的任何解决方案在时间和 space 方面都可能优于我的解决方案。
我把这个问题的意思是要确定一行中的任何值是否至少重复了 n 次。为了解决这个问题，我选择使用 C 标准库中的 qsort 对每一行的副本进行排序，然后很容易找到每个 运行 值的长度。
module sortrow
use ISO_C_BINDING
implicit none
interface
subroutine qsort(base, num, size, compar) bind(C,name='qsort')
import
implicit none
integer base(*)
integer(C_SIZE_T), value :: num, size
procedure(icompar) compar
end subroutine qsort
end interface
contains
function icompar(p1, p2) bind(C)
integer(C_INT) icompar
integer p1, p2
select case(p1-p2)
case(:-1)
icompar = -1
case(0)
icompar = 0
case(1:)
icompar = 1
end select
end function icompar
end module sortrow
program main
use sortrow
implicit none
integer, parameter :: M = 3, N = 10
integer i, j
integer array(M,N)
real harvest
integer, allocatable :: row(:)
integer current, maxMatch
call random_seed
do i = 1, M
do j = 1, N
call random_number(harvest)
array(i,j) = harvest*3
end do
end do
do i = 1, M
row = array(i,:)
call qsort(row, int(N,C_SIZE_T), C_SIZEOF(array(1,1)), icompar)
maxMatch = 0
current = 1
do j = 2, N
if(row(j) == row(j-1)) then
current = current+1
else
current = 1
end if
maxMatch = max(maxMatch,current)
end do
write(*,'(*(g0:1x))') array(i,:),'maxMatch =',maxMatch
end do
end program main
样本运行:
0 0 0 2 0 2 1 1 1 0 maxMatch = 5
2 1 2 1 0 1 2 1 2 0 maxMatch = 4
0 0 2 2 2 2 2 0 1 1 maxMatch = 5