Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #89676

Re: Is my implementation of happy number OK

Path csiph.com!usenet.pasdenom.info!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <davea@davea.name>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.012
X-Spam-Evidence '*H*': 0.98; '*S*': 0.00; 'algorithm': 0.04; 'exercise': 0.04; 'memory.': 0.07; 'sized': 0.07; 'cest': 0.09; 'subject:number': 0.09; 'stored': 0.12; '(it': 0.16; 'caching': 0.16; 'detects': 0.16; 'fancy': 0.16; 'feasible': 0.16; 'sooner.': 0.16; 'subject:happy': 0.16; 'wrote:': 0.18; 'version.': 0.19; 'written': 0.21; 'memory': 0.22; 'header:User-Agent:1': 0.23; 'finally,': 0.24; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'testing': 0.29; 'sets': 0.30; "i'm": 0.30; 'apparently': 0.31; 'sets.': 0.31; 'subject:skip:i 10': 0.31; 'run': 0.32; 'not.': 0.33; 'could': 0.34; 'but': 0.35; 'version': 0.36; "didn't": 0.36; 'similar': 0.36; 'error.': 0.37; 'members.': 0.37; 'mine': 0.38; 'to:addr:python-list': 0.38; 'list,': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'dave': 0.60; 'challenge': 0.61; 'real': 0.63; 'charset:windows-1252': 0.65; 'received:74.208': 0.68; 'counts': 0.83; '2015': 0.84; 'difference.': 0.84; 'sets,': 0.84; 'yours': 0.88; 'items,': 0.91
Date Thu, 30 Apr 2015 17:31:24 -0400
From Dave Angel <davea@davea.name>
User-Agent Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version 1.0
To python-list@python.org
Subject Re: Is my implementation of happy number OK
References <87oam5vc8k.fsf@Equus.decebal.nl> <mailman.140.1430420006.3680.python-list@python.org> <87vbgds6b7.fsf@Equus.decebal.nl>
In-Reply-To <87vbgds6b7.fsf@Equus.decebal.nl>
Content-Type text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding 7bit
X-Provags-ID V03:K0:QRLpP27FT5kyHG4MSXhE54UXp2YxxTk9KD0fZSbv7CR0qvSXrJW LM58E3TrQb7EOgkGGfU7iDu8QCL2jMDZFfhZnko+uUBmQWyLxHa2HEs7sWPAPftrk6sOEWT oqTeRts1jkHuHoCW8EtpjM2Tq/TIuGOzUGvXNf8VDKXsuOY2PZ3ARPjCh3JGhEyYOer3Su4 uaPvx/Lp55H64ixFNlI/A==
X-UI-Out-Filterresults notjunk:1;
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.20+
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.148.1430429500.3680.python-list@python.org> (permalink)
Lines 30
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1430429500 news.xs4all.nl 2969 [2001:888:2000:d::a6]:60732
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:89676

Show key headers only | View raw

On 04/30/2015 04:35 PM, Cecil Westerhof wrote:
> Op Thursday 30 Apr 2015 20:53 CEST schreef Dave Angel:
>
>>
>> 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.
>
> My version has 1625 and 9814. I do not understand the difference.
>

My error.  I had also written a version of the function that stored 
strings instead of ints, and the counts of 3250/19630 was for sets that 
had BOTH.

An exercise for the reader.  Notice that in my brute force algorithm I 
use no global sets.  But I do use an internal list, which is apparently 
unbounded.  So it's feasible to run out of memory.  The challenge is to 
write a similar function that uses no lists, sets, or dicts, just an 
algorithm that detects for an arbitrary sized number whether it's happy 
or not.  (It may not be very quick, but that's yet to be decided.  I'm 
already surprised that the present brute force function  davea1() only 
takes about twice as long as the fancy global caching schemes.

-- 
DaveA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is my implementation of happy number OK Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 17:59 +0200
  Re: Is my implementation of happy number OK Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2015-04-30 17:04 +0000
  Re: Is my implementation of happy number OK Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-30 11:37 -0600
    Re: Is my implementation of happy number OK Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 21:05 +0200
  Re: Is my implementation of happy number OK Dave Angel <davea@davea.name> - 2015-04-30 14:53 -0400
    Re: Is my implementation of happy number OK Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 22:35 +0200
      Re: Is my implementation of happy number OK Dave Angel <davea@davea.name> - 2015-04-30 17:31 -0400
    Re: Is my implementation of happy number OK Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2015-04-30 23:31 +0000
      Re: Is my implementation of happy number OK Dave Angel <davea@davea.name> - 2015-04-30 19:52 -0400
        Re: Is my implementation of happy number OK Cecil Westerhof <Cecil@decebal.nl> - 2015-05-01 06:36 +0200
        Re: Is my implementation of happy number OK Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2015-05-01 07:23 +0000
          Re: Is my implementation of happy number OK Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-01 18:27 +1000
            Re: Is my implementation of happy number OK Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-01 09:03 -0600
            Re: Is my implementation of happy number OK Peter Otten <__peter__@web.de> - 2015-05-01 20:13 +0200
              Re: Is my implementation of happy number OK Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2015-05-02 21:23 +0000

csiph-web