Programming Forums > Community Forums > Coder's Corner Lounge

Sane · Jan 2nd, 2008, 9:28 AM

Quote:

Originally Posted by The Dark

I did a fairly simple binary tree version in C++.

How did you keep the tree balanced? AVL tree rotations?

Quote:

Originally Posted by The Dark

The only addition I added was counters for each node on the number of nodes to the left of the current node (left meaning higher score).

I would assume that's only necessary, no? I had to do that too.

titaniumdecoy · Jan 2nd, 2008, 10:40 AM

Quote:

Originally Posted by The Dark

I did a fairly simple binary tree version in C++.

Binary trees have a worst-case insert time of $O(n)$ , so your solution most likely does not satisfy the problem requirements. (Unless you kept the tree balanced somehow, as Sane suggested.)

The Dark · Jan 2nd, 2008, 5:00 PM

Quote:

Originally Posted by titaniumdecoy

Binary trees have a worst-case insert time of $O(n)$ , so your solution most likely does not satisfy the problem requirements. (Unless you kept the tree balanced somehow, as Sane suggested.)

No, it was just a simple binary tree - I didn't see anything in the problem requirements in the PDF about O(nlogn), just Sane's assertion that a N^2 algorithm can't finish it. Clearly, that is not the case.

Sane · Jan 2nd, 2008, 5:07 PM

Really? Well there were a few other data files that I haven't bothered to upload. I guess the one I did upload wasn't the one that exploits the worst case. At least one of them must be able to hit it. The professor told me that $O(N^2)$ is a lose.

The Dark · Jan 2nd, 2008, 5:12 PM

Quote:

Originally Posted by Sane

Really? Well there were 10 other data file inputs. At least one of them must be able to hit your worst case, which must not be as easily exlpoitable in this case...

You might have mentioned them, or linked to them or something. I was just looking at the file you gave. I wasn't "exploiting" anything.

I am trying it out with a worst case - sorting the s5.txt file. So far it just crashes with a stack overflow, due to my simple recursive program structure.

Edit: I see you have changed your original post to be a bit less aggressive, thank you.

Sane · Jan 2nd, 2008, 5:16 PM

I was talking about the data file doing the exploiting. Not you exploiting anything. lol

But I'm pretty sure N^2 can't make it.

(Toggle Plain Text)

N = 100,000
N^2 = 10000000000
NlogN = 1660964
N^2/NlogN = 6021

So it's 6000 times slower with worst case. Doesn't seem likely that it can finish it in less than an hour or so.

The Dark · Jan 2nd, 2008, 5:26 PM

Is a sorted list the worst case? Here is my (crappy) output from the sorted version for a non-recursive binary tree:
Count : 100000
Sum : 100000
Average: 1
Time : 22106 (ms)
Depth : 99999

and for reverse sorted :

Count : 100000
Sum : 5000049999
Average: 50000.5
Time : 19110 (ms)
Depth : 99998

Obviously a bigger input file would get worse exponentially, but it still only took 22 seconds for 100,000 objects. The original PDF did say that that would be the maximum.

Sane · Jan 2nd, 2008, 5:30 PM

That's wild. I need to rethink why that is for a moment. Even the professor acknowledged that N^2 couldn't finish it.

Why is your sum different?

Edit: Nevermind. Of course it should be different.

Sane · Jan 2nd, 2008, 5:52 PM

I gave it a bit closer examination. I had forgotten that N grows as the tree progresses. So that has to be taken into account.

 Python Syntax (Toggle Plain Text) 
import math
def log2(x):return math.log(x,2)
 
n = 100000
 
n_sq = sum(xrange(1, n+1))
n_logn = sum(map(log2, xrange(1, n+1)))
 
print "N^2     %i"%(n_sq)
print "NlogN   %i"%(n_logn)
print "       x%i"%(n_sq/n_logn)
import math
def log2(x):return math.log(x,2)

n = 100000

n_sq = sum(xrange(1, n+1))
n_logn = sum(map(log2, xrange(1, n+1)))

print "N^2     %i"%(n_sq)
print "NlogN   %i"%(n_logn)
print "       x%i"%(n_sq/n_logn)

(Toggle Plain Text)

N^2     5000050000
NlogN   1516704
       x3296

That reduces the speed factor to 3,000. But that's still an hour, if the balanced tree takes one second. Of course Big Oh is imprecise, but that can't possibly make the difference between a factor of 3,000 and a factor of 20. What else do you think is going on here?

The Dark · Jan 2nd, 2008, 7:21 PM

I think, of the 1 second (1.1 with the non-recursive code), a significant portion is reading the file and writing the output.
I split the input and sort loops up and put the timer only counting the sort loop. I ended up with 670ms for the normal input and 18000 ms for the sorted input.

