標籤: 南投搬家費用

導言

動態規劃問題一直是算法面試當中的重點和難點，並且動態規劃這種通過空間換取時間的算法思想在實際的工作中也會被頻繁用到，這篇文章的目的主要是解釋清楚 什麼是動態規劃，還有就是面對一道動態規劃問題，一般的 思考步驟 以及其中的注意事項等等，最後通過幾道題目將理論和實踐結合。

什麼是動態規劃

如果你還沒有聽說過動態規劃，或者僅僅只有耳聞，或許你可以看看 Quora 上面的這個 回答。

How to explain dynamic

用一句話解釋動態規劃就是 “記住你之前做過的事”，如果更準確些，其實是 “記住你之前得到的答案”。

我舉個大家工作中經常遇到的例子。

在軟件開發中，大家經常會遇到一些系統配置的問題，配置不對，系統就會報錯，這個時候一般都會去 Google 或者是查閱相關的文檔，花了一定的時間將配置修改好。

過了一段時間，去到另一個系統，遇到類似的問題，這個時候已經記不清之前修改過的配置文件長什麼樣，這個時候有兩種方案，一種方案還是去 Google 或者查閱文檔，另一種方案是借鑒之前修改過的配置，第一種做法其實是萬金油，因為你遇到的任何問題其實都可以去 Google，去查閱相關文件找答案，但是這會花費一定的時間，相比之下，第二種方案肯定會更加地節約時間，但是這個方案是有條件的，條件如下：

• 之前的問題和當前的問題有着關聯性，換句話說，之前問題得到的答案可以幫助解決當前問題
• 需要記錄之前問題的答案

當然在這個例子中，可以看到的是，上面這兩個條件均滿足，大可去到之前配置過的文件中，將配置拷貝過來，然後做些細微的調整即可解決當前問題，節約了大量的時間。

不知道你是否從這些描述中發現，對於一個動態規劃問題，我們只需要從兩個方面考慮，那就是 找出問題之間的聯繫，以及 記錄答案，這裏的難點其實是找出問題之間的聯繫，記錄答案只是順帶的事情，利用一些簡單的數據結構就可以做到。

概念

上面的解釋如果大家可以理解的話，接

  動態規劃算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。它的幾個重要概念如下所述。

  階段：對於一個完整的問題過程，適當的切分為若干個相互聯繫的子問題，每次在求解一個子問題，則對應一個階段，整個問題的求解轉化為按照階段次序去求解。

  狀態：狀態表示每個階段開始時所處的客觀條件，即在求解子問題時的已知條件。狀態描述了研究的問題過程中的狀況。

  決策：決策表示當求解過程處於某一階段的某一狀態時，可以根據當前條件作出不同的選擇，從而確定下一個階段的狀態，這種選擇稱為決策。

  策略：由所有階段的決策組成的決策序列稱為全過程策略，簡稱策略。

  最優策略：在所有的策略中，找到代價最小，性能最優的策略，此策略稱為最優策略。

  狀態轉移方程：狀態轉移方程是確定兩個相鄰階段狀態的演變過程，描述了狀態之間是如何演變的。

思考動態規劃問題的四個步驟

一般解決動態規劃問題，分為四個步驟，分別是

• 問題拆解，找到問題之間的具體聯繫
• 狀態定義
• 遞推方程推導
• 實現

這裏面的重點其實是前兩個，如果前兩個步驟順利完成，後面的遞推方程推導和代碼實現會變得非常簡單。

這裏還是拿 Quora 上面的例子來講解，“1+1+1+1+1+1+1+1” 得出答案是 8，那麼如何快速計算 “1+ 1+1+1+1+1+1+1+1”，我們首先可以對這個大的問題進行拆解，這裏我說的大問題是 9 個 1 相加，這個問題可以拆解成 1 + “8 個 1 相加的答案”，8 個 1 相加繼續拆，可以拆解成 1 + “7 個 1 相加的答案”，… 1 + “0 個 1 相加的答案”，到這裏，第一個步驟 已經完成。

狀態定義 其實是需要思考在解決一個問題的時候我們做了什麼事情，然後得出了什麼樣的答案，對於這個問題，當前問題的答案就是當前的狀態，基於上面的問題拆解，你可以發現兩個相鄰的問題的聯繫其實是 后一個問題的答案 = 前一個問題的答案 + 1，這裏，狀態的每次變化就是 +1。

定義好了狀態，遞推方程就變得非常簡單，就是 dp[i] = dp[i - 1] + 1，這裏的 dp[i] 記錄的是當前問題的答案，也就是當前的狀態，dp[i - 1] 記錄的是之前相鄰的問題的答案，也就是之前的狀態，它們之間通過 +1 來實現狀態的變更。

最後一步就是實現了，有了狀態表示和遞推方程，實現這一步上需要重點考慮的其實是初始化，就是用什麼樣的數據結構，根據問題的要求需要做那些初始值的設定。

public int dpExample(int n) {
    int[] dp = new int[n + 1];  // 多開一位用來存放 0 個 1 相加的結果

    dp[0] = 0;      // 0 個 1 相加等於 0

    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
    }

    return dp[n];
}

