关于Python的Query Board挑战，求指点

1 投票

2 回答

1321 浏览

数据工程师

提问于 2025-04-17 20:28

我在CodeEval上遇到了一个挑战，但我不知道从哪里开始，所以我需要一些指引（如果可以的话，也希望能得到答案）来帮助我解决这个挑战。

描述：

这里有一个棋盘（矩阵）。棋盘的每个格子里最开始都放着一个整数，初始值为0。

可以对查询棋盘进行以下操作：

SetRow i x: it means that all values in the cells on row "i" have been change value to "x" after this operation. 
SetCol j x: it means that all values in the cells on column "j" have been changed to value "x" after this operation. 
QueryRow i: it means that you should output the sum of values on row "i". 
QueryCol j: it means that you should output the sum of values on column "j".

棋盘的大小是256x256

i和j是从0到255的整数

x是从0到31的整数

输入示例：

你的程序应该接受一个路径作为第一个参数，这个路径指向一个文件名。这个文件中的每一行都包含一个查询操作。例如：

SetCol 32 20
SetRow 15 7
SetRow 16 31
QueryCol 32
SetCol 2 14
QueryRow 10
SetCol 14 0
QueryRow 15
SetRow 10 1
QueryCol 2

输出示例：

对于每个查询，输出查询的结果。例如：

我在Python方面不是特别厉害，但这个挑战非常有趣，尽管我不知道该怎么解决它。所以，我需要你们的帮助。

谢谢！

数据结构算法编程输入输出矩阵查询操作棋盘挑战

2 个回答

WIDTH, HEIGHT = 256, 256
board = [[0] * WIDTH for i in range(HEIGHT)]

def set_row(i, x):
    global board
    board[i] = [x]*WIDTH

... 实现每个功能，然后解析每一行输入来决定调用哪个功能，

for line in inf:
    dat = line.split()
    if dat[0] == "SetRow":
        set_row(int(dat[1]), int(dat[2]))
    elif ...

编辑：根据Martijn的评论：

整个 board 的内存使用量大约是2.1MB。相比之下，经过100次随机的行/列写入后， matrix 是3.1MB（虽然它到这儿就不再增大了）。
是的，当修改一个全局对象时，global 是不必要的（只要不试图给它赋值就行）。
虽然从字典中调度是不错且高效的，但我不想让一个“对Python不太熟悉”的人去使用它，尤其是只有四个条目的情况下。

为了比较，怎么样

time = 0
WIDTH, HEIGHT = 256, 256
INIT = 0

rows = [(time, INIT) for _ in range(WIDTH)]
cols = [(time, INIT) for _ in range(HEIGHT)]

def set_row(i, x):
    global time
    time += 1
    rows[int(i)] = (time, int(x))

def set_col(i, x):
    global time
    time += 1
    cols[int(i)] = (time, int(x))

def query_row(i):
    rt, rv = rows[int(i)]
    total = rv * WIDTH + sum(cv - rv for ct, cv in cols if ct > rt)
    print(total)

def query_col(j):
    ct, cv = cols[int(j)]
    total = cv * HEIGHT + sum(rv - cv for rt, rv in rows if rt > ct)
    print(total)

ops = {
    "SetRow": set_row,
    "SetCol": set_col,
    "QueryRow": query_row,
    "QueryCol": query_col
}

inf = """SetCol 32 20
SetRow 15 7
SetRow 16 31
QueryCol 32
SetCol 2 14
QueryRow 10
SetCol 14 0
QueryRow 15
SetRow 10 1
QueryCol 2""".splitlines()

for line in inf:
    line = line.split()
    op = line.pop(0)
    ops[op](*line)

只需要4.3k的内存来存储rows[]和cols[]。

编辑2：

使用你上面提到的代码来处理matrix、set_row、set_col，

import sys

for n in range(256):
    set_row(n, 1)
    print("{}: {}".format(2*(n+1)-1, sys.getsizeof(matrix)))
    set_col(n, 1)
    print("{}: {}".format(2*(n+1), sys.getsizeof(matrix)))

返回的结果是（简化版）：

1: 12560
2: 49424
6: 196880
22: 786704
94: 3146000

... 基本上，每一步分配的内存都会增加到四倍。如果我把内存测量改为包括键元组，

def get_matrix_size():
    return sys.getsizeof(matrix) + sum(sys.getsizeof(key) for key in matrix)

它的增加会更平滑，但在上述点仍然会有一些跳跃：

5  :  127.9k
6  :  287.7k

21 :  521.4k
22 : 1112.7k

60 : 1672.0k
61 : 1686.1k   <-- approx expected size on your reported problem set

93 : 2121.1k
94 : 4438.2k

回答于 2025-04-17 由 Python大师

分享举报

你可以使用稀疏矩阵来解决这个问题；用 (列, 行) 的组合作为字典的键，这样可以节省内存。否则，64k个单元格会变成一个很大的列表（在64位系统上超过2MB）：

matrix = {}

这样做效率更高，因为这个挑战不太可能会给棋盘上的所有行和列都设置值。

设置某一列或某一行的方法是：

def set_col(col, x):
    for i in range(256):
        matrix[i, col] = x

def set_row(row, x):
    for i in range(256):
        matrix[row, i] = x

然后对某一行或某一列求和的方法是：

def get_col(col):
    return sum(matrix.get((i, col), 0) for i in range(256))

def get_row(row):
    return sum(matrix.get((row, i), 0) for i in range(256))

回答于 2025-04-17 由 Python大师

分享举报

关于Python的Query Board挑战，求指点

2 个回答

撰写回答