之前對於跨域相關的知識一致都很零碎，正好現在的代碼中用到了跨域相關的，現在來對這些知識做一個匯總整理，方便自己查看，說不定也可能對你有所幫助。

本篇主要內容如下：

• 瀏覽器同源策略
• http 請求跨域
• http 請求跨域解決辦法
• cookie 機制
• 如何共享 cookie

瀏覽器同源策略

  相信很多人在 web 入門時，都被跨域問題折磨的死去活來。要想完全掌握跨域就得知道為什麼會有跨域這個問題出現。

  簡單來說跨域問題是因為瀏覽器的同源策略導致的。那瀏覽器為什麼要有同源策略呢？

  當然是為了安全。沒有同源策略限制的瀏覽器環境是非常危險的（即使有了同源策略也不是百分百安全），有興趣的可以去了解了解CSRF和XSS攻擊。

  所謂的“同源”指的是“三個相同”：

• 協議相同。不能一個是 http 協議，一個是 https
• 域名相同
• 端口相同

如果非同源頁面有以下限制：

• LocalStore 和 IndexDB 無法讀取。這兩個顯然是不能讀取的，但是 cookie 有點不一樣，放在後面單獨說明
• DOM 無法獲取,比如如法在頁面 A 中通過 iframe 獲取異源頁面 B 的 DOM
• AJAX 請求無法讀取（可以發送請求，但是無法讀取到請求結果。比如在頁面 A 中請求異源接口 B，請求會正常發出處理，但是在頁面 A 中無法獲取請求結果，除非響應頭 Access-Control-Allow-Headers 中允許了頁面 A 的源，這樣就能讀取到結果）

  但是這裡有個例外，所有帶“src”屬性的標籤都可以跨域加載資源，不受同源策略的限制，這樣你應該可以想到一個比較古老的跨域解決方案（JSONP）,同時這個特性也會被用作 CSRF 攻擊。

http 請求跨域

  在前端開發中經常會遇到跨域的問題，比如前後端分離中前後端部署在不同的端口上，或者在前端頁面中需要向另外一個服務請求數據，這些都會被跨域所阻擋。

目前主要有以下幾種辦法解決跨域問題：

1. 關閉瀏覽器同源檢查

  這個太暴力，也太不安全了，不用考慮。

1. jsonp 實現跨域請求

  前面說過了瀏覽器對於帶 src 屬性的標籤都可以跨域的。因此 jsonp 的實現流失利用了這個特性，在頁面中動態插入一個<script>標籤,然後他的 src 屬性就是接口調用地址，這樣就能訪問過去了，然後再講返回內容特殊處理成立即執行的函數，這樣就看起像進行了一次跨域請求。之所以不推薦這種方式，主要有以下兩個原因：

• 實現複雜,且需要前後台同時修改才能實現
• 只能進行 get 請求

1. 服務器設置運行跨域

  這種方法只需要後台做處理便能實現跨域，前面說的 http 跨域請求是能夠發出去的，只是不能接收，那我們只要在響應頭Access-Control-Allow-Headers中加入允許請求的地址即可，以,分隔，同時*代表所有地址都允許。比如：

Access-Control-Allow-Headers:http://localhost:8081,http://localhost:8082

本方法是較為常用的一中跨域辦法,只需簡單修改服務端代碼即可。

1. 請求代理

  這也是非常常用的一種跨域方法。跨域限制只是瀏覽器限制，服務端並沒有這個概念，因此我們在前端還是請求同域地址，然後在服務端做一個代理，將請求轉發到真正的 ip 和端口上。通常使用 nginx 實現端口轉發，比如下面一段 nginx 配置：

server {
    # /test1/abc 轉發到 http://a.com:8011/abc
    location /test1/ {
        proxy_pass http://a.com:8011/;
    }

    # /test2/abc 轉發到 http://b.com:8011/main/abc
    location /test2/ {
        proxy_pass http://b.com:8011/main/;
    }

    # /test3/abc 轉發到 http://c.com:8011/test3/abc
    location /test3/ {
        proxy_pass http://c.com:8081;
    }
}

cookie 同源策略

  cookie 的同源策略是通過

Domain和path兩個部分來共同確認一個 cookie 在哪些頁面上可用。

  Domain確定這個 cookie 所屬的域名，不能帶端口或協議。因此 cookie 便可在不同端口/不同協議下共享,只要域名相同。有一個例外是父子域名間也能共享 cookie，只需將 Domain 設置為.父域名。

  path就簡單多了，通過 Domain 確定哪些域名可以共享 cookie，然後在通過path來確定 cookie 在哪些路徑下可用。使用/表示所有路徑都可共享。

具體如下：

• Domain : example,path : /a可獲取 cookie:http://example:8081/a,https://example:8081/a
• Domain : example,path : /可獲取 cookie:http://example:8081/a,https://example:8081/a , http://example:12/abcd
• Domain : .example,path : /a可獲取 cookie:http://example:8081/a , https://localhost:8081/a , http://test.example:889/a

注意:在跨域請求中，即時目標地址有 cookie 且發起請求的頁面也能讀取到該 cookie，瀏覽器也不會將 cookie 自動設置到該跨域請求中。比如在http://localhost:8082/a頁面中請求http://localhost:8081/abc,這兩個地址下擁有共享cookie，http請求也不會攜帶cookie。

本篇原創發佈於：FleyX 的個人博客

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

本文在個人技術博客不同步發布，詳情可用力戳
亦可掃描屏幕右側二維碼關注個人公眾號，公眾號內有個人聯繫方式，等你來撩…

   前两天發了工資，第一反應是想着要給遠方的女朋友一點驚喜！於是打開了平安銀行的APP給女朋友轉點錢！填寫上對方招商銀行卡的卡號、開戶名，一鍵轉賬！搞定！在我點擊的那瞬間，就收到了app的賬戶變動的提醒，並且出現了圖一所示的提示界面：“處理中，正在等待對方銀行返回結果…”。嗯！畢竟是跨行轉賬嘛，等個幾秒也正常！腦海開始浮現出女朋友收到轉賬后驚喜與感動的畫面！

   然而，一切並沒有那麼順利，剛過一會兒，app卻如圖二所示的提示我“由於收款人戶名不符”導致轉賬失敗！！！

   剛剛都已經從我卡里扣過錢了，現在卻提示我轉賬失敗，銀行會不會把我的錢給吞了？轉賬失敗的錢還能退換給我嗎？正在我緊張、焦慮、坐立不安之時又收到一條app沖正的消息，剛剛轉賬失敗的錢已經退還給我了，看來我多慮了……這也證明咱平安銀行的app還是比較安全靠譜的！

   為啥從我卡里扣錢那麼迅速，而對方卻要幾秒才能到賬？並且轉賬失敗后，扣除的錢還能及時的返還到我的卡里？萬一錢返還失敗怎麼辦？又或者我轉一次錢，對方卻收到了兩次轉賬的申請又該如何？帶着這些問題，我腦海中浮現出“事務”二字！

   在我們還在“牙牙學語”的時候，老師經常會通過轉賬的栗子來跟我們講解事務，但跟這裏場景不一樣的是，老師講的是本地事務，而這裏面對的是分佈式事務！我們先來簡單回顧一下本地事務！

本地事務

   談到本地事務，大家可能都很熟悉，因為這個數據庫引擎層面能支持的！所以也稱數據庫事務，數據庫事務四大特徵：原子性（A），一致性（C），隔離性（I）和持久性（D），而在這四大特性中，我認為一致性是最基本的特性，其它的三個特性都為了保證一致性而存在的！

   回到學生時代老師給我們舉的經典栗子，A賬戶給B賬戶轉賬100元（A、B處於同一個庫中），如果A的賬戶發生扣款，B的賬戶卻沒有到賬，這就出現了數據的不一致！為了保證數據的一致性，數據庫的事務機制會讓A賬戶扣款和B在賬戶到賬的兩個操作要麼同時成功，如果有一個操作失敗，則多個操作同時回滾，這就是事務的原子性，為了保證事務操作的原子性，就必須實現基於日誌的REDO/UNDO機制！但是，僅有原子性還不夠，因為我們的系統是運行在多線程環境下，如果多個事務并行，即使保證了每一個事務的原子性，仍然會出現數據不一致的情況。例如A賬戶原來有200元的餘額， A賬戶給B賬戶轉賬100元，先讀取A賬戶的餘額，然後在這個值上減去100元，但是在這兩個操作之間，A賬戶又給C賬戶轉賬100元，那麼最後的結果應該是A減去了200元。但事實上，A賬戶給B賬戶最終完成轉賬后，A賬戶只減掉了100元，因為A賬戶向C賬戶轉賬減掉的100元被覆蓋了！所以為了保證併發情況下的一致性，又引入的隔離性，即多個事務併發執行后的狀態，和它們串行執行后的狀態是等價的！隔離性又有多種隔離級別，為了實現隔離性（最終都是為了保證一致性）數據庫又引入了悲觀鎖、樂觀鎖等等……本文的主題是分佈式事務，所以本地事務就只是簡單回顧一下，需要記住的一點是，事務是為了保證數據的一致性！

分佈式理論

  還記得剛畢業那年，帶着滿腔的熱血就去到了一家互聯網公司，領導給我的第一個任務就是在列表上增加一個修改數據的功能。這能難倒我？我分分鐘給你搞出來！不就是在列表上增加了一個“修改”按鈕，點擊按鈕彈出框修改后保存就好了么。然而一切不像我想象的那麼順利，點擊保存並刷新列表后，頁面上的數據還是显示的修改之前的內容，像沒有修改成功一樣！過一會兒再刷新列表，數據就能正常显示了！測試多次之後都是這樣！沒見過什麼大場面的我開始有點慌了，是我哪裡寫得不對么？最終，我不得不求助組內經驗比較豐富的前輩！他深吸了一口氣告訴我說：“畢竟是剛畢業的小伙子啊！我來跟你講講原因吧！我們的數據庫是做了讀寫分離的，部分讀庫與寫庫在不同的網絡分區。你的數據更新到了寫庫，而讀數據的時候是從讀庫讀取的。更新到寫庫的數據同步到讀庫是有一定的延遲的，也就是說讀庫與寫庫會有短暫的數據不一致”！ “這樣不會體驗不好么？為什麼不能做到寫入的數據立馬能讀出來？那我這個功能該怎麼實現呢？” 面對我的一堆問題，同事有些不耐煩的說：“聽說過CAP理論嗎？你先自己去了解一下吧”！是我開始查閱各種資料去了解這個陌生的詞背後的秘密！

  CAP理論是由加州大學Eric Brewer教授提出來的，這個理論告訴我們，一個分佈式系統不可能同時滿足一致性(Consistency)、可用性(Availability)、分區容錯性(Partition tolerance)這三個基本需求，最多只能同時滿足其中兩項。
  一致性：這裏的一致性是指數據的強一致，也稱為線性一致性。是指在分佈式環境中，數據在多個副本之間是否能夠保持一致的特性。也就是說對某個數據進行寫操作后立馬執行讀操作，必須能讀取到剛剛寫入的值。（any read operation that begins after a write operation completes must return that value, or the result of a later write operation）
  可用性：任意被無故障節點接收到的請求，必須能夠在有限的時間內響應結果。（every request received by a non-failing node in the system must result in a response）
  分區容錯性：如果集群中的機器被分成了兩部分，這兩部分不能互相通信，系統是否能繼續正常工作。（the network will be allowed to lose arbitrarily many messages sent from one node to another）

  在分佈式系統中，分區容錯性是基本要保證的。也就是說只能在一致性和可用性之間進行取捨。一致性和可用性，為什麼不可能同時成立？回到之前修改列表的例子，由於數據會分佈在不同的網絡分區，必然會存在數據同步的問題，而同步會存在網絡延遲、異常等問題，所以會出現數據的不一致！如果要保證數據的一致性，那麼就必須在對寫庫進行操作時，鎖定其他讀庫的操作。只有寫入成功且完成數據同步后，才能重新放開讀寫，而這樣在鎖定期間，系統喪失了可用性。更詳細關於CAP理論可以參考這篇文章，該文章講得比較通俗易懂！

分佈式事務

   分佈式事務就是在分佈式的場景下，需要滿足事務的需求！上篇文章我們聊過了消息中間件，那這篇文章我們要聊的是分佈式事務，把兩者一結合，便有了基於消息中間件的分佈式事務解決方案！不管是本地事務，還是分佈式事務，都是為了解決數據的一致性問題！一致性這個詞咱們前面多次提及！與本地事務不同的是，分佈式事務需要保證的是分佈式環境下，不同數據庫表中的數據的一致性問題。分佈式事務的解決方案有多種，如XA協議、TCC三階段提交、基於消息隊列等等，本文只會涉及基於消息隊列的解決方案！

   本地事務講到了一致性，分佈式事務不可避免的面臨着一致性的問題！回到最開始跨行轉賬的例子，如果A銀行用戶向B銀行用戶轉賬，正常流程應該是：

1、A銀行對轉出賬戶執行檢查校驗，進行金額扣減。
2、A銀行同步調用B銀行轉賬接口。
3、B銀行對轉入賬戶進行檢查校驗，進行金額增加。
4、B銀行返回處理結果給A銀行。

   在正常情況對一致性要求不高的場景，這樣的設計是可以滿足需求的。但是像銀行這樣的系統，如果這樣實現大概早就破產了吧。我們先看看這樣的設計最主要的問題：

1、同步調用遠程接口，如果接口比較耗時，會導致主線程阻塞時間較長。
2、流量不能很好控制，A銀行系統的流量高峰可能壓垮B銀行系統（當然B銀行肯定會有自己的限流機制）。
3、如果“第1步”剛執行完，系統由於某種原因宕機了，那會導致A銀行賬戶扣款了，但是B銀行沒有收到接口的調用，這就出現了兩個系統數據的不一致。
4、如果在執行“第3步”后，B銀行由於某種原因宕機了而無法正確回應請求（實際上轉賬操作在B銀行系統已經執行且入庫），這時候A銀行等待接口響應會異常，誤以為轉賬失敗而回滾“第1步”操作，這也會出現了兩個系統數據的不一致。

   對於問題的1、2都很好解決，如果對消息隊列熟悉的朋友應該很快能想到可以引入消息中間件進行異步和削峰處理，於是又重新設計了一個方案，流程如下：