Note that the original input is far from best case, giving a binary tree depth of 8468. I think that they probably designed it that way.

Jan 2nd, 2008, 5:07 PM	#24
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,869 Rep Power: 5	Re: Challenging Programming Problem - "Pinball Ranking" Really? Well there were a few other data files that I haven't bothered to upload. I guess the one I did upload wasn't the one that exploits the worst case. At least one of them must be able to hit it. The professor told me that $O(N^2)$ is a lose.

Jan 2nd, 2008, 5:16 PM	#26
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,869 Rep Power: 5	Re: Challenging Programming Problem - "Pinball Ranking" I was talking about the data file doing the exploiting. Not you exploiting anything. lol But I'm pretty sure N^2 can't make it. (Toggle Plain Text) N = 100,000 N^2 = 10000000000 NlogN = 1660964 N^2/NlogN = 6021 N = 100,000 N^2 = 10000000000 NlogN = 1660964 N^2/NlogN = 6021 So it's 6000 times slower with worst case. Doesn't seem likely that it can finish it in less than an hour or so.

Jan 2nd, 2008, 5:26 PM	#27
The Dark Expert Programmer Join Date: Jun 2005 Posts: 850 Rep Power: 4	Re: Challenging Programming Problem - "Pinball Ranking" Is a sorted list the worst case? Here is my (crappy) output from the sorted version for a non-recursive binary tree: Count : 100000 Sum : 100000 Average: 1 Time : 22106 (ms) Depth : 99999 and for reverse sorted : Count : 100000 Sum : 5000049999 Average: 50000.5 Time : 19110 (ms) Depth : 99998 Obviously a bigger input file would get worse exponentially, but it still only took 22 seconds for 100,000 objects. The original PDF did say that that would be the maximum.

Jan 2nd, 2008, 5:30 PM	#28
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,869 Rep Power: 5	Re: Challenging Programming Problem - "Pinball Ranking" That's wild. I need to rethink why that is for a moment. Even the professor acknowledged that N^2 couldn't finish it. Why is your sum different? Edit: Nevermind. Of course it should be different. Last edited by Sane; Jan 2nd, 2008 at 5:45 PM.

Jan 2nd, 2008, 5:52 PM	#29
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,869 Rep Power: 5	Re: Challenging Programming Problem - "Pinball Ranking" I gave it a bit closer examination. I had forgotten that N grows as the tree progresses. So that has to be taken into account. Python Syntax (Toggle Plain Text) import math def log2(x):return math.log(x,2) n = 100000 n_sq = sum(xrange(1, n+1)) n_logn = sum(map(log2, xrange(1, n+1))) print "N^2 %i"%(n_sq) print "NlogN %i"%(n_logn) print " x%i"%(n_sq/n_logn) import math def log2(x):return math.log(x,2) n = 100000 n_sq = sum(xrange(1, n+1)) n_logn = sum(map(log2, xrange(1, n+1))) print "N^2 %i"%(n_sq) print "NlogN %i"%(n_logn) print " x%i"%(n_sq/n_logn) (Toggle Plain Text) N^2 5000050000 NlogN 1516704 x3296 N^2 5000050000 NlogN 1516704 x3296 That reduces the speed factor to 3,000. But that's still an hour, if the balanced tree takes one second. Of course Big Oh is imprecise, but that can't possibly make the difference between a factor of 3,000 and a factor of 20. What else do you think is going on here? Last edited by Sane; Jan 2nd, 2008 at 6:14 PM.

Jan 2nd, 2008, 7:21 PM	#30
The Dark Expert Programmer Join Date: Jun 2005 Posts: 850 Rep Power: 4	Re: Challenging Programming Problem - "Pinball Ranking" I think, of the 1 second (1.1 with the non-recursive code), a significant portion is reading the file and writing the output. I split the input and sort loops up and put the timer only counting the sort loop. I ended up with 670ms for the normal input and 18000 ms for the sorted input. Note that the original input is far from best case, giving a binary tree depth of 8468. I think that they probably designed it that way.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
programming or virus problem	mukul	C++	3	Sep 30th, 2007 3:53 AM
need advice on problem with wireless network programming	dark_omen	C++	2	Mar 13th, 2007 8:46 PM
programming problem	mcl1008	Java	6	Nov 6th, 2006 1:59 PM
C programming problem	mmmm_strawberries	C++	3	Mar 1st, 2005 3:48 PM
SPIM Assembly Programming Simulation Problem	tsgrimey	Assembly	1	Feb 9th, 2005 2:21 AM

Programming Forums > Community Forums > Coder's Corner Lounge

Challenging Programming Problem - "Pinball Ranking"