[Cs5500] Making HSR playground scalable

Sat Dec 3 20:17:22 EST 2011

Professor,

Sure. I can do that.

On Sat, Dec 3, 2011 at 4:39 PM, Karl Lieberherr <lieber at ccs.neu.edu> wrote:

> 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
>>
>>
>
>
> _______________________________________________
> Cs5500 mailing list
> Cs5500 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs5500
>
>

-- 
 Thanks
- Madhu
-------------- next part --------------
HTML attachment scrubbed and removed