Building a simple database in Python

Question

I choose to use a dictionary to store the variables for fast GET and SET commands. In my code, I have saved all of the open transactional blocks in memory. I can't see any way around this since it is always possible to have enough ROLLBACK commands to access all open blocks.

One problem I do have is that numequalto_command() is not \$ O(logN) \$. Since I am using a dictionary, I must check each value to count them. So right now it is \$ O(N) \$.

Does anyone have any idea how to make this faster? Should I create another dictionary where the keys are the values of the original dictionary and the values are their counts?

Anyways, here is my code (written very quickly and not very neat):

def set_command(db,name,value):
 if name not in db:
 db[name]=[]
 db[name].append(value)
 else:
 db[name].append(value)
 return db
def get_command(db,name):
 if len(db[name])>0:
 print db[name][-1]
 else:
 print "NULL"
def numequalto_command(db,value):
 count=0
 for key in db:
 if db[key][-1]==value:
 count+=1
 print count
def rollback(db,block):
 for i in block:
 if (i.split(' ')[0]=='SET') or (i.split(' ')[0]=='UNSET'):
 del(db[i.split(' ')[1]])[-1]
 return db
def execute_trans_block(block,database):
 for i in block:
 if i.split(' ')[0]=='SET':
 database=set_command(database,i.split(' ')[1],i.split(' ')[2])
 elif i.split(' ')[0]=='GET':
 name=i.split(' ')[1]
 get_command(database,name)
 elif i.split(' ')[0]=='UNSET':
 database=set_command(database,i.split(' ')[1],'NULL')
 elif i.split(' ')[0]=='NUMEQUALTO':
 numequalto_command(database,i.split(' ')[1])
def main():
 sampleIn1=['SET a 10','GET a','UNSET a','GET a','END']
 sampleIn2=['SET a 10','SET b 10','NUMEQUALTO 10','NUMEQUALTO 20','UNSET a','NUMEQUALTO 10','SET b 30','NUMEQUALTO 10','END']
 sampleIn3=['BEGIN','SET a 10','GET a','BEGIN','SET a 20','GET a','ROLLBACK','GET a','ROLLBACK','GET a','END']
 sampleIn4=['BEGIN','SET a 30','BEGIN','SET a 40','COMMIT','GET a','ROLLBACK','END']
 sampleIn5=['SET a 10','BEGIN','NUMEQUALTO 10','BEGIN','UNSET a','NUMEQUALTO 10','ROLLBACK','NUMEQUALTO 10','END']
 sampleIn6=['SET a 50','BEGIN','GET a','SET a 60','BEGIN','UNSET a','GET a','ROLLBACK','GET a','COMMIT','GET a','END']
 case=sampleIn6
 database={}
 trans_blocks=[]
 i=0
 while (case[i]!='END'):
 #if there is a 'BEGIN', this means the start of a block that we want to save
 if case[i]=='BEGIN':
 block=[]
 j=i+1
 while (case[j]!='BEGIN') and (case[j]!='ROLLBACK') and (case[j]!='COMMIT') :
 block.append(case[j])
 j+=1
 execute_trans_block(block,database)
 trans_blocks.append(block)
 i=j
 #'ROLLBACK' means undo SETS and UNSETS from most recent block
 elif case[i]=='ROLLBACK':
 if len(trans_blocks)>0:
 database=rollback(database,trans_blocks[-1])
 del(trans_blocks[-1])
 else:
 print 'NO TRANSACTION'
 i+=1
 #'COMMIT' means delete all saved blocks
 elif case[i]=='COMMIT':
 trans_blocks=[]
 i+=1
 #for statements written outside a block. Just execute them.
 else:
 execute_trans_block([case[i]],database)
 i+=1
if __name__ == '__main__':
 main()

I made a change by introducing a separate dictionary holding the frequency for that values in the original dictionary. Its pretty ugly but it seems to work

def set_command(db,name,value,freq):
 if name in db:
 freq[db[name][-1]]-=1
 if value not in freq:
 freq[value]=1
 else:
 freq[value]+=1
 if name not in db:
 db[name]=[]
 db[name].append(value)
 else:
 db[name].append(value)
def get_command(db,name):
 if len(db[name])>0:
 print db[name][-1]
 else:
 print "NULL"
def numequalto_command(db,value,freq):
 if value in freq:
 print freq[value]
 else:
 print 0
def rollback(db,block,freq):
 for i in block:
 if (i.split(' ')[0]=='SET') or (i.split(' ')[0]=='UNSET'):
 del(db[i.split(' ')[1]])[-1]
 if i.split(' ')[0]=='SET':
 freq[i.split(' ')[2]]-=1
 elif i.split(' ')[0]=='UNSET':
 freq[db[i.split(' ')[1]][-1]]+=1
 return db
