Fortran二维数组前N个最大值定位修改的性能优化需求

你的当前方法时间复杂度为O(N*M)（N为要选的前N个最大值数量，M为数组总元素数），在超大规模数据集下效率极低。更高效的方式是通过排序索引一次性获取所有元素的排序位置，再提取前N个元素的坐标，时间复杂度为O(M log M)，性能提升几个数量级。

核心思路 #

1. 将二维数组展平为一维数组，保留元素的原始行列映射关系；
2. 使用Fortran内置的SORTED_INDICES函数获取按值降序排列的元素索引；
3. 根据前N个索引计算对应的行列位置，在结果数组中标记为1。

修改后的完整代码 #

PROGRAM mapalgebra
  IMPLICIT NONE

  REAL, DIMENSION(:,:), ALLOCATABLE :: n, a, r, ine, s, p, TTP
  INTEGER, DIMENSION(:,:), ALLOCATABLE :: newlu
  INTEGER :: row, col, max_rows, max_cols, i, demand, total_elements
  INTEGER, DIMENSION(:), ALLOCATABLE :: sorted_idx
  REAL, DIMENSION(:), ALLOCATABLE :: TTP_flat

  ! 定义数组维度（可根据实际数据调整）
  max_rows = 64
  max_cols = 126
  demand = 50  ! 可修改为实际需求的1672137

  ! 动态分配数组，适配大规模数据
  ALLOCATE(n(max_rows, max_cols), a(max_rows, max_cols), r(max_rows, max_cols))
  ALLOCATE(ine(max_rows, max_cols), s(max_rows, max_cols), p(max_rows, max_cols))
  ALLOCATE(TTP(max_rows, max_cols), newlu(max_rows, max_cols))
  newlu = 0

  ! 读取输入文件（原逻辑不变）
  OPEN(UNIT=1, FILE="urb.txt") 
  OPEN(UNIT=2, FILE="acc.txt") 
  OPEN(UNIT=4, FILE="ran.txt")  
  OPEN(UNIT=5, FILE="lu1.txt") 
  OPEN(UNIT=7, FILE="suit.txt") 
  OPEN(UNIT=8, FILE="pob.txt") 

  DO row = 1, max_rows
      READ(1,*) (n(row,col), col=1, max_cols)
  END DO
  DO row = 1, max_rows
      READ(2,*) (a(row,col), col=1, max_cols)
  END DO
  DO row = 1, max_rows
      READ(4,*) (r(row,col), col=1, max_cols)
  END DO
  DO row = 1, max_rows
      READ(5,*) (ine(row,col), col=1, max_cols)
  END DO
  DO row = 1, max_rows
      READ(7,*) (s(row,col), col=1, max_cols)
  END DO
  DO row = 1, max_rows
      READ(8,*) (p(row,col), col=1, max_cols)
  END DO

  print *, "Land use demand is : ", demand

  ! 计算TTP（原逻辑不变）
  TTP = (ine + n + r + a + s) * p  

  ! 展平二维数组为一维，并生成排序索引
  total_elements = max_rows * max_cols
  ALLOCATE(TTP_flat(total_elements), sorted_idx(total_elements))
  TTP_flat = RESHAPE(TTP, [total_elements])

  ! 获取按降序排列的元素索引（Fortran 2008及以上支持）
  sorted_idx = SORTED_INDICES(TTP_flat, ORDER='DESCENDING')

  ! 标记前demand个最大值的位置
  DO i = 1, demand
      ! 根据一维索引计算原始二维数组的行列（列优先存储）
      row = MOD(sorted_idx(i) - 1, max_rows) + 1
      col = (sorted_idx(i) - 1) / max_rows + 1
      newlu(row, col) = 1
  END DO

  ! 写入输出文件（优化格式符适配大数）
  OPEN(UNIT=3, FILE="output.txt", ACTION="write", STATUS="replace")
  WRITE(3,11) 'ncols ', max_cols
  WRITE(3,11) 'nrows ', max_rows
  WRITE(3,11) 'xllcorner 461229.21505206'
  WRITE(3,11) 'yllcorner 4478822.89048722'
  WRITE(3,11) 'cellsize 99.38142966 '
  WRITE(3,11) 'NODATA_value 0 '
11 format(A,I0)  ! I0自动适配任意整数长度，避免溢出
  DO i = 1, max_rows
    WRITE(3,*) (newlu(i,j), j=1, max_cols)
  END DO

  ! 释放内存
  DEALLOCATE(n, a, r, ine, s, p, TTP, newlu, TTP_flat, sorted_idx)
  CLOSE(1); CLOSE(2); CLOSE(3); CLOSE(4); CLOSE(5); CLOSE(7); CLOSE(8)
     
END PROGRAM mapalgebra

关键优化点说明 #

1. 动态数组分配：将固定大小数组改为动态分配，方便适配不同规模的数据集；
2. 排序索引替代循环查找：SORTED_INDICES由编译器高度优化，比手动循环找最大值效率提升几个数量级；
3. 列优先映射：Fortran数组默认按列优先存储，展平后的一维索引转二维行列的计算需遵循该规则；
4. 格式符优化：将原I3改为I0，自动适配大数（比如max_cols为十万级时不会溢出）。

注意事项 #

• 确保编译器支持Fortran 2008标准（如gfortran需添加-std=f2008编译选项，Intel Fortran默认支持）；
• 大规模数据集下需确保机器有足够内存：1e8元素的REAL数组约400MB，整数索引数组约400MB，合计约800MB，主流服务器/工作站均可满足；
• 如果需要进一步优化性能（比如N远小于M），可自行实现快速选择算法找到第N大的元素，再标记所有大于等于该值的位置（需处理重复值的边界情况），时间复杂度可降至O(M)。

内容的提问来源于stack exchange，提问作者richjh