Re: Python 3.3 vs. MSDOS Basic
On 02/20/2013 04:49 PM, Tim Daneliuk wrote: On 02/20/2013 12:38 PM, Ian Kelly wrote: On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk wrote: Thanks. I was specifically curious about your use of dynamic programming. What about this algorithm makes it particularly an example of this? Is it your use of memoization or something other than this? In retrospect, I was using the term overly broadly, as the algorithm does not really use dynamic programming. I should have written "memoization" instead. That's why I asked. Dynamic Programming itself is a sort of wide term and I was curious which version of it you found useful. Thanks for the discussion. One other point of interest: The formal notion of Dynamic Program is to decompose problems into potentially overlapping subproblems and only solve each subproblem once, and reapply the results as needed. Hence, your use of memoization is indeed an example of Dynamic Programming. Notwithstanding the formal ideas of a Dynamic Program, my interest in this context really had more to do with the word "dynamic". Languages like Python are "dynamic" in the sense that a running program can actually generate new code as it runs. This makes it possible to write adaptive programs that morph as they run, typically in response to their inputs and state.*** I was thinking that perhaps you'd done something in this sense of the word in solving the OPs problem. *** To be sure, you can do this in assembler too, it's just much more convenient in dynamic languages like Python. -- Tim Daneliuk tun...@tundraware.com PGP Key: http://www.tundraware.com/PGP/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 02/20/2013 12:38 PM, Ian Kelly wrote: On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk wrote: Thanks. I was specifically curious about your use of dynamic programming. What about this algorithm makes it particularly an example of this? Is it your use of memoization or something other than this? In retrospect, I was using the term overly broadly, as the algorithm does not really use dynamic programming. I should have written "memoization" instead. That's why I asked. Dynamic Programming itself is a sort of wide term and I was curious which version of it you found useful. Thanks for the discussion. -- Tim Daneliuk tun...@tundraware.com PGP Key: http://www.tundraware.com/PGP/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk wrote: > Thanks. I was specifically curious about your use of dynamic programming. > What about this algorithm makes it particularly an example of this? Is > it your use of memoization or something other than this? In retrospect, I was using the term overly broadly, as the algorithm does not really use dynamic programming. I should have written "memoization" instead. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 2013-02-19, John Immarino wrote: > Thanks,Chris. I'm a newbie to Python and didn't realize that > it's not as 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. Python is good enough at number crunching for Project Euler. Its data types and library make a few of the problems otherwise uninteresting, in fact. Sometimes, as in this case, memoization is good enough (a quick look at my own code for this shows that's what I did, too). But when it's a particularly good example of a Project Euler problem, you'll need to do some mathematical analysis to improve your approach, first. But yeah, do not get in the habit of comparing your times to, say, C++ programs. ;) -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 02/19/2013 12:31 PM, Ian Kelly wrote:
On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk wrote:
Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...
Very well:
def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]
def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
run_collatz(100)
(837799, 524)
It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
Thanks. I was specifically curious about your use of dynamic programming.
What about this algorithm makes it particularly an example of this? Is
it your use of memoization or something other than this?
--
---
Tim Daneliuk
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
Chris Angelico wrote: On Wed, Feb 20, 2013 at 7:28 AM, Serhiy Storchaka wrote: 10-15% faster: ... num = max(range(2, M + 1), key=g) ... Yes, but 20-30% less clear and readable. Though I do like the idea of playing this code in the key of G Major. On the SmartStupid, presumably. http://wordsmith.org/board/ubbthreads.php?ubb=showflat&Number=101906 -- Greg -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tuesday, February 19, 2013 3:28:25 PM UTC-5, Serhiy Storchaka wrote:
> 10-15% faster:
>
>
> def f(M):
> def g(n, cache = {1: 0}):
> if n in cache:
> return cache[n]
> if n % 2:
> m = 3 * n + 1
> else:
> m = n // 2
> cache[n] = count = g(m) + 1
> return count
> num = max(range(2, M + 1), key=g)
> return num, g(num)
>
> print(*f(100))
I managed another 15-20% (on my machine) with a different caching scheme.
def g(n):
cache = [1,1] + [0]*(n - 2)
longest = 0
for x in range(1, n):
num = 0
y = x
while True:
if x < n and cache[x]:
cache[y] = num + cache[x]
break
if x&1:
x = (3*x + 1)//2#Credit to Terry
num += 2
else:
x = x//2
num += 1
ans = cache.index(max(cache))
return ans, cache[ans] - 1
Python 3.2.3 (default, Oct 19 2012, 19:53:57)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)
16.590431928634644
>>> timeit.Timer('euler014.f(10**7)', 'import euler014').timeit(1)
17.689634084701538
>>> timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)
13.558412790298462
>>> timeit.Timer('euler014.g(10**7)', 'import euler014').timeit(1)
14.075398921966553
In this code only entries less than n (100 in the project Euler problem)
are cached, and only one is cached per run of the inner loop, which to
me would seem to me much less efficient. I supposed the advantages are no
overhead from dict lookups, function calls, or recursion, plus it uses Terry
Reedy's nice observation that one can take two steps at a time for odd
values. I would think my version uses less memory as well, since the cache
dict/list would be maximally dense for indices less than n in either scheme.
I'm still surprised that both algorithm's seem pretty much O(n) tho.
Intuitively I'd have thought mine would start to lose out with larger
numbers, given the much lower degree of caching.
With PyPy the results are more striking:
Python 2.7.2 (1.9+dfsg-1, Jun 19 2012, 23:23:45)
[PyPy 1.9.0 with GCC 4.7.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``Is rigobot around when the
universe ceases to exist?''
import timeit
timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)
26.138880014419556
timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)
1.5725858211517334
I guess PyPy can JIT the iterative loop more effectively than it can the
recursion.
This is my first post on this list btw, please let me know if I screwed
anything up.
workshed
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 5:23 PM, Alexander Blinne wrote: > If changed into > > signed int n; > > there is a veeery long, perhaps infinite loop. Yes, infinite. Here's the first such sequence encountered with a signed 32-bit int. [113383, 340150, 170075, 510226, 255113, 765340, 382670, 191335, 574006, 287003, 861010, 430505, 1291516, 645758, 322879, 968638, 484319, 1452958, 726479, 2179438, 1089719, 3269158, 1634579, 4903738, 2451869, 7355608, 3677804, 1838902, 919451, 2758354, 1379177, 4137532, 2068766, 1034383, 3103150, 1551575, 4654726, 2327363, 6982090, 3491045, 10473136, 5236568, 2618284, 1309142, 654571, 1963714, 981857, 2945572, 1472786, 736393, 2209180, 1104590, 552295, 1656886, 828443, 2485330, 1242665, 3727996, 1863998, 931999, 2795998, 1397999, 4193998, 2096999, 6290998, 3145499, 9436498, 4718249, 14154748, 7077374, 3538687, 10616062, 5308031, 15924094, 7962047, 23886142, 11943071, 35829214, 17914607, 53743822, 26871911, 80615734, 40307867, 120923602, 60461801, 181385404, 90692702, 45346351, 136039054, 68019527, 204058582, 102029291, 306087874, 153043937, 459131812, 229565906, 114782953, 344348860, 172174430, 86087215, 258261646, 129130823, 387392470, 193696235, 581088706, 290544353, 871633060, 435816530, 217908265, 653724796, 326862398, 163431199, 490293598, 245146799, 735440398, 367720199, 1103160598, 551580299, 1654740898, 827370449, -1812855948, -906427974, -453213987, -1359641960, -679820980, -339910490, -169955245, -509865734, -254932867, -764798600, -382399300, -191199650, -95599825, -286799474, -143399737, -430199210, -215099605, -645298814, -322649407, -967948220, -483974110, -241987055, -725961164, -362980582, -181490291, -544470872, -272235436, -136117718, -68058859, -204176576, -102088288, -51044144, -25522072, -12761036, -6380518, -3190259, -9570776, -4785388, -2392694, -1196347, -3589040, -1794520, -897260, -448630, -224315, -672944, -336472, -168236, -84118, -42059, -126176, -63088, -31544, -15772, -7886, -3943, -11828, -5914, -2957, -8870, -4435, -13304, -6652, -3326, -1663, -4988, -2494, -1247, -3740, -1870, -935, -2804, -1402, -701, -2102, -1051, -3152, -1576, -788, -394, -197, -590, -295, -884, -442, -221, -662, -331, -992, -496, -248, -124, -62, -31, -92, -46, -23, -68, -34, -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, ...] -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
Am 19.02.2013 12:42, schrieb Piet van Oostrum:
> Terry Reedy writes:
>> I find this surprising too. I am also surprised that it even works,
>> given that the highest intermediate value is about 57 billion and I do
>> not remember that Basic had infinite precision ints.
>
> That may explain why the Basic version is faster: it gets overflow and
> then it may have taken some shortcuts.
Consider this C program
#include
int main(void) {
int max = 0;
int m = 0;
long int n;
int count;
int num;
while(m<=100) {
m++;
n = m;
count = 0;
while(n != 1) {
count++;
if(n % 2 == 0) {
n = n / 2;
}
else {
n = n*3 + 1;
}
}
if(count > max) {
max = count;
num = m;
}
}
printf("%d, %d\n", num, max);
}
If the line
long int n;
is changed into
unsigned int n;
the program runs in 0.68 sec instead of 0.79, so there is some shortcut.
If changed into
signed int n;
there is a veeery long, perhaps infinite loop.
Greetings
Alexander
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Wed, Feb 20, 2013 at 7:28 AM, Serhiy Storchaka wrote: > 10-15% faster: > ... num = max(range(2, M + 1), key=g) ... Yes, but 20-30% less clear and readable. Though I do like the idea of playing this code in the key of G Major. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 19.02.13 20:31, Ian Kelly wrote:
On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk wrote:
Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...
Very well:
def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]
def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
run_collatz(100)
(837799, 524)
It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
10-15% faster:
def f(M):
def g(n, cache = {1: 0}):
if n in cache:
return cache[n]
if n % 2:
m = 3 * n + 1
else:
m = n // 2
cache[n] = count = g(m) + 1
return count
num = max(range(2, M + 1), key=g)
return num, g(num)
print(*f(100))
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk wrote:
> Are you sure you wouldn't like to share with the class? I'd be interested
> in seeing your approach...
Very well:
def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]
def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
>>> run_collatz(100)
(837799, 524)
It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 02/18/2013 03:54 PM, Ian Kelly wrote: On Mon, Feb 18, 2013 at 12:13 PM, John Immarino wrote: I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program. I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python. Well, I don't see anything that looks especially slow in that code, but the algorithm that you're using is not very efficient. I rewrote it using dynamic programming (details left as an exercise), which got the runtime down to about 4 seconds. Are you sure you wouldn't like to share with the class? I'd be interested in seeing your approach... -- Tim Daneliuk tun...@tundraware.com PGP Key: http://www.tundraware.com/PGP/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
> max=0 > m=0 > while m<=100: > m+=1 > count=0 > n=m > while n!=1: > count+=1 > if n%2==0: > n=n//2 > else: > n=3*n+1 > if count>max: > max=count > num=m > print(num,max) > I have tried to run your program with pypy (Python git compiler) (http://pypy.org/), it runs about 15x faster (8 sec instead of 2m2sec in my old Celeron M420 computer). Olive -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
Terry Reedy writes: > On 2/18/2013 2:13 PM, John Immarino wrote: >> I coded a Python solution for Problem #14 on the Project Euler >> website. I was very surprised to find that it took 107 sec. to run >> even though it's a pretty simple program. I also coded an equivalent >> solution for the problem in the old MSDOS basic. (That's the 16 bit >> app of 1980s vintage.) It ran in 56 sec. Is there a flaw in my >> coding, or is Python really this slow in this particular application. >> MSDOS Basic usually runs at a snails pace compared to Python. > > I find this surprising too. I am also surprised that it even works, > given that the highest intermediate value is about 57 billion and I do > not remember that Basic had infinite precision ints. That may explain why the Basic version is faster: it gets overflow and then it may have taken some shortcuts. -- Piet van Oostrum WWW: http://pietvanoostrum.com/ PGP key: [8DAE142BE17999C4] -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 18.02.13 21:13, John Immarino wrote: max=0 m=0 while m<=100: m+=1 count=0 n=m while n!=1: count+=1 if n%2==0: n=n//2 else: n=3*n+1 if count>max: max=count num=m print(num,max) Some minor tips: 1. Use range() for m iteration. 2. Instead of "if n%2==0:" use just "if n%2:". 3. Convert all you code to a function. Python is a little faster with locals than with globals. In sum all this tips will speedup your code about 2x. And one big tip: Use cashing (and recursion). This will speedup your code more than 10x. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
John Immarino writes: > I coded a Python solution for Problem #14 on the Project Euler > website. I was very surprised to find that it took 107 sec. to run > even though it's a pretty simple program. I also coded an equivalent > solution for the problem in the old MSDOS basic. (That's the 16 bit > app of 1980s vintage.) Just out of curiosity, can you post the basic version as well? -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 2/18/2013 4:55 PM, Chris Angelico wrote: Running under Python 2.6, both your version and mine take about 90 seconds to run. But under Python 3.3, where (among other things) range() yields values lazily, my version is significantly faster than yours. BUT! Both versions, under 3.3, are significantly *slower* than under 2.6. My first thought is that it's because Py2 has different types for 'int' and 'long', and Py3 doesn't (effectively, everything's a long), so I added an L suffix to every number and ran each of them under 2.6 again. Seems that was the bulk of the difference, though not all. Pythonistas, does this count as a regression, or is Python sufficiently "not a number crunching language" that we don't care? Both. This brute-force algorithm is almost pure number crunching. This is the sort of thing pypy and cython are good at speeding up. (I leave out numpy only because it is not an array-oriented problem.) I put a counter in the inner loop of my improved version the does (3*n+1)//2 in one step and got 87 826 478 in 40 seconds (without the counter). That is 2 million loops per second and each loop does a compare, one or two integer ops, and creates and releases one or two ints. If I were doing a lot of int crunching like this with CPython and were building my own interpreter, I would greatly expand the range of pre-allocated 'small' ints to avoid some of the repeated allocation and de-allocation. On a multi-gibibyte machine, allocating up to 100 instead of 256 would be feasible. As Ian noted, an intelligent algorithm in CPython can match pypy and is in the ballpark of C, but is much easier to write in Python than C. It is possible that Ian's code could be improved further. A pre-allocated arrray + dict might be faster. Whenever an odd value is filled in, powers of 2 times that value can also be. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
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 following uses dictionary lookups to store previously computed sequence lengths, thus 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 dictionaries a better fit than lists. This code crosses the line in under 3s on a 64-bit laptop. MS-DOS BASIC anyone? :-) 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 fast, I think again this is because the problem is sparse and the time the computer 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, 4241362, 2120681, 6362044, 3181022, 1590511, 4771534, 2385767, 7157302, 3578651, 10735954, 5367977, 16103932, 8051966, 4025983, 12077950, 6038975, 18116926, 9058463, 27175390, 13587695, 40763086, 20381543, 61144630, 30572315, 91716946, 45858473, 137575420, 68787710, 34393855, 103181566, 51590783, 154772350, 77386175, 232158526, 116079263, 348237790, 174118895, 522356686, 261178343, 783535030, 391767515, 1175302546, 587651273, 1762953820, 881476910, 440738455, 1322215366, 661107683, 1983323050, 991661525, 2974984576, 1487492288, 743746144, 371873072, 185936536, 92968268, 46484134, 23242067, 69726202, 34863101, 104589304, 52294652, 26147326, 13073663, 39220990, 19610495, 58831486, 29415743, 88247230, 44123615, 132370846, 66185423, 198556270, 99278135, 297834406, 148917203, 446751610, 223375805, 670127416, 335063708, 167531854, 83765927, 251297782, 125648891, 376946674, 188473337, 565420012, 282710006, 141355003, 42 4065010, 212032505, 636097516, 318048758, 159024379, 477073138, 238536569, 715609708, 357804854, 178902427, 536707282, 268353641, 805060924, 402530462, 201265231, 603795694, 301897847, 905693542, 452846771, 1358540314, 679270157, 2037810472, 1018905236, 509452618, 254726309, 764178928, 382089464, 191044732, 95522366, 47761183, 143283550, 71641775, 214925326, 107462663, 322387990, 161193995, 483581986, 241790993, 725372980, 362686490, 181343245, 544029736, 272014868, 136007434, 68003717, 204011152, 102005576, 51002788, 25501394, 12750697, 38252092, 19126046, 9563023, 28689070, 14344535, 43033606, 21516803, 64550410, 32275205, 96825616, 48412808, 24206404, 12103202, 6051601, 18154804, 9077402, 4538701, 13616104, 6808052, 3404026, 1702013, 5106040, 2553020, 1276510, 638255, 1914766, 957383, 2872150, 1436075, 4308226, 2154113, 6462340, 3231170, 1615585, 4846756, 2423378, 1211689, 3635068, 1817534, 908767, 2726302, 1363151, 4089454, 2044727, 6134182, 3067091, 9201274, 4600637, 13801912, 6900956, 3450478, 1725239, 5175718, 2587859, 7763578, 3881789, 11645368, 5822684, 2911342, 1455671, 4367014, 2183507, 6550522, 3275261, 9825784, 4912892, 2456446, 1228223, 3684670, 1842335, 5527006, 2763503, 8290510, 4145255, 12435766, 6217883, 18653650, 9326825, 27980476, 13990238, 6995119, 20985358, 10492679, 31478038, 15739019, 47217058, 23608529, 70825588, 35412794, 17706397, 53119192, 26559596, 13279798, 6639899, 19919698, 9959849, 29879548, 14939774, 7469887, 22409662, 11204831, 33614494, 16807247, 50421742, 25210871, 75632614, 37816307, 113448922, 56724461, 170173384, 85086692, 42543346, 21271673, 63815020, 31907510, 15953755, 47861266, 23930633, 71791900, 35895950, 17947975, 53843926, 26921963, 80765890, 40382945, 121148836, 60574418, 30287209, 90861628, 45430814, 22715407, 68146222, 34073111, 102219334, 51109667, 153329002, 76664501, 229993504, 114996752, 57498376, 28749188, 14374594, 7187297, 21561892, 10780946, 5390473, 16171420, 8085710, 4042855, 12128566, 6064283, 18192 850, 9096425, 27289276, 13644638, 6822319, 20466958, 10233479, 30700438, 15350219, 46050658, 23025329, 69075988, 34537994, 17268997, 51806992, 25903496, 12951748, 6475874, 3237937, 9713812, 4856906, 2428453, 7285360, 3642680, 1821340, 910670, 455335, 1366006, 683003, 2049010, 1024505, 3073516, 1536758, 768379, 2305138, 1152569, 3457708, 1728854, 864427, 2593282, 1296641, 3889924, 1944962, 972481, 2917444, 1458722, 729361, 2188084, 1094042, 547021, 1641064, 820532, 410266, 205133, 615400, 307700, 153850, 76925, 230776, 115388, 57694, 28847, 86542, 43271, 129814, 64907, 194722, 97361, 292084, 146042, 73021, 219064, 109532, 54766, 27383, 82150, 41075, 123226, 61613, 184840, 92420, 46210, 23105, 69316, 34658, 17329, 51988, 25994, 12997, 38992, 19496, 9748, 4874, 2437, 7312, 3656, 1828, 914, 457, 1372, 686, 343, 1030, 515, 1546, 773, 2320, 1160, 580, 290, 145, 436, 218, 109, 328, 164, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 12:39 PM, John Immarino wrote: > On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote: >> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico wrote: >> >> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico wrote: >> >> >> How long did your BASIC version take, and how long did the Python >> >> >> version on the same hardware? >> >> > >> >> > Oops, my bad, you already posted the figures :) And I forgot to ask: >> >> > Which Python version didyou use? >> >> > >> >> > ChrisA >> >> >> >> Doh. I'm having a great day of not reading properly, today. (I blame >> >> checking mail on the bus, it took me over an hour to read this one >> >> message and I'd forgotten the subject line by the time I got to the >> >> end.) Python 3.3, right there in the header. Disregard me! >> >> >> >> ChrisA > > Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as 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. Yes, Python is excellent at data handling. I'll cheerfully use Python to manipulate huge lists or arrays, and its performance at that is usually well within the "good enough" range (for instance, anything that manipulates the file system will be waiting on my disks, not on Python). It's an excellent tool in the toolkit, just not the one solution to everything. (Nothing's that!) ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
> > > max=0 > > > > "max" is a bad name -- it masks the built-in max() function > > > > > m=0 > > > while m<=100: > > > m+=1 > > > > Since "m" is only modified here and has a value of 1 for the first > > pass through, you can replace those three lines with > > > > for m in xrange(1, 101): #python 2.x, just use range() for 3.x > > > > > count=0 > > > n=m > > > > > while n!=1: > > > count+=1 > > > if n%2==0: > > > n=n//2 > > > else: > > > n=3*n+1 > > > > Avoid the comparison to 0 by reversing the then/else actions... Any > > 0 result is false. > > > > -=-=-=-=- > > import time > > > > mx = 0 > > > > start = time.time() > > for m in xrange(1, 101): > > count = 0 > > n = m > > while n > 1: > > count += 1 > > if n % 2: # 0 means false > > n = 3 * n + 1 > > else: > > n = n // 2 > > > > if count > mx: > > mx, num = count, m > > > > end = time.time() > > > > print num, mx > > print end-start > > -=-=-=-=- > > Microsoft Windows XP [Version 5.1.2600] > > (C) Copyright 1985-2001 Microsoft Corp. > > > > E:\UserData\Wulfraed\My Documents>cd "Python Progs" > > > > E:\UserData\Wulfraed\My Documents\Python Progs>Script1.py > > 837799 524 > > 83.203687 > > > > E:\UserData\Wulfraed\My Documents\Python Progs> > > > > > > > > > > > > > > -- > > Wulfraed Dennis Lee Bieber AF6VN > > wlfr...@ix.netcom.comHTTP://wlfraed.home.netcom.com/ Thanks, your suggestions are well taken. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote: > On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico wrote: > > > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico wrote: > > >> How long did your BASIC version take, and how long did the Python > > >> version on the same hardware? > > > > > > Oops, my bad, you already posted the figures :) And I forgot to ask: > > > Which Python version didyou use? > > > > > > ChrisA > > > > Doh. I'm having a great day of not reading properly, today. (I blame > > checking mail on the bus, it took me over an hour to read this one > > message and I'd forgotten the subject line by the time I got to the > > end.) Python 3.3, right there in the header. Disregard me! > > > > ChrisA Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On 2/18/2013 2:13 PM, John Immarino wrote: I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program. I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python. I find this surprising too. I am also surprised that it even works, given that the highest intermediate value is about 57 billion and I do not remember that Basic had infinite precision ints. The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Note that if n is odd, 3n + 1 is even (and not 1!), so one may take two steps with (3n + 1)/2. Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. https://en.wikipedia.org/wiki/Collatz_conjecture Which starting number, under one million, produces the longest chain? I suppose 'print(837799)' would not count as a proper solution. NOTE: Once the chain starts the terms are allowed to go above one million. Here is my slightly revised code with timings on a good, 20 month old win 7 machine. from time import time start = time() num, max = 0, 0 for m in range(1, 101): n = m count=0 while n !=1: if n & 1: #n % 2: n = (3*n + 1) // 2 count += 2 else: n = n//2 count += 1 if count > max: num = m max = count print(num, max , time()-start) # original: 837799, 524 steps, 53.9 secs # for ... range: 52.3 # reverse inner if 49.0 # double step 39.1 # n & 1 instead of n % 2 for test: 36.0, 36.0, 35.9 # n>>1 instead of n//2: 34.7, 36.1, 36.2; # this may be internally optimized, so skip I do not see any fluff left to remove, unless one takes the major step of saving already calculated values in an array. Since the highest intermediate value of n is 56991483520 (445245965 *2**7, from adding "if n > maxn: maxn = n" to the odd branch, before dividing by 2), the array would have to be limited to a much lower value, say a few million. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
Am 18.02.2013 20:13, schrieb John Immarino:
> I coded a Python solution for Problem #14 on the Project Euler website. I was
> very surprised to find that it took 107 sec. to run even though it's a pretty
> simple program. I also coded an equivalent solution for the problem in the
> old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec.
> Is there a flaw in my coding, or is Python really this slow in this
> particular application. MSDOS Basic usually runs at a snails pace compared to
> Python.
> max=0
> m=0
> while m<=100:
> m+=1
> count=0
> n=m
> while n!=1:
> count+=1
> if n%2==0:
> n=n//2
> else:
> n=3*n+1
> if count>max:
> max=count
> num=m
> print(num,max)
I cannot compare my timings with basic but python 2.7.3 and python 3.2.3
are both equally slow hier (~50 sec).
pypy is a lot faster (only some old version 1.7.0, current versions
should be faster still) with about 5 sec.
The following C-Program:
#include
int main(void) {
int max = 0;
int m = 0;
long int n;
int count;
int num;
while(m<=100) {
m++;
n = m;
count = 0;
while(n != 1) {
count++;
if(n % 2 == 0) {
n = n / 2;
}
else {
n = n*3 + 1;
}
}
if(count > max) {
max = count;
num = m;
}
}
printf("%d, %d\n", num, max);
}
Does the job in just under 1 sec.
Greetings
Alexander
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Mon, Feb 18, 2013 at 3:01 PM, Chris Angelico wrote: > On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly wrote: >> Well, I don't see anything that looks especially slow in that code, >> but the algorithm that you're using is not very efficient. I rewrote >> it using dynamic programming (details left as an exercise), which got >> the runtime down to about 4 seconds. > > Did it involve a dictionary, mapping a value to its count, so that any > time you hit a value you've seen, you can short-cut it? That was my > first optimization consideration, though I didn't implement it in any > version, so as to keep the timings comparable. Ayup. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly wrote: > Well, I don't see anything that looks especially slow in that code, > but the algorithm that you're using is not very efficient. I rewrote > it using dynamic programming (details left as an exercise), which got > the runtime down to about 4 seconds. Did it involve a dictionary, mapping a value to its count, so that any time you hit a value you've seen, you can short-cut it? That was my first optimization consideration, though I didn't implement it in any version, so as to keep the timings comparable. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico wrote: > How long did your BASIC version take, and how long did the Python > version on the same hardware? Oops, my bad, you already posted the figures :) And I forgot to ask: Which Python version didyou use? ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico wrote: > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico wrote: >> How long did your BASIC version take, and how long did the Python >> version on the same hardware? > > Oops, my bad, you already posted the figures :) And I forgot to ask: > Which Python version didyou use? > > ChrisA Doh. I'm having a great day of not reading properly, today. (I blame checking mail on the bus, it took me over an hour to read this one message and I'd forgotten the subject line by the time I got to the end.) Python 3.3, right there in the header. Disregard me! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Tue, Feb 19, 2013 at 6:13 AM, John Immarino wrote:
> I coded a Python solution for Problem #14 on the Project Euler website. I was
> very surprised to find that it took 107 sec. to run even though it's a pretty
> simple program. I also coded an equivalent solution for the problem in the
> old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec.
> Is there a flaw in my coding, or is Python really this slow in this
> particular application. MSDOS Basic usually runs at a snails pace compared to
> Python.
BASIC does a lot less. If you wrote an 8086 assembly language
interpreter in Python, it'd run fairly slowly too :) Python isn't
really the world's best language for number crunching inside a machine
word; though if this were a major project, I would recommend looking
into Cython, as it lets you translate a few critical portions of your
code to C while leaving the rest in Python.
In order to get some useful stats, I added a little timing code to
your original; on my Windows XP laptop, running Python 3.3, your
version took 212.64 seconds to get to a result (namely, 837799 with a
count of 524).
Here's how I'd code it:
import time
start=time.time()
max=0
for m in range(1,101):
n=m
count=0
while n>1:
if n%2: n=3*n+1
else: n//=2
count+=1
if count>max: max,num=count,m
if not m&16383: print("->",m,count)
print(num,max)
print(time.time()-start)
(You'll see the same timing information that I added to yours. It adds
immeasurably to the run-time, and gives some early idea of how it's
going.)
Running under Python 2.6, both your version and mine take about 90
seconds to run. But under Python 3.3, where (among other things)
range() yields values lazily, my version is significantly faster than
yours. BUT! Both versions, under 3.3, are significantly *slower* than
under 2.6. My first thought is that it's because Py2 has different
types for 'int' and 'long', and Py3 doesn't (effectively, everything's
a long), so I added an L suffix to every number and ran each of them
under 2.6 again. Seems that was the bulk of the difference, though not
all.
Pythonistas, does this count as a regression, or is Python
sufficiently "not a number crunching language" that we don't care?
(range = my code, as above; while = original version with a C-style
loop counter)
range py3: 171.07846403121948
while py3: 212.64104509353638
range py2: 87.859000206
while py2: 86.4059998989
range py2 longs: 190.530999899
while py2 longs: 176.12528
For comparison purposes, I also coded up the equivalent in Pike.
Pike's a very similar language to Python, but with a C-like syntax,
and certain optimizations - including, significantly to this exercise,
an integer type that sits within a machine word if it can (though
it'll happily go arbitrary precision when it's needed to). It pretends
to the programmer that it's a Py3-style "everything's an int", but
underneath, functions more like Py2 with separate short and long
types. The result: 22.649 seconds to reach the same conclusion.
How long did your BASIC version take, and how long did the Python
version on the same hardware?
This sort of pure number crunching isn't really where a modern high
level language shines. You'll come to *really* appreciate Python as
soon as you start working with huge arrays, dictionaries, etc. This is
a job for C, really.
ChrisA
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python 3.3 vs. MSDOS Basic
On Mon, Feb 18, 2013 at 12:13 PM, John Immarino wrote: > I coded a Python solution for Problem #14 on the Project Euler website. I was > very surprised to find that it took 107 sec. to run even though it's a pretty > simple program. I also coded an equivalent solution for the problem in the > old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec. > Is there a flaw in my coding, or is Python really this slow in this > particular application. MSDOS Basic usually runs at a snails pace compared to > Python. Well, I don't see anything that looks especially slow in that code, but the algorithm that you're using is not very efficient. I rewrote it using dynamic programming (details left as an exercise), which got the runtime down to about 4 seconds. -- http://mail.python.org/mailman/listinfo/python-list
Python 3.3 vs. MSDOS Basic
I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program. I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.) It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python. Below is the problem and the code: The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million. max=0 m=0 while m<=100: m+=1 count=0 n=m while n!=1: count+=1 if n%2==0: n=n//2 else: n=3*n+1 if count>max: max=count num=m print(num,max) -- http://mail.python.org/mailman/listinfo/python-list
