演算法在前端開發的中實際應用有哪些？

01-04

如題，本人做前端也有8年了，有很多公司面試都需要對數據結構和演算法有要求，但是實際工作中，幾乎沒有用到數據結構和演算法的場景，能想到的也就一個排序和一些可視化圖表了，那麼請問，在實際的前端開發中，數據結構和演算法到底有哪些實際應用，謝謝。

一、從廣義上的演算法定義來講，只要你寫程序就是演算法，把大象裝進冰箱，分三步，就是一個簡單的演算法。

二、從狹義的演算法，就是經典的，分治、動態規劃、排序、數據結構什麼的，有些案例，比如大概7、8年前有個做彩票的朋友問過我彩票批量投注，即買滿含有某個組合所有彩票組合，這個比較典型，屬於動態規劃。又比如前幾天我們討論滾動觸發元素onappear事件的可行性，我提了可以用元素位置做區域哈希，而不是挨個檢查。又比如虛擬dom比對，用到最短編輯距離，也是動態規劃。總之，要寫點複雜的東西，經典演算法是很好用的。

三、面試考個排序之類的，其實不是為了考演算法，而是考編程，說白了就是摘出最簡單最純粹的編程問題，看你寫代碼解決一下，總不能面試讓寫個資料庫或者編譯器吧？

四、其實有些人問這個問題，就是有種潛台詞：工作這麼多年都用不上的知識在面試里考是不合理的，要不是這樣我能進更好的公司。殊不知，面試就是為了過濾你這樣的人。大家都要這麼考，不是因為跟風，而是因為自然選擇：不肯這樣做的公司都倒閉了。

先舉幾個簡單的例子:

廣告屏蔽插件
可能要用到 Boyer-Moore algorithm (見 Adblock Plus and (a little) more).
在線編輯器或 IDE
語法高亮, 自動補全和拼寫檢查等必然離不開經典的詞法語法分析演算法與對應的數據結構.
拓撲圖可視化
可能要用到 Force-directed Layout algorithms (見 Force-Directed Graph 和 Curved Links).
不過這個不是 "經典演算法".

不過話又說回來, 這些大多也都已經有現成的開源庫可以直接使用了, 到底用不用得到取決於你是開車的還是造車的, 以及網上能找得到的開源實現好不好用...

當然, 看待問題也不能太功利, 可能大多數場景下確實用不到那麼多演算法, 只是拿來考察一下思維能力吧.

具體的例子，已經有一些不錯的回答。我補充一個其他的點：當面試官在面試數據結構和演算法的時候，他真正面試你的是什麼：

化繁為簡，直達問題本質的能力。很多面試題都披著或業務或時髦技術的外衣，而且一開始可能還沒有給你充足的信息，那能不能通過獨立思考，和面試官溝通獲得必要的約束和前提，然後透過現象看本質，就是一個很重要的考察點。而演算法本身，就是計算機領域內無數先哲牛人多年積累下來的解決一類通用問題的方法，所以問題的本質一般可以規約到一個或若干演算法
分析判斷的能力。定位到問題本質後，往往會有多種可行的解法，例如第 k 大數，矩陣列印等。那麼哪種解法更好呢？那能不能在掌握多種演算法的基礎上，通過分析時間複雜度、空間複雜度、可維護性等指標進行分析判斷，選擇一個較為匹配當前問題的解法，就是又一個很重要的考察點。這也是我自認為演算法最為精髓的所在。
融會貫通，舉一反三的能力。當你比較好的完成了以上兩個考驗的時候，面試官一般會將問題泛化或者變更，例如放鬆準確性要求來達到更好的性能，來試探你是否能夠靈活運用書面上刻板的知識，快速應變滿足新的需求。

前端工程師首先是工程師，工程師既然是吃計算機這碗飯，我覺得掌握基礎的數據結構和演算法，並能夠理解它們的內涵和外延，就是一個起碼的要求。只有這樣，才能在前端領域日益複雜的未來越走越遠。

好多遞歸都不會寫的人，確定知道DOM是如何遍歷的？

還有一些對數據形態做下轉換都搞不定、循環都寫不利索的人，確定能做程序員？

實際上多數演算法即使在後端開發中也不會天天用，用得到的也都封裝好了

但就算業務中用不到演算法，問的目的也是把這些不會的人給過濾掉

樓上的大神都把例子舉完了，我來說一個大家沒說到的，多級排序：

在頁面中經常需要做表格，而且還要能排序，而且還要能像成績單那樣可以總分相同按語文排，語文相同按數學排，依次類推；而且有些需求還是排序欄位不定的情況，比如下個需求就是先按數學排了；或者是主排序欄位由用戶決定。

這個時候要怎麼做呢，難道是在一個sort里寫很多if來判斷嗎？

實際上這裡只要知道排序演算法有個穩定性的概念，這個就很容易做，但如果不知道，代碼就會寫成一坨屎。

然後如果你知道的話，會發現瀏覽器自帶的排序演算法是不穩定的，那就需要你自己實現一個穩定的排序演算法了。

再舉一例：

樹狀結構比如文件夾的展示，需要樹相關的演算法，就不細說了

