limed's blog

Java 9 for Competitive Programming
By limed, history, 7 years ago, In English

As Java 9 has been released few days ago, I went through the What's New to see if there is something useful in the context of Competitive Programming. And I didn't find much, just these few enhancements:

  • new static factory methods on the List, Set, and Map interfaces (returning immutable instances of those collections), for example: Set<String> alphabet = Set.of("a", "b", "c");

  • internal String representation as array of bytes (8 bit) instead of array of chars (16 bit) in case the string contains only Latin-1 characters (which is normally the case in Competitive Programming); this would reduce memory consumption almost by half in String problems, and I wonder what would be the impact on performance;

  • JShell (aka REPL in some other languages) for executing small pieces of code / bruteforce solutions (thanks bhishma for suggesting this).

Also, there are some new standard library methods not mentioned in "What's new" (thanks eatmore for pointing this out). Here's what I found:

  • Math.fma(a, b, c) to compute a * b + c on doubles/floats with better performance and precision;

  • A few new Math.multiplyExact/multiplyFull/multiplyHigh methods;

  • Arrays.equals to compare two subarrays;

  • Arrays.compare to compare two arrays/subarrays lexicographically;

  • Arrays.mismatch to compute common prefix length of two arrays.

(Array methods should have efficient implementations using vectorised CPU instructions).

As a personal note, I feel like Java is still light years behind Scala (which unfortunately is broken on CF for 2 months already) for writing CP code, even though both of them run on the same JVM. Just please, don't start language flame wars, unless you have tried both :)

P. S. If someone goes through "What's new" of Java 9 and notices some more relevant enhancements, please post them here. I could have missed something.

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by limed (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scala may be better for CP (awesome standard library) but it is much slower than Java. Getting AC in Java is hard in some problems while getting AC in Scala can be impossible.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is true only if you use functional constructs in performance critical part of your code. Avoiding that gives you performance comparable to Java (since both languages compile to the same JVM). In case I'm not confident in performance, I write the inner-most loop as a plain while and then the constant factor is fine (of course, then I give up some of the benefits of the language; but just some).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I agree, but rewriting pure, functional Scala code into C seems like a waste of a nice language.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you expain, in what context Scala is good for CP?
    And are there any more good languages (apart from C++, Java) in your opinion with a good speed-library trade-off?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Tuples, mutable/immutable data structures, functional elements (i.e. folds/maps/forEachs) integrated into all collections and much more.

      Python has a nice library with powerful functions (for example, itertools) but it is quite slow.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for your quick reply. So which language do you use for biginteger or other libraries? How does Go compare?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Python/Java for arbitrary-precision arithmetic (Scala also has a very good BigInt class).

          I've never used Go in CP.

          → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To sum it up in a few words:

      • performance similar to Java (you need to be careful in some cases though);

      • the code is much shorter. Even this shiny new Java 9 code sample in my post is so verbose: why does it have to say Set twice? why cannot the compiler infer the generic type automatically if there is nothing else but Strings (and cannot be, since the set is immutable)? And to make the reference immutable, I have to add final to it. So we would have final Set<String> alphabet = Set.of("a", "b", "c"); vs val alphabet = Set("a", "b", "c"). Also, you have normal mathematical operators on BigInt/BigDecimal, versus all the a.add(b.multiply(c)); in Java.

      • someone already mentioned feature-rich collection library (it even has a KMP based implementation of substring/subarray matching).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But you don't have BigInteger::isProbablePrime on Scala's BigInt (but you can still use Java's BigInteger in Scala...). Java's Stream class in another great feature that Scala doesn't have.

        The comparison between Java and Scala is not really fair as a great part of the Java standard library can be easily used in Scala.

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think JShell would be helpful in creating brute force solutions and also for generating small test cases .

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Not everything is listed in "What's new". For example, java.lang.Math got some new methods.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, I've updated my post with the some details missing from "What's new".

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by limed (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Some more additions:

  • java.util.Arrays.equals variant that uses a Comparator.
  • java.util.Arrays.compareUnsigned.
  • New methods in java.util.Objects, java.util.Optional, java.util.OptionalInt, java.util.OptionalLong, java.util.OptionalDouble.
  • java.util.Scanner.tokens (to write A+B in one line ☺️).
  • New constructors, static field and methods in java.math.BigInteger. New method java.math.BigDecimal.sqrt.
  • New methods in java.io.InputStream.
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use Java 9 on codeforces?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Not the 9. But Java 11 support was added recently.

    → Reply