n阶整数网格最优分割线求解算法的性能优化问询

问题描述 #

给定n×n的整数网格，需绘制一条贯穿网格的直线，使包含左上角的区域数值总和最大。判定规则如下：

• 若方格中心位于直线上方或直线上，则该方格计入求和区域（上方指包含网格左上角的一侧）
• 直线不能恰好从左上角出发
• 直线需从网格一侧延伸至另一侧，起点和终点可位于边线上任意位置，不限于整数点

现有实现代码 #

import numpy as np
import fractions

def best_line(grid):
    n, m = grid.shape
    D = [(di, dj) for di in range(-(n - 1), n) for dj in range(-(n - 1), n)]
    def slope(d):
        di, dj = d
        if dj == 0:
            return float('inf') if di <= 0 else float('-inf'), -di
        else:
            return fractions.Fraction(di, dj), fractions.Fraction(-1, dj)
    D.sort(key=slope)
    D = np.array(D, dtype=np.int64)
    s_max = grid.sum()
    for grid in (grid, grid.T):
        left_sum = 0
        for j in range(grid.shape[1]):
            left_sum += grid[:,j].sum()
            for i in range(grid.shape[0]):
                p = np.array([i, j], dtype=np.int64)
                Q = p + D
                Q = Q[np.all((0 <= Q) & (Q < np.array(grid.shape)), axis=1)]
                s = left_sum 
                for q in Q:
                    if not np.any(q):
                        break
                    if q[1] <= j:
                        s -= grid[q[0],q[1]]
                    else:
                        s += grid[q[0],q[1]]
                    s_max = max(s_max, s)
    return s_max

性能现状 #

当前代码在n=30时运行缓慢，耗时约1分55秒得到结果57。已有并行优化版本将n=250的运行时间缩短至1分05秒，现寻求进一步的性能加速方案。

测试用例 #

• 全正整数网格：最优直线为包含整个网格的直线；全负整数网格：最优直线为排除所有网格的直线。
• 能清晰分离负整数与非负整数的直线为较优解。
• 示例1（最优值14）：

[[ 3 -1 -2 -1]
 [ 0  1 -1  1]
 [ 1  1  3  0]
 [ 3  3 -1 -1]]

• 示例2（最优值0）：

[[-3 -3  2 -3]
 [ 0 -2 -1  0]
 [ 1  0  2  0]
 [-1 -2  1 -1]]

• 示例3（最优值31）：

[[ 3  0  1  3 -1  1  1  3 -2 -1]
 [ 3 -1 -1  1  0 -1  2  1 -2  0]
 [ 2  2 -2  0  1 -3  0 -2  2  1]
 [ 0 -3 -3 -1 -1  3 -2  0  0  3]
 [ 2  2  3  2 -1  0  3  0 -3 -1]
 [ 1 -1  3  1 -3  3 -2  0 -3  0]
 [ 2 -2 -2 -3 -2  1 -2  0  0  3]
 [ 0  3  0  1  3 -1  2 -3  0 -2]
 [ 0 -2  2  2  2 -2  0  2  1  3]
 [-2 -2  0 -2 -2  2  0  2  3  3]]

测试矩阵生成代码 #

可通过以下代码生成更多随机测试矩阵：

import numpy as np
N = 30
square = np.random.randint(-3, 4, size=(N, N))

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