快速子集數組如果值在Python中的字典匹配

Question

我想加快此功能。它檢查列表值的總和是否存在於字典中。例如，如果在layout內部存在x在[0, 1],[1, 0],[0, -1]和[-1, 0]之後存在的值，則將其作爲輸出中的選項刪除。例如：

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和​​，因此這是輸出結果。

這個函數工作正常我只是希望它更快，因爲佈局可以變得非常大（數以萬計的項目），並且這個函數已經在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())獲取要在所有的大，你真的想這些值扔進一個散列映射：

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

現在的O（n）的線性掃描變成O（1）固定的時間哈希查找。

如果vals在一次myFun調用和下一次調用之間通常不會發生變化，那麼可以考慮將它作爲參數傳遞給layout。順便說一句，如果調用者願意通過x + possibilities，您可以取消x參數。

您是否考慮過使用集合交集？