Welcome to the Monastery | |
PerlMonks |
Adding a lot of small integersby kappa (Chaplain) |
on Jan 09, 2010 at 14:55 UTC ( [id://816485]=perlquestion: print w/replies, xml ) | Need Help?? |
kappa has asked for the wisdom of the Perl Monks concerning the following question: Update down there Good day, fellow monks. My question is more of academic interest than practical. Here's a simple task from an old CS collegiate contest: Sums in a Triangle. It's definitely NOT of the type Perl excels at but still I decided to give it a try. (Actually, my main motivation is that a working Python solution exists!) My C solution works fast and passed the online judge, it's O(n^2) and very efficient. But the best Perl code I came up with requires at least 6 seconds in the worst case on my fairly powerful Core 2 Duo 2.66Ghz box. It uses the same algorithm I used in C. If anyone feels like playing with it, I'd be very interested in results. My C code (before compressing into 256 chars which is not interesting): My best Perl code (strict was removed):
The worst test case I'm banging my head against: http://dl.dropbox.com/u/360558/input_big.txt.gz (will decompress to 14Mb) (Probably, my first reaction to such a question would be something like: "Wow, compiled C code is faster than Perl! Thank you, Captain Obvious!" I would definitely not spend several hours examining NYTProf beautiful reports unless I knew that some guy solved it in Python (albeit using a lot of memory, which is, by the way, a good indicator of a different algorithm)). Update. Big thanks to ikegami and zwon for their suggestions in comments! I just decreased my runtime by almost 30% implementing them! The last version looks like this:
It does not pass the SPOJ judge yet, although. But the box which will run it in 2 sec should be only twice as fast as my desktop :)
--kap
Back to
Seekers of Perl Wisdom
|
|