hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Code optimization
Goto page Previous  1, 2, 3, 4  Next
 
Reply to topic    hacker.org Forum Index » Crossflip View previous topic
View next topic
Code optimization
Author Message
AMindForeverVoyaging
Forum Admin


Joined: 28 May 2011
Posts: 473
Location: Germany

Post Reply with quote
compudemon wrote:

so i converted all my code to c++
created my own classes for bigints, stringbuffer, stringbufferarray
as any true hacker might do


I'm not sure why anyone would want to write such classes from scratch, when there are perfectly good existing libraries for all of these purposes out there. You are using other people's code with e.g. Java's BigInteger class, so why not do the same when coding in C++?

Anyway...
Boost
NTL
C++ Big Integer Library
...just to give a few examples.
Sat Sep 03, 2011 8:38 am View user's profile Send private message
compudemon



Joined: 13 Aug 2011
Posts: 33

Post find it and learn it v.s. make your own Reply with quote
AMindForeverVoyaging wrote:
compudemon wrote:

so i converted all my code to c++
created my own classes for bigints, stringbuffer, stringbufferarray
as any true hacker might do


I'm not sure why anyone would want to write such classes from scratch, when there are perfectly good existing libraries for all of these purposes out there. You are using other people's code with e.g. Java's BigInteger class, so why not do the same when coding in C++?

Anyway...
Boost
NTL
C++ Big Integer Library
...just to give a few examples.


i am aware something of biginteger exists in .net C++ and i know about boost as well
the thing is speed making your own classes v.s. speed finding and learning how to use existing ones. take the boost library i actually did look through the library hunting for a bigint class, i gave up even though i suspected one existed. i think i may have found it but then i would need to read the docs, look at use examples... considering i only needed a few one line fucntions it made more sense to roll my own.
Sat Sep 03, 2011 7:13 pm View user's profile Send private message
papa



Joined: 29 Oct 2008
Posts: 13
Location: Germany

Post Reply with quote
Optimizing the O(n^3) Gaussian Elimination e.g. by grouping booleans to integers took me to level ~400. Then I redesigned my algorithm. Now it has less than O(n^2) complexity and solves even the last levels in less than 20 seconds using Java without any optimization at all.
Algorithm beats implementation.
Mon Sep 05, 2011 11:36 pm View user's profile Send private message
bsguedes



Joined: 24 Feb 2009
Posts: 103
Location: Porto Alegre

Post Reply with quote
O(n^2) ? That's interesting.

My O(n^3) took approximately 40 minutes in the last level.
Tue Sep 06, 2011 5:27 am View user's profile Send private message
compudemon



Joined: 13 Aug 2011
Posts: 33

Post Reply with quote
guassian would be N^2 time with packed bools if each row could fit into an int. naturally its still an N^3 problem just done parallel. Am I correct in guessing that some form of algebra, letting the highly regular nature of the N unknowns trim down to a simplified matrix with (N ^ (2/3)) unknowns then guassian done on that?
Tue Sep 06, 2011 11:34 pm View user's profile Send private message
MyNameIsAlreadyTaken



Joined: 17 Oct 2010
Posts: 31
Location: Germany

Post Reply with quote
I'd rather say he uses the properties the matrix has [symmetric, sparse and Elements in Gf(2)].
Wed Sep 07, 2011 11:10 am View user's profile Send private message
dangermouse



Joined: 05 Jun 2011
Posts: 89
Location: deep space computing AG

Post Reply with quote
For the o(n^3) algo, i have a special approach...

the approach leads to fast code, but for some reason the solutions computed are sometimes wrong, especially for the higher levels... i worked hard to find the mistake in the freepascal code but can't find it. the first level where the approach fails is level 99.

I observerd that in my implementation, the rank of the matrix is different from the productive code i am using, and so the number of pivotal elements. But maybe i have some linear dependent rows which still need to be spotted...

Is the approach theoretically correct, or is there something fundamental I am missing?


Last edited by dangermouse on Thu May 03, 2012 5:31 am; edited 1 time in total
Fri Feb 17, 2012 9:08 am View user's profile Send private message Visit poster's website
dangermouse



Joined: 05 Jun 2011
Posts: 89
Location: deep space computing AG

Post Reply with quote
Never mind, i found the mistake. The author of the algorithm would turn into his grave, if he would see how I did pivoting when the linear system is undetermined... Still, with such a conceptual mistake i made it quite high...
No wonder i got bad grades in numerical parallel computing Very Happy


Last edited by dangermouse on Thu May 03, 2012 5:38 am; edited 1 time in total
Fri Feb 17, 2012 10:20 am View user's profile Send private message Visit poster's website
guga



Joined: 02 Mar 2012
Posts: 17

