bob22
BAN USERdef find(arr, n):
pos = 0
while pos < len(arr):
if arr[pos] == n:
return pos
pos += abs(arr[pos] - n)
assert find([1,2,3,4,3,4,5,6,7], 6) == 7
assert find([1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8], 8) == 17
if we want something quicker than linear search, we could try to choose the next pos smarter, but in worst case this is still O(n)
- bob22 June 15, 2015Use min-heap to store the least recently used element at the top. When a new element arrives, replace the topmost element with it and sift it down.
class LRUCache(object):
def __init__(self, size):
self._size = size
self._key_to_index = {}
self._index_to_key = [None] * self._size
self._heap = []
self._key_to_value = {}
self._access_counter = 0
def has(self, key):
"""Just check if cache has key without accessing it"""
return key in self._key_to_value
def _get_access_counter(self):
self._access_counter += 1
return self._access_counter
def _protect_counter_overflow(self):
if self._access_counter >= (1 << 31) - 1:
min_value = max_value = self._heap[0]
for i in xrange(self._size):
self._heap[i] -= min_value
max_value = max(self._heap[i], max_value)
self._access_counter = max_value
def get(self, key):
key_index = self._key_to_index.get(key)
if key_index is None:
raise KeyError(key)
self._heap[key_index] = self._get_access_counter()
self._sift_down(key_index)
self._protect_counter_overflow()
return self._key_to_value[key]
def set(self, key, value):
key_index = self._key_to_index.get(key)
if len(self._heap) < self._size:
if key_index is None:
self._key_to_index[key] = len(self._heap)
self._index_to_key[len(self._heap)] = key
self._key_to_value[key] = value
self._heap.append(self._get_access_counter())
if len(self._heap) == self._size:
self._heapify()
else:
self._heap[key_index] = self._get_access_counter()
else:
if key_index is None:
# Replace least recently used key
pop_key = self._index_to_key[0]
self._key_to_value.pop(pop_key)
self._key_to_index.pop(pop_key)
self._index_to_key[0] = key
self._heap[0] = self._get_access_counter()
self._key_to_value[key] = value
self._key_to_index[key] = self._size
self._sift_down(0)
else:
self._heap[key_index] = self._get_access_counter()
self._sift_down(key_index)
self._protect_counter_overflow()
def _heapify(self):
for i in xrange(1, self._size):
self._sift_up(i)
def _sift_down(self, index):
while True:
left_index = index * 2 + 1
right_index = index * 2 + 2
value = self._heap[index]
swap_with_index = None
if left_index < self._size:
if self._heap[left_index] < value:
value = self._heap[left_index]
swap_with_index = left_index
if right_index < self._size:
if self._heap[right_index] < value:
swap_with_index = right_index
if swap_with_index is None:
break
self._swap_index(index, swap_with_index)
index = swap_with_index
def _sift_up(self, index):
while index != 0:
parent_index = int((index - 1) / 2)
value = self._heap[index]
parent_value = self._heap[parent_index]
if value >= parent_value:
break
self._swap_index(index, parent_index)
index = parent_index
def _swap_index(self, left_index, right_index):
self._heap[left_index], self._heap[right_index] = self._heap[right_index], self._heap[left_index]
left_key = self._index_to_key[left_index]
right_key = self._index_to_key[right_index]
self._index_to_key[left_index] = right_key
self._index_to_key[right_index] = left_key
self._key_to_index[left_key] = right_index
self._key_to_index[right_key] = left_index
if __name__ == '__main__':
cache = LRUCache(3)
cache.set('a', 1)
cache.set('b', 2)
cache.set('c', 3)
assert cache.get('a') == 1
cache.set('d', 'hello')
assert not cache.has('b')
cache.set('e', 'world')
assert not cache.has('c')
assert cache.get('a') == 1
cache.get('d') == 'hello'
cache.set('f', 'another')
assert not cache.has('e')
cache = LRUCache(50)
for i in xrange(100):
cache.set(i, i)
for i in xrange(50, 100):
assert cache.has(i)
for i in xrange(25, 75):
cache.set(i, i)
for i in xrange(25):
cache.set(i, i)
for i in xrange(75):
if i < 25:
assert cache.has(i), i
if 25 <= i < 50:
assert not cache.has(i), i
if 50 <= i:
assert cache.has(i)
Repjasonmcarrier, Analyst at Abs india pvt. ltd.
Hello, I live in Houston and I am working as a Convention planner in Roberd's company, I also part ...
- bob22 July 25, 2015