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

Автор bukefala, история, 7 лет назад, По-английски

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

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

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

Tourist hates him! Such ANIMAL...

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

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

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

Can you elaborate on number 1?

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

    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

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

Why not use bitset in 10.?

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

I love the complexity of 6th.

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

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)

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

Is this a joke?

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

"The year is almost over"

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

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

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

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

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

ANIMALLL !!! Great optimizations!!

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

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.

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

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

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

    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

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

Great optimizations

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

I need to bookmark this :P

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

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.

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

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.

»
6 лет назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +153 Проголосовать: не нравится

    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.

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

      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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

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

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

Then bitset is Road to Grandmaster.

»
6 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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

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

?

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

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

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

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Are you the inventor of the bitset?

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

So basically Bitset is a God?