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:])