SPOJ in Scala

Leolinus 2012-12-11 17:13:45 UTC #1

Any Scala programmers here?

I've been trying to solve some of the introductory problems and I've been enjoying my short and readable functional solutions but for some reason they don't work.

I'm getting time limit exceeded and memory usage explodes to 207/208MB which is just ridiculous.

For example.
I tried solving the FCTRL problem hoping it would pass.
It passed but the runtime was almost 5 seconds.

I can tell you that the code is 10 lines long and the complexity is O(log(N)) where base of the logarithm is 5.

For numbers as huge as 1,000,000,000 it should take only 13 steps to finish the algorithm.
I tried to test it on my PC with 100,000 billions and it took 1.3s.
100,000 * log5(1,000,000,000) = 1287699 steps --> each number takes 1microsecond to process
time = 1287699 * 1microsecond = 1.287699s
I do not believe the test case has so many billions in it.

Tried solving PRIME1 and I'm getting TLE too.
When on my PC I'm able to solve the largest test case 10 times in 3 seconds.
I doubt the test cases provided are always the largest ones.

Anyone has any idea what could be wrong? (output functions too slow?)
I do not believe my solutions are inefficient.

br_ishi 2013-02-24 17:09:03 UTC #2

Hi,

I'm trying to learn Scala and thought that using SPOJ as a source of 'practical' examples could be helpful.

I must say, I'm a bit disappointed. Surely, we are not trying to establish which language generates the least memory footprint or where we can create faster code (obviously it's going to be assembler).

I'm getting similar results (i.e. min. memory consumption is 207M and ridiculous execution time, often leading to TLE).

I did some checking and managed to optimise my IO a fair bit. Just so you know (perhaps it could be useful to other Scala SPOJers):
[ul]
[li]readInt() performs resonably good (on my PC I was able to read 500k lines and parse them as ints in 130ms)[/li]
[li]most problems are caused by println: printing the same 500k lines took about 4.5s. However, if you do

the time drops to about 180ms[/li][/ul]

All in all I managed to read 500k ints and write them back in about 280ms, which isn't bad. The same in C takes about 130ms, so I think 300ms is 'good enough' for Scala.

Alas! I still get TLE.

I started investigating further by cutting out the functionalities of my code. It turns out that:

just reading and writing took 1.66s (this obviously generated 'wrong answer', but I did it just to check how bit an overhead I/O is)
writing loop counter took 1.41s
only reading data took 1.24s

I removed everything (just empty main()) and it still takes 1s and still consumes 207M. Probably, the mem is just 'normal' jvm footprint, but 1s for starting app which does nothing seems to indicate some kind of a problem...

I have the following suggestions:

please increase both mem and time for jvm languages. If empty main() takes 1s and consumes over 200M, I don't see how to avoid exceeding mem or time for some of the problems. Better yet, just subtract the 1s and 200M --- this seems to be baseline consumed by the jvm itself
add some scaling factor... obviously, the speed of languages isn't equal... it should be fairly easy to estimate... based on the existing results if nothing else

I think the tasks, where IO time has such high impact on the result aren't really well defined. Surely, it is possible to increase the complexity instead of the volume of data. Say, instead of processing 10 times more data, just multiply them by 10. This would test the algorithm much better.

Leolinus 2013-05-21 14:29:10 UTC #3

Any updates on this?

As much as I liked the optimizations in the post above, br_ishi still said these weren't enough.

johnnynonsense 2014-01-24 11:49:39 UTC #4

I was excited to find that this site supported Scala programming, but disappointed that I could not even get through the PRIME1 test without the time being exceeded. The time seems rather short - is it including compilation time too? On my computer, the code for this problem (and most problems) takes longer to compile that it takes to execute. I also found it rather strange how the PRIME1 problem was defined - it had us calculate prime numbers in batches of up to 100000, and then has us PRINT THEM ALL OUT!! I would assume it's comparing every single one of them with an answer that has been saved in a file. There is no reason to have exercises like this. If you want to test our abilities to print, then have us print a small number of values - there is no need to repeat the same print statement thousands of times. If you want to test our abilities to generate 100000 primes, first do some sort of data reduction operation like they do on projecteuler.net. Over there, they would do something like have us add up the 100000 primes, and report just the sum.

I would recommend that for non-competitive problems, you permit us to simply enter the program output, rather than enter the source code for you to run. Have a look at projecteuler.net for a good way to do this. Over there, the answer is usually just a single word, and their system works! People will sometimes submit solutions to programs that take minutes to run on their home computers, but it doesn't matter how long it takes. They focus on number theory problems, but after a while it begins to get a little bit boring. And that is what brought me to look for alternatives such as SPOJ.

johnnynonsense 2014-02-03 13:28:29 UTC #5

Okay, I was finally able able to solve PRIME1 in Scala. My execution time was just under 5 seconds. It takes about 3 seconds for me to solve it on my home PC using worst-case input, and using I/O redirection for input and output. To get it to run in under 5 seconds at SPOJ, I tried to minimize the number of println statements. To do this, I combined the output for each test into one long string, separating the string for each line by '\n' before sending the whole thing to println. (use mkString("\n") on a list holding the output lines). I'm thinking the JVM languages have very slow output to stdout. I did nothing to optimize input - it might help if I can read the whole thing in with one statement, but I'm not sure if it can be done in Scala (I'm a beginner with scala).

kuszi 2014-02-08 12:40:27 UTC #6

Hi,

This issue (incomparable speed for different languages) has been discussed before and nothing constructive has been decided.
Scala is one of the extreme examples.

As for now, my advice is to select problems for Scala with non strict time limits.