Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Newsgroups: comp.lang.python
Date: Mon, 18 Feb 2013 20:17:51 -0800 (PST)
In-Reply-To: <mailman.2001.1361242894.2939.python-list@python.org>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=124.168.69.161; posting-account=ZAg6xAoAAAAmY8bBi3VzYjWntm8Ct1P8
References: <e8a634af-4e29-4f45-b327-2dfd1fab5269@googlegroups.com> <CAPTjJmr6C0fyPxuLEhXOZL4GVKRgV1=sx8xhG0Z6zLeGNB6ySQ@mail.gmail.com> <CAPTjJmptPWWbYccU=zSq-hS6k=Ja1mRzK1df4hHv7CuUmhL+Gg@mail.gmail.com> <mailman.1976.1361224740.2939.python-list@python.org> <9a3cb042-2819-4147-9a47-ede0065e58f5@googlegroups.com> <mailman.2001.1361242894.2939.python-list@python.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Subject: Re: Python 3.3 vs. MSDOS Basic
From: Nick Mellor <thebalancepro@gmail.com>
To: comp.lang.python@googlegroups.com
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org
Precedence: list
Message-ID: <mailman.2005.1361247476.2939.python-list@python.org>
Lines: 272
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:39183

Hi John,

Thanks for the problem. I've been writing Python for about 4 years now and =
am beginning to feel like I'm writing much better Python code.

Python does fine on this problem if you play to its strengths. The followin=
g uses dictionary lookups to store previously computed sequence lengths, th=
us saving a lot of work. The problem is very "sparse", i.e. there are huge =
gaps between numbers that are actually used in the solution, making diction=
aries a better fit than lists.

This code crosses the line in under 3s on a 64-bit laptop. MS-DOS BASIC any=
one? :-)

I tried precomputing powers of 2 and multiples of 2, but to my surprise it =
made very little difference to timings. Even though precomputing n//2 is fa=
st, I think again this is because the problem is sparse and the time the co=
mputer saves is not offset by the cost of precomputing many multiples of 2 =
that are never needed.

Best wishes,

Nick

