public
Created

Database in O(1) (thumbtack challenge)

  • Download Gist
gistfile1.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
from collections import Counter
 
class State(dict):
"""
A state contains the previous value of each modified key
and the previous Counter object
"""
def __init__(self,counter):
self.counter = counter
 
class Database():
"""
key-integer Database as a mix of:
_ a first dict (db) containing the key-value data
_ another dict (counter) containing the number of occurence of each value
The two being in sync at any time
 
Complexity of each function:
GET: O(1)
SET: O(1)
UNSET: O(1)
NUMEQUALTO: O(1)
 
But, as we maintain two structure, it use more memory than a simple dict database
 
Transaction system:
To make the TRANSACTION system performant in term of memory, eachprevious state
is stored as a dict containing:
_ the previous value of each *modified* key (to save up memory)
_ the previous counter object
 
This method could be more memory efficient by maintaining a list of change of
the counter object too for example (instend of a raw copy)
"""
def __init__(self):
self.db = dict()
self.counter = Counter()
self.states = []
 
def get(self,var):
return self.db.get(var,False)
 
def __set(self,var,value):
if var in self.db:
self.counter[self.db[var]] -= 1
self.db[var] = value
self.counter[value] += 1
 
def set(self,var,value):
self.__save_state(var)
self.__set(var,value)
 
def __unset(self,var):
self.counter[self.db[var]] -= 1
del self.db[var]
 
def unset(self,var):
self.__save_state(var)
self.__unset(var)
 
def numequalto(self,value):
return self.counter[value]
 
def __save_state(self,var):
if self.states:
state = self.states[-1]
if var not in state:
if var in self.db:
state[var] = self.get(var)
else:
state[var] = None
 
def commit(self):
if self.states:
self.states = []
return True
return False
 
def begin(self):
self.states.append(State(self.counter.copy()))
 
def rollback(self):
if self.states:
state = self.states.pop()
for key in state:
if state[key] == None:
self.__unset(key)
else:
self.__set(key,state[key])
return True
return False
 
def CLI():
"Simple CLI without error checking / input sanitizing"
db = Database()
while True:
line = raw_input().upper()
if line == 'END': break
elif line == 'BEGIN': db.begin()
elif line == 'ROLLBACK':
if not db.rollback():
print("NO TRANSACTION")
elif line == "COMMIT":
if not db.commit():
print("NO TRANSACTION")
else:
command,args = line.split(' ',1)
if command == "GET":
x = db.get(args)
if x:
print(x)
else:
print("NULL")
elif command == "UNSET":
db.unset(args)
elif command == "SET":
var,value = args.split()
db.set(var,int(value))
elif command == "NUMEQUALTO":
print(db.numequalto(int(args)))
 
if __name__ == '__main__':
CLI()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.