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

Автор vishaaaal, история, 3 года назад, По-английски

Hello there!

I was trying to solve E-Partition Game from yesterday's round. And for those who have solved it, you know it can be solved using Segment Tree with Lazy Propagation(there might be other faster solutions, which I don't know). I use my (small) segment tree template when I encounter a problem on it and I did the same here and it got Accepted with a runtime of 2542ms(though the average runtime of submissons is around 1700ms maybe).
You need not read and understand or debug the implementations but only compare the class based implementation(can be found above the main function) of Segment tree across a few submissions :).
Anyways, I later changed the implementation slightly so that the update and query functions are declared inside the class and defined outside. And the runtime jumped to 2760ms. Then I also changed the implementation of createTree function in the same way, declared it inside the class but defined it outside and the runtime jumped to 2838ms! This "jump" runtime might be justified by the fact that the code is already slow and slight variations can cause bigger effects. However, I am not sure about it.
I tried to change the implementation a bit more and used "intermediate" functions. First I changed the normal update and query functions to update_ and query_. And created update and query functions to improve user interface.

update
query

And the runtime reduced to 2792ms.

Now I don't understand why this is happening. Is it because class based implementations are slow? But many great coders use class based implementations for their templates and they are super fast! If there is a way to convert DS/algorithm codes to efficient class based implementations, then please share you knowledge about it here. I want to write my own implementations but almost all of them turn out to be slow when done with classes :(.

Thanks for reading!

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