※ 引述《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产业算是会看到满多算法的地方(我还满多没写的)
只是这产业有点老 软件开发方式有点老旧就是了