你可以看到，動態規劃這四個步驟其實是相互遞進的，狀態的定義離不開問題的拆解，遞推方程的推導離不開狀態的定義，最後的實現代碼的核心其實就是遞推方程，這中間如果有一個步驟卡殼了則會導致問題無法解決，當問題的複雜程度增加的時候，這裏面的思維複雜程度會上升。

接下來我們再來看看 LeetCode 上面的幾道題目，通過題目再來走一下這些個分析步驟。

題目實戰

爬樓梯

但凡涉及到動態規劃的題目都離不開一道例題：爬樓梯（LeetCode 第 70 號問題）。

題目描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

題目解析

爬樓梯，可以爬一步也可以爬兩步，問有多少種不同的方式到達終點，我們按照上面提到的四個步驟進行分析：

• 問題拆解：

  我們到達第 n 個樓梯可以從第 n – 1 個樓梯和第 n – 2 個樓梯到達，因此第 n 個問題可以拆解成第 n – 1 個問題和第 n – 2 個問題，第 n – 1 個問題和第 n – 2 個問題又可以繼續往下拆，直到第 0 個問題，也就是第 0 個樓梯 (起點)

• 狀態定義

  “問題拆解” 中已經提到了，第 n 個樓梯會和第 n – 1 和第 n – 2 個樓梯有關聯，那麼具體的聯繫是什麼呢？你可以這樣思考，第 n – 1 個問題裏面的答案其實是從起點到達第 n – 1 個樓梯的路徑總數，n – 2 同理，從第 n – 1 個樓梯可以到達第 n 個樓梯，從第 n – 2 也可以，並且路徑沒有重複，因此我們可以把第 i 個狀態定義為 “從起點到達第 i 個樓梯的路徑總數”，狀態之間的聯繫其實是相加的關係。

• 遞推方程

  “狀態定義” 中我們已經定義好了狀態，也知道第 i 個狀態可以由第 i – 1 個狀態和第 i – 2 個狀態通過相加得到，因此遞推方程就出來了 dp[i] = dp[i - 1] + dp[i - 2]

• 實現

  你其實可以從遞推方程看到，我們需要有一個初始值來方便我們計算，起始位置不需要移動 dp[0] = 0，第 1 層樓梯只能從起始位置到達，因此 dp[1] = 1，第 2 層樓梯可以從起始位置和第 1 層樓梯到達，因此 dp[2] = 2，有了這些初始值，後面就可以通過這幾個初始值進行遞推得到。

參考代碼

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }

    int[] dp = new int[n + 1];  // 多開一位，考慮起始位置

    dp[0] = 0; dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

三角形最小路徑和

LeetCode 第 120 號問題：三角形最小路徑和。

題目描述

給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。

例如，給定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

說明：

如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題，那麼你的算法會很加分。

題目解析

給定一個三角形數組，需要求出從上到下的最小路徑和，也和之前一樣，按照四個步驟來分析：

• 問題拆解：

  這裏的總問題是求出最小的路徑和，路徑是這裏的分析重點，路徑是由一個個元素組成的，和之前爬樓梯那道題目類似，[i][j] 位置的元素，經過這個元素的路徑肯定也會經過 [i - 1][j] 或者 [i - 1][j - 1]，因此經過一個元素的路徑和可以通過這個元素上面的一個或者兩個元素的路徑和得到。

• 狀態定義

  狀態的定義一般會和問題需要求解的答案聯繫在一起，這裏其實有兩種方式，一種是考慮路徑從上到下，另外一種是考慮路徑從下到上，因為元素的值是不變的，所以路徑的方向不同也不會影響最後求得的路徑和，如果是從上到下，你會發現，在考慮下面元素的時候，起始元素的路徑只會從[i - 1][j] 獲得，每行當中的最後一個元素的路徑只會從 [i - 1][j - 1] 獲得，中間二者都可，這樣不太好實現，因此這裏考慮從下到上的方式，狀態的定義就變成了 “最後一行元素到當前元素的最小路徑和”，對於 [0][0] 這個元素來說，最後狀態表示的就是我們的最終答案。

• 遞推方程

  “狀態定義” 中我們已經定義好了狀態，遞推方程就出來了

  dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
  

• 實現

  這裏初始化時，我們需要將最後一行的元素填入狀態數組中，然後就是按照前面分析的策略，從下到上計算即可

參考代碼

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();

    int[][] dp = new int[n][n];

    List<Integer> lastRow = triangle.get(n - 1);

    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = lastRow.get(i);
    }

    for (int i = n - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }

    return dp[0][0];
}

最大子序和

LeetCode 第 53 號問題：最大子序和。

題目描述

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

題目解析

求最大子數組和，非常經典的一道題目，這道題目有很多種不同的做法，而且很多算法思想都可以在這道題目上面體現出來，比如動態規劃、貪心、分治，還有一些技巧性的東西，比如前綴和數組，這裏還是使用動態規劃的思想來解題，套路還是之前的四步驟：