Post Reply with quote
@dangermouse:
I have the exact same problem you described. Only that my pivoting sucks already on lvl 83. How did you get rid of that? Was it just changing the pivoting? Or did you have to do a totally different approach? I tried some more or less clever ways to find good pivots, but they all failed...
Mon Apr 23, 2012 2:33 pm View user's profile Send private message
dangermouse



Joined: 05 Jun 2011
Posts: 89
Location: deep space computing AG

Post Reply with quote
hey guga,

my problem was: i was not handling correctly the system of linear equations when it was undetermined!

My crucial error was: if i could not find a pivot in a column, then i did startx=startx+1,starty=starty+1, but i should have done only startx=startx+1. So, do not move along diagonal when you do not find a pivot, just go one right when looking for the next pivot in the next column.

btw this error is also in the linalgebra book i was using at university, and now i remember a good friend of mine pointing me at this error, 13 years ago Very Happy
Mon Apr 23, 2012 3:03 pm View user's profile Send private message Visit poster's website
guga



Joined: 02 Mar 2012
Posts: 17

Post Reply with quote
BÄM! My personal Hero of the day Smile
Since at my implementation startx and starty are the same, I'm just adding a row into the matrix with the diagonal element. That's also working.
Now I only have to improve my memory consumption. lvl 272 needs more than my 4GiB ram. Seems like the data structure I'm using has _way_ too much overhead...
Wed Apr 25, 2012 8:23 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
I am using java, BigInteger.
setBit while creating equations and testBit and xor while solving.
setBit, toString and substring to retrieve the solution.

Works rather fine ... still running on 294 requires under 30s.
BTW: My compose time (creating equations) on level 350 is twice as big as solving time ... with total around one minute.

--- edit ---
OK, I have changed the create equations part to process buttons in horizontal blocks "together" and than buttons in vertical blocks together. This speeded the compose time to about one tenth of solving time.
So now both parts together require about one third of original time.

BTW, now I use subtraction as well (and of course or as well).

--- edit ---
Now on around 450 it takes around 3 minutes per level.

--- edit ---
Level 522 seems to be roughly same size as 521, but I have reached Out of memory there ... seems recoding my own "BigInteger" will be needed (BTW solution times till it were under 5 mins in most cases).

--- edit ---
there is Xmx switch which could help, let us see for how long ...

--- edit ---
Next problem is on level 550 ... web challenge ... the page was downloaded just partially missing end of the board. OK accept encodding gzip helped with this problem.

--- edit ---
Problems with memory have returned on level 555 ... I am afraid I am almost on limits of easy implementation.

--- edit ---
Hmm, tonight it stopped by not downloading 568 level, even when repeat works fine. Sad
Maximal solving times are under 25 minutes.

--- edit ---
I have decided to change the algorithm (I was "almost" computing inverse matrix originally) I have decided to switch to diagonalizacion instead of triangularizacion (with square of "inverse") and the algorithm slowed down rapidly. So I changed it back to triangularizacion, but without "the square of inverse", but I speeded up the values retrieval from the triangle without further changing the matrix.
Seems this is faster than the original. ... Making small change to a BigInteger is indead very slow and implementing arrrays of longs must be much faster. But unless the boards would expand much more faster in levels above 575 the BigIntegers would be good enough ... now the solving time is less than 10 minutes per level.

--- edit ---
OK, I have decided to code matrix based on longs to replace BigInteger. I made a lot of (of 1 bugs), but comparision with results of previous implementations helped to debug them rather quickly ...
Now the running time should be O(n^3/64) compared to O(n^4/64) caused by BigInteger copying.
The speedup is visible even on low levels. (Levels around 300 under 3s per level)

--- edit ---
Hmm, its just about 5 times faster, and I got to out of Heap Space again. ... I reallocate the matrix for each level, but ... OK, let us see if it was caused by running too many levels in a row ... OK, maybe its a problem of long[][] alocation in one chunk instead of several...


Last edited by Hippo on Fri Oct 24, 2014 6:50 pm; edited 8 times in total
Mon Oct 20, 2014 12:47 pm View user's profile Send private message
CodeX



Joined: 17 Oct 2008
Posts: 350

Post Reply with quote
Try adding a "Accept-Encoding: gzip" header to your request
Wed Oct 22, 2014 4:43 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
CodeX wrote:
Try adding a "Accept-Encoding: gzip" header to your request


Thanks, seems it would work.
Wed Oct 22, 2014 6:36 pm View user's profile Send private message
Isaev



Joined: 16 Dec 2008
Posts: 34
Location: Germany

Post Reply with quote
How we will apply the Gaussian Elimination for example to such level?
11#0
#011
01#0
(#-wall)
Thu Jun 09, 2016 9:09 pm View user's profile Send private message ICQ Number
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Crossflip All times are GMT
Goto page Previous  1, 2, 3, 4  Next
Page 3 of 4

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.