SAT2020's blog

Why does caching take so long?
By SAT2020, history, 2 years ago, In English

Hi everyone,

I was recently working on the Timus problem "The Debut Album". While doing so, I came across something very odd: my nlog(n) algorithm is way too slow! To summarize the problem:

  1. You must assign n elements either 1 or 2
  2. There can be no more than "a" 1s in a row or "b" 2s in a row
  3. How many assignments can we make?

The solution I came up with was DP, where each state = {element number, count of the previous 1s in a row, count of the previous 2s in a row} --> {i, cntA, cntB}. Now, I understand why, in the worst case, this algorithm is ineffective. "n" can grow as large as 50,000, and "a" and "b" can get as large as 300 --> 50000*300*2 states (multiply by 2 because if cntA is positive, cntB must be 0 and vise versa) --> 3*10^7 * log2(3*10^7) is clearly way too much. But even when I reduce "n", "a", and "b" on my own computer to 50000, 30, and 30 respectively, the program still takes upwards of 10 seconds to run, which is ~10 times longer than you would expect (3*10^6 * log2(3*10^6) < 10^8). What's going on here?

Note: I do know the correct solution, I'm just wondering why this implementation takes so long for the future.

Here is my code: https://codeshare.io/loWmNR

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

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

Auto comment: topic has been updated by SAT2020 (previous revision, new revision, compare).

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

C++ maps have a fairly high constant, plus you're doing a vector compare and allocation in each function call which is fairly expensive. Try it using unordered_map and tuple or pair<pair<int,int>, int> for your keys instead of vector.

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

    Thank you for your help! I think the biggest issue was vector comparison, it took about twice as long as using pairs.

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

      You can also use array<int, 3>, it's pretty much the same thing as pair<pair<int,int>, int> but with nicer syntax

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

        never forget that there's the tuple<int,int,int> too

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

          It's longer, it's not a container (you can't easily sort it), you can't use [], you can only use compile-time constant indices (with ugly syntax, even worse than pairs IMO). But both can be decomposed like auto [x,y,z] = a;. There is no advantage of using tuples of same types.

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

            You're right, unfortunately. And I realized that you can still make a simple struct when they are homogeneous, because it's convenient to get the member variables a name instead of overusing get<>(). So the only situation when a tuple might be better than these alternatives, is when you're too lazy to write a comparator, but that's been taken care of through defaulted comparison (feature added on C++20).

            So, yeah. Basically, the tuple might be too powerless considering the alternatives.

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

        That's actually a sick tip, can't believe I didn't know that! Thank you!

        → Reply