So far I have a class that reads /usr/share/dict/words and organizes the words by their first letter:
#!/usr/bin/env python
# encoding: utf-8
import timeit
import dis
class Dictionary(object):
def __init__(self, filename='/usr/share/dict/words'):
self.by_letter = {}
self.load_file(filename)
def load_file(self, filename):
f = open(filename, 'rt')
try:
words = [l.strip() for l in f.readlines()]
for word in words:
try:
self.by_letter[word[0]].append(word)
except KeyError:
self.by_letter[word[0]] = [word]
finally:
f.close()
if __name__ == '__main__':
print 'DISASSEMBLY:'
dis.dis(Dictionary)
print
t = timeit.Timer('d = Dictionary()', 'from dis_slow_loop import Dictionary')
iterations = 2
print 'TIME: %0.4f' % (t.timeit(iterations)/iterations)
I've optimized it a bit to get this:
#!/usr/bin/env python
# encoding: utf-8
import collections
import dis
import timeit
class Dictionary(object):
def __init__(self, filename='/usr/share/dict/words'):
self.by_letter = collections.defaultdict(list)
self.load_file(filename)
def load_file(self, filename):
by_letter = self.by_letter
with open(filename, 'rt') as f:
for line in f:
word = line.strip()
by_letter[word[0]].append(word)
if __name__ == '__main__':
print 'DISASSEMBLY:'
dis.dis(Dictionary)
print
t = timeit.Timer('d = Dictionary()', 'from dis_faster_loop import Dictionary')
iterations = 2
print 'TIME: %0.4f' % (t.timeit(iterations)/iterations)
The first example gives me a run time of 0.2712 sec and the second is 0.1998.
I'm looking for either alternative loops or a way to increase that spread without making the "slow" version obviously obtuse (no sleeps, unnecessary sub-loops, etc.).
9 comments:
I'm not sure it is the solution you are looking for, but it might be interesting to see the difference between collections.defaultdict and dict.setdefault.
In my case it would have been my first optimization and I not sure if it is the best one.
By the way, thank you for your PyMOTW it's a great resource!
@PsyCow, that may be a good intermediate step. I'll investigate it, thanks for the suggestion.
What about walking down a directory?
I've a modification which is slightly faster most of the time. I use square bracket notation, remove dots, and for grins used PsyCow's "setdefault" suggestion. Here are typical timings:
./orig.py
TIME: 0.0739
./opt.py
TIME: 0.0565
./opt2.py
TIME: 0.0559
#!/usr/bin/env python
# encoding: utf-8
# import collections
# import dis
import timeit
class Dictionary(object):
def __init__(self, filename='/usr/share/dict/words'):
self.by_letter = dict()
self.load_file(filename)
def load_file(self, filename):
by_letter_set = self.by_letter.setdefault
[ by_letter_set(line[0], []).append(line.rstrip())
for line in open(filename, 'rt') ]
if __name__ == '__main__':
# print 'DISASSEMBLY:'
# dis.dis(Dictionary)
# print
t = timeit.Timer('d = Dictionary()', 'from opt import Dictionary')
iterations = 20
print 'TIME: %0.4f' % (t.timeit(iterations)/iterations)
Does the compiler factor out common subexpressions such as converting
e = a + (b*c)
f = d + (b*c)
into
t = (b*c)
e = a + t
f = d + t
or:
if a > b:
c = True
else:
c = False
into:
c = a > b
?
I recommend doing something like edit distance w/ different weights, or some other DP problem. Something with an inner and outer loop and conditionals in both.
Damerau–Levenshtein Edit Distance is just the canonical DP example for fun language specific optimizations. (NOTE: having different weights for insert, sub. delete is key, otherwise the problem can be boiled down)
Damerau–Levenshtein
Levenshtein (This has some exposition so you can see what is happening)
Hamming (Just to show an example of how equal weights can simplify the problem, and in python too! Used often in signal processing)
D-LED 2/4/3 is the calc we use for determining the WER (word error rate) of our speech recognizer (comparing words, not characters as in the wikipedia examples)
I take that back, we use LED for WER, and D-LED for MCR (min-correction rate) or the minimum number of steps to correct the transcript (important for measuring correctionists effort)
I am not sure exactly what you are asking. Does replacing the "for line" loop with a ".split()" and then an itertools ".groupby()" count as a modification of your loop? Or does that eliminate the loop entirely, from the point of view of the disassembler, and render the point of the exercise meaningless?
@Brandon - Using split and groupby is another good optimization. The goal is to show how you can look at the disassembled code to understand the amount of work being done in the interpreter by comparing the number of opcodes. Moving work to C would cut that down, and should be faster.
Post a Comment