[Cs5500] Making HSR playground scalable

Sat Dec 3 16:39:14 EST 2011

Hi Madhu:

David and also Matthew Strax-Haber pointed out a weekness in our HSR
playground which I and the testing by Tuba and Nanda did not catch: valid
is inefficient.

Ravi can retrieve David's code from Blackboard and give it to you. Please
can you check it and
put this improvement into the playground on SourceForge.

-- Karl

---------- Forwarded message ----------
From: Karl Lieberherr <lieber at ccs.neu.edu>
Date: Sat, Dec 3, 2011 at 3:37 PM
Subject: Re: [Cs4800] Reg: HSR Counting Tournament
To: David Richards <dirich at ccs.neu.edu>
Cc: Ravishankar Rajagopal <rajagopal.r at husky.neu.edu>, CS4800 Mailing List <
cs4800 at lists.ccs.neu.edu>

Hi David:

Thank you for giving the precise reason why our HSR playground does not
scale for large ladders.
This example shows how important it is to analyze the running time of our
algorithms.

Our decision trees are full binary trees with n leaves. For each leaf we
have an O(n) operation
of deleting the leaf from the ArrayList. Which gives a cost of O(n^2). We
can have a much faster algorithm for checking whether each leaf appears
exactly once. Use an array[0,n-1] of boolean called used. Initially, all
entries are false. If we find leaf k, we set used[k] to true after checking
that it was not true before. At the end of the tree traversal through 2*n+1
nodes we check that the array contains all true. This improved algorithm is
O(n) because we have n array lookups which are constant time.

We will improve the playground definition so that it scales for large
ladders.

Moral of the story: Check the API of the methods you use and analyze the
running time
of the algorithm implementation. Try improving it?

-- Karl

On Thu, Dec 1, 2011 at 10:56 PM, David Richards <dirich at ccs.neu.edu> wrote:

> One quick problem I noticed with running a 100,000 rung tournament is that
> the valid function for the HSR playground
> slows down pretty drastically.  While it was taking me a fraction of a
> second to produce a 100,000 rung solution, it was
> taking multiple seconds to compute its validity.  When I ran a 1,000,000
> rung solution, it took about 5 minutes after which
> I gave up and terminated the program.
>
> The problem behind this seems to be in the use of ArrayLists.  One of the
> things valid does is produce an ArrayList of
> Integers from 0 to n-1.  It then iterates through the solution tree and
> removes the question of each node from the ArrayList.
> At the end, it checks to make sure that the list is empty.  The problem
> with this approach is that removing an item from an
> ArrayList is actually a potentially long running operation since it needs
> to shift every element in the list after the element
> that was removed.  I did some refactoring and implemented essentially the
> same solution using a stack, which is possible
> as long as we're careful to traverse the solution in the correct order
> (left, current node, right).  Since stacks are designed
> to quickly pop the top element, the runtime was reduced to essentially
> linear in respect to the size of the solution.
>
> -David
>
>
> On Dec 1, 2011, at 10:18 PM, Karl Lieberherr wrote:
>
> > Hi Nimrod:
> >
> > thank you for running the tournament. I have not been told yet what went
> wrong with the 100 000 tournament.
> > There is a danger of a stack overflow happening. A larger stack size for
> the admin and avatars might do the trick.
> >
> > I am at a loss why this was not done before. I double checked this
> morning with the graduate class and a testing team was working on it.
> >
> > -- Karl
> >
> > On Thu, Dec 1, 2011 at 10:10 PM, Nimrod E. Drizlikh <nimdriz at ccs.neu.edu>
> wrote:
> > I spent a decent chunk of time testing for 100,000 and making sure it
> would work. If anyone else is in the same boat and wants to test their
> avatar in a 100,000 rung competition I am running one on tank.ccs.neu.edu.
> It starts at 10:37pm. The tournament id is 34. I can't promise this but I
> should also have the babyavatar running in the tournament for comparison.
> >
> > Thanks,
> > Nimrod Drizlikh
> > ----- Original Message -----
> > From: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>
> > To: "Dennis Zografos" <dzog at ccs.neu.edu>
> > Cc: cs4800 at lists.ccs.neu.edu
> > Sent: Thursday, December 1, 2011 9:59:44 PM GMT -05:00 US/Canada Eastern
> > Subject: Re: [Cs4800] Reg: HSR Counting Tournament
> >
> >
> > No unfortunately at this point, n = 100000 setting has not been tested
> enough and therefore this will be a maxN: 1000 tournament.
> >
> > Also i request all of you to signup again at tvtennis for the MMG.
> Thanks.
> >
> > Regards,
> > Ravi Rajagopal
> >
> >
> > On Thu, Dec 1, 2011 at 9:46 PM, Dennis Zografos < dzog at ccs.neu.edu >
> wrote:
> >
> >
> > the config file for that tournament has
> >
> > hsr_config[maxN: 1000 ]
> >
> > isn't this supposed to be an n=100000 tournament?
> >
> >
> > ----- "Ravishankar Rajagopal" < rajagopal.r at husky.neu.edu > wrote:
> >
> > > Hi All,
> > >
> > > The HSR Counting tournament has been scheduled at 10.30 PM tonight at
> > > seawolf.ccs.neu.edu . I will approve signups every 5 minutes. You can
> >
> > > use the same version of the code - 76 - as you have used for MMG.
> > >
> > > Regards,
> > > Ravi Rajagopal
> > >
> >
> >
> >
> > > _______________________________________________
> > > Cs4800 mailing list
> > > Cs4800 at lists.ccs.neu.edu
> > > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
>
-------------- next part --------------
HTML attachment scrubbed and removed