Better optimization technique using if/else or dictionary

Question

Which is better optimization?

• A series of if/else statement which receives the 'string' returns the appropriate function for it. (Around 40-50 if/else statements).
• A dictionary maintaining the key-value pair. key as strings, and values as the function objects, and one main function to search and return the function object.

The main function which actually returns the function object using above method would be called millions or billions of times, so need to do this intelligently. What could be the better way?

For e.g.

dict['str1'] = func1
dict['str2'] = func2
and so on..

def main_func(str):
    return dict[str]

Or

def main_func(str):
    if 'str1':
      return func1
    elif 'str2':
      return func2

Which would be better..? if we have 50-60 such strings, and this process needs to be billions of times.

Storing function object inside dictionary, in function itself:-

def func1():
   if dict.has_key('str1'):
        dict['str1'] = func1
   -- do something --

Which is better, this or the above one. This looks much cleaner.? But remember, these functions would be called many times so has_key function would also be called many times.

Thanks

Answer 1

Choose the dictionary.

The dictionary ...

• is built-in
• is pythonic
• requires less boilerplate code
• has O(1) complexity, compared to the if-else linear O(n) complexity
• isn't guilty of premature pessimization (we have insufficient reason to believe without profiling that it is a less efficient method by a large margin)

I would suggest writing the solution using a dictionary first and seeing if the solution is fast enough for your needs. If so, great, you're done. If not, time it against the other way.

Consider a solution like this (which will return None if the string is not found):

func_dict = {}
func_dict['str1'] = fun1
func_dict['str2'] = fun2
...
def function_lookup(func_string):
    return func_dict.get(func_string)

Then, in your main, simply write function_lookup(whatever_string_variable) to attempt a lookup for your function. This avoids the dictionary from being rebuilt every time function_lookup is called.

Answer 2

The dictionary will be faster: it is approximately O(1), while the chain of if statements is O(n). To demonstrate, this script (make_test.py) will output a python script that runs some peformance tests:

ifs = []
dict = []
for i in range(60):
    string = 'str%d' % i
    ifs.append('  %sif str == "%s": return %d' % ('el' if i else '', string, i))
    dict.append('"%s": %d' % (string, i))

print 'dict = {', ','.join(dict), '}'
print 'def with_dict(str):'
print '  return dict[str]'

print 'def with_if(str):'
print '\n'.join(ifs)

print '''
import timeit

def test_dict():
    for i in range(60):
        with_dict("str%d" % i)

def test_if():
    for i in range(60):
        with_if("str%d" %i)

print 'dict:', timeit.timeit(test_dict, number=10000)
print 'if:  ', timeit.timeit(test_if, number=10000)'''

Running it like python make_test.py | python, gives me:

dict: 0.706176042557
if:   1.67383503914

That is, the if version is more than 2 times slower than the dict version.