SleepingThread's blog

Don't use "struct" ?
By SleepingThread, history, 3 years ago, In English

Hello everyone!

I was trying to solve this problem using hash struct, the complexity of my solution is O(N) which should pass the testings, but the judgment was giving me TLE, and after hours of trying to fix the problem, I decided to remove struct hash and instead of it, build the hash in the main, and Surprisingly it passed the testings!

this is my hash struct: 

struct Hash
{
    int n,Base,Mod,Inv;
    vector <int> Po,iPo,Pre;
    Hash(string &s,int base,int mod)
    {
        Mod=mod;
        Base=base;
        Po.pb(1);
        iPo.pb(1);
        Pre.pb(0);
        Inv=inv(base,Mod);
        for(int i=1; i<=(int)s.size(); i++)
            Add(s[i-1]);
    }
    void Add(char c)
    {
        Po.pb(mul(Base,Po.back(),Mod));
        iPo.pb(mul(Inv,iPo.back(),Mod));
        Pre.pb(sum(Pre.back(),mul(c,Po.back(),Mod),Mod));
    }
    int G(int L,int R)
    {
        R++;
        int g=sub(Pre[R],Pre[L],Mod);
        return mul(iPo[L+1],g,Mod);
    }
};

and this is the first submission which was giving TLE and this the accepted submission

you can compare between them and notice that is exactly no difference except replacing the struct with normal code. so the question is, is using struct time consuming ?

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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

maybe using push_back() in the hash struct is the cause, the vectors will spend extra time when it exceeds its size

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

    I tried to replace the vectors with arrays, it's definitely better, the new solution reached test 37 instead of 17, but still not working

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

This is probably because of inlining Mod. Compilers can generate much faster code to compute modulo when the Mod a compile time constant than a variable. When you use the struct, if the functions don't get inlined, the compiler might not realize that Mod is a compile time constant, but in your second case, the compiler can realize that Mod is always 1e9+7 and is never changed, so it inlines that value. (The same thing might happen if you used helper functions instead of a struct and passed Mod as an argument.)

The best way to guarantee that Mod is a compile time constant is to either declare+use a global const int Mod, or to make Mod a template int parameter to your hash struct.

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

    Thank you so much! very important point to know

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

    constexpr int Mod

    The compiler can actually detect that a variable's hardcoded and declare it a constexpr (or store a constexpr-declared variable in RAM if you force it) since it's just a hint that automatically gives the const type trait. In this case, the problem's that the code's written specifically to handle a general modulo.

    Do you know what x86 assembly results from inlined modulo (that isn't just a power of 2) vs non-inlined?

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

      It's not really accurate to say the "compiler will declare a variable constexpr", since constexpr is more of a language thing and constant folding is more of an optimizer thing, which is lower level. It's worth noting that in C++, constexpr does not guarantee that the compiler will evaluate your expression at compiletime; it's more of a typecheck that it can be evaluated at compiletime. For actual guarantees, see the new consteval and constinit keywords.

      Here's one example of what gcc expands the modulo to: https://godbolt.org/z/Mc8MPxPMa. If you want to look up more literature, I think these transformations are usually called "strength reduction" because you reduce the strength of the general operator a % b to a % (1e9+7).

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

        Yeah I mean that getting constants optimised happens very reliably (unlike some other optimisations) so the overall effect is much like writing constexpr. At least for stuff with static linkage.

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

I even got TLE without using struct , i think time limit is bad in this problem, it should be 2s .

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

    I think it's not a bad problem, actually, it's a very good one. this kind of problems will keep you trying your best to make your code as fast as possible!

    you are getting TLE for a reason definitely, so keep trying ^_^

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

    I added small changes to your solution and got Accepted. 147993909

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

Btw, I'm surprised that nobody mentioned that you should use rolling hashes. That way you need 2 arrays instead of 3.

To be more precise you can change your current code to use 2 arrays for building but doing it with rolling hashes is easier.

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

    Can you please show me how the code will look like with only 2 arrays, and thank you in advance.

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

      https://codeforces.me/contest/7/submission/148070093 like this.

      That along with a helpful reserve call was enough to barely squeeze it into an AC. Just one thing, if you plan on using that code check the G function because it might be R-L-1 instead of R-L, I'm not sure since I didn't stop to rethink about it but I trust you are able to figure it out ;)

      → Reply