Python上的查询板挑战，需要一些指针

Question

所以，我在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到{}的整数

x是从0到{}的整数

输入样本：

程序应该接受文件名的路径作为第一个参数。此文件中的每一行都包含一个查询操作。E、 g

^{pr2}$

输出样本：

对于每个查询，输出查询的答案。E、 g

^{3}$

我在Python上不是很好，但是这个挑战非常有趣，尽管我没有任何关于如何解决它的线索。所以，我需要你们的帮助。在

谢谢！在

Answer 1

您可以为此使用稀疏矩阵；通过(col, row)元组作为字典中的键来寻址，以节省内存。64k单元是一个大列表，否则（在64位系统上为2MB+）：

matrix = {}

这是更有效的方法，因为挑战不太可能为板上的所有行和列设置值。在

设置列或行是：

^{pr2}$

对一行或一列求和就是：

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))

Answer 2

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

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

。。。实现每个函数，然后解析每行输入以决定调用哪个函数

^{pr2}$

编辑：根据Martijn的评论：

• board的总内存使用量约为2.1MB。相比之下，在100次随机的行/列写入之后，matrix是3.1MB（尽管它是最高的，并且没有变大）。

• 是的，global在修改全局对象时是不必要的（只是不要试图分配给它）。

• 虽然从dict进行调度是好的和高效的，但是我不想把它强加给那些“在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内存。在

编辑2:

用你上面的代码来做矩阵，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