如果看不懂我上面說的，說明你需要學學演算法了。

通過canvas進行圖片處理

最近有感而發答一個，答錯勿噴！！！

最近帶個新人前端，有個數據，我後端傳過來是[{key:val}]數組，然後這個東西是應用啟動一次，緩存起來然後拿key 取val ，他就每次用for 循環一遍然後if 比較一遍，取val 。。。提醒他這個不能這樣，應該第一次取到之後就for 一下，變成key—val 對象，以後要取了直接傳key 進去就可以，有就有沒有就undefined 了！

好了，高潮來了

之後過一天有個表格數據，我傳給前端的還是個數組，然後這貨又把數組去拼裝成對象。。。。。。

問他為什麼？

他說:你不是說要變成key_ val 嗎？

?我滿臉黑線。。。

這。。。好像他說的也沒錯噢，無fuck可說，之前是讓他把數組拼裝成對象了！！！

我在想

我到底做錯了什麼？？？

再說下工作二年的感受，無論前端後端，無論多複雜的業務邏輯，其實數據結構清晰了，基本業務也清晰了一半！

所以

堆棧，隊列，列表，集合，字典這幾種基本數據結構還是要有點意識的。。。

不考演算法，怎麼考你的編程能力？難道讓你用100種語言寫hello world 么？

本科數據結構課程里涉及的演算法其實就是編程基礎的一部分，連這些都不會的那肯定是基礎不牢了。

- 處理API裡面的數據，有可能會用到遞歸的，比如導航多層級展開

treeObj parent{ string name treeObj child ... }

- 處理字元串，也可以動態規劃。

返回搜索結構，如果是部分匹配即返回，比如搜索字元ABC，返回ABCABDCABC。頁面需要高亮匹配的部分，類似ABCABDCABC, 當然你可以暴力演算法，但是使用簡單演算法可以提高瀏覽器效率。

我上述幾個例子都是Leetcode中屬於最簡單且通過率非常高的題目，每個程序員（前端也是程序員）都應該在最開始找工作或者（和）前幾年刷刷演算法題，比如Leetcode簡單和中等題（當然大牛們刷刷難題也可以）。

舉個例子：「背包問題「在實際業務中的應用。

某個樹狀語料庫管理界面中，需要用目錄樹（Category Tree）展示不同語料庫，大概長這樣子：

這個玩意，簡單，我會！

首先，遞歸生成節點 -&> 然後，實現「點擊展開」和「點擊摺疊」 -&> 最後，寫點邏輯切換展示的數據，perfect！

然而，問題沒有這麼簡單 (╯‵□′)╯︵┻━┻：

1. 如果目錄樹在初始化時完全摺疊，則用戶體驗很差（每次都要手動展開一個文件夾）。

2. 如果目錄樹在初始化時完全展開，則用戶體驗也很差（展開後太長了要滾來滾去）。

因此，需要一個演算法來指定初始化時，哪些目錄應該展開，哪些目錄應該摺疊。

因此，問題等價於：

對於容量為N的背包，從m個文件夾節點中，選擇k個展開，使得這k個被展開文件夾包含的子節點個數之和最大。（假設N&>0，假設每個文件夾權重一樣，假設每個子節點占像素高度一樣）

（so easy，怎麼實現就不細說了）

==============

然而，還沒完 (╯‵□′)╯︵┻━┻：

1. 如果對每個文件夾「興趣」不一樣，怎麼辦？（需要量化「興趣」，然後加權重）

2. 如果希望嵌套文件夾的子文件夾也能被自動展開，怎麼辦？（有依賴背包問題）

所以你看，有些問題也不是拖個庫，改一改，那麼簡單……

（還有更糾結的，json to json定義唯一映射規則，可以抽象成「類B+樹」映射問題，有空再說）

從事前端快兩年了，之前做react 和node 現在做vue。有個感受就是剛開始工作時候用到了演算法但其實自己並不清楚、就好比用到了設計模式不清楚一樣。後來看了一些文章和書籍，漸漸懂得了一些專業術語。舉幾個例子吧。

1、笛卡兒乘積

返回多個集合的所以組合結果

所有選項的可能合集就是一個笛卡爾乘積。

貼上代碼：

2、快速排序（Quicksort - Wikipedia）

這個也是前端常用的演算法了。（很多時候數組的排序會用sort方法代替）

3、遞歸

遞歸也是前端經常會用到的，比如文件的列隊下載，文件夾底下文件的遍歷。

大概可能是這樣的：

4、當然還有很多其它用到的，比如位元組數轉換成更友好的顯示

數組去重：

當然canvas裡面用到的演算法就更多了

暫時就先這些吧，後面有想到了再繼續補充。

（本人也是一直在學習前端的路上，如果有錯誤的地方，歡迎指正）

舉一個例子，給你一組高度不確定的圖片，需要你去實現一個兩列的瀑布流效果，怎麼去劃分這些圖片才能讓兩列的高度差儘可能小甚至一樣呢？如果你熟悉動態規劃，可能很快就能想到這玩意兒其實就是一個簡單的01背包問題。如果不熟悉的話，估計想破腦袋也很難了

這個問題可否先修修，通順了再談？