Question

Problem Set 6 - Question 4:
My "faster" function actually seems .05 seconds slower than the supposedly less efficient function. I feel like I satisfied the requirements, but did I do something wrong?

Answer 1

Here's the code:

def powerset(s):
"""powerset('abc') -> a b ab c ac bc abc"""
pairs = [(2**index, char) for index, char in enumerate(s)]
for index in xrange(1, 2**len(s)):
yield ''.join(char for mask, char in pairs if mask & index)

def pick_best_word_faster(hand,REARRANGE_DICT):
rhand = ""
best_score = 0
trial_score = 0
best_word = "."
for key in hand.keys():
for ii in range(0, hand.get(key,0)): rhand = rhand+key
rhand = ''.join(sorted(rhand))
mygenerator = powerset(rhand)
for ii in mygenerator:
if ii in REARRANGE_DICT.keys():
trial_score = get_word_score(REARRANGE_DICT[ii])
if trial_score > best_score:
best_score = trial_score
best_word = REARRANGE_DICT[ii]
return best_word

Answer 2

please use dpaste.com to post your code
seems slower or is slower? if i remember correctly the less-faster one would have to check all the permutations and with the sorted points dictionary you only had to do combinations - should be much less 'loops'/iterations with the latter, especially for a large hand
very, very cool generator function,
I haven't used one yet and haven't quite gotten the hang of the list comprehensions yet.
I ran across this and used it: http://docs.python.org/library/itertools.html#itertools.combinations

Answer 3

Apologies. Here's the dpaste: http://dpaste.com/555751/

The "faster" function actually is .05 seconds slower according to the system clock.

It doesn't make sense though because the generator creates all possible permutations of the hand and and checks them against the dictionary. Because the "if ii in dictionary" search is a hash it should be O(1) which would be much better than the O(n) of the less efficient function's linear search. However my tests show that the O(n) function is actually a bit faster which makes me think I've made a mistake somewhere.

I can't take credit for the generator function, I grabbed it from a google search, but you're right it's very cool.

Answer 4

Seems like there may be a speed trade off for space here. My generator function is testing each permutation of the sorted hand one at a time and throwing out the permutations once tested. The faster functions seem to generate a big list of all the permutations and then test them in sequence.

Can anyone confirm this?

Answer 5

do you get the same words with both functions with the same hand??

This is the approach I took:
- if the hand has seven letters you have to look at 'words' that are 1-7 letters long
- for pick_best_word the keys in the points dictionary are not sorted, order matters
* if the hand is 'abcdefg' and you are looking for three letter words that contain
just 'abc' you have to check 'abc', 'bac', 'bca', 'cba', 'acb', 'cab', (more?).
* you have to check every permutation of 7 letters, taken 1 at a time, 2 at a time,
3 at a time, 4 at a time ....... that turns out to be a lot and it gets bigger faster
with larger hands
- for pick_best_word_faster the keys in the points dictionary are sorted,
order doesn't matter
* if the hand is 'abcdefg' and you are looking for three letter words that contain
'abc' you only have to check 'abc'.
* you have to check every combination of 7 letters, taken 1 at a time, 2 at a time,
3 at a time, 4 at a time ....... that turns out to be way less than the other and it
doesn't increase as fast with letter count.

Here's my function for testing the two versions: http://dpaste.com/555961/
here are some results: http://dpaste.com/555962/

maybe my pick_best_word function is doing too much??

http://www.themathpage.com/aprecalc/permutations-combinations.htm

Answer 6

Yeah it seems to be the exact same result. When I run your functions I get the same issue - your faster function is faster and your slower function runs about the same time as my slower one.

No idea what the issue is. I'm going to chalk this one upto some arcane mechanism and move on. Thanks for the help!