ijxjdjd's blog

Are there any further optimizations to this Java code? (1388E)
By ijxjdjd, history, 4 years ago, In English

Link to my code: https://mirror.codeforces.com/contest/1388/submission/88538912

I think I've pretty much explored all avenues for optimization (besides switching to C++). The number of operations is around $$$2\cdot10^8$$$ in the absolute worst case, so I don't have any idea what could be slowing down my code. Is there anyone who's more knowledgeable in me at Java that can identify any further optimizations or possible bottlenecks in my code?

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

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

You can try using <<1 rather than *2 (remember to put parentheses). It won't be significant but it's something :)

To be fair, the code seems decent. Tagging some Java GMs to get attention

SecondThread uwi eatmore cwise Lewin

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

    You forgot about Petr :)

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

      I didn't include Petr or Egor because they no longer use Java. I guess it wouldn't hurt to tag them though.

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

        Right, I guess the knowledge is still there

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

Don't use(Never) $$$Arrays.sort()$$$ instead use $$$Collections.sort()$$$ because $$$Arrays.sort()$$$ is $$$O(N^2)$$$ in worst case since it's uses quick sort on the other hand $$$Collections.sort()$$$ uses merge sort which guaranteed to be $$$O(NlogN)$$$ one of such instance

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

    Use Integer[] array is okay with Arrays.sort(), and since java has automatic unboxing you just need that deceleration, the advice is to not use a primitives

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

      @above: you are correct. Let me elaborate a bit more.

      Arrays.sort(Object[] o) has O(n log n) time complexity.

      The only sort that has worst case O(n^2) is Arrays.sort for primitive types. For example, calling Arrays.sort(new int[10]); will sort with quicksort but Arrays.sort(new int[10][10]); will sort with O(n log n) time complexity (although throwing an exception as int[] can't be cast to Comparable<int[]>

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

In my experience, there are two major instances in which Java just falls on its face runtime wise: n^2*log(n) geo problems and TreeSet problems with a lot of maintenance. I don’t think storing things as shorts actually helps at all unless your issues is an MLE.

Math.max and Math.min are for no explainable reason ~35% slower than writing your own version with a ternary operator.

Like skittles said *2 to leftshift works as well usually, but that shouldn’t be an issue here.

Last thing: it looks like your bottleneck is the sort which happens n*n*log times, compared to everything else which happens O(n) times. You can improve that by not putting nulls in the actual arrayList and instead just storing a count for how many of those you have.

Oh, real last thing: sometimes arrayLists are unreasonably slow too, so using arrays is usually better if you can. Sorting arrays is only trash if they are of primitives (since it doesn’t need a stable sort for primitives, so it quicksorts). That might not help too much, but it is something.

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

    Some questions:

    Math.max and Math.min are for no explainable reason ~35% slower than writing your own version with a ternary operator
    The implementation for Math.max(int, int) I think we can safely assume that it is the same with other primitives:

    public static int max(int a, int b) {
    return (a >= b) ? a : b;
}

    Just curious, why would this be slow, as compared to a ternary operator?

    Also, in your (short) template, you have the sort(int[]) method, which basically copies an array to an arraylist, sorts the arraylist, then copies back to an array. When comparing this method and another method of shuffling (implemented by making n random swaps) the array, this method is about double the speed of the shuffling method (sometimes triple). Why do you still use this method?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I just benchmarked Math.max() again. On Java 11 it seems to be pretty much the same as my own ternary operator. In previous versions, it has accounted for huge differences in some submission times. I think what was happening was setting some flag to do something in a thread-safe way. This happened every time you called a static method I think, so that was really the problem, not the implementation of the actual method. I updated Java recently and can't reproduce the slowdown anymore though.

      The reason for my sort was that it is faster to type and I just made my template one day when I needed to sort like $$$10^5$$$ numbers on a CF problem and I just wanted something that was n*log(n). Then I just pasted it into my template. After some testing, shuffling is about 3x faster, so I'll probably use that now, despite it doubling the length of my sort method to 8 lines.

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

        I think that Math.max may have a slowdown in some Java versions. I know a friend who submitted a USACO (which uses Java 8_121)solution which did Math.min around 1e6 times. It TLE'd on 8 of the testcases and was extrememly slow. I then removed the Math.min (as it was an attempt for an unecessary optimization) and it got AC with only around 1000 ms (in contrast to the >4000ms tle)

        Also, a small trick for swapping, you can do a^=b;b^=a;a^=b; Much faster than doing the addition trick or setting a tmp variable (I haven't tested but I'd assume that xor would be pretty fast).

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it 
        public static void main(String[] args) {
        for(int i = 0; i < 70000; i++) {
            for(int j = 0; j < 70000; j++) {
                //int k = Math.max(i, j); //2822 ms
                //int k = max1(i, j); //2839 ms
                int k = max2(i, j); //2823 ms
            }
        }
    }
    static int max1(int a, int b) {
        if(a > b) return a;
        return b;
    }
    static int max2(int a, int b) {
        return a >= b ? a : b;
    }
}

    There is a bit of fluctuation but theyre always around the 2820-2840 range

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

      Well those are pretty much exactly the same code. The suspected difference is in calling a static method in another class vs calling a non-static method in your own class, not the ternary operator

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

I think a Pair class holding two ints is faster than using int[2]. Maybe making the Intersect class static can also improve the speed.

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

Doable but definitely not advisable: https://mirror.codeforces.com/contest/1388/submission/88543263

WA41 is from your original code, I didn't read the statement.

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

For reference, I also solved this in Java in 2854 ms (88545032), though I had to optimize mine a tiny bit as well (I changed a Pair<Double, Integer> class to a custom class that stored a double and int to eliminate some autoboxing, and that sped my code up by almost 2x).

Anyway, I tried testing your code in custom invocation on a random n=2000 case I generated, and it takes 5366 ms, but also gives WA (at least, it disagrees with my code).

I tried isolating parts of your code, and it looks like when you sort intersect that takes 4100ms, so speeding that part up will help a lot more than anything else, if you can think of a way to do so.

Specifically, this block takes 80% of your time.
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I actually got my Java solution down to 639 ms.

    Submission: 88545616

    Like you, my limiting step was sorting an array of $$$N^2$$$ objects, which is slow in Java. So instead, I used some black magic to encode a Pair<Double, Boolean> into a single primitive double that still sorts the same way (by using 1 bit of the mantissa to represent the boolean).

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

      Sadly my logic is a more complex than a boolean and double but you've given a fairly large speed up on TC #22 by deleting some items in my object which gives me hope to push my code through eventually.

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

Make Intersect static class, it could reduce a lot of memory.

[deleted, a wrong idea]

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

The best optimization is just rewrite solution on C++.

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

I see a problem here: an array intersect with 8000000 objects. To optimize, I'd use an array of primitive type (such as int idx[]) and a custom in-place sort implementation with comparator. Also, the performance of Float.compare is suboptimal, because it has code for handling NaNs.

→ Reply