| 3 | from time import time |
| 4 | |
| 5 | class RandomTrackingDict(object): |
| 6 | maxPending = 10 |
| 7 | pendingTimeout = 60 |
| 8 | def __init__(self): # O(1) |
| 9 | self.dictionary = {} |
| 10 | self.indexDict = [] |
| 11 | self.len = 0 |
| 12 | self.pendingLen = 0 |
| 13 | self.lastPoll = 0 |
| 14 | self.lock = RLock() |
| 15 | |
| 16 | def __len__(self): |
| 17 | return self.len |
| 18 | |
| 19 | def __contains__(self, key): |
| 20 | return key in self.dictionary |
| 21 | |
| 22 | def __getitem__(self, key): |
| 23 | return self.dictionary[key][1] |
| 24 | |
| 25 | def _swap(self, i1, i2): |
| 26 | with self.lock: |
| 27 | key1 = self.indexDict[i1] |
| 28 | key2 = self.indexDict[i2] |
| 29 | self.indexDict[i1] = key2 |
| 30 | self.indexDict[i2] = key1 |
| 31 | self.dictionary[key1][0] = i2 |
| 32 | self.dictionary[key2][0] = i1 |
| 33 | # for quick reassignment |
| 34 | return i2 |
| 35 | |
| 36 | def __setitem__(self, key, value): |
| 37 | with self.lock: |
| 38 | if key in self.dictionary: |
| 39 | self.dictionary[key][1] = value |
| 40 | else: |
| 41 | self.indexDict.append(key) |
| 42 | self.dictionary[key] = [self.len, value] |
| 43 | self._swap(self.len, self.len - self.pendingLen) |
| 44 | self.len += 1 |
| 45 | |
| 46 | def __delitem__(self, key): |
| 47 | if not key in self.dictionary: |
| 48 | raise KeyError |
| 49 | with self.lock: |
| 50 | index = self.dictionary[key][0] |
| 51 | # not pending |
| 52 | if index < self.len - self.pendingLen: |
| 53 | # left of pending part |
| 54 | index = self._swap(index, self.len - self.pendingLen - 1) |
| 55 | # pending |
| 56 | else: |
| 57 | self.pendingLen -= 1 |
| 58 | # end |
| 59 | self._swap(index, self.len - 1) |
| 60 | # if the following del is batched, performance of this single |
| 61 | # operation can improve 4x, but it's already very fast so we'll |
| 62 | # ignore it for the time being |
no outgoing calls
no test coverage detected