1、A銀行對賬戶進行檢查校驗，進行金額扣減。
2、將對B銀行的請求異步寫入隊列，主線程返回。
3、啟動後台程序從隊列獲取待處理數據。
4、後台程序對B銀行接口進行遠程調用。
5、B銀行對轉入賬戶進行檢查校驗，進行金額增加。
6、B銀行處理完成回調A銀行接口通知處理結果。

   通過上面的圖我們能看到，引入消息隊列后，系統的複雜性瞬間提升了，雖然彌補了我們第一種方案的幾個不足點，但也帶來了更多的問題，比如消息隊列系統本身的可用性、消息隊列的延遲等等！並且，這樣的設計依然沒有解決我們面臨的核心問題-數據的一致性！

1、如果“第1步”剛執行完，系統由於某種原因宕機了，那會導致A銀行賬戶扣款了，但是寫入消息隊列失敗，無法進行B銀行接口調用，從而導致數據不一致。
2、如果B銀行在執行“第5步”時由於校驗失敗而未能成功轉賬，在回調A銀行接口通知回滾時網絡異常或者宕機，會導致A銀行轉賬無法完成回滾，從而導致數據不一致。

   面對上述問題，我們不得不對系統再次進行升級改造。為了解決“A銀行賬戶扣款了，但是寫入消息隊列失敗”的問題，我們需要藉助一個轉賬日誌表，或者叫轉賬流水表，該表簡單的設計如下：

   這個流水表需要怎麼用呢？我們在“第1步”進行扣款時，同時往流水表寫入一條操作流水，狀態為“待處理”，並且這兩個操作必須是原子的，也就是說必須通過本地事務保證這兩個操作要麼同時成功，要麼同時失敗！這就保證了只要轉賬扣款成功，必定會記錄一條狀態為“待處理”的轉賬流水。如果在這一步失敗了，那自然就是轉賬失敗，沒有後續操作了。如果這步操作后系統宕機了導致沒有將消息成功寫入消息隊列（也就是“第2步”）也沒關係，因為我們的流水數據已經持久化了！這時候我們只需要加入一個後台線程進行補償，定期的從轉賬流水表中讀取狀態為“待處理”且最後更新的時間距當前時間大於某個閾值的數據，重新放入消息隊列進行補償。這樣，就保證了消息即使丟失，也會有補償機制！B銀行在處理完轉賬請求後會回調A銀行的接口通知轉賬的狀態，從而更新A銀行流水表中的狀態字段！這樣就完美解決了上一個方案中的兩個不足點。系統設計圖如下：
  

   到目前為止，我們很好的解決了消息丟失的問題，保證了只要A銀行轉賬操作成功，轉賬的請求就一定能發送到B銀行！但是該方案又引入了一個問題，通過後台線程輪詢將消息放入消息隊列處理，同一次轉賬請求可能會出現多次放入消息隊列而多次消費的情況，這樣B銀行會對同一轉賬多次處理導致數據出現不一致！那怎麼保證B銀行轉賬接口的冪等性呢？

   同樣的，我們可以在B銀行系統中需要增加一個轉賬日誌表，或者叫轉賬流水表，B銀行每次接收到轉賬請求，在對賬戶進行操作的時候同時往轉賬日誌表中插入一條轉賬日誌記錄，同樣這兩個操作也必須是原子的！在接收到轉賬請求后，首先根據唯一轉賬流水Id在日誌表中查找判斷該轉賬是否已經處理過，如果未處理過則進行處理，否則直接回調返回！ 最終的架構圖如下：
  

   所以，我們這裏最核心的就是A銀行通過本地事務保證日誌記錄+後台線程輪詢保證消息不丟失。B銀行通過本地事務保證日誌記錄從而保證消息不重複消費！B銀行在回調A銀行的接口時會通知處理結果，如果轉賬失敗，A銀行會根據處理結果進行回滾。

   當然，分佈式事務最好的解決方案是盡量避免出現分佈式事務！

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

這裡會列舉在C#中處理CLR異常方面的規範，幫助大家構建和開發一個運行良好和可靠的應用系統。

前言

  迄今為止，CLR異常機制讓人關注最多的一點就是“效率”問題。其實，這裏存在認識上的誤區，因為正常控制流程下的代碼運行並不會出現問題，只有引發異常時才會帶來效率問題。基於這一點，很多開發者已經達成共識：不應將異常機制用於正常控制流中。達成的另一個共識是：CLR異常機制帶來的“效率”問題不足以“抵消”它帶來的巨大收益。
CLR異常機制至少有以下幾個優點：

• 正常控制流會被立即中止，無效值或狀態不會在系統中繼續傳播。
• 提供了統一處理錯誤的方法。
• 提供了在構造函數、操作符重載及屬性中報告異常的便利機制。
• 提供了異常堆棧，便於開發者定位異常發生的位置。

  另外，“異常”其名稱本身就說明了它的發生是一個小概率事件。所以，因異常帶來的效率問題會被限制在一個很小的範圍內。實際上，try catch所帶來的效率問題幾乎是可以忽略的。在某些特定的場合，如Int32的Parse方法中，確實存在着因為濫用而導致的效率問題。在這種情況下，我們就應該考慮提供一個TryParse方法，從設計的角度讓用戶選擇讓程序運行得更快。另一種規避因為異常而影響效率的方法是：Tester-doer模式

正文

1.用拋出異常代替返回錯誤代碼

在異常機制出現之前，應用程序普遍採用返回錯誤代碼的方式來通知調用者發生了異常。本建議首先闡述為什麼要用拋出異常的方式來代替返回錯誤代碼的方式。對於一個成員方法而言，它要麼執行成功，要麼執行失敗。成員方法執行成功的情況很容易理解，但是如果執行失敗了卻沒有那麼簡單，因為我們需要將導致執行失敗的原因通知調用者。拋出異常和返回錯誤代碼都是用來通知調用者的手段。

但是當我們想要告訴調用者更多細節的時候，就需要與調用者約定更多的錯誤代碼。於是我們很快就會發現，錯誤代碼飛速膨脹，直到看起來似乎無法維護，因為我們總在查找並確認錯誤代碼。
在沒有異常處理機制之前，我們只能返回錯誤代碼。但是，現在有了另一種選擇，即使用異常機制。如果使用異常機制，那麼最終的代碼看起來應該是下面這樣的：

static void Main(string[]args)
{    
try  
    {   
     SaveUser(user); 
    }    
catch(IOException)   
    {       
    //IO異常,通知當前用戶 
    }    
catch(UnauthorizedAccessException)
    {       
    //權限失敗,通知客戶端管理員  
    }    
catch(CommunicationException) 
    {        
   //網絡異常,通知發送E-mail給網絡管理員  
    }
}

private static void SaveUser(User user)
{   
  SaveToFile(user); 
  SaveToDataBase(user);
}

使用CLR異常機制后，我們會發現代碼變得更清晰、更易於理解了。至於效率問題，還可以重新審視“效率”的立足點：throw exception產生的那點效率損耗與等待網絡連接異常相比，簡直微不足道，而CLR異常機制帶來的好處卻是顯而易見的。

這裏需要稍加強調的是，在catch（CommunicationExcep-tion）這個代碼塊中，代碼所完成的功能是“通知發送”而不是“發送”本身，因為我們要確保在catch和finally中所執行的代碼是可以被執行的。換句話說，盡量不要在catch和finally中再讓代碼“出錯”，那會讓異常堆棧信息變得複雜和難以理解。

在本例的catch代碼塊中，不要真的編寫發送郵件的代碼，因為發送郵件這個行為可能會產生更多的異常，而“通知發送”這個行為穩定性更高（即不“出錯”）。

以上通過實際的案例闡述了拋出異常相比於返回錯誤代碼的優越性，以及在某些情況下錯誤代碼將無用武之地，如構造函數、操作符重載及屬性。語法特性決定了其不能具備任何返回值，於是異常機制被當做取代錯誤代碼的首要選擇。

2.不要在不恰當的場合下引發異常

程序員，尤其是類庫開發人員，要掌握的兩條首要原則是：
正常的業務流程不應使用異常來處理。
不要總是嘗試去捕獲異常或引發異常，而應該允許異常向調用堆棧往上傳播。
那麼，到底應該在怎樣的情況下引發異常呢？

第一類情況　如果運行代碼後會造成內存泄漏、資源不可用，或者應用程序狀態不可恢復，則應該引發異常。
在微軟提供的Console類中有很多類似這樣的代碼：

if((value<1)||(value>100))
{    
    throw new ArgumentOutOfRangeException("value",value, Environment.GetResourceString("ArgumentOutOfRange_CursorSize"));
}

或者：

if(value==null)
{    
  throw new ArgumentNullException("value");
}

在開頭首先提到的就是：對在可控範圍內的輸入和輸出不引發異常。沒錯，區別就在於“可控”這兩個字。所謂“可控”，可定義為：發生異常后，系統資源仍可用，或資源狀態可恢復。

第二類情況　在捕獲異常的時候，如果需要包裝一些更有用的信息，則引發異常。
這類異常的引發在UI層特別有用。系統引發的異常所帶的信息往往更傾向於技術性的描述；而在UI層，面對異常的很可能是最終用戶。如果需要將異常的信息呈現給最終用戶，更好的做法是先包裝異常，然後引發一個包含友好信息的新異常。

第三類情況　如果底層異常在高層操作的上下文中沒有意義，則可以考慮捕獲這些底層異常，並引發新的有意義的異常。
例如在下面的代碼中，如果拋出InvalidCastException，則沒有任何意義，甚至會造成誤解，所以更好的方式是拋出一個ArgumentException：

private void CaseSample(object o)
{  
  if(o==null)    
  {        
   throw new ArgumentNullException("o");   
  }
}   
 
User user=null;   
try  
{   
   user=(User)o; 
}    
catch(InvalidCastException)
{    
   throw new ArgumentException("輸入參數不是一個User","o"); 
}  

//do something}

需要重點介紹的正確引發異常的典型例子就是捕獲底層API錯誤代碼，並拋出。查看Console這個類，還會發現很多地方有類似的代碼：

int errorCode=Marshal.GetLastWin32Error();
if(errorCode==6)
{   
  throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_ConsoleKeyAvailableOnFile"));
}

Console為我們封裝了調用Windows API返回的錯誤代碼，而讓代碼引發了一個新的異常。

很顯然，當需要調用Windows API或第三方API提供的接口時，如果對方的異常報告機制使用的是錯誤代碼，最好重新引發該接口提供的錯誤，因為你需要讓自己的團隊更好地理解這些錯誤。

3.重新引發異常時使用Inner Exception

當捕獲了某個異常，將其包裝或重新引發異常的時候，如果其中包含了Inner Exception，則有助於程序員分析內部信息，方便代碼調試。
以一個分佈式系統為例，在進行遠程通信的時候，可能會發生的情況有：
1）網卡被禁用或網線斷開，此時會拋出SocketException，消息為：“由於目標計算機積極拒絕，無法連接。”
2）網絡正常，但是要連接的目標機沒有端口沒有處在偵聽狀態，此時，會拋出SocketException，消息為：“由於連接方在一段時間后沒有正確答覆或連接的主機沒有反應，連接嘗試失敗。”
3）連接超時，此時需要通過代碼實現關閉連接，並拋出一個SocketException，消息為：“連接超過約定的時長。”
發生以上三種情況中的任何一種情況，在返回給最終用戶的時候，我們都需要將異常信息包裝成為“網絡連接失敗，請稍候再試”。

所以，一個分佈式系統的業務處理方法，看起來應該是這樣的：

try
{    
SaveUser5(user);
}
catch(SocketException err)
{  
  throw new CommucationFailureException("網絡連接失敗,請稍後再試",err);
}

但是，在提示這條消息的時候，我們可能需要將原始異常信息記錄到日誌里，以供開發者分析具體的原因（因為如果這種情況頻繁出現，這有可能是一個Bug）。那麼，在記錄日誌的時候，就非常有必要記錄導致此異常出現的內部異常或是堆棧信息。
上文代碼中的：就是將異常重新包裝成為一個CommucationFailureException，並將SocketException作為Inner Exception（即err）向上傳遞。

此外還有一個可以採用的技巧，如果不打算使用Inner Exception，但是仍然想要返回一些額外信息的話，可以使用Exception的Data屬性。如下所示：

try
{   
 SaveUser5(user);
}
catch(SocketException err)
{    
 err.Data.Add("SocketInfo","網絡連接失敗,請稍後再試");   
 throw err;
}

在上層進行捕獲的時候，可以通過鍵值來得到異常信息：

catch(SocketException err)
{   
 Console.WriteLine(err.Data["SocketInfo"].ToString());
}

4.避免在finally內撰寫無效代碼

你應該始終認為finally內的代碼會在方法return之前執行，哪怕return是在try塊中。
C#編譯器會清理那些它認為完全沒有意義的C#代碼。

private static int TestIntReturnInTry()
{   
  int i;    
  try    
  {        
    return i=1;  
  } 
  
finally   
 {        
    i=2;      
   Console.WriteLine("\t將int結果改為2,finally執行完畢");   
 }
}

5.避免嵌套異常

應該允許異常在調用堆棧中往上傳播，不要過多使用catch，然後再throw。過多使用catch會帶來兩個問題：

• 代碼更多了。這看上去好像你根本不知道該怎麼處理異常，所以你總在不停地catch。
• 隱藏了堆棧信息，使你不知道真正發生異常的地方。

嵌套異常會導致 調用堆棧被重置了。最糟糕的情況是：如果方法捕獲的是Exception。所以也就是說，如果這個方法中還存在另外的異常，在UI層將永遠不知道真正發生錯誤的地方。
除了第3點提到的需要包裝異常的情況外，無故地嵌套異常是我們要極力避免的。當然，如果真的需要捕獲這個異常來恢復一些狀態，然後重新拋出，代碼看起來應該是這樣的：

try{ 
  MethodTry();
}
catch(Exception)
{ 
   //工作代碼   
 throw;
}

或者：

