詞典是一個字典中的關鍵Python

我想要一個O（1）方法來檢查我是否處於某種狀態。問題在於狀態是由地圖上幾個縮放比例的位置定義的。 Zoombini = {（1,1）：0，（2,2）：1，（3,3）：3} {Position：Zoombini ID} 我正在使用廣度優先搜索，並推送到我的隊列此字典的職位。詞典是一個字典中的關鍵Python

dirs = [goNorth, goSouth, goWest, goEast] ## List of functions 
zoom = {} 
boulders = {} 
visited = {} ## {(zoom{}): [{0,1,2},{int}]} 
      ## {Map: [color, distance] 0 = white, 1 = gray, 2 = black 
n = len(abyss) 
for i in xrange(n): 
    for j in xrange(n): 
     if (abyss[i][j] == 'X'): 
      boulders[(i,j)] = True 
     elif (isInt(abyss[i][j])): 
      zoom[(i,j)] = int(abyss[i][j])  ## invariant only 1 zomb can have this position 
     elif (abyss[i][j] == '*'): 
       exit = (i, j) 
sQueue = Queue.Queue() 
zombnum = 0 
done = False 
distance = 0 
sQueue.put(zoom) 
while not(sQueue.empty()): 
    currZomMap = sQueue.get() 
    for zom in currZomMap.iterkeys(): ## zoom {(i,j): 0} 
     if not(zom == exit): 
      z = currZomMap[zom] 
      for fx in dirs: ## list of functions that returns resulting coordinate of going in some direction 
       newPos = fx(zom) 
       newZomMap = currZomMap.copy() 
       del(newZomMap[zom]) ## Delete the old position 
       newZomMap[newPos] = z ## Insert new Position 
       if not(visited.has_key(newZomMap)): 
        sQueue.put(newZomMap)

我的實現沒有完成，但我需要一個更好的方法來檢查我是否已經訪問過一個狀態。我可以創建一個函數來創建字典中的整數哈希，但我不認爲我能夠有效。時間也是一個問題。我怎樣才能做到這一點最佳？

來源

2012-11-06 Nonconformist

而不是建造一些脆弱的自定義哈希函數，我可能只用一個frozenset：

>>> Z = {(1,1): 0, (2,2):1, (3,3):3} 
>>> hash(Z) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: unhashable type: 'dict' 
>>> frozenset(Z.items()) 
frozenset([((2, 2), 1), ((1, 1), 0), ((3, 3), 3)]) 
>>> hash(frozenset(Z.items())) 
-4860320417062922210

的frozenset可以存儲在集和類型的字典沒有任何問題。你也可以使用從Z.items()構建的元組，但是你必須確保它總是以規範格式存儲（比如說先排序）。

來源

2012-11-06 04:16:58 DSM

Python不允許可變鍵，所以我最終創建了一個哈希我的字典的函數。

edit--

def hashthatshit(dictionary): 
result = 0 
i =0 
for key in dictionary.iterkeys(): 
    x = key[0] 
    y = key[1] 
    result+=x*10**i+y*10**(i+1)+\ 
      10**(i+2)*dictionary[key] 
    i+=3 
return result

我用這個是專門針對我的實現這就是爲什麼我原本不包括它。

來源

2012-11-06 02:59:15 Nonconformist

如果你發佈了一些關於**的代碼，這將是一個有效的答案。 **你做了這個散列函數。如果你正在寫這個「答案」來簡單地否定你原來的帖子，那麼你應該刪除它，而不是 – inspectorG4dget

剛剛編輯它。 – Nonconformist

你的'x'和'y'值總是在0到9之間嗎？如果不是，你的散列有很多衝突，如{{（100,0）：0}，{{0,10}：0}和{{（0，0）：1}到'100'。對於較大的字典，哈希值也取決於您在字典的鍵上進行迭代的順序，在添加和刪除內容時不能保證穩定。 – Blckknght

詞典是一個字典中的關鍵Python

回答

相關問題