資料科學小嫩嫩 9/27 - Day 7 Leetcode fizz buzz

 前篇：資料科學小嫩嫩 9/26 - Day 6 Leetcode two sum

資料科學小嫩嫩

ITHome Day 7 FizzBuzz

--

Leetcode 412 FizzBuzz

github

暴力法:

   Runtime: 4ms

發現 FizzBuzz : Fizz 會在前面

   Runtime: 0ms

用 hash map ( 這邊有些 tricky, 因為 unordered_map 順序不保證. 

但用 map 這邊速度一樣是 4ms.. 

--

Leetcode 1195 Fizz Buzz multithread

這題最主要其實是在 multithread 的實作. 

上述的 Fizz / Buzz 字串連接加速方式, 在這題因為獨立出 FizzBuzz threadC, 

所以這技巧沒辦法用. 

同樣用上面 ITHome 維元老師所說的 

  先 初探直覺解, 再優化 的技巧.

這技巧在很多事務上都可以用到.

github

做一個 semaphore

目前 Leetcode 上還是 c++ 11, 所以得自己做. 

c++20 時就有 Semaphore 了. 

接著用 number() 這個做主迴圈, 其他的 thread 等待專門列印

主迴圈:

其他各 3/5/15 倍數的 thread 都類似, semaphore wait()等待, 做完後

notify() 通知回到主迴圈

這個方式, 花費 48ms, 只領先 41%

==

優化 1 減少 %

      只做一次, 其他因為 switch 在 compiler 優化就是用 hash 方式.

這個方式, 有快一些, 花費 36ms, 領先 63.9%

==

優化 2: 嘗試完全不用 %, 

   因為每個 15 個數字之後, 型態又相同了.

   可以針對這看情況通知不同的 thread. 

這個方式, 又再快一些, 花費 16ms, 領先 85.9%

似乎還沒到極致,

看了一下討論區, 有些寫可以到 9x 甚至 100% 的, 

但似乎 server 並不是很穩定, 同樣的程式沒辦法跑到這麼快. 

1. 方法1

   其實有 sem_init() / sem_wait() / sem_post() 函數可以用

   以 threadC 15 的倍數的這個 thread 為起始, 開始執行. 

   當不是 15 的 倍數時, 依序從 3 的倍數, 5 的倍數檢查起, 都不是的話則用 number 印出. 

   若有發現則跳回15

2. 方法2

    這個寫法蠻有趣的. 

    先設計一個 run function

 每個都同時在跑, 檢查是該倍數則印出來

如何確保印的順序是對的? 也是靠 semaphore, 因為這四個 threads, 

只會有一個 thread 條件是滿足的.