• 問題拆解：

  問題的核心是子數組，子數組可以看作是一段區間，因此可以由起始點和終止點確定一個子數組，兩個點中，我們先確定一個點，然後去找另一個點，比如說，如果我們確定一個子數組的截止元素在 i 這個位置，這個時候我們需要思考的問題是 “以 i 結尾的所有子數組中，和最大的是多少？”，然後我們去試着拆解，這裏其實只有兩種情況：

• i 這個位置的元素自成一個子數組

• i 位置的元素的值 + 以 i – 1 結尾的所有子數組中的子數組和最大的值

  你可以看到，我們把第 i 個問題拆成了第 i – 1 個問題，之間的聯繫也變得清晰

• 狀態定義

  通過上面的分析，其實狀態已經有了，dp[i] 就是 “以 i 結尾的所有子數組的最大值”

• 遞推方程

  拆解問題的時候也提到了，有兩種情況，即當前元素自成一個子數組，另外可以考慮前一個狀態的答案，於是就有了

  dp[i] = Math.max(dp[i - 1] + array[i], array[i])
  

  化簡一下就成了：

  dp[i] = Math.max(dp[i - 1], 0) + array[i]
  

• 實現

  題目要求子數組不能為空，因此一開始需要初始化，也就是 dp[0] = array[0]，保證最後答案的可靠性，另外我們需要用一個變量記錄最後的答案，因為子數組有可能以數組中任意一個元素結尾

參考代碼

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;

    int[] dp = new int[n];

    dp[0] = nums[0];

    int result = dp[0];

    for (int i = 1; i < n; ++i) {
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        result = Math.max(result, dp[i]);
    }

    return result;
}

總結

通過這幾個簡單的例子，相信你不難發現，解動態規劃題目其實就是拆解問題，定義狀態的過程，嚴格說來，動態規劃並不是一個具體的算法，而是凌駕於算法之上的一種 思想 。

這種思想強調的是從局部最優解通過一定的策略推得全局最優解，從子問題的答案一步步推出整個問題的答案，並且利用空間換取時間。從很多算法之中你都可以看到動態規劃的影子，所以，還是那句話 技術都是相通的，找到背後的本質思想是關鍵。

公眾號：五分鐘學算法（ID：CXYxiaowu）
博客：www.cxyxiaowu.com（目前更新了 500 篇算法文章，歡迎訪問學習）
知乎：程序員吳師兄
一個正在學習算法的人，致力於將算法講清楚​！

​

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

摘錄自2019年12月21日中央社報導

日本京都新聞報導，包括滋賀縣在內的京阪神近郊區域，及JR西日本公司福知山支社轄區內，今年秋天電車撞上野生動物的次數較去年同期增加大約25%，在這些野生動物遭電車撞擊事件中，多數是梅花鹿遭殃，最主要原因是梅花鹿數量本來就持續增加，根據日本政府環境省調查推估，2017年度結束時，日本共有約244萬頭梅花鹿，數量是30年前的8倍。

示意圖，轉載自Unsplash免費圖庫

日鐵建材公司研究發現，鹿群為補充鐵質會舔食鐵軌。基於這項研究成果，日鐵建材公司開發出混合鐵質與鹽份、能引誘鹿群舔食的產品，讓鹿群攝取後就不會靠近鐵軌，以避免被電車撞上。只不過，如果真的有效，就無法解釋今年秋天電車撞上鹿群的事故為何會增加。

因此有另一種看法指出，單以今年來說，也許跟鹿群主食的橡子（團栗）歉收有關。橡子歉收造成亞洲黑熊出沒村落覓食案例增加。

※ 本文與 行政院農業委員會 林務局   合作刊登

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

進程調度原因及調度切換時機，進程調度方式與實現及各種調度算法的個人總結：

1.一般調度概念 1）什麼是調度 就是選出待分派的作業或進程。 操作系統管理了系統的有限資源，當有多個進程（或作業）發出請求要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（或作業）來佔用資源。這就是調度。

2）調度目的 1.控制資源使用者的數量 2.選取資源使用者 3.許可哪些使用者佔用資源 4.讓使用者直接佔用資源。

二、調度類型 1、高級調度(長程調度)。 即作業調度，選取輸入井中的作業，生成根進程。目的是控制使用系統資源的進程數。

2、中級調度（中程調度）。 指選取進程佔用內存或有資格佔用內存，又稱進程滾入滾出，中級調度將在存儲管理章節中介紹，有頁式調度、段式調度、段頁式調度等。

3、低級調度（短程調度） 指選取進程佔用處理機,又稱進程調度。 4、I/O調度 選取進程佔用I/O設備。

三、調度和狀態轉換 在許多系統中，調度被分為三種：長程、中程和短程。 1）調度和進程狀態轉換

從狀態轉換的觀點： 1、長程調度（作業調度）就是將一個或一批作業從後備狀態變為運行狀態。一個作業一旦被高級調度選中，便可獲得所需要的基本內存和設備資源，並被裝入內存，此後就以進程形式參与併發執行，與其它進程競爭CPU。

