Win a copy of Serverless Applications with Node.js this week in the NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • paul wheaton
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Ron McLeod
  • Tim Moores
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Vijitha Kumara

Need help for code which is too slow  RSS feed

 
Ranch Hand
Posts: 99
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Ranchers!
I need some help to speed up this code.
The problem is as follow: https://open.kattis.com/problems/encodedmessage



This code works but it's very slow!
Junilu said once "main is a pain", is it why? Should I made helper functions? How can I make it faster or more efficient?

Thanks to everyone who read and respond.
 
Marshal
Posts: 63849
209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

D.J. Quavern wrote:. . . Junilu said once "main is a pain", is it why?

No, it was Wnston Gutkowski who said that.
  • 1: Because it is static, so use of the main method means you are not working in the object‑orientated paradigm.
  • 2: Because it is a void method, which means you cannot use it as a function and can't use it is a functional paradigm.
  • 3: Because lots of code in a method make it difficult to follow and difficult to maintain or update.
  • Should I made helper functions?

    You already have helper functions, in this case the utility class' methods which you are using for input. I think no; I think you should write the code in a object‑oriented fashion, so you have a Message class with one instance for each of your 10 messages, with the array of arrays as a field. It would need getEncoded() and getPlain(() methods, though you can probably use the toString() method for one of those. Or you could use PlainMessage and EncodedMessage classes with one method each. That would be the object‑oriented way to solve your problem, even though Kattis might only be looking at results and timings.

    Why ave you called a char[][] something like doubleArray? That is a confusing name. Maybe lettersMatrix or similar would be better.

    How can I make it faster or more efficient? . . .

    The only way I can think of making it faster is to remove the multiple print() instructions. Don't print individual characters; append them to a StringBuilder object and print the whole StringBuilder out. Even so, I am surprised to find you exceeding 1′ for something straightforward llke this exercise.
     
    Sheriff
    Posts: 13392
    221
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Up to 100 strings to decode that can be up to 10K characters long each.

    Not surprised. I think the StringBuilder can help a bit but two sets of nested loops is not necessary. You can cut down time by half what it is now by changing your approach and using only one nested loop.

    String has a toCharArray() method.

    Edit: My submitted solution based on the above hints was accepted. CPU reported was .29s
     
    D.J. Quavern
    Ranch Hand
    Posts: 99
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, this solution passes but I have 0.78 secs, which is long.
    @Junilu: I'll try with your hints.
     
    Junilu Lacar
    Sheriff
    Posts: 13392
    221
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This is why you never optimize with your gut. I changed the solution to use System.out.print() instead of the StringBuilder and CPU shot up to .85s

    So I guess the I/O made more of a difference than the multiple nested loops.
     
    D.J. Quavern
    Ranch Hand
    Posts: 99
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks to everyone.
    I reduced it to one loop with a period instead, and a string builder.
    I am down to 0.19 s now.



    Do you mind checking another problem ?
    And Junilu, can I please see your solution?
     
    Junilu Lacar
    Sheriff
    Posts: 13392
    221
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have to admit, I learned something about I/O today. I switched to Kattio for I/O and got 0.19s (down from 0.29s with Scanner and System.out.println).

    Some things to note:

    1. Got the same performance number even when doing I/O after every line decoded instead of just once at the end.

    2. The variable names I used. I found the variable names you used confusing. I used terms that come from the domain: "cipher text" and "plain text"

    3. Admittedly, your code helped me clean up mine a little. Previously, I was doing a little bit more arithmetic with the loop indices. So I stole two things from you: the I/O and the cleaner loop index management.

     
    Junilu Lacar
    Sheriff
    Posts: 13392
    221
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Keeping decode() a separate method allowed me to write a unit test for it:

    Having a unit test like this while I was working through the logic and cleaning it up really helps make your my life easier and development faster.  It makes your life better if you had to come in and make more improvements to my code.
     
    Junilu Lacar
    Sheriff
    Posts: 13392
    221
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I wonder if the difference of 0.1s has more to do with the sheer size of Scanner rather than its actual performance characteristics. Relatively, it's much larger than Kattio. Should be an interesting exercise to find out just where the performance gains are for Kattio.
     
    D.J. Quavern
    Ranch Hand
    Posts: 99
    Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It's an honor that you thought small pieces of my code were good enough to borrow

    I did not write a test: my bad. In the end, I lost more time copy-pasting tests than if I had taken 5 minutes to write a decent test. My bad.

    I'll post another code shortly on which I would really appreciate some insights
     
    my overalls have superpowers - they repel people who think fashion is important. Tiny ad:
    global solutions you can do in your home or backyard
    https://coderanch.com/t/708587/global-solutions-home-backyard
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!