try
{    
 MethodTry();
}
catch
{    
  //工作代碼 
   throw;
}

盡量避免像下面這樣引發異常：

catch(Exception err)
{   
 //工作代碼  
  throw err;
}

直接throw err而不是throw將會重置堆棧信息。

6.避免“吃掉”異常

嵌套異常是很危險的行為，一不小心就會將異常堆棧信息，也就是真正的Bug出處隱藏起來。但這還不是最嚴重的行為，最嚴重的就是“吃掉”異常，即捕獲，然後不向上層throw拋出。如果你不知道如何處理某個異常，那麼千萬不要“吃掉”異常，如果你一不小心“吃掉”了一個本該往上傳遞的異常，那麼，這裏可能誕生一個Bug，而且，解決它會很費周折。

避免“吃掉”異常，並不是說不應該“吃掉”異常，而是這裏面有個重要原則：該異常可被預見，並且通常情況它不能算是一個Bug。 比如有些場景存在你可以預見的但不重要的Exception，這個就不算一個bug。

7.為循環增加Tester-Doer模式而不是將try-catch置於循環內

如果需要在循環中引發異常，你需要特別注意，因為拋出異常是一個相當影響性能的過程。應該盡量在循環當中對異常發生的一些條件進行判斷，然後根據條件進行處理。

8.總是處理未捕獲的異常

處理未捕獲的異常是每個應用程序應具備的基本功能，C#在AppDomain提供了UnhandledException事件來接收未捕獲到的異常的通知。常見的應用如下：

static void Main(string[]args)
{    
  AppDomain.CurrentDomain.UnhandledException+=new  UnhandledExceptionEventHandler(CurrentDomain_UnhandledException);
}

static void CurrentDomain_UnhandledException(object sender, UnhandledExceptionEventArgs e)
{    
  Exception error=(Exception)e.ExceptionObject;   
 Console.WriteLine("MyHandler caught:"+error.Message);
}

未捕獲的異常通常就是運行時期的Bug，我們可以在App-Domain.CurrentDomain.UnhandledException的註冊事件方法CurrentDomain_UnhandledException中，將未捕獲異常的信息記錄在日誌中。值得注意的是，UnhandledException提供的機制並不能阻止應用程序終止，也就是說，執行CurrentDomain_UnhandledException方法后，應用程序就會被終止。

9.正確捕獲多線程中的異常

多線程的異常處理需要採用特殊的方法。以下的處理方式會存在問題：

try{  
  Thread t=new Thread((ThreadStart)delegate    
{        
  throw new Exception("多線程異常");    
});   

 t.Start();
}

catch(Exception error)
{ 
   MessageBox.Show(error.Message+Environment.NewLine+error.StackTrace);
}

應用程序並不會在這裏捕獲線程t中的異常，而是會直接退出。從.NET 2.0開始，任何線程上未處理的異常，都會導致應用程序的退出（先會觸發AppDomain的UnhandledException）。上面代碼中的try-catch實際上捕獲的還是當前線程的異常，而t屬於新起的異常，所以，正確的做法應該是把 try-catch放在線程裏面