從狀態轉換的觀點： 2、中程調度就是將進程從活動態變為靜止的掛起態，或者將進程從掛起態變為就緒或阻塞態。 3、短程調度就是將某個進程從就緒態變為(在CPU上運行的)執行態。

2）調度的層次（調度作用的嵌套關係）

3）三級調度示意圖 調度從根本上講，是要使隊列延遲的時間最小，並優化系統的執行效率

4.1.2作業調度的功能

①記錄系統中各個作業的情況。 ②按照某種調度算法從後備作業隊列中挑選作業，即決定接納多少個作業進入內存和挑選哪些作業進入內存。

③為選中的作業分配內存和外設等資源。 ④為選中的作業建立相應的進程，並把該進程放入就緒隊列中。 ⑤作業結束後進行善後處理工作。如輸出必要的信息，收回該作業所佔用的全部資源，撤消與該作業相關的全部進程和該作業的JCB 。

4.1.3進程調度的功能與調度時機 一、進程調度的功能 (1)保存現場(2)挑選進程(3)恢復現場

二、進程調度的時機 一般在下列事件發生后要執行進程調度。 （1）創建進程。 當進程創建時，要決定是運行父進程還是子進程。 （2）進程終止。 （3）等待事件。 （4）中斷髮生。 （5）運行到時。

4.1.4進程調度的基本方式 1）非剝奪調度（非搶佔） 只有當處理機上的進程主動放棄處理機時，才重新調度。 2）剝奪調度（搶佔） 當進程運行時可以被系統以某種原則為由剝奪其處理機。

例：只有一部電話機，小李正在通電話，此時小張有急事也要打電話，此時小張的調度方式有兩種： 一種是非搶佔，即等待小李打完電話，自己再打電話。 另一種是搶佔，不等小李通完電話，搶過話筒就撥打電話。

3）進程調度在核心態進行。 CPU狀態有兩種，目態和管態。 管態——也稱核心態或系統態，系統程序在CPU上運行的狀態。 目態——用戶程序在CPU上運行的狀態。

4.2 調度算法 4.2.1 常用的調度算法

1. FCFS 誰先到就緒隊列就將處理機分給誰。 2. 短作業優先 取一個下次所需運行時間最短的作業(該算法能使平均等待時間最短)。

3. 優先級調度 選優先級最高的進程佔用處理機（優先級可動態改變）。 4.輪轉調度法 以先來後到的次序+ 時間片輪轉。

