Generally, the method used will be dependent upon your data. I've constructed some simple tests that use different types of data to illustrate how the timings can change.
Strings used:
- The string in the question.
- A larger, pseudorandom string (supposedly with more distinct mers/keys in the hash).
- A string that has very few distinct mers/keys in the hash.
Here is some quick code to test the various methods (I've up-voted the defaultdict
answer since it seems to be the fastest).
import random
from timeit import Timer
from collections import defaultdict
def test_check_first(st, mersize):
""" Look for the existance of the mer in the dict.
"""
mer_hash = {}
r = len(st)-mersize+1
for i in range(0, r):
mer = st[i:i+mersize]
if mer in mer_hash:
mer_hash[mer].append(i)
else:
mer_hash[mer] = [i]
return mer_hash
def test_throw_exception(st, mersize):
""" Catch the KeyError thown if a mer doesn't exist in the dict.
"""
mer_hash = {}
r = len(st)-mersize+1
for i in range(0, r):
mer = st[i:i+mersize]
try:
mer_hash[mer].append(i)
except KeyError:
mer_hash[mer] = [i]
return mer_hash
def test_defaultdict(st, mersize):
""" Use a defaultdict.
"""
mer_hash = defaultdict(list)
r = len(st)-mersize+1
for i in range(0, r):
mer = st[i:i+mersize]
mer_hash[mer].append(i)
return mer_hash
def test_dict_setdefault(st, mersize):
""" Use dict's setdefault method
"""
mer_hash = {}
r = len(st)-mersize+1
for i in range(0, r):
mer = st[i:i+mersize]
mer_hash.setdefault(mer, []).append(i)
return mer_hash
def gen_pseudorandom_string(size):
""" Generate a larger, more "random" string of data.
"""
# only use four letters
letters = ('A', 'B', 'C', 'D')
return ''.join(random.choice(letters) for i in range(size))
if __name__ == '__main__':
# test functions
test_strings = ('ABCDABBBBBAAACCCCABCDDDD', gen_pseudorandom_string(1000), 'A'*100 + 'B'*100 + 'C'*100 + 'D'*100)
mer_size = 3
passes = 10000
for string in test_strings:
display_string = string if len(string) <= 30 else string[:30] + '...'
print 'Testing with string: "' + display_string + '" and mer size: ' + str(mer_size) + ' and number of passes: ' + str(passes)
t1 = Timer("test_check_first(string, mer_size)", "from __main__ import test_check_first, string, mer_size")
print '\tResults for test_check_first: ',
print "%.2f usec/pass" % (1000000 * t1.timeit(number=passes)/passes)
t2 = Timer("test_throw_exception(string, mer_size)", "from __main__ import test_throw_exception, string, mer_size")
print '\tResults for test_throw_exception: ',
print "%.2f usec/pass" % (1000000 * t2.timeit(number=passes)/passes)
t3 = Timer("test_defaultdict(string, mer_size)", "from __main__ import test_defaultdict, string, mer_size")
print '\tResults for test_defaultdict: ',
print "%.2f usec/pass" % (1000000 * t3.timeit(number=passes)/passes)
t4 = Timer("test_dict_setdefault(string, mer_size)", "from __main__ import test_dict_setdefault, string, mer_size")
print '\tResults for test_dict_setdefault: ',
print "%.2f usec/pass" % (1000000 * t4.timeit(number=passes)/passes)
Here are the results that I got when I ran it on my machine:
Testing with string: "ABCDABBBBBAAACCCCABCDDDD" and mer size: 3 and number of passes: 10000
Results for test_check_first: 8.70 usec/pass
Results for test_throw_exception: 22.78 usec/pass
Results for test_defaultdict: 10.61 usec/pass
Results for test_dict_setdefault: 8.88 usec/pass
Testing with string: "BACDDDADAAABADBDADDBBBCAAABBBC..." and mer size: 3 and number of passes: 10000
Results for test_check_first: 305.19 usec/pass
Results for test_throw_exception: 320.62 usec/pass
Results for test_defaultdict: 254.56 usec/pass
Results for test_dict_setdefault: 342.55 usec/pass
Testing with string: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA..." and mer size: 3 and number of passes: 10000
Results for test_check_first: 114.23 usec/pass
Results for test_throw_exception: 107.96 usec/pass
Results for test_defaultdict: 94.11 usec/pass
Results for test_dict_setdefault: 125.72 usec/pass