And the winner is 837799 with sequence length 524
Time (s):  2.924168109893799
Sequence is:
[837799, 2513398, 1256699, 3770098, 1885049, 5655148, 2827574, 1413787, 424=
1362, 2120681, 6362044, 3181022, 1590511, 4771534, 2385767, 7157302, 357865=
1, 10735954, 5367977, 16103932, 8051966, 4025983, 12077950, 6038975, 181169=
26, 9058463, 27175390, 13587695, 40763086, 20381543, 61144630, 30572315, 91=
716946, 45858473, 137575420, 68787710, 34393855, 103181566, 51590783, 15477=
2350, 77386175, 232158526, 116079263, 348237790, 174118895, 522356686, 2611=
78343, 783535030, 391767515, 1175302546, 587651273, 1762953820, 881476910, =
440738455, 1322215366, 661107683, 1983323050, 991661525, 2974984576, 148749=
2288, 743746144, 371873072, 185936536, 92968268, 46484134, 23242067, 697262=
02, 34863101, 104589304, 52294652, 26147326, 13073663, 39220990, 19610495, =
58831486, 29415743, 88247230, 44123615, 132370846, 66185423, 198556270, 992=
78135, 297834406, 148917203, 446751610, 223375805, 670127416, 335063708, 16=
7531854, 83765927, 251297782, 125648891, 376946674, 188473337, 565420012, 2=
82710006, 141355003, 424065010, 212032505, 636097516, 318048758, 159024379,=
 477073138, 238536569, 715609708, 357804854, 178902427, 536707282, 26835364=
1, 805060924, 402530462, 201265231, 603795694, 301897847, 905693542, 452846=
771, 1358540314, 679270157, 2037810472, 1018905236, 509452618, 254726309, 7=
64178928, 382089464, 191044732, 95522366, 47761183, 143283550, 71641775, 21=
4925326, 107462663, 322387990, 161193995, 483581986, 241790993, 725372980, =
362686490, 181343245, 544029736, 272014868, 136007434, 68003717, 204011152,=
 102005576, 51002788, 25501394, 12750697, 38252092, 19126046, 9563023, 2868=
9070, 14344535, 43033606, 21516803, 64550410, 32275205, 96825616, 48412808,=
 24206404, 12103202, 6051601, 18154804, 9077402, 4538701, 13616104, 6808052=
, 3404026, 1702013, 5106040, 2553020, 1276510, 638255, 1914766, 957383, 287=
2150, 1436075, 4308226, 2154113, 6462340, 3231170, 1615585, 4846756, 242337=
8, 1211689, 3635068, 1817534, 908767, 2726302, 1363151, 4089454, 2044727, 6=
134182, 3067091, 9201274, 4600637, 13801912, 6900956, 3450478, 1725239, 517=
5718, 2587859, 7763578, 3881789, 11645368, 5822684, 2911342, 1455671, 43670=
14, 2183507, 6550522, 3275261, 9825784, 4912892, 2456446, 1228223, 3684670,=
 1842335, 5527006, 2763503, 8290510, 4145255, 12435766, 6217883, 18653650, =
9326825, 27980476, 13990238, 6995119, 20985358, 10492679, 31478038, 1573901=
9, 47217058, 23608529, 70825588, 35412794, 17706397, 53119192, 26559596, 13=
279798, 6639899, 19919698, 9959849, 29879548, 14939774, 7469887, 22409662, =
11204831, 33614494, 16807247, 50421742, 25210871, 75632614, 37816307, 11344=
8922, 56724461, 170173384, 85086692, 42543346, 21271673, 63815020, 31907510=
, 15953755, 47861266, 23930633, 71791900, 35895950, 17947975, 53843926, 269=
21963, 80765890, 40382945, 121148836, 60574418, 30287209, 90861628, 4543081=
4, 22715407, 68146222, 34073111, 102219334, 51109667, 153329002, 76664501, =
229993504, 114996752, 57498376, 28749188, 14374594, 7187297, 21561892, 1078=
0946, 5390473, 16171420, 8085710, 4042855, 12128566, 6064283, 18192850, 909=
6425, 27289276, 13644638, 6822319, 20466958, 10233479, 30700438, 15350219, =
46050658, 23025329, 69075988, 34537994, 17268997, 51806992, 25903496, 12951=
748, 6475874, 3237937, 9713812, 4856906, 2428453, 7285360, 3642680, 1821340=
, 910670, 455335, 1366006, 683003, 2049010, 1024505, 3073516, 1536758, 7683=
79, 2305138, 1152569, 3457708, 1728854, 864427, 2593282, 1296641, 3889924, =
1944962, 972481, 2917444, 1458722, 729361, 2188084, 1094042, 547021, 164106=
4, 820532, 410266, 205133, 615400, 307700, 153850, 76925, 230776, 115388, 5=
7694, 28847, 86542, 43271, 129814, 64907, 194722, 97361, 292084, 146042, 73=
021, 219064, 109532, 54766, 27383, 82150, 41075, 123226, 61613, 184840, 924=
20, 46210, 23105, 69316, 34658, 17329, 51988, 25994, 12997, 38992, 19496, 9=
748, 4874, 2437, 7312, 3656, 1828, 914, 457, 1372, 686, 343, 1030, 515, 154=
6, 773, 2320, 1160, 580, 290, 145, 436, 218, 109, 328, 164, 82, 41, 124, 62=
, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274=
, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395=
, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132,=
 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238,=
 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 307=
7, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 2=
44, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, =
8, 4, 2, 1]
Sparsity calculations...
Computed sequence lengths 2168611
Largest term:  56991483520
Test range:  1 1000000
Biggest gap:  4508198208
Sparsity: 0.00175%


# If True, will precompute powers of 2 and multiples of 2
# in practice this made little difference on 64-bit hardware
OPTIMISE =3D True

def build_sequence(n):
    """return sequence as a list given the starting number
    Uses the trail of data left by compute_sequence"""
    tmp =3D compute_sequence(n)
    sequence =3D []
    while n:
        sequence.append(n)
        n =3D next_num[n]
    return sequence

def compute_sequence(n):
    """lazily compute sequences for Collatz problem"""
    if n in seqlength:
        return seqlength[n]
    if n not in next_num:
        # NOTE: (some) evens are pre-computed
        next_num[n] =3D 3 * n + 1 if n % 2 else n // 2
    seqlength[n] =3D 1 + compute_sequence(next_num[n])
    return seqlength[n]

