是否有一個相當於python中非唯一集合的數據結構？

我有一個非常大的整數列表，我想用「hash（）」來提高搜索速度。每個嵌套列表的結果散列值需要獨立於整數的順序，並且僅與列表中的值相關。這表明一個（凍結）設置爲一個合適的數據結構來散列。但是，我需要保留每個整數值，無論是否重複，這是一個集合的顯示限制。是否有一個相當於python中非唯一集合的數據結構？

所以，這讓我排序列表，轉換爲一個元組和哈希，這是很慢，我想有更好的策略。

我很感激任何關於如何更有效地做到這一點的建議。

來源

2011-04-16 Andy

爲什麼你需要保持重複？是重要的命令還是你真的只需要每個整數的正確數？ – delnan 2011-04-16 12:35:14

好點，我只需要每一個正確的計數。在這種情況下，整數：字典似乎是有效的。但我不認爲字典是可散列的。 – Andy 2011-04-16 12:40:46

字典是散列。

>>> def bag_random(d, n): 
...  x = random.randint(0, n) 
...  if x in d: 
...    d[x] += 1 
...  else: 
...    d[x] = 1 
... 
>>> a = {} 
>>> for i in xrange(10**6): 
...  bag_random(a, 100) 
... 
>>> a 
{0: 9856, 1: 9787, 2: 9944, 3: 9822, 4: 9978, 5: 9915, 6: 9915, 7: 9860, 8: 9926, 9: 9756, 10: 9914, 11: 10030, 12: 10009, 13: 9803, 14: 9918, 15: 10136, 16: 9818, 17: 9868, 18: 9893, 19: 9971, 20: 9998, 21: 9982, 22: 9884, 23: 9806, 24: 9998, 25: 9926, 26: 9977, 27: 10011, 28: 10030, 29: 9899, 30: 9808, 31: 9825, 32: 9980, 33: 9812, 34: 9928, 35: 9827, 36: 9934, 37: 9883, 38: 9913, 39: 9893, 40: 9822, 41: 9714, 42: 9871, 43: 9954, 44: 9989, 45: 9694, 46: 9878, 47: 9984, 48: 9893, 49: 9928, 50: 10093, 51: 9881, 52: 9828, 53: 9660, 54: 9884, 55: 9745, 56: 10048, 57: 9845, 58: 9916, 59: 9933, 60: 9944, 61: 9979, 62: 9992, 63: 9635, 64: 9811, 65: 9900, 66: 9950, 67: 9744, 68: 9829, 69: 10037, 70: 9929, 71: 9811, 72: 9830, 73: 10056, 74: 9957, 75: 9992, 76: 9777, 77: 9942, 78: 9809, 79: 9734, 80: 9855, 81: 10021, 82: 9914, 83: 10009, 84: 10018, 85: 9961, 86: 10036, 87: 9849, 88: 9951, 89: 9770, 90: 9795, 91: 9899, 92: 9975, 93: 9935, 94: 10037, 95: 9992, 96: 9868, 97: 10014, 98: 9689, 99: 9883, 100: 9878}

花了一秒鐘左右一個不是很快的桌面。

來源

2011-04-16 13:20:23 msw

是的，這可能是一個從字典中派生出來的類，並且可以添加其他效率。鑑於問題的最低要求，這可能是最清楚的。 – msw 2011-04-16 13:56:35

您錯過了需要對生成的結構進行散列處理的需求。 Python字典相當於Perl哈希，但這並不意味着您可以哈希Python字典！ – 2011-04-16 14:00:57

同意你不能散列字典，但不能弄清楚這是一個需求還是OP的混淆。 – msw 2011-04-16 15:24:51

你的數據結構很好，你需要的是一種計算滿足你的需求的散列的方法：整數的順序無關緊要，但重複需要被尊重，並且它需要很快。

如何計算數字的乘積？得到的數字可以很好地工作。如果你想避免滑入多頭會減慢你的速度，你可以保持它在一個32位的整數。唯一的問題是零，但你可以跳過它們，它不會破壞散列，只會使它更少歧視。

LIMIT = 999999937 # largest 9-digit prime 
def list_hash(l): 
    h = 1 
    for i in l: 
     if i: 
      h *= i 
      h %= LIMIT 
    return h

來源

2011-04-16 14:15:14

非常感謝 - 這看起來像一個非常好的計劃。 – Andy 2011-04-19 20:30:03

創建一個帶有計數的字典。（如果你的Python版本夠新，你可以使用反類代替。構建了一套從項目列表和散列的那

counter = collections.defaultdict(int) 
for item in items: 
    counter[item] += 1 
return hash(frozenset(counter.items()))

但我不知道它會不會有更有效，你「已經已經完成

由於這是一個哈希，它並不需要代表一個事實，即一些您的號碼被複制，從而你可以只使用：。

return hash(frozenset(items))

來源

2011-04-16 14:30:29

是否有一個相當於python中非唯一集合的數據結構？

回答

相關問題