5.多隊列調度法 按屬性將就緒進程分類,不同類進程可有不同的調度算法。 6.多級反饋隊列調度法 設置多條就緒隊列,進程被調度執行后,在被剝奪或放棄處理機后而在就緒時，可以改變其就緒隊列(見下圖）。

又一個多級反饋隊列調度算法的例子：使用優先權實現調度。做法如下：

（1）以優先級設置多隊列。 （2）各隊列的調度算法採用FCFS+時間片輪轉. （3）進程優先級升降原則是:等待過久升,輸入/輸出完成時升,運行完一個完整時間片降……

（4）進程最初進入就緒隊列以用戶初置優先級為參數。 （5）開始調度時，先從最高優先權的就緒隊列（RQ0）開始選取一個進程，如果RQ0空，則檢查RQ1，如此下去。見下圖示：

4.2.2 調度策略的討論

一、調度性能評價準則 1、CPU利用率。 2、吞吐率。即每單位時間所完成的作業數目。 3、周轉時間。即從作業提交直至完成這一作業的時間間隔。

4、等待時間。即作業在就緒隊列中等待所花的時間。 5、響應時間。即從作業提交到首次產生回答信息之間的時間。

二、主要的調度算法 下面以表所示的進程集作為範例討論不同的調度策略。 到達時間：進程或作業提交時間。 服務時間：進程要求服務的時間，或完成作業所需的時間。

一、FCFS調度策略（或先進先出）

FCFS策略更適合於長進程。例：

注：周轉時間=完成時間—到達時間 tq/ts ：帶權周轉時間=周轉時間/服務時間

（1）進程C的等待標準化時間是不能容忍的。它位於系統的總時間是它所需服務時間的100倍。無論何時，一個長進程到后，一個短進程就會出現較長的等待。 （2）進程D的標準化等待時間尚可容忍，小於2.0。進程D的輪轉時間差不多是C的兩倍。

總結： FCFS（First Come First Served）即先來先服務，故它的本質是非搶佔的。它簡單易行，但調度性能較差，有可能使短的、重要的或緊迫的作業等進程長期等待，其實現過程容易，可採用FIFO隊列管理。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

目錄

示例代碼託管在：

博客園地址：

華為雲社區地址：

附件PPT來自開發文檔。術語里的cc指的是Chromium Compositor

一直以來都想了解瀏覽器合成層的運作機制，但是相關的中文資料大多比較關注框架和開發技術，這方面的資料實在是太少了，後來在chromium官方網站的文檔里找到了項目組成員malaykeshav在 2019年4月的一份關於瀏覽器合成流水線的演講PPT，個人感覺裏面講的非常清楚了，由於沒有找到視頻，有些部分只能自行理解，本文僅對關鍵信息做一些筆記，對此感興趣的讀者可以在文章開頭的github倉庫或附件中拿到這個PPT自行學習。

摘要

1.合成流水線

合成流水線，就是指瀏覽器處理合成層的工作流程，其基本步驟如下：

大致的流程就是說Paint環節會生成一個列表，列表裡登記了頁面元素的繪製指令，接着這個列表需要經過Raster光柵化處理，並在合成幀中處理紋理，最後的Draw環節才是將這些紋理圖展示在瀏覽器內容區。

2. 預定義UI層

chromium中預定義了一些指定類型的UI層，大致分為：

• Not Drawn – 為了處理透明度或濾鏡效果、transform變形或者clip剪裁的非繪製層
• Solid color layer – 固有顏色層
• Painted texture layer – Texture紋理會在這個層執行paint渲染和後續的rasterized光柵化任務
• Transferable resource layer – 共享資源層，可能是GPU裏面的Texture紋理也可能未來會發給GPU的位圖
• Surface layer – 臨時佔位層，因為自頂向下遍歷layer樹時子樹都還沒處理，需要先佔位最後再填充
• Nine patch layer – 用於實現陰影的層

3. paint是什麼意思

每個層layer是由若干個views組成的，所謂paint，就是每個views將自己對應圖形的繪製指令添加到層的可展示元素列表Display Item List里，這個列表會被添加到一個延遲執行的光柵化任務中，並最終生成當前層的texture紋理（可以理解為當前層的繪製結果），考慮到傳輸性能以及未來增量更新的需求，光柵化的結果會以tiles瓦片形式保存。在chrome中也可以看到頁面瓦片化拆分的結果:

4. 分層的優勢和劣勢

分層的優勢和劣勢也在此進行了說明，和之前我們主動思考的答案基本一致（暗爽一下）。

5. 視圖屬性及其處理方式

views中支持的屬性包含Clip剪裁，transform變換,effect效果（如半透明或濾鏡等）,mask遮罩，通常按照後序遍歷的方式自底向上進行遍歷處理。

clip剪裁的處理方式是在父節點和子節點之間插入一個剪裁層，用來將其子樹的渲染結果剪裁到限定的範圍內，然後再向上與父級進行合併；

transform變換直接作用於父節點，處理到這個節點時其子樹都已經處理完畢，直接將整體應用變形即可；

effect效果一般直接作用於當前處理的節點，有時也會產生交叉依賴的場景；

PPT第40頁中在介紹effect效果處理時描述了兩種不同的透明度處理需求，從而引出了一個Render Surface的概念，它相當於一個臨時的層，它的子樹需要先繪製在這個層上，然後再向上與父節點進行合併，屏幕就是是根級的Render Surface。

6. Quads

Layer遍歷處理輸出的結果被稱為Quads（從意思上理解好像就是指輸出了很多個矩形方塊），每個quad都持有它被繪製到目標緩衝區所需要的資源，根據它持有的資源不同可以分為：

• Solid Color-固定顏色型
• Texture– 紋理型
• Tile– 瓦片型
• Surface– 臨時繪圖表面型
• Video – 視頻幀型
• Render Pass – Render Surface類型的佔位區，Render Surface子樹處理完后填充到關聯的Render Pass

7. Compositor Frame

合成層真正的工作要開始了，主角概念Compositor Frame(合成幀)登場，它負責將quads合併繪製在一起，膠片里59-62頁非常清楚地展示了合成的過程，最終輸出的結果就是根節點的紋理。

chromium是多進程架構，Browser Process瀏覽器進程會對菜單欄等等容器部分的畫面生成合成幀來輸出，每個網頁的Render Process渲染進程會對頁面內容生成合成幀來輸出，最終的結果都被共享給GPU ProcessGPU進程進行聚合併生成最終完整的合成表面，接着在Display Compositor環節將最後的位圖展示在屏幕上。

8. 關於光柵化以及渲染方式

膠片里並沒有描述具體的光柵化的處理過程，但是layer輸出的quads看起來應該是光柵化以後的結果，推測應該是處理Display Item List中的繪圖指令時也和WebGL類似，經過頂點着色器和片元着色器的遍歷式處理機制，並在過程中自動完成像素插值。

9.【重要】軟件渲染和硬件渲染的區別

聲明：本節內容是個人理解，僅用作技術交流，不保證對！

軟件渲染和硬件渲染的區別對筆者而言一直非常抽象，只是知道基本概念。後來在（國內可能無法訪問）中《Compositor Thread Architecture》這篇合成器線程架構的文章中找到了一些相關描述，也解開了筆者心中一直以來的疑惑，相關部分摘抄如下：

Texture Upload

One challenge with all these textures is that we rasterize them on the main thread of the renderer process, but need to actually get them into the GPU memory. This requires handing information about these textures (and their contents) to the impl thread, then to the GPU process, and once there, into the GL/D3D driver. Done naively, this causes us to copy a single texture over and over again, something we definitely don’t want to do.

We have two tricks that we use right now to make this a bit faster. To understand them, an aside on “painting” versus “rasterization.”

• Painting is the word we use for telling webkit to dump a part of its RenderObject tree to a GraphicsContext. We can pass the painting routine a GraphicsContext implementation that executes the commands as it receives them, or we can pass it a recording context that simply writes down the commands as it receives them.
• Rasterization is the word we use for actually executing graphics context commands. We typically execute the rasterization commands with the CPU (software rendering) but could also execute them directly with the GPU using Ganesh.
• Upload: this is us actually taking the contents of a rasterized bitmap in main memory and sending it to the GPU as a texture.With these definitions in mind, we deal with texture upload with the following tricks:
• Per-tile painting: we pass WebKit paint a recording context that simply records the GraphicsContext operations into an SkPicture data structure. We can then rasterize several texture tiles from that one picture.
• SHM upload: instead of rasterizing into a void* from the renderer heap, we allocate a shared memory buffer and upload into that instead. The GPU process then issues its glTex* operations using that shared memory, avoiding one texture copy.The holy grail of texture upload is “zero copy” upload. With such a scheme, we manage to get a raw pointer inside the renderer process’ sandbox to GPU memory, which we software-rasterize directly into. We can’t yet do this anywhere, but it is something we fantasize about.

大概翻譯一下，方便英語水平一般的小夥伴理解，GPU處理圖片的方式是按照Texture進行貼圖的，對此不熟悉的小夥伴可以查看筆者以前發的有關Three.js相關的博文。

紋理上傳:
處理紋理的挑戰之一就是它是在渲染進程（可以理解為單個Tab網頁的進程）的主線程里進行的，但是最終需要將其放入GPU內存。這就需要將紋理數據遞交給合成器線程，然後再交給GPU進程（Chromium架構里有專門的GPU進程用來專門處理和GPU之間的協作任務），最後再傳遞給底層的Direct3D或OpenGL（也就是圖形學的底層技術），如果只是按照常規流程來處理，就會需要一次又一次來複制生成的紋理數據，這顯然不是我們想要的。
我們現在使用了兩個小方法來使這個流程變得快一點。它們分別作用於painting（繪製）和rasterization（光柵化）兩個階段。

• 1號知識點！！！Painting我們用來告訴webkit為RenderObject Tree的來生成對應的GraphicsContext。通過給painting routine（繪製流程）傳遞一個GraphicsContext的具體實現來執行這些已經編排好的繪製命令，也可以傳遞一個record context（記錄上下文）只是簡單地把繪圖命令都記錄下來。
• 2號知識點！！！Rasterization（光柵化）是指Graphics context關聯的繪圖命令實際被執行的過程。通常我們使用CPU（也就是軟件渲染的方式）來執行光柵化任務，也可以直接使用GPU來渲染（也就是硬件渲染的方式）。
• 上傳：指在主線程存儲區獲取到光柵化以後的位圖內容然後將它作為紋理上傳給GPU的過程，考慮到上述已經提及的定義，上傳過程是如下來處理的：
  • 瓦片繪製：我們在webkit中使用recording context來簡單地記錄Graphics Context的操作指令，將它存儲為SkPicture類型（直接使用軟件光柵化時生成的是SkBitmap類型），隨後可以從一張picture裏面光柵化處理得到多個紋理瓦片。
  • 共享內存：在軟件渲染的方式中，光柵化的結果會被存儲在renderer進程的堆內存里，現在不這樣搞了，我們重新分配了一塊共享緩衝區，然後通過它來傳遞相關對象，GPU進程隨後在獲取紋理時直接從共享內存中獲取就行了，這樣就避免了數據的拷貝。
    總的來說，紋理上傳的過程幾乎是零拷貝的。利用這樣的結構，我們在renderer進程（也就是網頁的渲染進程）的沙箱環境內也可以獲取到指向GPU 內存的指針，而在軟件光柵化的過程中，是直接將位圖結果放在這裏的。

• Painting: this is the process of asking Layers for their content. This is where we ask webkit to tell us what is on a layer. We might then rasterize that content into a bitmap using software, or we might do something fancier. Painting is a main thread operation.
• Drawing: this is the process of taking the layer tree and smashing it together with OpenGL onto the screen. Drawing is an impl-thread operation.
• painting:表示的過程是向Layers對象查詢層內容，也就是讓webkit告訴我們每一層上面到底有什麼。接下來我們就可以使用軟件光柵化的方式將這些內容處理為位圖，也可以做一些更牛的事情，painting是一個主線程行為。
• drawing：是指將Layer中的內容用OpenGL繪製在屏幕上的過程，它是另一個線程中的操作。

概念比較多沒有基礎的讀者可能理解起來有難度，我嘗試用自己的話複述一下：

【軟件渲染】的模式下，在paint時會直接利用Graphics Context繪圖上下文將結果繪製出來，在一個SkBitmap實例中保存為位圖信息；【硬件渲染】的模式下，在paint時傳入一個SkPicture實例，將需要執行的繪圖命令保存在裏面先不執行，然後通過共享內存將它傳給GPU進程，藉助GPU來最終去執行繪圖命令，生成多個瓦片化的位圖紋理結果（OpenGL中頂點着色器向片元着色器傳遞數據時可以自動進行數據插值，完成光柵化的任務）。 純軟件渲染里嚴格說是沒有合成層概念的，因為最終輸出的只有一張位圖，按照順序從下往上畫，和畫到一個新層上再把新層貼到已有結果上其實是一樣的。

不管使用哪種途徑，paint動作都是得到位圖數據，而最終的draw這個動作是藉助OpenGL和位圖數據最終把圖形显示在显示器上。

所以【硬件渲染】就是渲染進程把要做的事情和需要的數據都寫好，然後打包遞給GPU讓它去幹活。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

最近，我們對新版博客後台（Angular 8.2.7 + .NET Core 3.0）進行了灰度發布，如果您訪問博客後台時跳轉到 ，說明使用的就是新版博客後台。

今天我們在一次基於 gitlab-ci 的自動化發布過程中，由於操作問題在發布前沒有對 appsettings.Production.json 的修改進行保存，造成容器在啟動時使用了舊版的配置文件，再加上容器的健康檢查不能檢查出這種不正常情況（這個地方的改進還沒完成），最不該的是在發布后沒有對關鍵功能進行測試驗證以及值班人員沒有及時處理用戶反饋，從而造成 18:22~19:27 期間使用新版博客后的用戶無法正常發布博文，非常抱歉由此給您帶來了麻煩，請您諒解。

我們會吸取教訓，並採取以下改進措施：

• 更高優先級改進健康檢查。一是容器的健康檢查，二是阿里云云監控的健康檢查。當關鍵功能不可用時，讓健康檢查失敗（之前的健康檢查沒有對業務功能進行檢查）。這樣發布時如果出現問題，容器健康檢查失敗，docker swarm 就不會部署新容器。當正在運行的容器出現問題影響關鍵功能的使用時及時報警。
• 盡可能實現在生產環境發布後用“機器人”對關鍵功能進行測試驗證。
• 每次自動化發布時在值班群發消息通知值班人員留意用戶反饋。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

面試的時候，常常會問數組和鏈表的區別，很多人都回答說，“鏈表適合插入、刪除，時間複雜度O(1)；數組適合查找，查找時間複雜度為O(1)”。實際上，這種表述是不準確的。數組是適合查找操作，但是查找的時間複雜度並不為O(1)。即便是排好序的數組，你用二分查找，時間複雜度也是O(logn)。所以，正確的表述應該是，數組支持隨機訪問，根據下標隨機訪問的時間複雜度為O(1)。

每一種編程語言中，基本都會有數組這種數據類型。不過，它不僅僅是一種編程語言中的數據類型，還是一種最基礎的數據結構。儘管數組看起來非常基礎、簡單，但是我估計很多人都並沒有理解這個基礎數據結構的精髓。在大部分編程語言中，數組都是從0開始編號的，但你是否下意識地想過，為什麼數組要從0開始編號，而不是從1開始呢？ 從1開始不是更符合人類的思維習慣嗎？帶着這個問題來學習接下來的內容,帶着問題去學習往往效果會更好！！！

什麼是數組？我估計你心中已經有了答案。不過，我還是想用專業的話來給你做下解釋。數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。這個定義里有幾個關鍵詞，理解了這幾個關鍵詞，我想你就能徹底掌握數組的概念了。下面就從我的角度分別給你“點撥”一下。

第一是線性表（Linear List）。顧名思義，線性表就是數據排成像一條線一樣的結構。每個線性表上的數據最多只有前和后兩個方向。其實除了數組，鏈表、隊列、棧等也是線性表結構。而與它相對立的概念是非線性表，比如二叉樹、堆、圖等。之所以叫非線性，是因為，在非線性表中，數據之間並不是簡單的前後關係。

第二個是連續的內存空間和相同類型的數據。正是因為這兩個限制，它才有了一個堪稱“殺手鐧”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數組的很多操作變得非常低效，比如要想在數組中刪除、插入一個數據，數組為了保持內存數據的連續性，會導致插入、刪除這兩個操作比較低效,相反的數組查詢則高效

數組java代碼：

package array;

/**
 * 1) 數組的插入、刪除、按照下標隨機訪問操作；
 * 2）數組中的數據是int類型的；
 *
 * Author: Zheng
 * modify: xing, Gsealy
 */
public class Array {
    //定義整型數據data保存數據
    public int data[];
    //定義數組長度
    private int n;
    //定義中實際個數
    private int count;

    //構造方法，定義數組大小
    public Array(int capacity){
        this.data = new int[capacity];
        this.n = capacity;
        this.count=0;//一開始一個數都沒有存所以為0
    }

    //根據索引，找到數據中的元素並返回
    public int find(int index){
        if (index<0 || index>=count) return -1;
        return data[index];
    }

    //插入元素:頭部插入，尾部插入
    public boolean insert(int index, int value){
        //數組中無元素 

        //if (index == count && count == 0) {
        //    data[index] = value;
        //    ++count;
        //    return true;
        //}

        // 數組空間已滿
        if (count == n) {
            System.out.println("沒有可插入的位置");
            return false;
        }
        // 如果count還沒滿，那麼就可以插入數據到數組中
        // 位置不合法
        if (index < 0||index > count ) {
            System.out.println("位置不合法");
            return false;
        }
        // 位置合法
        for( int i = count; i > index; --i){
            data[i] = data[i - 1];
        }
        data[index] = value;
        ++count;
        return true;
    }
    //根據索引，刪除數組中元素
    public boolean delete(int index){
        if (index<0 || index >=count) return false;
        //從刪除位置開始，將後面的元素向前移動一位
        for (int i=index+1; i<count; ++i){
            data[i-1] = data[i];
        }
        //刪除數組末尾元素  這段代碼不需要也可以
        /*int[] arr = new int[count-1];
        for (int i=0; i<count-1;i++){
            arr[i] = data[i];
        }
        this.data = arr;*/

        --count;
        return true;
    }
    public void printAll() {
        for (int i = 0; i < count; ++i) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Array array = new Array(5);
        array.printAll();
        array.insert(0, 3);
        array.insert(0, 4);
        array.insert(1, 5);
        array.insert(3, 9);
        array.insert(3, 10);
        //array.insert(3, 11);
        array.printAll();
    }
}

GenericArray數組代碼

public class GenericArray<T> {
    private T[] data;
    private int size;

    // 根據傳入容量，構造Array
    public GenericArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    // 無參構造方法，默認數組容量為10
    public GenericArray() {
        this(10);
    }

    // 獲取數組容量
    public int getCapacity() {
        return data.length;
    }

    // 獲取當前元素個數
    public int count() {
        return size;
    }

    // 判斷數組是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // 修改 index 位置的元素
    public void set(int index, T e) {
        checkIndex(index);
        data[index] = e;
    }

    // 獲取對應 index 位置的元素
    public T get(int index) {
        checkIndex(index);
        return data[index];
    }

    // 查看數組是否包含元素e
    public boolean contains(T e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    // 獲取對應元素的下標, 未找到，返回 -1
    public int find(T e) {
        for ( int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }


    // 在 index 位置，插入元素e, 時間複雜度 O(m+n)
    public void add(int index, T e) {
        checkIndex(index);
        // 如果當前元素個數等於數組容量，則將數組擴容為原來的2倍
        if (size == data.length) {
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

    // 向數組頭插入元素
    public void addFirst(T e) {
        add(0, e);
    }

    // 向數組尾插入元素
    public void addLast(T e) {
        add(size, e);
    }

    // 刪除 index 位置的元素，並返回
    public T remove(int index) {
        checkIndexForRemove(index);

        T ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size --;
        data[size] = null;

        // 縮容
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return ret;
    }

    // 刪除第一個元素
    public T removeFirst() {
        return remove(0);
    }

    // 刪除末尾元素
    public T removeLast() {
        return remove(size - 1);
    }

    // 從數組中刪除指定元素
    public void removeElement(T e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
        builder.append('[');
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append(']');
        return builder.toString();
    }


    // 擴容方法，時間複雜度 O(n)
    private void resize(int capacity) {
        T[] newData = (T[]) new Object[capacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed! Require index >=0 and index <= size.");
        }
    }

    private void checkIndexForRemove(int index) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed! Require index >=0 and index < size.");
        }
    }
}

到這裏，就回溯最初的問題：

從數組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用a來表示數組的首地址，a[0]就是偏移為0的位置，也就是首地址，a[k]就表示偏移k個type_size的位置，所以計算a[k]的內存地址只需要用這個公式：

a[k]_address = base_address + k * type_size

但是，如果數組從1開始計數，那我們計算數組元素a[k]的內存地址就會變為：

a[k]_address = base_address + (k-1)*type_size

對比兩個公式，我們不難發現，從1開始編號，每次隨機訪問數組元素都多了一次減法運算，對於CPU來說，就是多了一次減法指令。那你可以思考一下，類比一下，二維數組的內存尋址公式是怎樣的呢？有興趣的可以在評論區評論出來哦QAQ

數組作為非常基礎的數據結構，通過下標隨機訪問數組元素又是其非常基礎的編程操作，效率的優化就要盡可能做到極致。所以為了減少一次減法操作，數組選擇了從0開始編號，而不是從1開始。
不過我認為，上面解釋得再多其實都算不上壓倒性的證明，說數組起始編號非0開始不可。所以我覺得最主要的原因可能是歷史原因。

關於數組，它可以說是最基礎、最簡單的數據結構了。數組用一塊連續的內存空間，來存儲相同類型的一組數據，最大的特點就是支持隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間複雜度為O(n)。在平時的業務開發中，我們可以直接使用編程語言提供的容器類，但是，如果是特別底層的開發，直接使用數組可能會更合適。

如果本文對你有一點點幫助，那麼請點個讚唄，謝謝~

最後，若有不足或者不正之處，歡迎指正批評，感激不盡！如果有疑問歡迎留言，絕對第一時間回復！

歡迎各位關注我的公眾號，一起探討技術，嚮往技術，追求技術，說好了來了就是盆友喔…

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!