Java seems to be hindering my efforts.

23 месяца назад, # ^ |

Yeah, I think I will have to learn C++ as well if I want to do competitive programming long-term.

→ Ответить

23 месяца назад, # |

+21

Tangential.

Here is a mostly direct translation of the C++ solution you mention, 184752199, into D language: 186740798. And it already takes 1.7 seconds instead of 2.8 seconds (probably, unordered_set is to blame in C++).

So, a tongue-in-cheek advice: if you want to use a language other than C++, use D, not Java :) !

→ Ответить

chromate00

23 месяца назад, # ^ |

+11

My advice to the OP would be to use the right tool for the job. If you have a hammer in your hand, everything looks like a nail, but at least you don't want to hammer a screw, right? Same story. In my case, Ruby is my secondary language. Ruby is typically a godly language in number theory, especially thanks to its module named "Prime". However, it is not a very fast language. I would rate it as on par with (or sometimes slower than) Python. Truth is, every language has its pros and cons. (Yes, even Java has its pros. For anyone who's curious, ever heard of java.awt.geom?) It's every coder's duty to select the right tool for the job, and the experience would be optimal if and only if you use the right tool.

→ Ответить

23 месяца назад, # ^ |

Well said.

In all seriousness, learning another language also helps to code in one's "main" language as well. Some neat ways to do stuff, best practices, other programming paradigms — they are sometimes applicable in the "main" language.

My comment was about a funny and rare case when something (D this time) is faster than the coveted C++. And I saw it rarely happen with Java and Python as well.

→ Ответить

23 месяца назад, # ^ |

+14

This particular C++ solution is resistant to Hash DoS because of a custom hash function and your D solution is vulnerable. So it's not apples to apples comparison. Associative arrays in D can be hacked:

Integer keys: https://mirror.codeforces.com/contest/1676/submission/156707849
String keys: https://mirror.codeforces.com/contest/1703/submission/163949653

→ Ответить

23 месяца назад, # ^ |

← Rev. 2 →

Sure thing.

Again, my point was not to produce the best solution. Rather, I translated the actual solution code (not the surrounding hacks) almost line-by-line. My hope was that it would still be mostly readable by the one who understands the original, and works in a similar fashion. Code being faster is actually an unexpected byproduct.

To take it to an extreme. Suppose I produce a solution in the language which looks like a bunch of Unicode emojis, but it's 0.2 seconds faster yet. That won't help the current discussion in any way, correct?

→ Ответить

23 месяца назад, # ^ |

-8

My point is that your translation is not exact. You are loading the array as 32-bit ints instead of 64-bit ints and your hash is not hardened against hacks. It's a line-by-line conversion, but not exact conversion. These minor differences do matter.

BTW, your submission seems to be nevertheless difficult or impossible to hack

→ Ответить

23 месяца назад, # ^ |

Actually, the thing that worries me the most about Java is not its speed, but rather the unpredictable behavior of TLE, such as how, even in the most complex scenes, it will typically work fine, but that, 1 out of 20 times, it will fail and you won't even realize that Java, and not you, screwed up here. This gives me restless dreams of what would happen if this happened during a contest, I will be screwed :')

→ Ответить

23 месяца назад, # ^ |

+19

Rust does the same in less than 1.4 seconds: 186751469.

Use Rust, not D :) !

→ Ответить

23 месяца назад, # ^ |

For a really fair comparison D language needs a 64-bit LDC compiler, which is currently missing on the Codeforces platform. That would make it 64-bit vs. 64-bit and LLVM backend vs. LLVM backend.

The currently available DMD compiler is famous for its very fast compilation time, but it can't generate fast code. Using DMD instead of LDC or GDC is similar to using TinyCC instead of Clang or GCC. I don't think that many people on Codeforces would be happy to have TinyCC as the only available option for C language. Even though TinyCC is famous for various compilation speed records, such as booting the Linux kernel from sources in less than 15 seconds.

→ Ответить

23 месяца назад, # ^ |

In a really fair comparison C++ would probably outperform both D and Rust, while being still almost as readable, although, with Rust it is not 100% clear. Another point is that one has to have about 10 years of experience to be able to write clear, reliable and extendable C++-code without any assistances that other languages may provide.

Also, it was mostly a joke.

→ Ответить

23 месяца назад, # ^ |

+13

When using exactly the same code generation backend and implementing the same algorithm, the performance of C++, Rust and D is expected to be roughly the same. They all are top tier programming language choices. Some performance differences are surely possible, but the cause of such differences can be usually identified and corrected in each particular case. Or at least explained.

For example, ABC279_F submissions sorted by execution time show that D code compiled by LDC 1.20.1 (37 ms) is near the top. I just took one of the faster C++ submissions and converted it to D. Something like this is also possible with Rust if anyone bothers to do this. Similar comparisons can be also done for the other problems on AtCoder.

But what really matters is the syntax of the language itself, safety, the standard library, etc. And of course, the availability on various competitive programming platforms. C++ is available everywhere and is also much less likely to be misconfigured.

→ Ответить

23 месяца назад, # ^ |

When using exactly the same code generation backend and implementing the same algorithm, the performance of C++, Rust and D is expected to be roughly the same.

