DiaaEddin's blog

Can anyone expline why my O(n log(n)) code takes 1620 ms to get the answer?
By DiaaEddin, history, 7 years ago, In English

I solved Mister B and PR Shifts using trie ... Time complexity of my code is O(n * log(n)) where maximum n = 1000000, but it takes about 1543 ms at least to get the answer, so can anyone please tell me why? Update.. some users advised me to use array instead of pointers with dynamic memory allocation and thats what I did this is the best code I came up with so far .. no dynamic memory allocating . no pointers but my code still too slow and I don't know why http://mirror.codeforces.com/contest/819/submission/28646689

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

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

root = new trie_nod(21);

Memory allocation is costly in terms of runtime. You can avoid it by keeping a static pool of nodes and assigning from there.

Did you implement an array based link list ever? Try to do the same for trie.

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

    no I did not :/ . can you explain that with an example or provide me a link please?

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

      Lets define a structure like,

      struct node {
    int cnt, child[26];
}
node trie[100000];

int used = 0;

      Now when you add a new character you do not need to allocate new memory for it. The memory is already allocated. Just use the node trie[used] for that one and do used++.

      Try checking some submission of top users. They may have a nice template for you.

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

        thank you ... it's better .. but still too slow. I edited my submission: is this a right implementation?

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

          Well. In my implementation I usually do not use any pointer. But that's not a problem. The implementation looks fine as there is no dynamic allocation now.

          Maybe there is some hidden factor that you didn't consider when you analysed the runtime.

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

            that is right.. but what factor that could be?

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

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

→ Reply