Thread t=new Thread((ThreadStart)delegate
{    
try   
 {      
  throw new Exception("多線程異常");   
 }    
catch(Exception error)   {  ....   });

t.Start();

10.慎用自定義異常

除非有充分的理由，否則一般不要創建自定義異常。如果要對某類程序出錯信息做特殊處理，那就自定義異常。需要自定義異常的理由如下：
1）方便調試。通過拋出一個自定義的異常類型實例，我們可以使捕獲代碼精確地知道所發生的事情，並以合適的方式進行恢復。
2）邏輯包裝。自定義異常可包裝多個其他異常，然後拋出一個業務異常。
3）方便調用者編碼。在編寫自己的類庫或者業務層代碼的時候，自定義異常可以讓調用方更方便處理業務異常邏輯。例如，保存數據失敗可以分成兩個異常“數據庫連接失敗”和“網絡異常”。
4）引入新異常類。這使程序員能夠根據異常類在代碼中採取不同的操作。

11.從System.Exception或其他常見的基本異常中派生異常

這個不說了，自定義異常一般是從System.Exception派生。。事實上，現在如果你在Visual Studio中輸入Exception，然後使用快捷鍵Tab，VS會自動創建一個自定義異常類。

12.應使用finally避免資源泄漏

前面已經提到過，除非發生讓應用程序中斷的異常，否則finally總是會先於return執行。finally的這個語言特性決定了資源釋放的最佳位置就是在finally塊中；另外，資源釋放會隨着調用堆棧由下往上執行（即由內到外釋放）。

13.避免在調用棧較低的位置記錄異常

即避免在內部深處處理記錄異常。最適合記錄異常和報告的是應用程序的最上層，這通常是UI層。
並不是所有的異常都要被記錄到日誌，一類情況是異常發生的場景需要被記錄，還有一類就是未被捕獲的異常。未被捕獲的異常通常被視為一個Bug，所以，對於它的記錄，應該被視為系統的一個重要組成部分。

如果異常在調用棧較低的位置被記錄或報告，並且又被包裝后拋出；然後在調用棧較高位置也捕獲記錄異常。這就會讓記錄重複出現。在調用棧較低的情況下，往往異常被捕獲了也不能被完整的處理。所以，綜合考慮，應用程序在設計初期，就應該為開發成員約定在何處記錄和報告異常。

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

1 基本概念

• 集成學習的主要思路是先通過一定的規則生成多個學習器，再採用某種集成策略進行組合，最後綜合判斷輸出最終結果。一般而言，通常所說的集成學習中的多個學習器都是同質的”弱學習器”。基於該弱學習器，通過樣本集擾動、輸入特徵擾動、輸出表示擾動、算法參數擾動等方式生成多個學習器，進行集成后獲得一個精度較好的”強學習器”。
• 目前集成學習算法大多源於bagging、boosting、stacking三種思想。

2 bagging

• 一種提高分類模型的方法。
  • (1) 從訓練集\(S\)中有放回的隨機選取數據集\(M\)\((∣M∣ < ∣S∣)\);
  • (2) 生成一個分類模型\(C\);
  • (3) 重複以上步驟\(m\)次，得到\(m\)個分類模型\(C_1,C_2,…,C_m\);
  • (4)對於分類問題，每一個模型投票決定，少數服從多數原則;
  • (5)對於回歸問題，取平均值。

• 注意：這種抽樣的方式會導致有的樣本取不到，大約有\(\lim_{n \to \infty}(1-\frac{1}{n})^n\) = \(36.8%\)的樣本取不到，這部分可用來做測試集。

• 優點: 通過減少方差來提高預測結果。

• 缺點: 失去了模型的簡單性。

2.1 Random Forest

• 是一種基於樹模型的bagging算法改進的模型。假定數據集中有\(M\)個特徵和 \(N\)個觀測值。每一個樹有放回的隨機抽出\(N\)個觀測值\(m\)(\(m=M\)或者\(m=logM\))個特徵。把每一個單一決策樹的結果綜合起來。

• 優點:
  • (1) 減少了模型方差，提高了預測準確性。
  • (2) 不需要給樹做剪枝。
  • (3) 在大規模數據集，尤其是特徵較多的情況下，依然可以保持高效率。
  • (4) 不用做特徵選擇，並且可以給出特徵變量重要性的排序估計。
• 缺點：
  • (1) 隨機森林已經被證明在某些噪音較大的分類或回歸問題上會過擬合
  • (2) 對於有不同取值的屬性的數據，取值劃分較多的屬性會對隨機森林產生更大的影響，所以隨機森林在這種數據上產出的屬性權值是不可信的。

3 boosting

• 每一輪根據上一輪的分類結果動態調整每個樣本在分類器中的權重，訓練得到k個弱分類器，他們都有各自的權重，通過加權組合的方式得到最終的分類結果(綜合所有的基模型預測結果)。主要算法有AdaBoost/GBDT/Xgboost/LightGBM。

3.1 Adboost

• 給定數據集\(S\)，它包含\(n\)個元組\((X_1,y_1),(X_2,y_2),…,(X_n,y_n)(X_1,y_1), (X_2,y_2), …, (X_n,y_n)\)，其中\(y_i\)是數據對象\(X_i\)的類標號。
• (1) 開始時，Adaboost對每個訓練元組賦予相等的權重\(1/n\)。組合分類器包含\(T\)個基本分類器。
• (2) 針對第\(t\)個分類器\(M_t\)：
  • 首先，從S中的元組進行抽樣，形成大小為\(n\)的訓練集\(S_t\)，此處抽樣方式為有放回的抽樣，抽樣過程中，每個元組被選中的機會由它的權重決定；
  • 然後，根據\(S_t\)導出（訓練出）分類器\(M_t\)，使用\(S_t\)檢驗分類器\(M_t\)的分類誤差，並計算該分類器的“表決權”的權重；
  • 最後，訓練元組的權重根據分類器\(M_t\)的分類情況調整。
  • 如果元組被錯誤分類，則它的權重增加。
  • 如果元組被正確分類，則它的權重減少。
  • 元組的權重反映元組被分類的困難程度——權重越高，被錯誤分類的可能性越高。然後，使用這些權重，為下一輪分類器（下一個分類器）產生訓練樣本。
• 其基本的思想是，當建立分類器時，希望它更關註上一輪分類器（上一個分類器）錯誤分類的元組。整個分類過程中，某些分類器對某些“困難”元組的分類效果可能比其他分類器好。這樣，建立了一個互補的分類器系列。
• 用於二分類或多分類的應用場景。
• 優點
  • (1) 很好的利用了弱分類器進行級聯。
  • (2)可以將不同的分類算法作為弱分類器。
  • (3)AdaBoost具有很高的精度。
  • (4) 相對於bagging算法和Random Forest算法，AdaBoost充分考慮的每個分類器的權重。
• 缺點：
  • (1) AdaBoost迭代次數也就是弱分類器數目不太好設定，可以使用交叉驗證來進行確定。
  • (2) 數據不平衡導致分類精度下降。
  • (3) 訓練比較耗時，每次重新選擇當前分類器最好切分點。

3.2 GBDT

• 採用決策樹作為弱分類器的Gradient Boosting算法被稱為GBDT，有時又被稱為MART（Multiple Additive Regression Tree）。GBDT中使用的決策樹通常為CART。
• 用一個很簡單的例子來解釋一下GBDT訓練的過程，如圖下圖所示。模型的任務是預測一個人的年齡，訓練集只有A、B、C、D 4個人，他們的年齡分別是14、16、24、26，特徵包括了 “月購物金額”、”上網時長”、”上網歷史” 等。
• 下面開始訓練第一棵樹:
  • 訓練的過程跟傳統決策樹相同，簡單起見，我們只進行一次分枝。訓練好第一棵樹后，求得每個樣本預測值與真實值之間的殘差。
  • 可以看到，A、B、C、D的殘差分別是−1、1、−1、1。
  • 這時我們就用每個樣本的殘差訓練下一棵樹，直到殘差收斂到某個閾值以下，或者樹的總數達到某個上限為止。

• 由於GBDT是利用殘差訓練的，在預測的過程中，我們也需要把所有樹的預測值加起來，得到最終的預測結果。

• 優點：
  • （1）預測階段的計算速度快，樹與樹之間可并行化計算。
  • （2）在分佈稠密的數據集上，泛化能力和表達能力都很好，這使得GBDT在Kaggle的眾多競賽中，經常名列榜首。
  • （3）採用決策樹作為弱分類器使得GBDT模型具有較好的解釋性和魯棒性，能夠自動發現特徵間的高階關係，並且也不需要對數據進行特殊的預處理如歸一化等。
• 缺點:
  • （1）GBDT在高維稀疏的數據集上，表現不如支持向量機或者神經網絡。
  • （2）GBDT在處理文本分類特徵問題上，相對其他模型的優勢不如它在處理數值特徵時明顯。
  • （3）訓練過程需要串行訓練，只能在決策樹內部採用一些局部并行的手段提高訓練速度。

3.3 Xgboost

• XGBoost是陳天奇等人開發的一個開源機器學習項目，高效地實現了GBDT算法並進行了算法和工程上的許多改進。
• 目標函數：
  \[L^{(t)} = \sum_{i=1}^{n}l(y_i, \hat{y}_i^{(t)}) + \Omega(f_t) \]
• 優點：
  • (1)計算效率高，使用了二階導。
  • (2)有正則化，減少過擬合。
  • (3)列特徵抽樣減少過擬合，同時有利於并行計算。
• 缺點：
  • (1)每次迭代時都要遍歷整個數據集。
  • (2)內存佔用大。

3.4 GBDT與XGboost聯繫與區別

• (1) GBDT是機器學習算法，XGBoost是該算法的工程實現。
• (2) 在使用CART作為基分類器時，XGBoost顯式地加入了正則項來控制模型的複雜度，有利於防止過擬合，從而提高模型的泛化能力。
• (3) GBDT在模型訓練時只使用了代價函數的一階導數信息，XGBoost對代價函數進行二階泰勒展開，可以同時使用一階和二階導數。
• (4) 傳統的GBDT採用CART作為基分類器，XGBoost支持多種類型的基分類器，比如線性分類器。
• (5) 傳統的GBDT在每輪迭代時使用全部的數據，XGBoost則採用了與隨機森林相似的策略，支持對數據進行採樣。
• (6) 傳統的GBDT沒有設計對缺失值進行處理，XGBoost能夠自動學習出缺失值的處理策略。

3.5 LightGBM

• LightGBM也是一種基於決策樹的梯度提升算法，相比XGboost有做了許多改進。
  在樹分裂計算分裂特徵的增益時，xgboost 採用了預排序的方法來處理節點分裂，這樣計算的分裂點比較精確。但是，也造成了很大的時間開銷。為了解決這個問題，Lightgbm 選擇了基於 histogram 的決策樹算法。相比於pre-sorted算法，histogram在內存消耗和計算代價上都有不少優勢。
• Histogram算法簡單來說，就是先對特徵值進行裝箱處理，形成一個一個的bins。在Lightgbm中默認的#bins為256（1個字節的能表示的長度，可以設置）。具體如下：
  • (1) 把連續的浮點特徵值離散化成N個整數，構造一個寬度為N的直方圖；對於分類特徵，則是每一種取值放入一個bin，且當取值的個數大於max_bin數時，會忽略那些很少出現的category值。
  • (2) 遍曆數據時，根據離散化后的值作為索引在直方圖中累積統計量。
  • (3) 一次遍歷后，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點。
• Level-wise 和 Leaf-wise
  • 相對於xgboost的level—wise的生長策略，lightgbm使用了leaf-wise樹生長策略。由於level-wise在分裂時，部分增益小的樹也得到了增長，雖然容易控制誤差，但是分裂有時是不合理的，而lightgbm使用level-wise，只在增益大的樹上分裂生長，甚至對Feature f如果分裂無收益，那麼後續也將不會對f計算。體現在參數上，xgboost使用max_depth，而lightgbm使用num_leaves控制過擬合。
  • Level-wise過一次數據可以同時分裂同一層的恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，容易進行多線程優化，也好控制模型複雜度，不容易過擬合。但實際上Level-wise是一種低效的算法，因為它不加區分的對待同一層的恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，帶來了很多沒必要的開銷，因為實際上很多恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子的分裂增益較低，沒必要進行搜索和分裂。
  • Leaf-wise則是一種更為高效的策略，每次從當前所有恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子中，找到分裂增益最大的一個恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，然後分裂，如此循環。因此同Level-wise相比，在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點是可能會長出比較深的決策樹，產生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

3.6 Xgboost與LightGBM對比

3.6.1 切分算法（切分點的選取）

• 佔用的內存更低，只保存特徵離散化后的值，而這個值一般用8位整型存儲就足夠了，內存消耗可以降低為原來的1/8。
• 降低了計算的代價：預排序算法每遍歷一個特徵值就需要計算一次分裂的增益，而直方圖算法只需要計算k次（k可以認為是常數），時間複雜度從O(#data#feature)優化到O(k#features)。(相當於LightGBM犧牲了一部分切分的精確性來提高切分的效率，實際應用中效果還不錯)
• 空間消耗大，需要保存數據的特徵值以及特徵排序的結果(比如排序后的索引，為了後續快速計算分割點)，需要消耗兩倍於訓練數據的內存
• 時間上也有較大開銷，遍歷每個分割點時都需要進行分裂增益的計算，消耗代價大
• 對cache優化不友好，在預排序后，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。
• XGBoost使用的是pre-sorted算法（對所有特徵都按照特徵的數值進行預排序，基本思想是對所有特徵都按照特徵的數值進行預排序；然後在遍歷分割點的時候用O(#data)的代價找到一個特徵上的最好分割點最後，找到一個特徵的分割點后，將數據分裂成左右子節點。優點是能夠更精確的找到數據分隔點；但這種做法有以下缺點
• LightGBM使用的是histogram算法，基本思想是先把連續的浮點特徵值離散化成k個整數，同時構造一個寬度為k的直方圖。在遍曆數據的時候，根據離散化后的值作為索引在直方圖中累積統計量，當遍歷一次數據后，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點；優點在於

3.6.2 決策樹生長策略

• XGBoost採用的是帶深度限制的level-wise生長策略，Level-wise過一次數據可以能夠同時分裂同一層的恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，容易進行多線程優化，不容易過擬合；但不加區分的對待同一層的恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，帶來了很多沒必要的開銷（因為實際上很多恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子的分裂增益較低，沒必要進行搜索和分裂）
• LightGBM採用leaf-wise生長策略，每次從當前所有恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子中找到分裂增益最大（一般也是數據量最大）的一個恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子，然後分裂，如此循環；但會生長出比較深的決策樹，產生過擬合（因此 LightGBM 在leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合）。
• Histogram做差加速。一個容易觀察到的現象：一個恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到。通常構造直方圖，需要遍歷該恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。利用這個方法，LightGBM可以在構造一個恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子的直方圖后，可以用非常微小的代價得到它兄弟恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子的直方圖，在速度上可以提升一倍。
• 直接支持類別特徵：LightGBM優化了對類別特徵的支持，可以直接輸入類別特徵，不需要額外的0/1展開。並在決策樹算法上增加了類別特徵的決策規則。

3.6.3 分佈式訓練方法上(并行優化)

• 在特徵并行算法中，通過在本地保存全部數據避免對數據切分結果的通信；
• 在數據并行中使用分散規約(Reducescatter)把直方圖合併的任務分攤到不同的機器，降低通信和計算，並利用直方圖做差，進一步減少了一半的通信量。基於投票的數據并行(ParallelVoting)則進一步優化數據并行中的通信代價，使通信代價變成常數級別。
• 特徵并行的主要思想是在不同機器在不同的特徵集合上分別尋找最優的分割點，然後在機器間同步最優的分割點。
• 數據并行則是讓不同的機器先在本地構造直方圖，然後進行全局的合併，最後在合併的直方圖上面尋找最優分割點。
• Cache命中率優化
• 基於直方圖的稀疏特徵優化
• DART(Dropout + GBDT)
• GOSS(Gradient-based One-Side Sampling):一種新的Bagging(row subsample)方法,前若干輪(1.0f /gbdtconfig->learning_rate)不Bagging;之後Bagging時, 採樣一定比例g(梯度)大的樣本。

4 stacking

• stacking的思想是將每個基模型的輸出組合起來作為一個特徵向量，重新進行訓練。可以理解為：將訓練好的所有基模型對整個訓練集進行預測，第j個基模型對第i個訓練樣本的預測值將作為新的訓練集中第i個樣本的第j個特徵值，最後基於新的訓練集進行訓練。同理，預測的過程也要先經過所有基模型的預測形成新的測試集，最後再對測試集進行預測。
• 具體算法如下(為方便理解我舉例說明)：
  • (1) 訓練集大小\(400\times10\)，400個樣本，每個樣本10個特徵，（如果算上target有11列）。測試集大小為\(120\times10\)。
  • (2) 首先對訓練集4折劃分:\(S_1\),\(S_2\),\(S_3\),\(S_4\),每個\(S_i\)的大小都收是\(100\times10\)。模型\(M_1\)第一次用\(S_1\),\(S_2\),\(S_3\)訓練，用\(S_4\)預測得到預測結果\(100\times1\)。重複訓練步驟，直到每一個\(S_i\)都有對應的預測結果\(100\times1\)。合併所有預測結果得到\(P_1\)\(400\times1\)。用\(M_1\)預測得到原始測試集的預測結果\(T_1\)\(120\times1\)。
  • (3) 模型\(M_2\)用4折叫交叉得到訓練集的預測結果：\(P_2\)\(400\times1\)；得到測試集的預測結果：\(T_2\)\(120\times1\)。
  • (4) 模型\(M_3\)用4折叫交叉得到訓練集的預測結果：\(P_3\)\(400\times1\)；得到測試集的預測結果：\(T_3\)\(120\times1\)。
  • (5) 綜合(2)(3)(4)底層模型得到的訓練集的預測結果\(P_1\)、\(P_2\)、\(P_3\)，得到上層模型的訓練集\(P_{train}\)\(400\times3\)；得到上層模型的測試集\(T_{test}\)\(120\times3\)。
  • (6) 用(5)得到的訓練集和測試集進行上層模型的訓練。
• 優點：學習了底層模型之間的關係

• 缺點：對於數據量要求比較大，因為要平衡第一層和第二層

  5 參考

• 《百面機器學習》
• https://zhuanlan.zhihu.com/p/26890738
• https://www.imooc.com/article/29530

• https://blog.csdn.net/anshuai_aw1/article/details/83040541

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

前言

       轉載請聲明，轉自【https://www.cnblogs.com/andy-songwei/p/11072989.html】，謝謝！

       前面兩篇文章，花了很大篇幅講解了Android的事件分發機制的原理性知識。然而，“紙上得來終覺淺，絕知此事要躬行”，前面講的那些原理，也都是為解決實際問題而服務的。本文將結合實際工作中經常遇到的滑動衝突案例，總結滑動衝突的場景以及解決方案。本文的主要內容如下：

一、滑動衝突簡介

       滑動組合在平時的UI開發中非常常見，比如下圖中某App界面（圖片來源：https://www.jb51.net/article/90032.htm），該頁面上半部分显示商品列表，而下半部分显示頁面導航。當滑動上面的列表時，列表部分滑動；當列表滑動到底或者滑動下半部分時，整個頁面一起滑動。

       但是在平時的開發中，可能會經常遇到這樣的場景，滑動列表部分時，整個頁面一起滑動，而不是只滑動列表內容。或者一會兒是列表滑動，一會兒是整個頁面滑動，而不是按照預期的要求來滑動。這就是我們常說的滑動衝突問題。滑動衝突的問題，經常讓開發者們頭痛不已。因為經常很多滑動相關的控件，如ScrollView、ListView等，在單獨使用的時候酷炫不已，但將他們組合在一起使用，就失靈了。比如上圖中，手指在屏幕上上下滑動，列表和整個頁面都有滑動功能，此時如果處理不當，就會導致系統也不知道要讓誰來消費這個滑動事件，這就是滑動衝突產生的原因。

二、滑動衝突的三種場景

       儘管實際工作中滑動衝突的場景看似各種各樣，但最終可以歸納為三種，如下圖所示：1）圖一：外部滑動和內部滑動方向不一致；2）圖二：外部滑動和內部滑動方向不一致；3）圖三：多層滑動疊加。

  1、外部滑動和內部滑動方向不一致

       圖一中只示意了外部為左右滑動，內部為上下滑動的場景。顯然，內外滑動不一致，還包括外部為上下滑動，內部為左右滑動的場景。對於這種場景，平時工作中最常見的使用大概是外層為PageView，內層為一個Fragment+ListView/RecyclerView了。慶幸的是，控件PageView和RecyclerView對事件衝突做了處理的，所以平時使用這兩個控件的時候不會感受到滑動衝突的存在。如果是ScrollView+GridView等這類組合，就需要解決衝突了。

  2、外部滑動和內部滑動方向一致

       同樣，這種場景除了圖二中的內外都是上下滑動的情況外，還包括內外到時左右滑動的場景了。ScollView(垂直滾動)+ListView的組合就是比較常見的場景。第一節中的動態圖就是一個外部滑動和內部滑動方向一致的例子。

  3、多層滑動嵌套

       這種場景一般就是前面兩種場景的嵌套。“騰訊新聞”客戶端就是典型的多層滑動嵌套的使用案例，如下圖中，圖一的左邊是主頁向右滑動時才出現的滑動側邊欄，圖二是主頁界面，頂部導航欄在主頁左右滑動時可以切換，整個“要聞”界面可以上下滑動，“熱點精選”是一個可以左右滑動的橫向列表，下方還有豎直方向的列表……可見這其中嵌套層數不少。

三、滑動衝突三種場景的處理思路

       儘管滑動衝突看起來比較複雜，但是上述將它們分為三類場景后，就可以根據這三類場景來分別找出對應的分析思路。

  1、內外滑動方向不一致時處理思路

       這一類場景其實比較容易分析，因為外層和內層滑動的方向不一致，所以根據手勢的動向來確定把事件給誰。我們前面兩篇文章中分析過，默認情況下，當點擊內層控件時，事件會先一層層從外層傳到內層，由內層來處理。這裏以外層為左右滑動，內層為上下滑動為例。當判定手勢的滑動為左右時，需要外層來消費事件，所以外層將事件攔截，即在外層的onInterceptTouchEvent中檢測為ACTION_MOVE時返回true；而如果判定手勢的滑動為上下時，需要內層來消費事件，外層不需要攔截，事件會傳遞到內層來處理（具體的代碼實現，在後面會詳細列出）。這樣就通過判斷滑動的方向來決定事件的處理對象，從而解決滑動衝突的問題。

       那麼，如何來判定手勢的滑動方向呢？最常用的辦法就是比較水平和豎直方向上的位移值來判斷。 MotionEvent事件包含了事件的坐標，只要記錄一次移動事件的起點和終點坐標，如下圖所示，通過比較在水平方向的位移|dx|和|dy|的大小，來決定滑動的方向：|dy|>|dx|，本次移動的方向認為是豎直方向；反之，則認為是水平方向。當然，還可以通過夾角α的大小、斜率、速率等方式來作為判斷條件。

  2、內外滑動方向一致時處理思路

       這種場景要比上面一種複雜一些，因為滑動方向一致，所以無法通過上述的方式來判斷將事件交給誰處理。在這種情況下，往往需要根據業務的需要來判定誰來處理事件。比如豎直方向的ScrollView嵌套ListView的場景下，手指在ListView上上下滑動時：當ListView滑動到頂部且手勢向下時，顯然ListView不能再向下滑動了，這種情況下事件需要被外層控件攔截，由ScrollView來消費；當ListView滑動到底部且手勢向上時，顯然ListView也不能再向上滑動了，這種情況下事件也需要被外層控件攔截，由ScrollView來消費；其它情況下，ScrollView就不能再攔截了，滑動事件就需要由ListView來消費了，即此時上下滑動時，滑動的是ListView，而不是ScrollView。後面會以這為案例進行編碼實現。

  3、多層滑動嵌套時處理思路

       場景3看起來比較複雜，但前面也說過了，也是由前面兩種場景嵌套形成的。所以在處理場景的處理方式，就是將其拆分為簡單的場景，然後按照前面的場景分析方式來處理。

四、滑動衝突的兩種解決套路

       前面我們將滑動衝突分為了3種場景，並根據每一種場景提供了解決衝突的思路。但是這些思路解決的是判斷條件問題，即什麼情況下事件交給誰的問題。這一節將拋開前面的場景分類，介紹對所有場景適用的兩種通用解決方法，可以通俗地理解為處理滑動衝突的“套路”。這兩種解決滑動衝突的方式為：外部攔截法和內部攔截法。

  1、外部攔截法

       顧名思義，就是在外部滑動控件中處理攔截邏輯。這需要外部控件重寫父類的onInterceptTouchEvent方法，在其中判斷什麼時候需要攔截事件由自身處理，什麼時候需要放行將事件傳給內層控件處理，內部控件不需要做任何處理。這個“套路”的偽代碼錶示所示：

 1 @Override
 2 public boolean onInterceptTouchEvent(MotionEvent ev) {
 3     boolean intercepted = false;
 4     switch (ev.getAction()){
 5         case MotionEvent.ACTION_DOWN:
 6             intercepted = false;
 7             break;
 8         case MotionEvent.ACTION_MOVE:
 9             if(父容器需要自己處理改事件){
10                 intercepted = true;
11             }else {
12                 intercepted = false;
13             }
14             break;
15         case MotionEvent.ACTION_UP:
16             intercepted = false;
17             break;
18             default:
19             break;
20     }
21     return intercepted;
22 }

前面對滑動處理的場景分類，並對不同場景給了分析思路，它們的作用就是在這裏的第9行來做判斷條件的。所以，不論什麼場景，都可以在這個套路的基礎上，修改判斷是否攔截事件的條件語句即可。另外，需要說明一下的是，第6行和第16行，這裏都賦值為false，因為ACTION_DOWN如果被攔截了，該動作序列的其它事件就都無法傳遞到子View中了，ListView也就永遠不能滑動了；而ACTION_UP如果被攔截，那子View就無法被點擊了，這兩點我們前面的文章都講過，這裏再強調一下。

  2、內部攔截法

       顧名思義，就是將事件是否需要攔截的邏輯，放到內層控件中來處理。這種方式需要結合requestDisllowInterceptTouchEvent(boolean)，在內層控件的重寫方法dispatchTouchEvent中，根據邏輯來決定外層控件何時需要攔截事件，何時需要放行。偽代碼如下：

 1 @Override
 2 public boolean dispatchTouchEvent(MotionEvent ev) {
 3     switch (ev.getAction()){
 4         case MotionEvent.ACTION_DOWN:
 5             getParent().requestDisallowInterceptTouchEvent(true);
 6             break;
 7         case MotionEvent.ACTION_MOVE:
 8             if (父容器需要處理改事件) {
 9                 //允許外層控件攔截事件
10                 getParent().requestDisallowInterceptTouchEvent(false);
11             } else {
12                 //需要內部控件處理該事件，不允許上層viewGroup攔截
13                 getParent().requestDisallowInterceptTouchEvent(true);
14             }
15             break;
16         case MotionEvent.ACTION_UP:
17             break;
18         default:
19             break;
20     }
21     return super.dispatchTouchEvent(ev);
22 }

除此之外，還需要外層控件在onInterceptTouchEvent中做一點處理：

1 @Override
2 public boolean onInterceptTouchEvent(MotionEvent ev) {
3     if (ev.getAction() == MotionEvent.ACTION_DOWN) {
4         return false;
5     } else {
6         return true;
7     }
8 }

ACTION_DOWN事件仍然不能攔截，上一篇文章分析源碼的時候講過，ACTION_DOWN時會初始化一些狀態和標誌位等變量，requestDisllowInterceptTouchEvent(boolean)作用會失效。這裏再順便強調一下，不明白的可以去上一篇文章中閱讀這部分內容。 

       這種方式比“外部攔截法”稍微複雜一些，所以一般推薦使用前者。同前者一樣，這也是一個套路用法，無論是之前提到的何種場景，只要根據實際判斷條件修改上述if語句即可。對於requestDisllowInterceptTouchEvent(boolean)的相關信息，在前面的文章中介紹過，這裏不再贅述了。

 五、代碼示例

       前面通過文字描述和偽代碼，對滑動衝突進行了介紹，並提供了一些對應的解決方案。本節將通過一個具體的實例，分別使用上述的套路來解決一個滑動衝突，從而具體演示前面“套路”的使用。

  1、未解決衝突前的示例情況

       本示例外層為一個ScrollView，內層為TextView+ListView+TextView，這兩個TextView分別為“Tittle”和”Bottom”，显示在ListView的頂部和底部，添加它們是為了方便觀察ScrollView的滑動效果。最終的布局效果如下所示：

在手機上的显示效果為：

在沒有解決衝突前，如果滑動中間的ListView部分，會出現ListView中的列表內容不會滑動，而是整個ScrollView滑動的現象，或者一會兒ListView滑動，一會兒ScrollView滑動。顯然，這不是我們希望看到的結果。我們希望的是，如果ListView滑到頂部時，而且手勢繼續下滑時，整個頁面下滑，即ScrollView滑動；如果ListView滑到底部了，而且手勢繼續上滑時，希望整個頁面上滑，即也是ScrollView向上滑動。

  2、用外部攔截法解決滑動衝突的示例

       前面說過了，這種方式需要外層的控件在重寫的onInterceptTouchEvent時進行攔截判斷，所以需要自定義一個ScrollView控件。

 1 public class CustomScrollView extends ScrollView {
 2 
 3     ListView listView;
 4     private float mLastY;
 5     public CustomScrollView(Context context, AttributeSet attrs) {
 6         super(context, attrs);
 7     }
 8 
 9     @Override
10     public boolean onInterceptTouchEvent(MotionEvent ev) {
11         super.onInterceptTouchEvent(ev);
12         boolean intercept = false;
13         switch (ev.getAction()){
14             case MotionEvent.ACTION_DOWN:
15                 intercept = false;
16                 break;
17             case MotionEvent.ACTION_MOVE:
18                 listView = (ListView) ((ViewGroup)getChildAt(0)).getChildAt(1);
19                    //ListView滑動到頂部，且繼續下滑，讓scrollView攔截事件
20                 if (listView.getFirstVisiblePosition() == 0 && (ev.getY() - mLastY) > 0) {
21                     //scrollView攔截事件
22                     intercept = true;
23                 }
24                 //listView滑動到底部，如果繼續上滑，就讓scrollView攔截事件
25                 else if (listView.getLastVisiblePosition() ==listView.getCount() - 1 && (ev.getY() - mLastY) < 0) {
26                     //scrollView攔截事件
27                     intercept = true;
28                 } else {
29                     //不允許scrollView攔截事件
30                     intercept = false;
31                 }
32                 break;
33             case MotionEvent.ACTION_UP:
34                 intercept = false;
35                 break;
36             default:
37                 break;
38         }
39         mLastY = ev.getY();
40         return intercept;
41     }
42 }

       相比於前面的偽代碼，這裏需要注意一點的是多了第12行。因為本控件是繼承自ScrollView，而ScrollView中的onInterceptTouchEvent做了很多的工作，這裏需要使用ScrollView中的處理邏輯，才需要加上這一句。如果是完全自繪的控件，即直接繼承自ViewGroup，那就無需這一句了，因為控件需要自己完成自己的特色功能。第18行是獲取子控件ListView的實例，這個是參照後面的布局文件activity_event_examples來定位的，也可以通過其它的方式來獲取實例。另外就是ListView的實例可以通過其它方式一次性賦值，而不用這裏每次ACTION_MOVE都獲取一次實例，從性能上考慮會更好，這裏為了便於演示，先忽略這一點。其它要點在註釋中也說得比較明確了，這裏不贅述。

       使用CustomScrollView控件，界面的布局如下：

 1 //==============activity_event_examples=============
 2 <?xml version="1.0" encoding="utf-8"?>
 3 <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
 4     android:layout_width="match_parent"
 5     android:layout_height="match_parent"
 6     android:orientation="vertical">
 7 
 8     <com.example.demos.customviewdemo.CustomScrollView
 9         android:id="@+id/demo_scrollview"
10         android:layout_width="match_parent"
11         android:layout_height="match_parent">
12 
13         <LinearLayout
14             android:layout_width="match_parent"
15             android:layout_height="match_parent"
16             android:orientation="vertical">
17 
18             <TextView
19                 android:id="@+id/tv_title"
20                 android:layout_width="match_parent"
21                 android:layout_height="100dp"
22                 android:background="@android:color/darker_gray"
23                 android:gravity="center"
24                 android:text="Title"
25                 android:textSize="50dp" />
26 
27             <ListView
28                 android:id="@+id/demo_lv"
29                 android:layout_width="match_parent"
30                 android:layout_height="600dp" />
31 
32             <TextView
33                 android:layout_width="match_parent"
34                 android:layout_height="100dp"
35                 android:background="@android:color/darker_gray"
36                 android:gravity="center"
37                 android:text="Bottom"
38                 android:textSize="50dp" />
39         </LinearLayout>
40     </com.example.demos.customviewdemo.CustomScrollView>
41 </LinearLayout>

這裏需要注意的是，在ScrollView中嵌套ListView時，ListView的高度需要特別處理，如果設置為match_parent或者wrap_content，都會一次只能看到一條item，所以上面給了固定的高度600dp來演示效果。平時工作中，往往還需要對ListView的高度做一些特殊的處理，這不是本文的重點，這裏不細講，讀者可以自行去研究。

       最後就是給ListView填充足夠的數據：

 1 public class EventExmaplesActivity extends AppCompatActivity {
 2 
 3     private String[] data = {"Apple", "Banana", "Orange", "Watermelon",
 4             "Pear", "Grape", "Pineapple", "Strawberry", "Cherry", "Mango",
 5             "Apple", "Banana", "Orange", "Watermelon",
 6             "Pear", "Grape", "Pineapple", "Strawberry", "Cherry", "Mango"};
 7 
 8     @Override
 9     protected void onCreate(Bundle savedInstanceState) {
10         super.onCreate(savedInstanceState);
11         setContentView(R.layout.activity_event_exmaples);
12         showList();
13     }
14 
15     private void showList() {
16         ArrayAdapter<String> adapter = new ArrayAdapter<String>(
17                 EventExmaplesActivity.this, android.R.layout.simple_list_item_1, data);
18         ListView listView = findViewById(R.id.demo_lv);
19         listView.setAdapter(adapter);
20     }
21 }

  3、用內部攔截法解決滑動衝突的示例

       同樣，前面的偽代碼中也講過，這裏需要在內層控件中重寫的dispatchTouchEvent方法處判斷外層控件的攔截邏輯，所以首先需要自定義ListView。

 1 public class CustomListView extends ListView {
 2 
 3     public CustomListView(Context context, AttributeSet attrs) {
 4         super(context, attrs);
 5     }
 6 
 7     //為listview/Y，設置初始值,默認為0.0(ListView條目一位置)
 8     private float mLastY;
 9 
10     @Override
11     public boolean dispatchTouchEvent(MotionEvent ev) {
12         int action = ev.getAction();
13         switch (action) {
14             case MotionEvent.ACTION_DOWN:
15                 //不允許上層的ScrollView攔截事件.
16                 getParent().requestDisallowInterceptTouchEvent(true);
17                 break;
18             case MotionEvent.ACTION_MOVE:
19                 //滿足listView滑動到頂部，如果繼續下滑，那就允許scrollView攔截事件
20                 if (getFirstVisiblePosition() == 0 && (ev.getY() - mLastY) > 0) {
21                     //允許ScrollView攔截事件
22                     getParent().requestDisallowInterceptTouchEvent(false);
23                 }
24                 //滿足listView滑動到底部，如果繼續上滑，允許scrollView攔截事件
25                 else if (getLastVisiblePosition() == getCount() - 1 && (ev.getY() - mLastY) < 0) {
26                     //允許ScrollView攔截事件
27                     getParent().requestDisallowInterceptTouchEvent(false);
28                 } else {
29                     //其它情形時不允ScrollView攔截事件
30                     getParent().requestDisallowInterceptTouchEvent(true);
31                 }
32                 break;
33             case MotionEvent.ACTION_UP:
34                 break;
35         }
36 
37         mLastY = ev.getY();
38         return super.dispatchTouchEvent(ev);
39     }
40 }

可能有讀者會有些疑惑，從布局結構上看，listView和ScrollView之間還隔了一層LinearLayout，getParent().requestDisallowInterceptTouchEvent(boolean)方法會奏效嗎？實際上這個方法是針對所有的父布局的，而不是只針對直接父布局，這一點需要注意。

       參照偽代碼的套路，這裏還需要對外層的ScrollView做一些邏輯處理：

 1 public class CustomScrollView extends ScrollView {
 2     public CustomScrollView(Context context, AttributeSet attrs) {
 3         super(context, attrs);
 4     }
 5 
 6     @Override
 7     public boolean onInterceptTouchEvent(MotionEvent ev) {
 8         if (ev.getAction() == MotionEvent.ACTION_DOWN) {
 9             return false;
10         } else {
11             return true;
12         }
13     }
14 }

       在布局文件中使用CustomListView，將前面activity_event_examples.xml布局文件中的第27行的ListView替換為com.example.demos.customviewdemo.CustomListView即可。其它的和前面外部攔截法示例一樣，這裏不贅述。

結語

       關於滑動衝突的內容就講完了。實際工作中的場景可能比這裏demo中要複雜一些，筆者為了突出重點，所舉的例子選得比較簡單，但原理都一樣的，所以希望讀者能夠好好理解，重要的地方，甚至需要記下來。同樣，Android事件分發機制系列的知識點，要講的也講完了，三篇文章側重於三個方面：1）第一篇重點總結了Touch相關的三個重要方法對事件的處理邏輯；2）第二篇重點分析源碼，從源碼的角度來分析第一篇文章中的邏輯；3）第三篇重點在實踐，側重解決實際工作中經常遇到的事件衝突問題——滑動衝突。當然，事件分發相關的問題遠不是這3篇文章能說清楚的，文中若有描述錯誤或者不妥的地方，歡迎讀者來拍磚！！！

參考資料

       任玉剛《Android開發藝術探索》

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

十多年來，NAS中已經存在的目錄和文件達到10億之多，在設計和開發備份系統的過程中碰到了很多挑戰，本文將分享大量文件名記錄的樹形結構存儲實踐。

一、引言

既然是定期備份，肯定會有1次以上的備份。對於一個特定目錄，每次備份時都要與上次備份時進行比較，以期找出哪些文件被刪除了，又新增了哪些文件，這就需要每次備份時把該目錄下的所有文件名進行保存。我們首先想到的是把所有文件名用特定字符進行拼接后保存。由於我們使用了MySQL保存這些信息，當目錄下文件很多時，這種拼接的方式很可能超出MySQL的Blob長度限制。根據經驗，當一個目錄有大量文件時，這些文件的名稱往往是程序生成的，有一定規律的，而且開頭一般是重複的，於是我們想到了使用一種樹形結構來進行存儲。

例如，一個有abc、abc1、ad、cde 4個文件的目錄對應的樹如圖1所示。

圖1 樹形結構示例

圖1中，R表示根節點，青色節點我們稱為結束節點，從R到每個結束節點的路徑都表示一個文件名。可以在樹中查找是否含有某個文件名、遍歷樹中所有的文件名、對樹序列化進行保存、由序列化結果反序列化重新生成樹。

二、涉及的數據結構

注意：我們使用java編寫，文中涉及語言特性相關的知識點都是指java。

2.1 Node的結構

包括根節點在內的每個節點都使用Node類來表示。代碼如下：

 class Node {
        private char value;
        private Node[]children = new Node[0];
        private byte end = 0;
    }

字段說明：

• value：該節點表示的字符，當Node表示根節點時，value無值。
• children：該節點的所有子節點，初始化為長度為0的數組。
• end：標記節點是否是結束節點。0不是；1是。恭弘=恭弘=恭弘=叶 恭弘 恭弘 恭弘子節點肯定是結束節點。默認非結束節點。

2.2 Node的操作

   public Node(char v);
    public Node findChild(char v);
    public Node addChild(char v);

操作說明：

• Node：構造方法。將參數v賦值給this.value。
• findChild：查找children中是否含有value為v的子節點。有則返回子節點，沒有則返回null。
• addChild：首先查找children中是否已經含有value為v的子節點，如果有則直接將查到的子節點返回；否則創建value為v的節點，將children的長度延長1，將新創建的節點作為children的最後一個元素，並返回新創建的節點。

2.3 Tree的結構

  class Tree {
        public Node root = new Node();
    }

字段說明：Tree只含有root Node。如前所述，root的value無值，end為0。初始時的children長度為0。

2.4 Tree的操作

  public void addName(String name) ;
    public boolean contain(String name);
    public Found next(Found found);
    public void writeTo(OutputStream out);
    public static Tree readFrom(InputStream in);

操作說明：

• addName：向樹中增加一個新的文件名，即參數name。以root為起點，name中的每個字符作參數調用addChild，返回值又作為新的起點，直到name中的全部字符添加完畢，對最後一次調用addChild的返回值標記為結束節點。
• contain：查詢樹中是否含有一個文件名。
• next：對樹中包含的所有文件名進行遍歷，為了使遍歷能夠順利進行，我們引入了新的類Found，細節會在後文詳述。
• writeTo：將樹寫入一個輸出流以進行持久化。
• readFrom：此方法是靜態方法。從一個輸入流來重新構建樹。

三、樹的構建

在新建的Tree上調用addName方法，將所有文件名添加到樹中，樹構建完成。仍然以含有abc、abc1、ad、cde 四個文件的目錄為例，對樹的構建進行圖示。

圖2 樹的構建過程

圖2中，橙色節點表示需要在該節點上調用addChild方法增加子節點，同時addChild的返回值作為新的橙色節點。直到沒有子節點需要增加時，把最後的橙色節點標記為結束節點。

四、樹的查詢

查找樹中是否含有一個某個文件名，對應Tree的contain方法。在圖2中的結果上分別查找ef、ab和abc三個文件來演示查找的過程。如圖3所示。

圖3 樹的查詢示意圖

圖3中，橙色節點表示需要在該節點上調用findChild方法查找子節點。

五、樹的遍歷

此處的遍歷不同於一般樹的遍歷。一般遍歷是遍歷樹中的節點，而此處的遍歷是遍歷根節點到所有結束節點的路徑。

我們採用從左到右、由淺及深的順序進行遍歷。我們引入了Found類，並作為next方法的參數進行遍歷。

5.1 Found的結構

 class Found {    
        private String name;
        private int[] idx ;
    }

為了更加容易的說明問題，在圖1基礎上進行了小小的改造，每個節點的右下角增加了下標，如圖4。

圖4 帶下標的Tree

對於abc這個文件名，Found中的name值為“abc”，idx為{0，0，0}。

對於abc1這個文件名，Found中的name值為“abc1”，idx為{0，0，0，0}。

對於ad這個文件名，Found中的name值為“ad”，idx為{0，1}。

對於cde這個文件名，Found中的name值為“cde”，idx為{1，0，0}。

5.2 如何遍歷

對於圖4而言，第一次調用next方法應傳入null，則返回第一個結果，即abc代表的Found；繼續以這個Found作為參數進行第二次next的調用，則返回第二個結果，即abc1代表的Found；再繼續以這個Found作為參數進行第三次next的調用，則返回第三個結果，即ad所代表的Found；再繼續以這個Found作為參數進行第四次next的調用，則返回第四個結果，即cde所代表的Found；再繼續以這個Found作為參數進行第五次調用，則返回null，遍歷結束。

六、序列化與反序列化

6.1 序列化

首先應該明確每個節點序列化后應該包含3個信息：節點的value、節點的children數量和節點是否為結束節點。

6.1.1 節點的value

雖然之前所舉的例子中節點的value都是英文字符，但實際上文件名中可能含有漢字或者其他語言的字符。為了方便處理，我們沒有使用變長編碼。而是直接使用unicode碼。字節序採用大端編碼。

6.1.2 節點的children數量

由於節點的value使用了unicode碼，所以children的數量不會多於unicode能表示的字符的數量，即65536。children數量使用2個字節。字節序同樣採用大端編碼。

6.1.3 節點的end

0或1可以使用1位（1bit）來表示，但java中最小單位是字節。如果採用1個字節來表示end，有些浪費空間，其實任何一個節點children數量達到65536/2的可能性都是極小的，因此我們考慮借用children數量的最高位來表示end。

綜上所述，一個節點序列化后佔用4個字節，以圖4中的根節點、value為b的節點和value為e的節點為例：

表1 Node序列化示例

6.1.4 樹的序列化過程

對樹進行廣度遍歷，在遍歷過程中需要藉助隊列，以圖4的序列化為例進行說明： 

圖5 對圖4的序列化過程

6.2 反序列化

反序列化是序列化的逆過程，由於篇幅原因不再進行闡述。值得一提的是，反序列化過程同樣需要隊列的協助。

七、討論

7.1 關於節省空間

為方便討論，假設目錄下的文件名是10個阿拉伯数字的全排列，當位數為1時，目錄下含有10個文件，即0、1、2……8、9，當位數為2時，目錄下含有100個文件，即00、01、02……97、98、99，以此類推。

比較2種方法，一種使用“/”分隔，另一種是本文介紹的方法。

表2 2種方法的存儲空間比較（單位：字節）

由表2可見，當位數為4時，使用Tree的方式開始節省空間，位數越多節省的比例越高，這正是我們所需要的。

表中，使用“/”分隔時，字節數佔用是按照utf8編碼計算的。如果直接使用unicode進行存儲，佔用空間會加倍，那麼會在位數為2時就開始節省空間。同樣使用“/”分隔，看起來utf8比使用unicode會更省空間，但實際上，文件名中有時候會含有漢字，漢字的utf8編碼佔用3個字節。

7.2 關於時間

在樹的構建、序列化反序列化過程中，引入了額外的運算，根據我們的實踐，user CPU並沒有明顯變化。

7.3 關於理想化假設

最初我們就是使用了“/”分隔的方法對文件名進行存儲，並且數據庫的相應字段類型是Blob（Blob的最大值是65K）。在測試階段就發現，超出65K是一件很平常的事情。在不可能預先統計最大目錄里所有文件名拼接后的大小的情況下，我們採取了2種手段，一是使用LongBlob類型，另一種就是盡量減小拼接結果的大小，即本文介紹的方法。

即使使用樹形結構來存儲文件名，也不能夠保證最終結果不超出4G(LongBlob類型的最大值)，至少在我們實踐的過程並未出現問題，如果真出現這種情況，只能做特殊處理了。

7.4 關於其他壓縮方法

把文件名使用“/”拼接后，使用gzip等壓縮算法對拼接結果進行壓縮后再存儲，在節省存儲空間方面會取得更好的效果。但是在壓縮之前，拼接結果存在於內存，這樣對JVM的堆內存有比較高的要求；另外，使用“/”拼接時，查找會比較麻煩。

作者：牛寧昌

來源：宜信技術學院

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

一、項目初始化

　　創建webpack模板項目如下所示：

MacBook-Pro:PycharmProjects hqs$ vue init webpack luffy_project

? Project name luffy_project
? Project description A Vue.js project
? Author hqs
? Vue build standalone
? Install vue-router? Yes
? Use ESLint to lint your code? No
? Set up unit tests No
? Setup e2e tests with Nightwatch? No
? Should we run `npm install` for you after the project has been created? (recommended) npm

   vue-cli · Generated "luffy_project".

　　根據提示啟動項目：

$ cd luffy_project/
$ npm run dev

　　由於在初始化時選擇了vue-router，因此會自動創建/src/router/index.js文件。

　　刪除Helloworld組件相關信息后，index.js文件內容如下所示：

import Vue from 'vue'
import Router from 'vue-router'
// @絕對路徑 檢索到 ...src/

// 如果Router當做局部模塊使用一定要Vue.use(Router)
// 以後在組件中，可以通過this.$router 獲取Router實例化對象
// 路由信息對象 this.$routes 獲取路由配置信息
Vue.use(Router)

// 配置路由規則
export default new Router({
  routes: [
    {
      'path': '/'
    }
  ]
})

二、基於ElementUI框架實現導航欄

1、elementUI——適合Vue的UI框架

　　elementUI是一個UI庫，它不依賴於vue，但確是當前和vue配合做項目開發的一個比較好的UI框架。

（1）npm安裝

　　推薦使用 npm 的方式安裝，能更好地和 webpack 打包工具配合使用。

$ npm i element-ui -S

（2）CDN

　　目前可以通過 unpkg.com/element-ui 獲取到最新版本的資源，在頁面上引入 js 和 css 文件即可開始使用。

<!-- 引入樣式 -->
<link rel="stylesheet" href="https://unpkg.com/element-ui/lib/theme-chalk/index.css">
<!-- 引入組件庫 -->
<script src="https://unpkg.com/element-ui/lib/index.js"></script>

　　使用CND引入 Element 需要在鏈接地址上鎖定版本，以免將來 Element 升級時受到非兼容性更新的影響。鎖定版本的方法請查看 unpkg.com。

2、引入 Element

　　在項目中可以引入整個Element，或者是根據需要僅引入部分組件。

（1）完整引入

　　在 main.js 中寫入如下內容：

import Vue from 'vue'
import App from './App'
import router from './router'
// elementUI導入
import ElementUI from 'element-ui'
import 'element-ui/lib/theme-chalk/index.css'  // 注意樣式文件需要單獨引入
// 調用插件
Vue.use(ElementUI);

Vue.config.productionTip = false;

/* eslint-disable no-new */
new Vue({
  el: '#app',
  router,
  components: { App },
  template: '<App/>'
});

　　以上代碼便完成了 Element 的完整引入。

　　嘗試在App.vue使用elementui的Button按鈕：

<template>
  <div id="app">
    <!-- 導航區域 -->
    <el-button type="info">信息按鈕</el-button>

    <router-view/>
  </div>
</template>

<script>
export default {
  name: 'App'
}
</script>

　　显示效果：

（2）按需引入

　　藉助 babel-plugin-component，可以只引入需要的組件，以達到減小項目體積的目的。

　　首先安裝babel-plugin-component：

$ npm install babel-plugin-component -D

　　然後將.babelrc文件修改如下：

{
  "presets": [["es2015", { "modules": false }]],
  "plugins": [
    [
      "component",
      {
        "libraryName": "element-ui",
        "styleLibraryName": "theme-chalk"
      }
    ]
  ]
}

　　如果只希望引入部分組件，如Buttion何Select，那麼需要在 main.js 中寫如下內容：

import Vue from 'vue';
import { Button, Select } from 'element-ui';
import App from './App.vue';

Vue.component(Button.name, Button);
Vue.component(Select.name, Select);
/* 或寫為
 * Vue.use(Button)
 * Vue.use(Select)
 */

new Vue({
  el: '#app',
  render: h => h(App)
});

3、導航欄實現

　　首先創建/src/components/Common/LuffyHeader.vue文件：

<template>
  <!-- element-ui -->
  <el-container>
    <el-header height = '80px' >
      <div class="header">
        <div class="nav-left">
          <img src="https://www.luffycity.com/static/img/head-logo.a7cedf3.svg" alt="">
        </div>
        <div class="nav-center">
          <ul>
            <li>
              <a href="#">
                導航鏈接
              </a>
            </li>
          </ul>
        </div>
        <div class="nav-right">
          <span>登錄</span>
          &nbsp;| &nbsp;
          <span>註冊</span>
        </div>
      </div>
    </el-header>
  </el-container>
</template>

<script>
  export default {
    name: 'LuffyHeader',
    data(){
      return {
      }
    },
  };
</script>

　　再創建/static/global/global.css文件：

* {
  padding: 0;
  margin: 0;
}

body {
  font-size: 14px;
  color: #4a4a4a;
  font-family: PingFangSC-Light; /*蘋果設計的一款全新的中文系統字體，該字體支持蘋果的動態字體調節技術*/
}

ul {
  list-style: none;
}

a {
  text-decoration: none;
}

　　最後在App.vue中引入和使用組件：

<template>
  <div id="app">
    <!-- 導航區域 -->
    <LuffyHeader/>
    <router-view/>
  </div>
</template>

<script>
  import LuffyHeader from '@/components/Common/LuffyHeader'
  export default {
    name: 'App',
    components:{
      LuffyHeader
    }
  }
</script>

　　显示效果如下所示：

三、導航欄路由跳轉

1、組件創建和路由配置編寫

　　添加“首頁”、“免費課程”、“輕課”、“學位課”四大組件，因此創建如下文件：

src/components/Home/Home.vue
src/components/Course/Course.vue
src/components/LightCourse/LightCourse.vue
src/components/Micro/Micro.vue

　　在src/router/index.js中引入組件，配置路由規則：

import Vue from 'vue'
import Router from 'vue-router'
// @絕對路徑 檢索到 ...src/

// 如果Router當做局部模塊使用一定要Vue.use(Router)
// 以後在組件中，可以通過this.$router 獲取Router實例化對象
// 路由信息對象 this.$routes 獲取路由配置信息
import Home from '@/components/Home/Home'
import Course from '@/components/Course/Course'
import LightCourse from '@/components/LightCourse/LightCourse'
import Micro from '@/components/Micro/Micro'

Vue.use(Router)

// 配置路由規則
export default new Router({
  routes: [
    {
      path: '/',
      redirect: '/home'   // 訪問/，直接跳轉到/home路徑
    },
    {
      path: '/home',
      name: 'Home',
      component: Home
    },
    {
      path: '/course',
      name: 'Course',
      component: Course
    },
    {
      path: '/home/light-course',
      name: 'LightCourse',
      component: LightCourse
    },
    {
      path: '/micro',
      name: 'Micro',
      component: Micro
    }
  ]
})

2、導航鏈接編寫

　　修改 LuffyHeader.vue頁面，編寫導航鏈接：

<template>
  <!-- element-ui -->
  <el-container>
    <el-header height = '80px' >
      <div class="header">
        <div class="nav-left">
          <img src="https://www.luffycity.com/static/img/head-logo.a7cedf3.svg" alt="">
        </div>
        <div class="nav-center">
          <ul>
            <li v-for="(list, index) in headerList" :key="list.id">
              <a href="#">
                {{ list.title }}
              </a>
            </li>
          </ul>
        </div>
        <div class="nav-right">
          <span>登錄</span>
          &nbsp;| &nbsp;
          <span>註冊</span>
        </div>
      </div>
    </el-header>
  </el-container>
</template>

<script>
  export default {
    name: 'LuffyHeader',
    data() {
      return {
        headerList: [
          {id: '1', name: 'Home', title: '首頁'},
          {id: '2', name: 'Course', title: '免費課程'},
          {id: '3', name: 'LightCourse', title: '輕課'},
          {id: '4', name: 'Micro', title: '學位課程'}
        ],
        isShow: false
      }
    }
  }
</script>

　　編寫headerList列表及列表中的導航對象，在 導航欄中遍歷對象獲取對應信息，显示在頁面效果如下所示：

3、router-link路由跳轉

　　經過上面的編寫，雖然導航欄已經可以正常显示，但是a標籤是不會做自動跳轉的。 需要使用 router-link 進一步改寫LuffyHeader.vue，使得路由跳轉得以渲染對應組件：

<template>
  <!-- element-ui -->
  <el-container>
    <el-header height = '80px' >
      <div class="header">
        <div class="nav-left">
          <img src="https://www.luffycity.com/static/img/head-logo.a7cedf3.svg" alt="">
        </div>
        <div class="nav-center">
          <ul>
            <li v-for="(list, index) in headerList" :key="list.id">
              <router-link :to="{name:list.name}">
                {{ list.title }}
              </router-link>
            </li>
          </ul>
        </div>
        <div class="nav-right">
          <span>登錄</span>
          &nbsp;| &nbsp;
          <span>註冊</span>
        </div>
      </div>
    </el-header>
  </el-container>
</template>

<script>
  export default {
    name: 'LuffyHeader',
    data() {
      return {
        headerList: [
          {id: '1', name: 'Home', title: '首頁'},
          {id: '2', name: 'Course', title: '免費課程'},
          {id: '3', name: 'LightCourse', title: '輕課'},
          {id: '4', name: 'Micro', title: '學位課程'}
        ],
        isShow: false
      }
    }
  }
</script>

　　使用to='{name:list.name}’設置命令路由，這樣點擊a標籤就可以跳轉了。显示效果如下所示：

　　可以看到雖然點擊了輕課，但是和其他導航項樣式沒有任何分別，需要設置路由active樣式完成優化。

4、linkActiveClass設置路由的active樣式

　　linkActiveClass 全局配置 <router-link> 的默認“激活 class 類名”。

　　active-class 設置 鏈接激活時使用的 CSS 類名。默認值可以通過路由的構造選項 linkActiveClass 來全局配置。

（1）在路由配置linkActiveClass

　　在 src/router/index.js 中做如下配置：

import Vue from 'vue'
import Router from 'vue-router'
// @絕對路徑 檢索到 ...src/

// 如果Router當做局部模塊使用一定要Vue.use(Router)
// 以後在組件中，可以通過this.$router 獲取Router實例化對象
// 路由信息對象 this.$routes 獲取路由配置信息
import Home from '@/components/Home/Home'
import Course from '@/components/Course/Course'
import LightCourse from '@/components/LightCourse/LightCourse'
import Micro from '@/components/Micro/Micro'

Vue.use(Router)

// 配置路由規則
export default new Router({
  linkActiveClass: 'is-active',
  routes: [
    {
      path: '/',
      redirect: '/home'   // 訪問/，直接跳轉到/home路徑
    },
    ......
    {
      path: '/micro',
      name: 'Micro',
      component: Micro
    }
  ]
})

（2）在LuffyHeader.vue中配置路由active樣式

<template>
  ......省略
</template>

<script>
  ......省略
</script>

<style lang="css" scoped>
  .nav-center ul li a.is-active{
    color: #4a4a4a;
    border-bottom: 4px solid #ffc210;
  }
</style>

（3）显示效果

5、hash模式切換為 history 模式

　　vue-router 默認 hash 模式——使用URL的hash來模擬一個完整的URL，於是當URL改變時，頁面不會重新加載。比如http://www.abc.com/#/index，hash值為#/index。hash模式的特點在於hash出現在url中，但是不會被包括在HTTP請求中，對後端沒有影響，不會重新加載頁面。

　　如果不想要這種显示比較丑的hash，可以用路由的 history模式，這種模式充分利用 history.pushState API來完成URL跳轉而無需重新加載頁面。

（1）路由修改為history模式

　　修改 src/router/index.js 文件如下所示：

import Vue from 'vue'
import Router from 'vue-router'
// @絕對路徑 檢索到 ...src/

// 如果Router當做局部模塊使用一定要Vue.use(Router)
// 以後在組件中，可以通過this.$router 獲取Router實例化對象
// 路由信息對象 this.$routes 獲取路由配置信息
import Home from '@/components/Home/Home'
import Course from '@/components/Course/Course'
import LightCourse from '@/components/LightCourse/LightCourse'
import Micro from '@/components/Micro/Micro'

Vue.use(Router)

// 配置路由規則
export default new Router({
  linkActiveClass: 'is-active',
  mode: 'history',   // 改為history模式
  routes: [
    {
      path: '/',
      redirect: '/home'   // 訪問/，直接跳轉到/home路徑
    },
    .....
  ]
})

　　使用history模式時，url就像正常url，例如http://yoursite.com/user/id，這樣比較美觀。

　　显示效果如下所示：

（2）後端配置

　　 但是要用好這種模式，需要後台配置支持。vue的應用是單頁客戶端應用，如果後台沒有正確的配置，用戶在瀏覽器訪問http://yoursite.com/user/id 就會返回404，這樣就不好了。

　　因此要在服務端增加一個覆蓋所有情況的候選資源：如果 URL 匹配不到任何靜態資源，則應該返回同一個 index.html 頁面，這個頁面就是app依賴的頁面。

　　後端配置示例：https://router.vuejs.org/zh/guide/essentials/history-mode.html#%E5%90%8E%E7%AB%AF%E9%85%8D%E7%BD%AE%E4%BE%8B%E5%AD%90

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!

目錄

• 一.概述
• 二. 數據結構
  • 2.1 鏈表
  • 2.2 二叉堆
• 三. 從setTimeout理解Timer模塊源碼
  • 3.1 timers.js中的定義
  • 3.2 Timeout類定義
  • 3.3 active(timeout)
  • 3.4 定時器的處理執行邏輯
  • 3.5 實例分析
• 四. 小結

示例代碼託管在：http://www.github.com/dashnowords/blogs

博客園地址：《大史住在大前端》原創博文目錄

華為雲社區地址：【你要的前端打怪升級指南】

一.概述

Timer模塊相關的邏輯較為複雜，不僅包含JavaScript層的實現，也包括C++編寫的與底層libuv協作的代碼，想要完整地看明白是比較困難的，本章僅以setTimeout這個API的實現機製為主線，講述源碼中的JavaScript相關的實現部分，這部分只需要一些數據結構的基本知識就可以理解。

二. 數據結構

setTimeout這個API的實現基於兩類基本數據結構，我們先來複習一下相關的特點。對數據結構知識比較陌生的小夥伴可以參考【野生前端的數據結構基礎練習】系列博文自行學習，所有的章節都有示例代碼。

2.1 鏈表

鏈表是一種物理存儲單元上非連續的存儲結構，存儲元素的邏輯順序是由鏈表中的指針鏈接次序來決定的。每一個節點包含一個存放數據的數據域和存放下一個節點的指針域（雙向鏈表中指針數量為2）。鏈表在插入元素時的時間複雜度為O(1)（因為隻影響插入點前後的節點，無論鏈表有多大），但是由於空間不連續的特點，訪問一個未排序鏈表的指定節點時就需要逐個對比，時間複雜度為O(n)，比數組結構就要慢一些。鏈表結構也可以根據指針特點分為單向鏈表,雙向鏈表和循環鏈表，Timer模塊中使用的鏈表結構就是雙向循環鏈表,Node.js中源碼的底層數據結構實現都是獨立的，鏈表的源碼放在lib/internal/linkedlist.js：

'use strict';

function init(list) {
  list._idleNext = list;
  list._idlePrev = list;
}

// Show the most idle item.
function peek(list) {
  if (list._idlePrev === list) return null;
  return list._idlePrev;
}

// Remove an item from its list.
function remove(item) {
  if (item._idleNext) {
    item._idleNext._idlePrev = item._idlePrev;
  }

  if (item._idlePrev) {
    item._idlePrev._idleNext = item._idleNext;
  }

  item._idleNext = null;
  item._idlePrev = null;
}

// Remove an item from its list and place at the end.
function append(list, item) {
  if (item._idleNext || item._idlePrev) {
    remove(item);
  }

  // Items are linked  with _idleNext -> (older) and _idlePrev -> (newer).
  // Note: This linkage (next being older) may seem counter-intuitive at first.
  item._idleNext = list._idleNext; //1
  item._idlePrev = list;//2

  // The list _idleNext points to tail (newest) and _idlePrev to head (oldest).
  list._idleNext._idlePrev = item;//3
  list._idleNext = item;//4
}

function isEmpty(list) {
  return list._idleNext === list;
}

鏈表實例初始化了兩個指針，初始時均指向自己，_idlePrev指針將指向鏈表中最新添加進來的元素，_idleNext指向最新添加進來的元素，實現的兩個主要操作為remove和append。鏈表的remove操作非常簡單，只需要將刪除項前後的元素指針加以調整，然後將被刪除項的指針置空即可，就像從一串鎖鏈中拿掉一節，很形象。

源碼中的idlePrev和idleNext很容易混淆，建議不用強行翻譯為“前後”或者“新舊”，（反覆記憶N次都記不住我也很無奈），直接按對應位置來記憶就可以了，愛翻譯成什麼就翻譯成什麼。

源碼中的鏈表實現並沒有提供指定位置插入的方法，append( )方法默認只接收list和item兩個參數，新元素會被默認插入在鏈表的固定位置，這與它的使用方式有關，所以沒必要實現完整的鏈表數據結構。append稍微複雜一些，但是源碼中也做了非常詳細的註釋。首先需要確保插入的元素是獨立的（也就是prev和next指針都為null），然後再開始調整，源碼中的鏈表是一個雙向循環鏈表，我們調整一下源碼的順序會更容易理解，其實插入一個元素就是要將各個元素的prev和next兩個指針調整到位就可以了。先來看_idlePrev指針鏈的調整， 也就是指針調整代碼中標記為2和3的語句：

item._idlePrev = list;//2
list._idleNext._idlePrev = item;//3

這裏可以把list看作是一個prev指針連接起來的單向鏈表，相當於將新元素item按照prev指針的指向添加到list和原本的list._idleNext指向的元素中間，而1和4語句是調整了反方向的next指針鏈：

item._idleNext = list._idleNext; //1
list._idleNext = item;//4

調整后的鏈表以next指針為依據就可以形成反方向的循環鏈表，然後只需要記住list._idleNext指針指向的是最新添加的項就可以了。

如上圖所示，next和prev分別可以作為鏈表的邏輯順序形成循環鏈。

2.2 二叉堆

源碼放在lib/internal/priority_queue.js中，一些博文也直接翻譯為優先隊列，它們是抽象結構和具體實現之間的關係，特性是一致的。二叉堆是一棵有序的完全二叉樹，又以節點與其後裔節點的關係分為最大堆和最小堆。完全二叉樹的特點使其可以很容易地轉化為一維數組來存儲，且不需要二外記錄其父子關係，索引為i的節點的左右子節點對應的索引為2i+1和2i+2(當然左右子節點也可能只有一個或都不存在)。Node.js就使用一維數組來模擬最小堆。源碼基本上就是這一數據結構和“插入”，“刪除”這些基本操作的實現。

堆結構的使用最主要的是為了獲得堆頂的元素，因為它總是所有數據里最大或最小的，同時堆結構是一個動態調整的數據結構，插入操作時會將新節點插入到堆底，然後逐層檢測和父節點值的相對大小而“上浮”直到整個結構重新變為堆；進行移除操作（移除堆頂元素也是移除操作的一種）時，需要將堆尾元素置換到移除的位置，以維持整個數據結構依然是一棵完全二叉樹，然後通過與父節點和子節點進行比較來決定該位置的元素應該“上浮”或“下沉”，並遞歸這個過程直到整個數據結構被重建為堆。相關的文章非常，本文不再贅述（可以參考這篇博文【二叉堆的添加和刪除元素方法】，有動畫好理解）。

三. 從setTimeout理解Timer模塊源碼

timer模塊並不需要手動引入，它的源碼在/lib/timers.js目錄中，我們以這樣一段代碼來看看setTimeout方法的執行機制：

setTimeout(()=>{console.log(1)},1000);
setTimeout(()=>{console.log(2)},500);
setTimeout(()=>{console.log(3)},1000);

3.1 timers.js中的定義

最上層方法的定義進行了一些參數格式化，將除了回調函數和延遲時間以外的其他參數組成數組（應該是用apply來執行callback方法時把這些參數傳進去），接着做了三件事，生成timeout實例，激活實例，返回實例。

3.2 Timeout類定義

Timeout類定義在【lib/internal/timers.js】中：

初始化了一些屬性，可以看到傳入構造函數的callback,after,args都被記錄下來，可以看到after的最小值為1ms，Timeout還定義了一些原型方法可以先不用管，然後調用了initAsyncResource( )這個方法，它在實例上添加了[async_id_symbol]和[trigger_async_id_symbol]兩個標記后，又調用了emitInit( )方法將這些參數均傳了進去，這個emitInit( )方法來自於/lib/internal/async_hooks.js，官方文檔對async_hook模塊的解釋是：

The async_hooks module provides an API to register callbacks tracking the lifetime of asynchronous resources created inside a Node.js application.

它是一個實驗性質的API，是為了Node.js內部創建的用於追蹤異步資源生命周期的模塊，所以推測這部分邏輯和執行機制關係不大，可以先擱在一邊。

3.3 active(timeout)

獲得了timeout實例后再回到上層函數來，接下來執行的是active(timeout)這個方法，它調用的是insert( item, true, getLibuvNow()),不難猜測最後這個方法就是從底層libuv中獲取一個準確的當前時間，insert方法的源碼如下：

首先為timeout實例添加了開始執行時間idleStart屬性，接下來的邏輯涉及到兩個對象，這裏提前說明一下：timerListMap是一個哈希表，延時的毫秒數為key，其value是一個雙向鏈表，鏈表中存放着timeout實例，所以timerListMap就相當於一個按延時時間來分組存放定時器實例的Hash+linkedList結構，另一個重要對象timerListQueue就是上面講過的優先隊列（後文使用“二叉堆”這一概念）。

這裡有一個小細節，就是將新的定時器鏈表加入二叉堆時，比較函數是自定義傳入的，在源碼中很容易看到compareTimersLists ( )這個方法使用鏈表的expiry屬性的值進行比較來得到最小堆，由此可以知道，堆頂的鏈表總是expiry最小的，也就是說堆頂鏈表的__idlePrev指向的定時器，就是所有定時器里下一個需要觸發回調的。

接下來再來看看active( )函數體的具體邏輯，如果有對應鍵的鏈表則獲取到它（list變量），如果沒有則生成一個新的空鏈表，然後將這個鏈表添加進二叉堆，跳過中間的步驟，在最後可以看到執行了：

L.append(list, item);

這個L實際上是來自於前文提過的linkedList.js中的方法，就是將timeout實例添加到list鏈表中，來個圖就很容易理解了：

中間我們跳過了一點邏輯，就是在新鏈表生成時執行的:

if(nextExpiry > expiry){
    scheduleTimer(msecs);
    nextExpiry = expiry;
}

nextExpiry是timer模塊中維護的一個模塊內的相對全局變量，這裏的expiry是新鏈表的下一個定時器的過期時間（也就是新鏈表中唯一一個timeout實例的過期時間）,這裏針對的情況就是新生成的定時器比已存在的所有定時器都要更早觸發，這時就需要重新調度一下，並把當前這個定時器的過期時間點設置為nextExpiry時間。

這個scheduleTimer( )使用internalBinding('timers')引入的，在lib/timer.cc中找到這個方法：

void ScheduleTimer(const FunctionCallbackInfo<Value>& args) {
  auto env = Environment::GetCurrent(args);
  env->ScheduleTimer(args[0]->IntegerValue(env->context()).FromJust());
}

再跳到env.cc:

void Environment::ScheduleTimer(int64_t duration_ms) {
  if (started_cleanup_) return;
  uv_timer_start(timer_handle(), RunTimers, duration_ms, 0);
}

可以看到這裏就將定時器的信息和libuv的事件循環聯繫在一起了，libuv還沒有研究，所以這條邏輯線暫時到此為止。再回到之前的示例，當三個定時器都添加完成后，內存中的對象關係基本是下面的樣子：

3.4 定時器的處理執行邏輯

至此我們已經將定時器的信息都存放好了，那麼它是如何被觸發的呢？我們找到node.js的啟動文件lib/internal/bootstrap/node.js284-290行，可以看到，在啟動函數中，Node.js通過調用setTimers( )方法將定時器處理函數processTimers傳遞給了底層，它最終會被用來調度執行定時器，processTimers方法由lib/internal/timers.js中提供的getTimerCallbacks(runNextTicks) 方法運行得到，所以聚焦到/lib/internal/timers.js中：

推測libuv每次需要檢查是否有定時器到期時都會運行processTimers( )方法，來看一下對應的邏輯，一個無限循環的while語句，直到二叉堆的堆頂沒有任何定時器時跳出循環並返回0。在循環體內部，會用堆頂元素的過期時間和當前時間相比，如果list.expiry更大，說明時機未到還不需要執行，把它的過期時間賦值給nextExpiry然後返回（返回邏輯先不細究）。如果邏輯執行到471行，說明堆頂元素的過期時間已經過了，ranAtLeastOneList這個標記位使得這段邏輯按照如下方式運行：

1.獲取到一個expiry已經過期的鏈表,首次向下執行時`ranAtLeastOneList`為false，則將其置為true，然後執行`listOnTimeout()`這個方法;
2.然後繼續取堆頂的鏈表，如果也過期了，再次執行時，會先執行`runNextTicks()`，再執行`listOnTimeout()`。

我們按照邏輯順序，先來看看listOnTimeout( )這個方法，它有近100行（我們以上面3個定時器的實例來看看它的執行邏輯）：

  function listOnTimeout(list, now) {
    const msecs = list.msecs; //500 , 500ms的鏈表在堆頂

    debug('timeout callback %d', msecs);

    var diff, timer;
    let ranAtLeastOneTimer = false;
    while (timer = L.peek(list)) {  //取鏈表_idlePrev指向的定時器，也就是鏈表中最先到期的
      diff = now - timer._idleStart;  //計算當前時間和它開始計時那個時間點的時間差，

      // Check if this loop iteration is too early for the next timer.
      // This happens if there are more timers scheduled for later in the list.
      // 原文翻譯：檢測當前事件循環對於下一個定時器是否過早，這種情況會在鏈表中還有其他定時器時發生。
      // 人話翻譯：就是當前的時間點只需要觸發鏈表中第一個500ms定時器，下一個500ms定時器還沒到觸發時間。
      //         極端的相反情況就是由於阻塞時間已經過去很久了，鏈表裡的N個定時器全都過期了，都得執行。
      if (diff < msecs) {
        //更新鏈表中下一個到期定時器的時間記錄，計算邏輯稍微有點繞
        list.expiry = Math.max(timer._idleStart + msecs, now + 1);
        list.id = timerListId++;
        timerListQueue.percolateDown(1);//堆頂元素值發生更新，需要通過“下沉”來重構“堆”
        debug('%d list wait because diff is %d', msecs, diff);
        return; //直接結束了
      }

      //是不是貌似見過這段，先放着等會一塊說
      if (ranAtLeastOneTimer)
        runNextTicks();
      else
        ranAtLeastOneTimer = true;

      // The actual logic for when a timeout happens.
      L.remove(timer);

      const asyncId = timer[async_id_symbol];

      if (!timer._onTimeout) {
        if (timer[kRefed])
          refCount--;
        timer[kRefed] = null;

        if (destroyHooksExist() && !timer._destroyed) {
          emitDestroy(asyncId);
          timer._destroyed = true;
        }
        continue;
      }

      emitBefore(asyncId, timer[trigger_async_id_symbol]);

      let start;
      if (timer._repeat) //這部分看起來應該是interval的邏輯，interval底層實際上就是一個重複的timeout
        start = getLibuvNow();

      try {
        const args = timer._timerArgs;
        if (args === undefined)
          timer._onTimeout();  //設置定時器時傳入的回調函數被執行了
        else
          timer._onTimeout(...args);
      } finally {
        if (timer._repeat && timer._idleTimeout !== -1) {
          timer._idleTimeout = timer._repeat;
          if (start === undefined)
            start = getLibuvNow();
          insert(timer, timer[kRefed], start);//interval的真實執行邏輯，重新獲取時間然後插入到鏈表中
        } else if (!timer._idleNext && !timer._idlePrev) {
          if (timer[kRefed])
            refCount--;
          timer[kRefed] = null;

          if (destroyHooksExist() && !timer._destroyed) {
            emitDestroy(timer[async_id_symbol]);
            timer._destroyed = true;
          }
        }
      }

      emitAfter(asyncId);
    }
      
    //這塊需要注意的是，上面整個邏輯都包在while(timer = L.peek(list)){...}裏面

    // If `L.peek(list)` returned nothing, the list was either empty or we have
    // called all of the timer timeouts.
    // As such, we can remove the list from the object map and
    // the PriorityQueue.
    debug('%d list empty', msecs);

    // The current list may have been removed and recreated since the reference
    // to `list` was created. Make sure they're the same instance of the list
    // before destroying.
    // 原文翻譯：當前的list標識符所引用的list有可能已經經過了重建，刪除前需要確保它指向哈希表中的同一個實例。
    if (list === timerListMap[msecs]) {
      delete timerListMap[msecs];
      timerListQueue.shift();
    }
  }

3.5 實例分析

代碼邏輯因為包含了很多條件分支，所以不容易理解，我們以前文的實例作為線索來看看定時器觸發時的執行邏輯：

程序啟動后，processTimer( )方法不斷執行，第一個過期的定時器會在堆頂的500ms定時器鏈表（下面稱為500鏈表）中產生，過期時間戳為511。

假設時間戳到達600時程序再次執行processTimer( )，此時發現當前時間已經超過nextExpiry記錄的時間戳511，於是繼續向下執行進入listOnTimeout(list, now)，這裏的list就是哈希表中鍵為500的鏈表，now就是當前時間600，進入listOnTimeout方法后，獲取到鏈表中最早的一個定時器timer,然後計算diff參數為600-11=589, 589 > 500， 於是繞過條件分支語句，ranAtLeastOneTimer為false也跳過（跳過後其值為true），接下來的邏輯從鏈表中刪除了這個timer，然後執行timer._onTimeout指向的回調函數，500鏈表只有一個定時器，所以下一循環時L.peek(list)返回null，循環語句跳出，繼續向後執行。此時list依然指向500鏈表，於是執行刪除邏輯，從哈希表和二叉堆中均移除500鏈表，兩個數據結構在底層會進行自調整。

processTimer( )再次執行時，堆頂的鏈表變成了1000ms定時器鏈表（下面稱為1000鏈表），nextExpiry賦值為list.expiry，也就是1001，表示1000ms定時器鏈表中下一個到期的定時器會在時間戳超過1001時過期，但時間還沒有到。下面分兩種情況來分析：

1.時間戳為1010時執行processTimer( )

時間來到1010點，processTimer( )被執行，當前時間1010大於nextExpiry=1001，於是從堆頂獲取到1000鏈表，進入listOnTimeout( )，第一輪while循環執行時的情形和500鏈表執行時是一致的，在第二輪循環中，timer指向1000鏈表中后添加的那個定時器，diff的值為 1010 – 21 = 989,989 < 1000 ,所以進入if(diff < msecs)的條件分支，list.expiry調整為下一個timer的過期時間1021，然後通過下沉來重建二叉堆（堆頂元素的expiry發生了變化），上面的實例中只剩了唯一一個鏈表，所以下沉操作沒有引發什麼實質影響，接着退出當前函數回到processTimer的循環體中，接着processTimer里的while循環繼續執行，再次檢查棧頂元素，時間還沒到，然後退出，等時間超過下一個過期時間1021后，最後一個定時器被觸發，過程基本一致，只是鏈表耗盡後會觸發listOnTimeout後面的清除哈希表和二叉堆中相關記錄的邏輯。

總結一下，鏈表的消耗邏輯是，從鏈表中不斷取出peek位置的定時器，如果過期了就執行，如果取到一個沒過期的，說明鏈表裡後續的都沒過期，就修改鏈表上的list.expiry屬性然後退回到processTimer的循環體里，如果鏈表耗盡了，就將它從哈希表和二叉堆中把這個鏈表刪掉。

2.時間戳為1050時執行processTimer( )

假如程序因為其他原因直到時間為1050時才開始檢查1000鏈表，此時它的兩個定時器都過期了需要被觸發，listOnTimeout( )中的循環語句執行第一輪時是一樣的，第二次循環執行時，跳過if(diff < msecs)的分支，然後由於ranAtLeastOneTimer標記位的變化，除了第一個定時器的回調外，其他都會先執行runNextTicks( )然後再執行定時器上綁的回調，等到鏈表耗盡后，進入後續的清除邏輯。

我們再來看一種更極端的情況，假如程序一直阻塞到時間戳為2000時才執行到processTimer(此時3個定時器都過期了，2個延遲1000ms，1個延遲500ms，堆頂為500ms鏈表)，此時processTimer( )先進入第一次循環，處理500鏈表，然後500鏈表中唯一的定時器處理完后，邏輯回到processTimer的循環體，再進行第二輪循環，此時獲取到堆頂的1000鏈表，發現仍然需要執行，那麼就會先執行runNextTicks( )，然後在處理1000鏈表，後面的邏輯就和上面時間戳為1050時執行processTimer基本一致了。

至此定時器的常規邏輯已經解析完了，還有兩個細節需要提一下，首先是runNextTicks( )，從名字可以推測它應該是執行通過process.nextTick( )添加的函數，從這裏的實現邏輯來看，當有多個定時器需要觸發時，每個間隙都會去消耗nextTicks隊列中的待執行函數，以保證它可以起到“盡可能早地執行”的職責，對此不了解的讀者可以參考上一篇博文【譯】Node.js中的事件循環，定時器和process.nextTick。

四. 小結

timer模塊比較大，在了解基本數據結構的前提下不算特別難理解，setImmediate( )和process.nextTick( )的實現感興趣的讀者可以自行學習，想要對事件循環機制有更深入的理解，需要學習C++和libuv的相關原理，筆者尚未深入涉獵，以後有機會再寫。

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

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

不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!