import time
start =3D time.time()

highest_number =3D int(1000000)
highest_term =3D highest_number * 3 + 1
highest_term +=3D 1 if highest_term % 2 else 0

next_num =3D {2:1}
if OPTIMISE:
    # quickly pre-compute (some of) the evens (used for n =3D n//2 if n is =
even)
    # how many should we precompute? Any mathematicians?
    doubles =3D range(2, highest_term, 2)
    numbers =3D range(1, highest_term//2)
    next_num =3D dict(zip(doubles, numbers))
# mark 1 as the end-point of any sequence
next_num[1] =3D 0

# initialise the sequence lengths
seqlength =3D {}
seqlength[1] =3D 0
seqlength[2] =3D 1
if OPTIMISE:
    # powers of 2 are trivial: 2**n has sequence length n
    n =3D 2
    pwr =3D 4
    while pwr < highest_term:
        seqlength[pwr] =3D n
        pwr =3D pwr * 2
        n +=3D 1
max_length =3D 0
for n in range(3, highest_number + 1):
    length =3D compute_sequence(n)
    if length > max_length:
        max_length =3D length
        winning_number =3D n
print ("And the winner is {0} with sequence length {1}".format(winning_numb=
er, max_length))
end =3D time.time()
print ("Time (s): ", (end-start))

print ("Sequence is:")
print (build_sequence(winning_number))

# Sparsity calculation
sorted_seqlengths =3D sorted(seqlength.keys())
print ("Sparsity calculations...")
print ("Computed sequence lengths", len(seqlength))
largest_term =3D sorted_seqlengths[-1]
print ("Largest term: ", largest_term)
print ("Test range: ", 1, highest_number)
gaps =3D (second - first for first, second in zip(sorted_seqlengths[0:-1], =
sorted_seqlengths[1:]))
biggest_gap =3D 0
for n in gaps:
    if biggest_gap < n:
        biggest_gap =3D n
print ("Biggest gap: ", n)
print ("Sparsity: {0:.5f}%".format(highest_number / largest_term * 100))


On Tuesday, 19 February 2013 14:01:31 UTC+11, Chris Angelico  wrote:
> On Tue, Feb 19, 2013 at 12:39 PM, John Immarino <johimm@gmail.com> wrote:
>=20
> > On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
>=20
> >> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wro=
te:
>=20
> >>
>=20
> >> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> w=
rote:
>=20
> >>
>=20
> >> >> How long did your BASIC version take, and how long did the Python
>=20
> >>
>=20
> >> >> version on the same hardware?
>=20
> >>
>=20
> >> >
>=20
> >>
>=20
> >> > Oops, my bad, you already posted the figures :) And I forgot to ask:
>=20
> >>
>=20
> >> > Which Python version didyou use?
>=20
> >>
>=20
> >> >
>=20
> >>
>=20
> >> > ChrisA
>=20
> >>
>=20
> >>
>=20
> >>
>=20
> >> Doh. I'm having a great day of not reading properly, today. (I blame
>=20
> >>
>=20
> >> checking mail on the bus, it took me over an hour to read this one
>=20
> >>
>=20
> >> message and I'd forgotten the subject line by the time I got to the
>=20
> >>
>=20
> >> end.) Python 3.3, right there in the header. Disregard me!
>=20
> >>
>=20
> >>
>=20
> >>
>=20
> >> ChrisA
>=20
> >
>=20
> > Thanks,Chris. I'm a newbie to Python and didn't realize that it's not a=
s good at number crunching as some of the others. It does seem to do better=
 than Basic with numbers in lists as opposed to arrays in Basic.
>=20
>=20
>=20
> Yes, Python is excellent at data handling. I'll cheerfully use Python
>=20
> to manipulate huge lists or arrays, and its performance at that is
>=20
> usually well within the "good enough" range (for instance, anything
>=20
> that manipulates the file system will be waiting on my disks, not on
>=20
> Python). It's an excellent tool in the toolkit, just not the one
>=20
> solution to everything. (Nothing's that!)
>=20
>=20
>=20
> ChrisA