On 04/30/2015 11:59 AM, Cecil Westerhof wrote:
I implemented happy_number function:
_happy_set = { '1' }
_unhappy_set = set()
def happy_number(n):
"""
Check if a number is a happy number
https://en.wikipedia.org/wiki/Happy_number
"""
def create_current(n):
current_array = sorted([value for value in str(n) if value != '0'])
return (current_array, ''.join(current_array))
global _happy_set
global _unhappy_set
current_run = set()
current_array, \
current_string = create_current(n)
if current_string in _happy_set:
return True
if current_string in _unhappy_set:
return False
while True:
current_run.add(current_string)
current_array, \
current_string = create_current(sum([int(value) ** 2
for value in
current_string]))
if current_string in current_run | _unhappy_set:
_unhappy_set |= current_run
return False
if current_string in _happy_set:
_happy_set |= current_run
return True
Besides it need some documentation: is it a good implementation? Or
are there things I should do differently?
To decide for the values from 1 to 1E8 if it is happy or not, takes
280 seconds. Not to bad I think. Also not very good.
First comment, if you're coding a complex implementation like this, take
the time to do a brute force one as well. Then you can compare the
results between brute force and your optimized one for all possible
values, and make sure you haven't introduced any bugs.
My brute force looks like:
#Dave's version, brute force
def davea1(n):
cache = []
anum = str(n)
newnum = 0
while newnum != 1:
newnum = sum(int(i)*int(i) for i in anum)
anum = str(newnum)
if newnum in cache:
return False #not a happy number
cache.append(newnum)
return True #found a happy number
I then tried an optimized one, and my speed is only about 10% faster
than yours for 1e7 loops. I show it anyway, since I think it reads a
little better. And readability counts much more than a little performance.
#optimizations:
# cached happy and unhappy sets
# sort the digits, and compare only the sorted values, without zeroes
davea_happy = {1}
davea_unhappy = set()
SQUARES = dict((str(i), i*i) for i in xrange(10))
def davea2(n):
global davea_happy, davea_unhappy
cache = set()
newnum = n
while newnum != 1:
newnum = int("".join(sorted(str(newnum))))
if newnum in davea_unhappy or newnum in cache:
davea_unhappy |= cache
return False #not a happy number
if newnum in davea_happy:
break
cache.add(newnum)
newnum = sum(SQUARES[ch] for ch in str(newnum))
davea_happy |= cache
return True #found a happy number
Finally, I did some testing on Jon Ribben's version. His was
substantially faster for smaller sets, and about the same for 10*7. So
it's likely it'll be slower than yours and mine for 10**8. But the real
reason I didn't like it was it produced a much larger set of
happy_numbers, which could clog memory a lot sooner. For 10**7 items, I
had 3250 happy members, and 19630 unhappy. And Jon had 1418854 happy
members.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
