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

Can anyone expline why my O(n log(n)) code takes 1620 ms to get the answer?
Автор DiaaEddin, история, 7 лет назад, По-английски

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

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить