架構(gòu)師的邏輯技術(shù)思維分析-文庫吧資料
2025-07-03 04:53本頁面
【正文】 另外，遞歸也是一種特殊的分治技術(shù)，掌握遞歸技術(shù)的開發(fā)人員，相當于掌握了一種強大的編程武器，可以解決一些一般開發(fā)人員無法解決的問題。總體上這是一個非常好的面試題，除了考察候選人的分治思維之外，還考察對各種排序算法（快排，外排序，歸并排序，堆排序）的理解，計算的時間空間復(fù)雜度估算，計算機的內(nèi)外存特性和組織，文件操作等等。因為是外排序+歸并排序，每次只需要讀取當前索引指向的文件記錄到內(nèi)存，進行比較，小的那個輸出到目標文件，內(nèi)存占用極少。這個時候該采用什么算法呢？這里考察候選人對外排序和歸并排序算法的掌握程度，我們可以將100個排好序的文件進行兩兩歸并排序，這樣不斷重復(fù)，我們就會得到50個排好序的文件，每個大小是2G。對于1G數(shù)據(jù)量的字符串排序，采用Java里頭提供的快速排序算法是比較合適的。實際上8G內(nèi)存的話，操作系統(tǒng)要用掉一部分，如果用Java開發(fā)排序程序，大致JVM可用2~4G內(nèi)存，基于一般的經(jīng)驗值，一次排1G左右的數(shù)據(jù)應(yīng)該沒有問題（我實際在計算機上干過1G數(shù)據(jù)的排序，是OK的）。這是一個典型的分治問題，100G的大文件肯定無法一次加載到內(nèi)存直接排序，所以需要先切分成若干小問題來解決。三、分治思維分而治之(divide and bine或者split and merge)也是應(yīng)對和管理復(fù)雜性的一般性方法，下圖展示一個分治的思維流程：對于一個無法一次解決的大問題，我們會先把大問題分解成若干個子問題，如果子問題還無法直接解決，則繼續(xù)分解成子子問題，直到可以直接解決的程度，這個是分解(divide)的過程；然后將子子問題的解組合拼裝成子問題的解，再將子問題的解組合拼裝成原問題的解，這個是組合(bine)的過程。分層架構(gòu)的案例很多，一個中小型的Spring Web應(yīng)用程序，我們一般會設(shè)計成三層架構(gòu)：操作系統(tǒng)是經(jīng)典的分層架構(gòu)，如下圖：TCP/IP協(xié)議棧也是經(jīng)典的分層架構(gòu)，如下圖：如果你關(guān)注人類文明演化史，你會發(fā)現(xiàn)今天的人類世界也是以分層方式一層層搭建和演化出來的。有些層次是縱向的，它貫穿所有其它層次，稱為共享層。舉個例子：一個電商網(wǎng)站在處理訂單時，一般會走這樣一個流程：1. 更新庫存(InventoryUpdate)2. 打折計算(Discounting)3. 支付卡校驗(PaycardVerification)4. 支付(Pay)5. 送貨(Shipping)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1