# 課堂問答簡記: 2023-09-12

## 用 Python 挑戰 LeetCode

善用 [functools](https://myapollo.com.tw/blog/python-functools/)

在 [LeetCode 204. Count Primes](https://leetcode.com/problems/count-primes/description/) (Medium) 中，要計算小於 $n$ (但不包括 $n$) 的所有質數的數量，亦即質數篩檢問題。若要判斷一個數 $n$ 是否為質數，我們可從 2 開始進行試除，嘗試找到可整除它的因數。若找到因數，則該數不是質數；反之，它就是質數。

下方程式碼展示對應的操作：

for i in range(2, upper):
    if n % i == 0:
        return False
return True

當我們從 2 開始試除時，需要考慮的是上限 upper 應設定多大。這將直接影響執行效率。最簡單的方法是將 upper 設為 $n$，不過其實只要設定 $upper = n//2 + 1$ 就夠。再者，我們可將 upper 設為 $int(\sqrt{n}) + 1$，因為若 $n = p \times q$，則 $p$ 和 $q$ 至少有一者小於等於 $\sqrt{n}$。

然而，現在的情況略有不同。我們不僅要檢測單個數值是否為質數，還要找出小於 $n$ 的所有質數。若對每個數值都使用上述的方法來進行檢測，那所需的時間是 $\sum_{i=2}^{n}\sqrt{i} = O(n^{3/2})$。

以下引入 [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 快速找出質數。

先建立表格 `prime[i]`，其中 `prime[i]` 表示數值 $i$ 是否為質數，起初所有位置都設定為 1，並且位置 0 和 1 不受影響。從 2 開始，當找到一個質數時，將其所有的倍數都標記為非質數。下面是對應的程式碼：

class Solution:
    def countPrimes(self, n: int) -> int:
        prime = [1] * n
        for i in range(2, min(n, int(n ** 0.5) + 2)):
            if prime[i]:
                for j in range(i + i, n, i):
                    prime[j] = 0
        return sum(prime[2:])

public int countPrimes(int n) {
    int[] prime = new int[n];
    for(int i=2;i<n;i++){
        prime[i]=1;
    }
    // sqrt(n)+1 > n, will only occur when n=1 or 0, but we start i at 2.
    // So the condition will be false when n=1 or 0.
    // That's why we can reduce comparing min(n, sqrt(n)+1).
    for(int i=2;i<(int)Math.sqrt(n)+1;i++){
        if(prime[i]==1){
            for(int j=i+i;j<n;j+=i){
                prime[j]=0;
            }
        }
    }
    int sum = 0;
    for(int i=2;i<n;i++){
        sum+=prime[i];
    }
    return sum;
}

該演算法的時間複雜度乍看是 $O(n^2)$，但實際上因為只有質數才會進行內部循環，所以內部循環的次數不會多於 $\sum_{i=2}^n \frac{n}{i} = O(n\log n)$，又由於質數的稀疏性，當時間複雜度接近 $O(n\log\log n)$，非常接近 $O(n)$，當 $n = 2^{64}$ 時，$\log\log n$ 等於 6。

延伸閱讀:
* [質數定理](https://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8%E5%AE%9A%E7%90%86)
* [Fastest Algorithm to Find Prime Numbers](https://www.baeldung.com/cs/prime-number-algorithms)
* [質數愈大愈孤獨：談質數分布](https://ir.nctu.edu.tw/bitstream/11536/129288/1/yaucenter-20131201-08.pdf)

## 太空產業與生態系
* [太空產業與太空科技生態系之間：你應該知道的這些事](https://findit.org.tw/researchPageV2.aspx?pageId=2265&mibextid=Zxz2cZ)
* [IC 運算平台趨勢 : 數位運算、人工智慧與量子運算](https://hackmd.io/@sysprog/BJyhRsMSF)
* [Switchblade 300 Block 20](https://avinc.com/lms/switchblade)
> AeroVironment，Inc. 是家美國國防承包商，總部位於維珍尼亞的阿靈頓，負責設計和製造無人駕駛飛行器

## 矽谷第一手經驗
[Ian Tsai](https://www.linkedin.com/in/iatsai/) (蔡昀庭), Smart News Senior software engineer (成大測量系 $\to$ LinkedIn $\to$ SmartNews)
* Ian Tsai 之前在台灣的新創公司做軟體開發 10 年，除了做開發以外也曾做過 Hiring manager、Software consultant，2015 年任職的新創公司賣給 LinkedIn 後，在 LinkedIn 擔任 senior Software engineer，目前在 SmartNews US 作 News Platform 的後端開發，平常喜歡觀察台灣美國兩地的新創公司
* 訪談: [10 的次方倍世界](https://player.soundon.fm/p/eb6f4537-358f-4d8f-9d2c-78079dee8e9e/episodes/f6561cab-c541-45e9-a816-a7556fdf64f7)
* [簡報](https://docs.google.com/presentation/d/1llybrdu7He-hLUyiNYNaSBdarv2gML0XCcoHSsKdi3o/edit?usp=sharing)

### 演講紀錄:
* 個人簡介
* 台灣先有輕工業，再來才是資本技術密集的電腦硬體製造
> [威盛，邊競爭邊合作](https://www.bnext.com.tw/article/8888/BN-ARTICLE-8888): VIA 和 Intel 在個人電腦主機板/處理器的競爭
* 用進廢退，人才被硬體市場拉走 (TSMC, UMC)。中國市場崛起，人力成本低。
* SI (system integration) 產業 (過去非專業分工/非本科佔多數)
* 名詞
* [刀鋒伺服器](https://www.ithome.com.tw/tech/28741)
* SOA: Service-oriented Architecture
* IAAS: Infrastructure As A Service
* PAAS: Platform As A Aervice
* SAAS: Software As A Service

> 市場需求為創新之母

* 古時候的臺灣「全端」工程師
- 分工意識薄弱、土法煉鋼
* Order of magnitude
* IE6 -> Chrome based on [V8 engine](https://v8.dev/) (78x speed improvement)
* Telecom network bandwidth: 2G (250k bps) -> 3G (3M bps) -> 4G (100M bps)
* 分散式架構時代的 LOG 救星 --- ELK
* [ElasticSearch - Logstash - Kibana (ELK)](https://www.webcomm.com.tw/blog/elk/)
* Tesla SOC
* [FSD Chip](https://www.edntaiwan.com/2021090231-teslas-dojo-ai-chip-revealed/)
> 當代開發者的 basic knowledge：不同算法應用在不同情境的判斷能力
> 其他：處理大量資料、找出 Insight 的能力
書單推薦：彼得杜拉客，創新者的兩難（令一個作者）
### 提問清單
* 1.台灣也有一些架構很完整的企業方案（華碩等等其他硬體廠商），跟講者提到的有什麼差別呢？
>ans:台灣對於軟體的想像不夠高，主要著重在提高硬體的效能以及支援，但是缺少革命性的創新以及想法＆產品，生態系統不夠完善。台灣的企業主傾向在成熟的產品為基礎上製作的更便宜更好（重構＆組裝）。創新性的人才基本上大多也是美國來的（ex:張忠謀先生）。
* 2.依照您所說的約每五至十年會誕生一個全新的領域與相應的職缺，在全新的領域面前，工作數年的人和 new grad 的起跑點似乎相差不遠（畢竟都沒有相關技術經驗），甚至 new grad 更有優勢（因為學校老師都會挑熱門的新領域做計畫，像現在幾乎沒有老師不做 AI），想請問您，工作數年的人在這樣的前提下，比起 new grad 的優勢是什麼？（如果是台資企業幾乎能夠想像會優先錄取給薪較低的 new grad？）；或者可以說是，當你已在某個領域耕耘一段時間，薪水也有所成長，轉換跑道時通常會以什麼來說服資方以保持薪資水準，甚至更上層樓？
>ans: 要先看人力資源市場在哪（台灣、中國、美國），企業對於人才的需求是什麼？不同環境對於人才的需求可能不同。
new grad 的優勢就是比較便宜，耐操，新鮮的肝。
一直發展自己的技能樹，保持企圖心，隨時吸收新東西，讓自己無法被取代，就不用太擔心被new grad取代
* 3.想請問，您認為在台灣創業（軟體公司）的困境為何？為什麼國內外同樣都是軟體產業，現在的發展會差距這麼多？
>ans:沒有需求（市場比較小），工程師的技術要怎麼發揮，所以一定要作海外市場（ex:東南亞...）。
* 4.想請問學長轉換公司的契機？
>ans:個人職業生涯發展考量。（ex:家人＆看不看好產業）。
目前的產業領域在現今或可見的未來沒辦法有顯著成長(ex: DVD vs online stream)
* 5.請問學長現在考慮創業嗎，或是曾經考慮過創業嗎？如果沒有考慮的原因是什麼？
>ans:
* 6.AI在台灣發展的起來嗎？還是會繼續跟往年一樣從事洗資料為主的工作
>ans:這個目前還沒有定論，因為現在還為時尚早。DSL還沒有出現。就算有框架，但是分工框架沒有很明確。
* 7.請問學長，對於社會新鮮人，選擇大公司與新創公司各自的優劣為何?另外，最近有意開始自學後端(寫些專案之類的)，有建議的方式、工具或程式語言嗎?
>ans:
* 8.請問學長對於念研究所的看法?
>ans:看人的個性，是理論派還是實作派的
但去美國念是例外，主要是為了拿簽證去那邊工作
如果不是對知識有熱情，想要作研究，覺得手邊的資源無法滿足，
那建議先工作，畢竟也有可能當下花了好幾年學的東西、作的研究到時候已經過時了
* 9.想問學長有沒有欣賞哪些剛剛提到的做海外市場的本土公司呢
>ans:
* 10.想請問學長當時怎麼在當完兵，腦袋被格式化的狀態下，學習程式的？還記得自己的學習路線圖嗎？
>ans:
* 11.這兩天成大發生了一件小事，就是選課系統連續崩潰兩次。想請問學長如果以「全端」工程師的角度，發生這個問題是哪一些節點出了問題？像是是哪一個 layer 10 年沒換之類的
>ans:啊沒辦法啊，這個選課系統就是一個活化石啊（主要就是因為沒錢）。
現在技術更新很快，若是超過三個世代以上沒跟上，後面就跟不太上ㄌ