It is not necessarily true. Firstly, it is not true because of RAII vs GC. They just shine in different cases and RAII usually fits competitive programming purposes a bit better. That is a reason why Java-TL was a thing for such a long time.

And even with C++ vs Rust it is not so clear. I know a problem where making one of parameters template makes the code run six times faster. It is just not possible to do in Rust, because it simply does not have integer templates (or generics, for true crustaceans). And even besides that there are differences in how compilers can optimize the code. I don't want to go in-depth on theoretical foundations of those differences, I rather show a practical example of unexpected speed loss with exactly the same algorithm written in two languages (for which I still don't know the reason).

→ Ответить

23 месяца назад, # ^ |

D language supports RAII and can work without GC too, but this is not necessary. GC is generally disliked in interactive applications, such as games. That's because GC tends to postpone memory deallocations and does them as big batches whenever it decides to collect garbage (causing occasional pauses at unpredictable times). But for competitive programming purposes this doesn't really matter (unless the MLE limit is very tight).

Java/Kotlin/PyPy are slow primarily because of the startup/warmup overhead of JIT. JIT generates native code at runtime and this costs precious CPU cycles. If an application is very short lived (such as competitive programming solutions), then a significant fraction of time is spent on generating the native code (from the sources or from bytecode) rather than actually executing it. If the competition rules were changed to check the combined compilation time + run time against the time limit, then GNU C++ wouldn't be the best choice anymore (losing to PyPy, LuaJIT, TinyCC and DMD in many cases).

As for your practical example. It just confirms what I mentioned before. C++, Rust and D code can be equally fast when doing the same task. There's a reason for any observed big difference and most of such differences can be corrected/workarounded. Profiling tools can be used to get some stats for your slow vs. fast Rust code and this works better than just making random guesses. You mentioned the "unexpected 60% slowdown which is not present in C++". But it is possible to observe big slowdowns/speedups in C++ solutions too by tweaking really minor things or using a different compiler version. There are many blogs on Codeforces about this.

→ Ответить

23 месяца назад, # ^ |

D language supports RAII and can work without GC too

Yes, but then, AFAIK, you have to give up the standard library as well, so it does not really count. Also, you can add GC in C++ too, but who in their full sanity would do that?

As for your practical example. It just confirms what I mentioned before. C++, Rust and D code can be equally fast when doing the same task.

My point was not that they can't, but that it does not always happen (also, I would argue that in the example with templates they can't). And although you can question my choice of profiling tool (which was unix time, btw), the effect persists even in your experiments and it gives almost 30% slowdown, that I personally still can't explain (and do you?). The problem is not that it cannot be corrected, but that it has no apparent reason. In C++ you definitely can achieve huge slowdowns/speedups by minor tweaking your code, much bigger than 60%, but slowdowns without visible reasons do not really happen too much. At least I personally never seen an example that I can't explain after reading the code and the assembly.

→ Ответить

23 месяца назад, # ^ |

On the contrary, my impression is that the horrors of GC are greatly exaggerated. For people fearing it too much, D's GC collection cycles can be disabled altogether at program start, making it essentially heap allocation without freeing. But 99%+ of the time, your competitive programming solution won't be able to trigger GC collection anyway.

→ Ответить

23 месяца назад, # ^ |

Ugh, just when I thought I was making progress with C++ tutorials, you made me realize I have to learn D too. When will the learning ever end?

→ Ответить

chromate00

23 месяца назад, # ^ |

-10

You should better understand his actual purpose in saying that, he doesn't really mean you must learn D for CP. Instead, he means that, sometimes, very great languages are outperformed by mostly unpopular choices.

→ Ответить

SouLPegasiuuuS

23 месяца назад, # |

Not related to the topic of the blog but related to the problem mentioned in the blog.

Why is 185759665 this code passing and 185759576 this code giving TLE verdict.

→ Ответить

Perry_Prasad_Platypus

23 месяца назад, # ^ |

In this code:

if(m[sieve[j]]==2){
cout<<"YES\n";
return;
}

You are accessing m[sieve[j]] many times which takes much more time than simple O(1) operations.

→ Ответить

SouLPegasiuuuS

23 месяца назад, # ^ |

Thanks. Got it. If I move this check part in the if(a[i]%sieve[j]==0) block then it passes.

→ Ответить

Alex7

23 месяца назад, # |

There is a technical term for this class of problems. We call it financial illiquidity.

→ Ответить

Atlas

23 месяца назад, # |

← Rev. 3 →

Don't use Java unless you are Petr or Egor or uwi or eatmore or SecondThread.(Just kidding)

→ Ответить

yadavDipesh

23 месяца назад, # ^ |

SecondThread

→ Ответить

Klein

23 месяца назад, # |

← Rev. 2 →

You loop over too many numbers unnecessarily and in the wrong order leading to bad cache performance. You also unnecessarily use long instead of int in some places.

Here's a Java solution that passes test case #3: https://mirror.codeforces.com/contest/1771/submission/186823679 But it gets WA on test case 33. Finding that bug is left as an exercise for the reader. ;)

Edit: And here's the same Java solution that gets AC https://mirror.codeforces.com/contest/1771/submission/186824168.

→ Ответить