I was trying to solve 618E - Robot Arm from the last contest using 15683254. But (strangely?) I suffer a MLE on (pre)test 5. I thought I was using only static memory (each of the 3 arrays has fixed size), so any memory limit exceed error must occur right on the first test, if it occurs later.
I'm new to Java, so can anyone explain why I'm getting a MLE on #5? Where is the extra memory I'm using being allocated?
Thanks in advance!
I think it's because of object headers: each object stores some "header" (size may vary, something like 12 bytes, afaik) together with fields. Plus,
Cmplx[] ais not the same asCmplx a[]orvector<Cmplx> ain C++, it's more likeCmplx* a[]— array of pointers to objects.Not so sure how all these add together to occupy more than 256 MB of memory, though. Maybe it's garbage collector who does not do his job properly because default run parameter is to worry about fitting into 512MB of memory, not 256MB. If that's correct, then each operation with complex number creates another object and does not get rid of the previous one and memory leaks quickly.
Thanks for the reply. :)
I tried changing
Complx[] StoComplx S[]and also changed the other arrays : 15689135 . Still MLE remains. :(Is there any way to change the default run parameter to make the garbage collector fit into 256 MB?
According to my calculations. I have (in effect) 2 arrays of size 8*4*10^5, each element taking up 8+8+12 = 28 for the two doubles and overhead. So total memory ~ 179 MB.
There is no difference between
Complx[] SandComplx S[]. There is no way in Java to allocate an "in-place" array of objects.Have you measured memory footprint on maxtest locally? If yes, and it's over 256, try some memory profilers. Or simple PM some top coder who uses Java :)
Can you try add static to Cmplx declaration?
Wow, that change made it Accepted : 15715799 :o :D
Thanks! :)
BTW : Why was
staticso magical?You may read about that here. Briefly: each instance of non-static nested class holds an additional reference to the object of outer class which 'created' it. Additional pointer. Static nested classes do not do that, they're not tied to a specific 'outer' object.