0o0o0o0o0o0's blog

To use or not to use oop
By 0o0o0o0o0o0, history, 6 years ago, In English

When implementing a data structure like a segment tree or union find is it worth it to wrap the data structure in a class?

Will it pay off? Will the object overhead be feasible? Will the scoping play such a big role? Or maybe the typing speed?

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

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The general rule is: don't worry too much about such micro optimizations. Internally the program might have to follow a few more pointers, but not many, so your program might be <1% slower. And the odds are good that the compiler will even eliminate those overhead and you have the exact same speed.

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

    So do you recommend the oop version?

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

      I'm not thinking only about speed. Some problems with non-oop version are scoping which may cause clashes with other variables or just the ambiguity.

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

        If you are worried about name clashes you could use namespaces instead, which would introduce no overhead.

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

      Yes, I do. But keep in mind that you have only limited time in a coding contest. For that reason I also use OOP too rarely. And if I do, I usually don't use any good practices like private variables, getter, setter, ...

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I prefer using OOP while implementing data structures.

There are some reasons behind this:

  1. You can create multiple instances of your object. There are some problems where you may create, for example, more than one Fenwick tree. It's much easier to implement it if you have Fenwick tree as a class.

  2. It may also decrease the amount of code. I remember a problem where I needed two segment trees with different operations. You need to implement it once if you put it into a class. Also this class can be made template.

  3. The code looks much simpler and cleaner.

  4. Classes are better when re-using code (it's helpful when you can use pre-written code on contests).

The disadvantages you noticed doesn't matter much:

  1. Code speed. If you write on C++, the perfomance is nearly identical (maybe slower, maybe faster) to the implementation without OOP.

  2. Typing speed. It doesn't take much to write this, isn't it?

class Klass {
private:

public:

};

That's all the overhead. If you care much, you can configure your editor to generate this template automatically.

Besides, I never write treaps in OOP style (only struct Treap + functions). It's more convenient for me.

→ Reply