Re: [討論] 各位工作上用到演算法的頻率高嗎?
※ 引述《jammy50605 (小刀)》之銘言：
: 小弟我在一家系統廠上班 算是純軟體頂多一點點韌體
: 平常大部分的時間都在解bug 一定是先想python有沒有類似的函式或Linux的指令可以直
: 接用
: 不得不說python真的是懶人版的C 一堆記憶體指標處理的麻煩事都省了 開發之神速
: 有時想學校上了一堆演算法 排序 最短路徑 搜尋樹 DP 圖論 flow network 實際工作上
: 用到的機率少之又少
: 最常用的排序python也有內建sort可用 不常碰C後 氣泡 選擇 快排 都忘的差不多了
: 雖然看到自己的code能進產品賣錢頗爽外
: 工作礙於有出貨死線 客戶會該 不得不以最短時限內能夠正常運行為主
: 很少會有時間讓你慢慢思考能不能有更好的演算法來解決問題
: 是碼農在台灣軟體業的生態都差不多嗎?
: 還是有哪位神人可以分享自己在工作中遇到什麼問題需要用到高超的演算法呢?
EDA產業(Ex:Synopsys, Candance, ATopTech做的是IC Designer用的tool)
就會碰到很多演算法
因為IC內部可以想成在三維空間中
非常多非常多細微的線
這些線需要把非常多方塊連在一起
那麼問題就來了
方塊要怎麼擺 整個面積才會比較小
而且擺的時候要估計線有沒有辦法連得好 不能打架
而且因為製程技術(像台積電和Samsung就不一樣)和物理現象的關系
會有很多限制
例如說這條線走這樣 旁邊一條線走的時候就不能怎樣怎樣
這條線走太長了造成blahblah 必須加某個方塊連上去… 諸如此類
所以為了擺方塊 有跟擺方塊相關的演算法
你說方塊擺了一堆 線都還沒連 怎麼知道會不會有些太長 甚至線連不起來
所以擺的時候就要估計線多長
這時候就會用到像minimum spanning tree(MST)之類的來估計
而CS常用的那本IOA講的graph的edge大都是只能把2個點連起來
電線因為可以分枝 所以常用的會是steiner tree
而且電線通常走直角
所以估計時也有可能用rectilinear minimum steiner tree(RMST)
這些很多相關論文 像是說用MST來估 和RMST來估 會差多少
這裡扯遠了 總之IOA講的MST這產業常用
而且這種都不是library拿來用就好 因為很多細節 都是自幹
再來就是方塊擺好之後要怎麼連
這時候就會有A*之類的演算法了
這裡有很多問題要研究
例如說如果你是一組方塊連好再連下一組
而且一開始都走最短 連得很開心
那連到後來線越來越多 就越來越難連了
搞不好前面連得太爽 害後面的連不起來
上面這2大主題在這產業叫做placement & route (P&R)
其它像是排序 有的(ㄅㄣˇ)公司也是自幹
有個introsort 在元素數12以下時用insertion sort 超過就用merge sort
也有自幹的quicksort
紅黑樹做的map、vector、link list也是自幹
那為什麼要自幹？我也不知道
說是要接自幹的memory pool(可能是不會用STL和allocator)
我只知道不能用STL寫得很幹
另外像DP這種就看要不要用而已
我有遇過某個類似背包問題的問題，要用DP去算也是可以
但最後發現要解的東西算個大略值就好，就別的方式快速算過
而BFS DFS這種是家常便飯 因為常常要在電線上traverse
總之EDA產業算是會看到滿多演算法的地方(我還滿多沒寫的)
只是這產業有點老 軟體開發方式有點老舊就是了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.65.150
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1465474881.A.0F5.html
推
06/09 20:45, , 1F
06/09 20:45, 1F
推
06/09 21:44, , 2F
06/09 21:44, 2F
推
06/09 21:48, , 3F
06/09 21:48, 3F
推
06/09 22:03, , 4F
06/09 22:03, 4F
推
06/09 23:42, , 5F
06/09 23:42, 5F
推
06/09 23:45, , 6F
06/09 23:45, 6F
stl那一段主要是在講有的公司禁止(或不建議)用STL
其實這產業很老了 大老都是在C++之前的時代
以前是自幹 所以就用到現在了 我猜這是最主要原因
再補充一下
這整個tool chain還有很多東西 這裡只是寫P&R的部份 還有很多其它重要的
但進來不一定會做到核心的部份
如果有認識的最好問問看
※ 編輯: Arton0306 (118.168.65.150), 06/10/2016 02:31:18
推
06/10 05:36, , 7F
06/10 05:36, 7F
→
06/10 05:37, , 8F
06/10 05:37, 8F
推
06/10 10:48, , 9F
06/10 10:48, 9F
推
06/10 13:02, , 10F
06/10 13:02, 10F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：