def execute_trans_block(block,database,freq):
 for i in block:
 if i.split(' ')[0]=='SET':
 set_command(database,i.split(' ')[1],i.split(' ')[2],freq)
 elif i.split(' ')[0]=='GET':
 name=i.split(' ')[1]
 get_command(database,name)
 elif i.split(' ')[0]=='UNSET':
 set_command(database,i.split(' ')[1],'NULL',freq)
 elif i.split(' ')[0]=='NUMEQUALTO':
 numequalto_command(database,i.split(' ')[1],freq)
def main():
 sampleIn1=['SET a 10','GET a','UNSET a','GET a','END']
 sampleIn2=['SET a 10','SET b 10','NUMEQUALTO 10','NUMEQUALTO 20','UNSET a','NUMEQUALTO 10','SET b 30','NUMEQUALTO 10','END']
 sampleIn3=['BEGIN','SET a 10','GET a','BEGIN','SET a 20','GET a','ROLLBACK','GET a','ROLLBACK','GET a','END']
 sampleIn4=['BEGIN','SET a 30','BEGIN','SET a 40','COMMIT','GET a','ROLLBACK','END']
 sampleIn5=['SET a 10','BEGIN','NUMEQUALTO 10','BEGIN','UNSET a','NUMEQUALTO 10','ROLLBACK','NUMEQUALTO 10','END']
 sampleIn6=['SET a 50','BEGIN','GET a','SET a 60','BEGIN','UNSET a','GET a','ROLLBACK','GET a','COMMIT','GET a','END']
 case=sampleIn6
 freq_dict={}
 database={}
 trans_blocks=[]
 i=0
 while (case[i]!='END'):
 #if there is a 'BEGIN', this means the start of a block that we want to save
 if case[i]=='BEGIN':
 block=[]
 j=i+1
 while (case[j]!='BEGIN') and (case[j]!='ROLLBACK') and (case[j]!='COMMIT') :
 block.append(case[j])
 j+=1
 execute_trans_block(block,database,freq_dict)
 trans_blocks.append(block)
 i=j
 #'ROLLBACK' means undo SETS and UNSETS from most recent block
 elif case[i]=='ROLLBACK':
 if len(trans_blocks)>0:
 database=rollback(database,trans_blocks[-1],freq_dict)
 del(trans_blocks[-1])
 else:
 print 'NO TRANSACTION'
 i+=1
 #'COMMIT' means delete all saved blocks
 elif case[i]=='COMMIT':
 trans_blocks=[]
 i+=1
 #for statements written outside a block. Just execute them.
 else:
 execute_trans_block([case[i]],database,freq_dict)
 i+=1
if __name__ == '__main__':
 main()

Answer 1

Python has a built in dictionary method for numequalto:

print dict.values().count(value)

I don't know exactly how fast this is, but am sure it is faster than implementing your own O(N) function. Unfortunately it isn't compatible with your implementation of rollback. It would require you to have only one value for each name in the dictionary, rather than a list. I would anyway consider finding other, more memory-efficient ways to implement rollback which would also allow you to use dictionaries more easily.

By the way, there is no need for functions to return dictionary objects, as Python in any case passes dictionaries by reference, so the original object is being edited. (For illustration, try the following)

def change_dictionary(d):
 d['new_key'] = 'something new'
d = {'original key': 'something'}
change_dictionary(d)
print d

EDIT: this is how you could do it using an undo list.

def run_database(input_lines):
 def set(name, value):
 if undo:
 undo.append((name, database.get(name)))
 database[name] = value
 def unset(name):
 if undo:
 undo.append((name, database.get(name)))
 del database[name]
 def get(name):
 print database.get(name, 'NULL')
 def begin():
 undo.append('stop')
 def numequalto(value):
 print database.values().count(value)
 def rollback():
 while undo:
 action = undo.pop()
 if action == 'stop':
 break
 name, value = action
 if value is None and name in database:
 del database[name]
 elif value is not None:
 database[name] = value
 else:
 print "NO TRANSACTION" 
 def commit():
 if undo:
 del undo[:]
 else:
 print "NO TRANSACTION" 
 undo = []
 database = {}
 commands = {'SET': set, 'UNSET': unset, 'GET': get, 'BEGIN': begin, 
 'NUMEQUALTO': numequalto, 'ROLLBACK': rollback, 'COMMIT': commit}
 for line in input_lines:
 if line == 'END':
 break
 else:
 words = line.split()
 commands[words[0]](*words[1:])

• user1893354: I am using the list in the dictionary to keep track of the previous values so I can delete the newest ones when rollback occurs. I'm not really sure of another way to do this.
• Stuart: You could have separate dictionaries for each open transaction, for example, or keep a list of 'undo' instructions that would reverse the instructions that have been carried out.
• Stuart: If you don't want to do that you could also do [L[-1] for L in db.values()].count(value), which would be faster than what you have. Another possibility: use collections.Counter
• user1893354: I made an edit. This time I added another dictionary to keep track of the frequencies. It seems to work on the test cases
• Stuart: Okay but I think you need to implement rollback differently to solve the problem in a memory-efficient (and less ugly) way. I would try keeping an 'undo list' of instructions that reverse the given instructions.