python - 如果值在Python中的字典中匹配，则快速子集数组

Question

我正在尝试加快此功能的速度。它检查字典中是否存在列表值的总和。例如，如果 x 的值加上 [0, 1], [1, 0], [0, -1] 和 [-1, 0] 存在于 layout 中，然后将其作为输出中的选项删除。例如:

layout = { 0:[2,1], 1:[3,1], 2:[2,2], 3:[6,3] }
x = [2, 1]

possibilities = numpy.zeros(shape=(4,2))
possibilities[0] = [1, 0]
possibilities[1] = [-1, 0]
possibilities[2] = [0, 1]
possibilities[3] = [0, -1]

def myFun(x, layout, possibilities):
    new_possibilities = possibilities + x

    output_direction = []
    for i in new_possibilities:
        i = list(i)
        output_direction.append( (i in layout.values()) )

    output_direction = true_to_false(output_direction)
    possibilities = possibilities[output_direction]
    if possibilities.size == 0:
        possibilities = [0, 0]
        return possibilities
    else:
        return possibilities

# This changes True to False
def true_to_false(y):
output = []
for i in y:
    if i == True:
         output.append((False))
    elif i == False:
        output.append((True))       
return output

如果我现在运行这个函数，我会得到以下输出:

myFun(x, layout, possibilities)

array([[-1.,  0.],
       [ 0., -1.]])

我得到这个输出的原因是因为 [0, 0] + x 在布局中被 [2,1] 占用，[0,1 ] + x在布局中被[2,2]占用，[1,0] + x被[3,1占用] 在布局中，而 [-1, 0] + x 和 [0, -1] + x 在布局中不存在，因此这是输出结果。

这个函数工作得很好，我只是希望它更快，因为布局可能变得非常大(数以万计的项目)，并且这个函数已经在 for 循环内运行。

Answer 1

风格

当只需说 print(42) 时，请不要说 print((((42))))。多余的括号使代码更难阅读。

否定

您的否定函数可以简化为:

def true_to_false(y):
    return [not b
            for b in y]

但你甚至不需要那个。您可以在追加时使用 not 来删除函数并避免函数调用的成本:

output_direction = []
for i in new_possibilities:
    output_direction.append(list(i) not in layout.values())
possibilities = possibilities[output_direction]
...

即使这么多也很冗长，因为它自然适合列表理解:

output_direction = [list(i) not in layout.values()
                    for i in new_possibilities]

速度

反复询问 i 是否在 .values() 内的麻烦在于这是一个线性扫描。如果 len(layout.values()) 变得非常大，您确实希望将这些值放入 HashMap 中:

vals = set(layout.values())
output_direction = [list(i) not in vals
                    for i in new_possibilities]

现在 O(n) 线性扫描变为 O(1) 恒定时间哈希查找。

如果 vals 在一次 myFun 调用和下一次调用之间通常不会改变，那么请考虑将其作为参数与 layout 一起传递。顺便说一句，如果调用者愿意传递 x + 可能性，您可以省略 x 参数。

您是否考虑过使用集合交集来代替？