Is my implementation of happy number OK
Dave Angel
davea at davea.name
Thu Apr 30 14:53:10 EDT 2015
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
More information about the Python-list
mailing list