python - Code takes a lot of time to run for large numbers

Question

Given the number of squares in a board (e.g. scrabble or chess board), N and dimensions AxB, this code tries to determine all possible dimensional combinations that can give N number of squares in the board.

Example: N = 8

There are four possible dimensional combinations to obtain exactly 8 squares in the board. So, the code outputs board dimensions 1x8 2x3, 3x2 and 8x1. The 8x1 boards have eight 1x1 squares; the 3x2 boards have six 1x1 squares and two 2x2 squares.

Here is my solution:

def dims(num_sqrs):
    dim_list=[]
    for i in range(1,num_sqrs+1):
        temp = []
        for x in range(1,num_sqrs+1):
            res = 0
            a = i
            b = x
            while (a != 0) and (b !=0):
                res = res + (a*b)
                a = a -1
                b = b-1
            if res == num_sqrs:
                dim_list.append((i,x))
    print(dim_list)

dims(8)

However, this code takes too much time to run for large values of N. Any suggestion to optimize the efficiency of the code will be much appreciated.

标签： pythonalgorithm

Answer 1

我认为关键细节是@Qudus 正在寻找有 N 个任意大小的正方形的板。

一种简单的优化是在res > n. 另一个使它快两倍的优化是只在长度>=宽度的板上运行它。

def dims(num_sqrs):
    dim_list=[]
    for i in range(1, num_sqrs + 1):
        temp = []
        for x in range(1, i + 1):
            res = 0
            a = i
            b = x
            while (a != 0) and (b != 0):
                res = res + (a * b)
                a = a - 1
                b = b - 1
                if res > num_sqrs:
                    break
            if res == num_sqrs:
                dim_list.append((i, x))
                if i != x:
                    dim_list.append((x, i))
    print(dim_list)

这是一个更快的解决方案，它采用不同的方法：

def dims(num_sqrs):
    dim_list = []
    sum_squares = [0]
    sums = [0] 
    for i in range(1, num_sqrs + 1):
        sums.append(sums[-1] + i)
        sum_squares.append(sum_squares[-1] + i * i)

    for i in range(1, num_sqrs + 1):
        if sum_squares[i] > num_sqrs:
            break
        if sum_squares[i] == num_sqrs:
            dim_list.append((i, i))
            break
        for x in range(i + 1, num_sqrs + 1):
            total_squares = sum_squares[i] + sums[i] * (x - i)
            if total_squares == num_sqrs:
                dim_list.append((x, i))
                dim_list.append((i, x))
                break
            if total_squares > num_sqrs:
                break
    return dim_list