Re: To count number of quadruplets with sum = 0

> FWIW, the original program can also be compiled with Shed Skin (http:// > mark.dufour.googlepages.com), an experimental (static-)Python-to-C++ > compiler, resulting in a speedup of about 8 times for a single test > with 500 tuples. here's a slightly modified version that works with > Shed Skin C

Re: To count number of quadruplets with sum = 0

"n00m" <[EMAIL PROTECTED]> writes: > my dial-up line's too slow for downloading 4mb of shedskin-0.0.20.exe Don't worry! We can email it to you. :-D -- Jorge Godoy <[EMAIL PROTECTED]> -- http://mail.python.org/mailman/listinfo/python-list

Re: To count number of quadruplets with sum = 0

>>> RESTART === >>> 0 30.4740708665 secs (Anton Vredegoor) >>> RESTART === >>> 0 30.4132625795 secs (Anton Vredegoor) >>> RESTART === >>> 0 30.4812175849 secs (Anton Vredegoor) >>> +

Re: To count number of quadruplets with sum = 0

my dial-up line's too slow for downloading 4mb of shedskin-0.0.20.exe -- http://mail.python.org/mailman/listinfo/python-list

Re: To count number of quadruplets with sum = 0

bearophileH! I gave to your "oil" svrl runs ("z in dict" instd of "dict.has_key" saved only ~0.4 sec). The result is (and I'm completely lost in all these *optimizations* :)): >>> RESTART === >>> 0 34.78 secs (bearophileH) >>> RES

Re: To count number of quadruplets with sum = 0

Mark Dufour: > FWIW, the original program can also be compiled with Shed Skin (http:// > mark.dufour.googlepages.com), an experimental (static-)Python-to-C++ > compiler, resulting in a speedup of about 8 times for a single test > with 500 tuples. If we want to play, then this is a literal translat

Re: To count number of quadruplets with sum = 0

Paul Rubin wrote: > "n00m" <[EMAIL PROTECTED]> writes: > > Two first outputs is of above (your) code; next two - of my code: > > Yeah, I see now that we both used the same algorithm. At first glance > I thought you had done something much slower. The 10 second limit > they gave looks like they i

Re: To count number of quadruplets with sum = 0

[EMAIL PROTECTED] writes: > for x in e: > for y in r: > if -x-y in h: > sch += h[-x-y] I wonder whether g = h.get for x in e: for y in r: if -x-y in h: sch += g(-x-y, 0) might be a little bit faster. Also, -x-y

Re: To count number of quadruplets with sum = 0

n00m: > i have no NumPy to test it... > without Psyco Anton's code is the winner: ~48sec vs ~58sec of my code > But with Psyco my runtime is ~28sec; Anton's - ~30sec (PC: 1.6 ghz, > 512 mb) > Not so bad.. keeping in mind that 256000 billions quadruplets to > check :) I have oiled it a bit, you can

Re: To count number of quadruplets with sum = 0

i have no NumPy to test it... without Psyco Anton's code is the winner: ~48sec vs ~58sec of my code But with Psyco my runtime is ~28sec; Anton's - ~30sec (PC: 1.6 ghz, 512 mb) Not so bad.. keeping in mind that 256000 billions quadruplets to check :) import psyco, time psyco.full() t = time.clock(

Re: To count number of quadruplets with sum = 0

My attempt uses a different approach: create two sorted arrays, n^2 elements each; and then iterate over them looking for matching elements (only one pass is required). I managed to get 58,2250612857 s on my 1,7 MHz machine. It requires numpy for decent performance, though. import numpy import tim

Re: To count number of quadruplets with sum = 0

Steven Bethard <[EMAIL PROTECTED]> writes: > > According to a post by Raymond Hettinger it's faster to use that > > iterator instead of `int`. > Yep. It's because the .next() method takes no arguments, while int() > takes varargs because you can do:: ... Heh, good point. Might be worth putting a

Re: To count number of quadruplets with sum = 0

Marc 'BlackJack' Rintsch wrote: > In <[EMAIL PROTECTED]>, Paul Rubin wrote: > >> "n00m" <[EMAIL PROTECTED]> writes: >>> h = collections.defaultdict(itertools.repeat(0).next) >> Something wrong with >>h = collections.defaultdict(int) >> ? > > According to a post by Raymond Hettinger it's

Re: To count number of quadruplets with sum = 0

n00m wrote: > 62.5030784639 Maybe this one could save a few seconds, it works best when there are multiple occurrences of the same value. A. from time import time def freq(L): D = {} for x in L: D[x] = D.get(x,0)+1 return D def test(): t = time() f = fil

Re: To count number of quadruplets with sum = 0

In <[EMAIL PROTECTED]>, Paul Rubin wrote: > "n00m" <[EMAIL PROTECTED]> writes: >> h = collections.defaultdict(itertools.repeat(0).next) > > Something wrong with >h = collections.defaultdict(int) > ? According to a post by Raymond Hettinger it's faster to use that iterator instead of `in

Re: To count number of quadruplets with sum = 0

On Mar 16, 12:49 am, "n00m" <[EMAIL PROTECTED]> wrote: > for o in range(int(f.readline())): > row = map(int, f.readline().split()) > q.append(row[0]) > w.append(row[1]) > e.append(row[2]) > r.append(row[3]) Does this help at all in reading in your data? numlines = f.readline() rows = [

Re: To count number of quadruplets with sum = 0

"n00m" <[EMAIL PROTECTED]> writes: > http://rapidshare.com/files/21267938/m1000.txt > http://rapidshare.com/files/21268386/m4000.txt I get 33190970 for the first set and 0 for the second set. The first set only makes 38853 distinct dictionary entries, I guess because the numbers are all fairly sm

Re: To count number of quadruplets with sum = 0

For those who interested, my test input files: http://rapidshare.com/files/21267938/m1000.txt http://rapidshare.com/files/21268386/m4000.txt -- http://mail.python.org/mailman/listinfo/python-list

Re: To count number of quadruplets with sum = 0

Steve, imo strangely enough but your suggestion to replace "if...: else:..." with x_y = x + y h[x_y] = h.get(x_y, 1) s=l=o=w=e=d the thing by ~1 sec. -- http://mail.python.org/mailman/listinfo/python-list

Re: To count number of quadruplets with sum = 0

n00m wrote: > http://www.spoj.pl/problems/SUMFOUR/ > > 3 > 0 0 0 0 > 0 0 0 0 > -1 -1 1 1 > Answer for this input data is 33. > > My solution for the problem is > == > > import time > t = time.clock() > > q,w,e,r,sch,h = [],[],[

Re: To count number of quadruplets with sum = 0

"n00m" <[EMAIL PROTECTED]> writes: > Two first outputs is of above (your) code; next two - of my code: Yeah, I see now that we both used the same algorithm. At first glance I thought you had done something much slower. The 10 second limit they gave looks like they intended to do it about this wa

Re: To count number of quadruplets with sum = 0

"n00m" <[EMAIL PROTECTED]> writes: > h = collections.defaultdict(itertools.repeat(0).next) Something wrong with h = collections.defaultdict(int) ? > for x in e: > for y in r: > sch += h[-(x + y)] That scares me a little: I think it makes a new entry in h, for the cases where -(x+y)

Re: To count number of quadruplets with sum = 0

Paul, import time t = time.clock() f = open("D:/m4000.txt","rt") npairs = int(f.readline()) quads = [map(int, f.readline().split()) for i in xrange(npairs)] f.close() da = {} for p in quads: for q in quads: z = p[2] + q[3] da[z] = da.get(z,0) + 1 print sum(da.get(-(p[0]+q[1]),

Re: To count number of quadruplets with sum = 0

Steven, I ran this: import time, collections, itertools t = time.clock() q,w,e,r,sch = [],[],[],[],0 h = collections.defaultdict(itertools.repeat(0).next) f = open("D:/m4000.txt","rt") for o in range(int(f.readline())): row = map(int, f.readline().split()) q.append(row[0]) w.append(row[1

Re: To count number of quadruplets with sum = 0

Paul Rubin writes: > print sum([da.get(-(p[0]+q[1]), 0) for p in quads for q in quads]) The above should say: print sum(da.get(-(p[0]+q[1]), 0) for p in quads for q in quads) I had to use a listcomp instead of a genexp for testing, since I'm still using python 2.3, a

Re: To count number of quadruplets with sum = 0

"n00m" <[EMAIL PROTECTED]> writes: > http://www.spoj.pl/problems/SUMFOUR/ > 3 > 0 0 0 0 > 0 0 0 0 > -1 -1 1 1 > Answer for this input data is 33. f = open('input1') npairs = int(f.readline()) quads = [map(int, f.readline().split()) for i in xrange(npairs)] assert len(quads) == npairs da = {} fo

Re: To count number of quadruplets with sum = 0

n00m wrote: > http://www.spoj.pl/problems/SUMFOUR/ > > 3 > 0 0 0 0 > 0 0 0 0 > -1 -1 1 1 > Answer for this input data is 33. > > My solution for the problem is > == > > import time > t = time.clock() > > q,w,e,r,sch,h = [],[],[

Re: To count number of quadruplets with sum = 0

Your suggestion speeded it up 1.5 times (on my 4000 test input rows)! -- http://mail.python.org/mailman/listinfo/python-list

Re: To count number of quadruplets with sum = 0

> Any ideas to speed it up say 10 times? Or the problem only for C-like > langs? I dout this will speed it up by a factor of 10, but in your solution you are mapping the values in the input file to longs. The problem statement states that the maximum value for any of the numbers is 2**28. I assume

To count number of quadruplets with sum = 0

http://www.spoj.pl/problems/SUMFOUR/ 3 0 0 0 0 0 0 0 0 -1 -1 1 1 Answer for this input data is 33. My solution for the problem is == import time t = time.clock() q,w,e,r,sch,h = [],[],[],[],0,{} f = open("D:/m4000.txt","rt")