spacepaste

Paste details

reply | raw

  1.  
  2. import array
  3. import collections
  4. import itertools
  6. # Placeholder constants
  7. FREE = -1
  8. DUMMY = -2
  10. class Dict(collections.MutableMapping):
  11. 'Space efficient dictionary with fast iteration and cheap resizes.'
  13. def _lookup(self, key, hashvalue):
  14. 'Same lookup logic as currently used in real dicts'
  15. assert self.filled < len(self.indices) # At least one open slot
  16. freeslot = None
  17. PERTURB_SHIFT = 5
  18. if hashvalue < 0:
  19. perturb = -hashvalue
  20. else:
  21. perturb = hashvalue
  22. n = len(self.indices)
  23. i = perturb & (n-1)
  24. while True:
  25. index = self.indices[i]
  26. if index == FREE:
  27. return (FREE, i) if freeslot is None else (DUMMY, freeslot)
  28. elif index == DUMMY:
  29. freeslot = i
  30. elif (self.keylist[index] is key or
  31. self.hashlist[index] == hashvalue
  32. and self.keylist[index] == key):
  33. return (index, i)
  34. i = 5 * i + perturb + 1
  35. i = i & (n-1)
  36. perturb >>= PERTURB_SHIFT
  38. @staticmethod
  39. def _make_index(n):
  40. 'New sequence of indices using the smallest possible datatype'
  41. if n <= 2**7: return array.array('b', [FREE]) * n # signed char
  42. if n <= 2**15: return array.array('h', [FREE]) * n # signed short
  43. if n <= 2**31: return array.array('l', [FREE]) * n # signed long
  44. return [FREE] * n # python integers
  46. def _resize(self, n):
  47. '''Reindex the existing hash/key/value entries.
  48. Entries do not get moved, they only get new indices.
  49. No calls are made to hash() or __eq__().
  51. '''
  52. n = 2 ** n.bit_length() # round-up to power-of-two
  53. self.indices = self._make_index(n)
  54. PERTURB_SHIFT = 5
  55. for index, hashvalue in enumerate(self.hashlist):
  56. if hashvalue < 0:
  57. perturb = -hashvalue
  58. else:
  59. perturb = hashvalue
  60. i = hashvalue & (n-1)
  61. while True:
  62. if self.indices[i] == FREE:
  63. break
  64. i = 5 * i + perturb + 1
  65. i = i & (n-1)
  66. perturb >>= PERTURB_SHIFT
  67. self.indices[i] = index
  68. self.filled = self.used
  70. def clear(self):
  71. self.indices = self._make_index(8)
  72. self.hashlist = []
  73. self.keylist = []
  74. self.valuelist = []
  75. self.used = 0
  76. self.filled = 0 # used + dummies
  78. def __init__(self, *args, **kwds):
  79. try:
  80. self.keylist
  81. except AttributeError:
  82. self.clear()
  83. self.update(*args, **kwds)
  85. def __getitem__(self, key):
  86. hashvalue = hash(key)
  87. index, i = self._lookup(key, hashvalue)
  88. if index < 0:
  89. raise KeyError(key)
  90. return self.valuelist[index]
  92. def __setitem__(self, key, value):
  93. hashvalue = hash(key)
  94. index, i = self._lookup(key, hashvalue)
  95. if index < 0:
  96. self.indices[i] = self.used
  97. self.hashlist.append(hashvalue)
  98. self.keylist.append(key)
  99. self.valuelist.append(value)
  100. self.used += 1
  101. if index == FREE:
  102. self.filled += 1
  103. if self.filled * 3 > len(self.indices) * 2:
  104. self._resize(4 * len(self))
  105. else:
  106. self.valuelist[index] = value
  108. def __delitem__(self, key):
  109. hashvalue = hash(key)
  110. index, i = self._lookup(key, hashvalue)
  111. if index < 0:
  112. raise KeyError(key)
  113. self.indices[i] = DUMMY
  114. self.used -= 1
  115. # If needed, swap with the lastmost entry to avoid leaving a "hole"
  116. if index != self.used:
  117. lasthash = self.hashlist[-1]
  118. lastkey = self.keylist[-1]
  119. lastvalue = self.valuelist[-1]
  120. lastindex, j = self._lookup(lastkey, lasthash)
  121. assert lastindex >= 0 and i != j
  122. self.indices[j] = index
  123. self.hashlist[index] = lasthash
  124. self.keylist[index] = lastkey
  125. self.valuelist[index] = lastvalue
  126. # Remove the lastmost entry
  127. self.hashlist.pop()
  128. self.keylist.pop()
  129. self.valuelist.pop()
  131. def __len__(self):
  132. return self.used
  134. def __iter__(self):
  135. return iter(self.keylist)
  137. def iterkeys(self):
  138. return iter(self.keylist)
  140. def keys(self):
  141. return list(self.keylist)
  143. def itervalues(self):
  144. return iter(self.valuelist)
  146. def values(self):
  147. return list(self.valuelist)
  149. def iteritems(self):
  150. return itertools.izip(self.keylist, self.valuelist)
  152. def items(self):
  153. return zip(self.keylist, self.valuelist)
  155. def __contains__(self, key):
  156. index, i = self._lookup(key, hash(key))
  157. return index >= 0
  159. def get(self, key, default=None):
  160. 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
  161. index, i = self._lookup(key, hash(key))
  162. return self.valuelist[index] if index >= 0 else default
  164. def popitem(self):
  165. ''' D.popitem() -> (k, v), remove and return some (key, value) pair as a
  166. 2-tuple; but raise KeyError if D is empty.
  167. '''
  168. try:
  169. key = self.keylist[-1]
  170. value = self.valuelist[-1]
  171. except IndexError:
  172. raise KeyError( 'popitem(): dictionary is empty')
  173. del self[key]
  174. return key, value
  176. def __repr__(self):
  177. return 'Dict(%r)' % self.items()
  179. def show_structure(self):
  180. 'Diagnostic method. Not part of the API.'
  181. print '=' * 50
  182. print self
  183. print 'Indices:', self.indices
  184. for i, row in enumerate(zip(self.hashlist, self.keylist, self.valuelist)):
  185. print i, row
  186. print '-' * 50
  189. if __name__ == '__main__':
  190. import sys
  191. def f():
  192. if len(sys.argv) > 1:
  193. d = {}
  194. else:
  195. d = Dict()
  196. class A(object):
  197. pass
  198. for i in range(10000000):
  199. d[i] = A()
  200. f()
  201.  
Powered by spacepaste. Paste removal.