bukefala's blog

Top 10 optimizations 2017- (collectors edition)

By bukefala, history, 7 years ago, In English

Hello friends. The year is almost over so I have prepared the top 10 optimizations of 2017 for your viewing pleasure. Without forthor ado, let us begin.

  1. OPTIMIZATION OF FLOYD VARŠAL ALGORITHM TO RUN IN N^2: simply instead of going from 1 to N in third loop we willuse bitset which will visit the remaining nodes automatically

  2. SEGMENT TREE OPTIMIZATION TO RUN IN O(NlogMlogQ) complexity. We will simply use bitset to fetch our data between nodes instead of every time having to calculate hashes in nodes all over again.

  3. OPTIMIZATION OF FENWICK TO ACCEPT QUERIES OF TYPE: EXPAND INTERVAL BY CONSTANT C We will simply use bitset which will store every expansion in every possible moment in time. You will say this is obviously too slow. But it can be easily optimized. We will simply make another bitset map for these changes.

  4. USING LCA AS A TOOL TO OPTIMIZE TRIE You maybe thinking that LCA has nothing to do with trie. but-witg SIMPLE usage of little thing called bitset,. we can chsnge this. simply make bitset remeber on evrry turn where yoou ended up afta joining nodes into components. time complexity: o(QlogLoglogNM) it can be essily proven but i will leave it to readers prectis

  5. COMPRESSING ENTIRE HASMHAP INTO A TRIPLET OF BINARY SEARCH TREES How? YOU WILLASK. i willsay: it csn be done with the help of our little mriemd bitset. we will simply store him into a SEPARATE container instead of keeping it with the other trees . This will also improve memory!!!! Readers practice

  6. MULTIPLYING BIGNUMS IN O(LOG23.5NMQRSQRT(LOG(nm))) Simply store the factors inside a RB tree of bitsets and use improved FFT.

  7. IMPROVED FFT Simply make bitset for every multiplication and merge them every logNth operation. You can not merge naively but it csn be easily merged via heuristic approach. readers prectis

  8. CONCAVE HULL TRICK Ok. You ssy concave hull can not be used for quad tree optimization trick. It can. One word: bitset.

  9. MACHINE LEARNING TRICK WITH BITSET Simply use AI bitset for storing your patterns.

  10. REVOLUTIONARY OPTIMIZATION OF BLOCK CHAIN The circular implementation of a new hashing algorithm using to optimize proof of work concept. Hashing the last block with the nonce from the previous nth block as to make it circular.

thank you for your attention mriemds,

With respect. bukefala

Literature: https://arxiv.org/pdf/0909.4437.pdf http://www.amazon.com/Optimizing-energy-consumption-wireless-networks/dp/3659121207 http://www.superknjizara.hr/index.php?page=autor&idautor=13819 http://www.jucs.org/jucs_23_3/generating_politician_profiles_based http://authors.elsevier.com/a/1SQGc5aecSN1Bg https://arxiv.org/pdf/1705.07279.pdf

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

Comments Comments (57)
| Write comment?
»
7 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Tourist hates him! Such ANIMAL...

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

Number 5 shocked me, but how do I keep track of the hierarchy of the containers?

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

Can you elaborate on number 1?

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

    of course mriemd. ok so: if you do normal floyd varsal you will take k i j for loops and imrpove path from i to j though k. But it is n^3! So for final loop which chooses the j destination you can simply store the first part of the paths lengths in a bitset which will then automaticslly update the paths when you remove the loop j and cslculate with values previously stored in the bitset

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

Why not use bitset in 10.?

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

I love the complexity of 6th.

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

I think you have a mistake in 6.

Real complexity is O(LOG23.5NMQRSQRT(SQRT(LOG(nm)))) (Because you can use a 2d bitset and get faster solution)

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

    Ooooooh very nice idea to include 2d bitset. Thank you for sharing it!

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

Is this a joke?

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

"The year is almost over"

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

Can you give a sample code for the first optimization? I still can't imagine how it work.

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

Are you serious? I personally don't think the first one's complexity is O(N^2). Could you please explain it more clearly?

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

    I think he accidentally swapped the complexities of 1. and 6. because the "optimized" complexity of Floyd-Warshall really looks like O(LOG23.5NMQRSQRT(LOG(nm))).

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

      If you use 3D bitset you can get

      complexity :)

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

      Let alone the complexity,could someone please provide the sample code for the optimized Floyd-Warshall? I think maybe I misunderstand the process of the algorithm.

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

        Here you go. Might be buggy, I didn't stresstest it.

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

          Where's the main part of your programme? Why is there nothing in your loop ?

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

            Because bitset takes care of it.

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

            Why do I feel that I am being tricked by you guys? And now I begin to believe what mredigonda says.

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

ANIMALLL !!! Great optimizations!!

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

In fact, you can optimize bitset to use only O(1) memory. Just keep an additional bitset in each bit so that everything is stuffed into a single bit.

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

I can't believe there is a lot of people who actually thought this was true.

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

    I only read #1, revised my memory of Floyd Warshall by going to Wikipedia, then spent 10 minutes trying to figure out how the optimization worked! XD This is a magnificent post! :D

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

Great optimizations

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

I need to bookmark this :P

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

9 is not very practical because you can't do gradient decent on Boolean values. And anyways, what do you get when you apply a bitset convolution on a bitset? It can't result in another bitset.

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

Does it get any better? Is there a reason for posting anything after this post came into existence?

Painting has Mona Lisa, sculpture has David, football has Maradona's goal against England, and Codeforces has this. Pure art.

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

    This blog post is simply enlightening. It is the Bible of the bitset religion.

    → Reply
»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

As I understand, bitset is just a compact representation. So, it should just improve the time by dividing by a constant (which is max 64 if we used a long instead of each bit) and this does not improve time complexity. So, how does it improve complexity?

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

    We can optimize a bitset by using another bitset. This divides the constant every time by 64, and since , the operation will eventually converge to O(1) if we use enough bitsets.

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

      Basically, it belongs to a class of limit optimizations. Consider any algorithm A for a problem P, that brings down the complexity from f(P) to g(P) where . Applying A sufficiently many times, you can bring down the complexity to g *  which can be practically O(1).

      A trivial example of this is linear search to binary search. For P(n) = searching in sorted list of size n, f(P(n)) = n, but . The conditions for the optimization are satisfied, and consequently the complexity can be brought down to g *  ≈ O(1).

      The idea is very trivial and frequently used by high rated coders, so I thought I should post it here for the benefit of the community.

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

      I don't get it, how do you apply bitset optimization twice?

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

Then bitset is Road to Grandmaster.

→ Reply
»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

You forgot to mention that Traveler Salesman can also be solved in O(N) using bitset<bitset<bitset<bitset>>>.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

?

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

Legend says that Fermat used n-dimensional bitset to prove his last theorem, but his margin was not enough to contain the code...

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

Can I see the code of OPTIMIZATION OF FLOYD VARŠAL ALGORITHM TO RUN IN N^2 ?

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

Are you the inventor of the bitset?

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

So basically Bitset is a God?

→ Reply