Блог пользователя limed

Автор limed, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          I've never used Go in CP.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we use Java 9 on codeforces?