分類
發燒車訊

『圖論』LCA 最近公共祖先

概述篇

LCA (Least Common Ancestors) ,即最近公共祖先,是指這樣的一個問題:在一棵有根樹中,找出某兩個節點 uv 最近的公共祖先。

LCA 可分為在線算法離線算法

  • 在線算法:指程序可以以序列化的方式一個一個處理輸入,也就是說在一開始並不需要知道所有的輸入。
  • 離線算法:指一開始就需要知道問題的所有輸入數據,而在解決一個問題后立即輸出結果。

算法篇

對於該問題,很容易想到的做法是從 u、v 分別回溯到根節點,然後這兩條路徑中的第一個交點即為 u、v 的最近公共祖先,在一棵平衡二叉樹中,該算法的時間複雜度可以達到 O(logn)O(log⁡n) ,但是對於某些退化為鏈狀的樹來說,算法的時間複雜度最壞為 O(n)O(n) ,顯然無法滿足更高頻率的查詢。

本節將介紹幾種比較高效的算法來解決這一問題,常見的算法有三種:在線 DFS + ST 算法、倍增算法、離線 Tarjan 算法。

接下來我們來一一解釋這三種 /* 看似高深,其實也不簡單 */ 的算法。

在線 DFS + ST 算法

首先看到 ST 你會想到什麼呢?(腦補許久都沒有想到它會是哪個單詞的縮寫)

看過前文 『數據結構』RMQ 問題 的話你便可以明白 ST算法 的思路啦~

So ,關於 LCA 的這種在線算法也是可以建立在 RMQ 問題的基礎上咯~

我們設 LCA(T,u,v) 為在有根樹 T 中節點 u、v 的最近公共祖先, RMQ(A,i,j) 為線性序列 A 中區間 [i,j] 上的最小(大)值。

如下圖這棵有根樹:

我們令節點編號滿足父節點編號小於子節點編號(編號條件)

可以看出 LCA(T,4,5) = 2, LCA(T,2,8) = 1, LCA(T,3,9) = 3

設線性序列 A 為有根樹 T 的中序遍歷,即 A = [4,2,5,1,8,6,9,3,7]

由中序遍歷的性質我們可以知道,任意兩點 u、v 的最近公共祖先總在以該兩點所在位置為端點的區間內,且編號最小。

舉個栗子:

假設 u = 8, v = 7 ,則該兩點所確定的一段區間為 [8,6,9,3,7] ,而區間最小值為 3 ,也就是說,節點 3u、v 的最近公共祖先。

解決區間最值問題我們可以採用 RMQ 問題中的 ST 算法

但是在有些問題中給出的節點並不一定滿足我們所說的父節點編號小於子節點編號,因此我們可以利用節點間的關係建圖,然後採用前序遍歷來為每一個節點重新編號以生成線性序列 A ,於是問題又被轉化為了區間最值的查詢,和之前一樣的做法咯~

時間複雜度: n×O(logn)n×O(log⁡n) 預處理 + O(1)O(1) 查詢

想了解 RMQ 問題 的解法可以戳上面的鏈接哦~

以上部分介紹了 LCA 如何轉化為 RMQ 問題,而在實際中這兩種方案之間可以相互轉化

類比之前的做法,我們如何將一個線性序列轉化為滿足編號條件的有根樹呢?

  1. 設序列中的最小值為 AkAk ,建立優先級為 AkAk 的根節點 TkTk
  2. 將 A[1…k−1]A[1…k−1] 遞歸建樹作為 TkTk 的左子樹
  3. 將 A[k+1…n]A[k+1…n] 遞歸建樹作為 TkTk 的右子樹

讀者可以試着利用此方法將之前的線性序列 A = [4,2,5,1,8,6,9,3,7] 構造出有根樹 T ,結果一定滿足之前所說的編號條件,但卻不一定唯一。

離線 Tarjan 算法

Tarjan 算法是一種常見的用於解決 LCA 問題的離線算法,它結合了深度優先搜索與並查集,整個算法為線性處理時間。

首先來介紹一下 Tarjan 算法的基本思路:

  1. 任選一個節點為根節點,從根節點開始
  2. 遍歷該點 u 的所有子節點 v ,並標記 v 已經被訪問過
  3. 若 v 還有子節點,返回 2 ,否則下一步
  4. 合併 v 到 u 所在集合
  5. 尋找與當前點 u 有詢問關係的點 e
  6. 若 e 已經被訪問過,則可以確定 u、e 的最近公共祖先為 e 被合併到的父親節點

偽代碼:

Tarjan(u)               // merge 和 find 為並查集合併函數和查找函數
{
    for each(u,v)       // 遍歷 u 的所有子節點 v
    {
        Tarjan(v);      // 繼續往下遍歷
        merge(u,v);     // 合併 v 到 u 這一集合
        標記 v 已被訪問過;
    }
    for each(u,e)       // 遍歷所有與 u 有查詢關係的 e
    {
        if (e 被訪問過)
            u, e 的最近公共祖先為 find(e);
    }
}
C++

感覺講到這裏已經沒有其它內容了,但是一定會有好多人沒有理解怎麼辦呢?

我們假設在如下樹中模擬 Tarjan 過程(節點數量少一點可以畫更少的圖o( ̄▽ ̄)o)

存在查詢: LCA(T,3,4)、LCA(T,4,6)、LCA(T,2,1)

注意:每個節點的顏色代表它當前屬於哪一個集合,橙色線條為搜索路徑,黑色線條為合併路徑。

當前所在位置為 u = 1 ,未遍歷孩子集合 v = {2,5} ,向下遍歷。

當前所在位置為 u = 2 ,未遍歷孩子集合 v = {3,4} ,向下遍歷。

當前所在位置為 u = 3 ,未遍歷孩子集合 v = {} ,遞歸到達最底層,遍歷所有相關查詢發現存在 LCA(T,3,4) ,但是節點 4 此時標記未訪問,因此什麼也不做,該層遞歸結束。

遞歸返回,當前所在位置 u = 2 ,合併節點 3u 所在集合,標記 vis[3] = true ,此時未遍歷孩子集合 v = {4} ,向下遍歷。

當前所在位置 u = 4 ,未遍歷孩子集合 v = {} ,遍歷所有相關查詢發現存在 LCA(T,3,4) ,且 vis[3] = true ,此時得到該查詢的解為節點 3 所在集合的首領,即 LCA(T,3,4) = 2 ;又發現存在相關查詢 LCA(T,4,6) ,但是節點 6 此時標記未訪問,因此什麼也不做。該層遞歸結束。

遞歸返回,當前所在位置 u = 2 ,合併節點 4u 所在集合,標記 vis[4] = true ,未遍歷孩子集合 v = {} ,遍歷相關查詢發現存在 LCA(T,2,1) ,但是節點 1 此時標記未訪問,因此什麼也不做,該層遞歸結束。

遞歸返回,當前所在位置 u = 1 ,合併節點 2u 所在集合,標記 vis[2] = true ,未遍歷孩子集合 v = {5} ,繼續向下遍歷。

當前所在位置 u = 5 ,未遍歷孩子集合 v = {6} ,繼續向下遍歷。

當前所在位置 u = 6 ,未遍歷孩子集合 v = {} ,遍歷相關查詢發現存在 LCA(T,4,6) ,且 vis[4] = true ,因此得到該查詢的解為節點 4 所在集合的首領,即 LCA(T,4,6) = 1 ,該層遞歸結束。

遞歸返回,當前所在位置 u = 5 ,合併節點 6u 所在集合,並標記 vis[6] = true ,未遍歷孩子集合 v = {} ,無相關查詢因此該層遞歸結束。

遞歸返回,當前所在位置 u = 1 ,合併節點 5u 所在集合,並標記 vis[5] = true ,未遍歷孩子集合 v = {} ,遍歷相關查詢發現存在 LCA(T,2,1) ,此時該查詢的解便是節點 2 所在集合的首領,即 LCA(T,2,1) = 1 ,遞歸結束。

至此整個 Tarjan 算法便結束啦~

PS:不要在意最終根節點的顏色和其他節點顏色有一點點小小差距,可能是在染色的時候沒仔細看,總之就這樣咯~

PPS:所謂的首領就是、就是首領啦~

倍增算法

哇!還有一個倍增算法以後繼續補充吧!

總結篇

對於不同的 LCA 問題我們可以選擇不同的算法。

假若一棵樹存在動態更新,此時離線算法就顯得有點力不從心了,但是在其他情況下,離線算法往往效率更高(雖然不能保證得到解的順序與輸入一致,不過我們有 sort 呀)

總之,喜歡哪種風格的 code 是我們自己的意願咯~

另外, LCA 和 RMQ 問題是兩個非常基礎的問題,很多複雜問題都可以轉化為這兩類問題來解決。(當然這兩類問題之間也可以相互轉化啦~)

參考資料

OI wiki https://oi-wiki.org/graph/lca/

https://blog.csdn.net/my_sunshine26/article/details/72717112

https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/03.03.html

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

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

FB行銷專家,教你從零開始的技巧

分類
發燒車訊

最新 iOS 框架整體梳理(三),最新 iOS 框架整體梳理(一),最新 iOS 框架整體梳理(二),iOS – QuartzCore

 

      這一篇得把介紹框架這個系列終結了,不能超過三篇了,不然太長了….. 還是老規矩,前面兩篇的機票在下方:

      最新 iOS 框架整體梳理(一)

      最新 iOS 框架整體梳理(二)

 

Part – 3

 

           

 

62、Metal  MetalKit

       Metal ( [ˈmetl] )  這是一個和 OpenGLES 類似的面向底層的圖形處理接口,這也是蘋果自己搞出來的,所以這個框架我還是推薦要有一個大概的了解。

       Metal 系列教程(1)- Metal 介紹及基本使用  (系列文章三篇都是講述 Metal 的,可以學習一下)

       iOS漸變二維碼之Metal實現篇

       官方文檔

63、MetalPerdormanceShaders

       其實這個 MetalPerdormanceShaders 也是屬於Metal的內容,關於它的具體的使用我推薦一篇利用它組高斯迷糊的文章。

       學習用MetalPerformanceShaders進行圖像處理

       官方文檔

64、MetricKit

       這是一個在 iOS 13 中新加入的框架,iOS 13 中推出了MetricKit,它用於收集和處理電池和性能指標。

       iOS MetricsKit 收集電量和性能數據

       官方文檔

65、MobileCoreServices

       要是在iOS10 以後在有一些APP之間跳轉的時候是需要這個框架的,我也了解了一下關於這個框架,幾乎說的都是使用它的私有API的情況下跳轉,所以不推薦使用!按照現在的審核要求私有API是行不通的,要承擔被下架的風險,具體的UTIs可以在下面查詢.

       UTIs

66、ModelIo

      這個框架出來的相對比較早了 iOS 9 的時候發布的,但在日常中使用的還真的不多,但關於這個框架的基本的認知還是可以通過官方文檔了解到的。

      官方文檔 

67、MultiPeerConnectivity

       這個框架我們也是有必要了解一下的,它主要是用於iOS設備間的通信,就像我們兩台iOS設備間使用 Airdrop 傳輸文件等都是屬於iOS通訊的,藉助這個機會我也給大家介紹一個直接從手機拍照導入mac的快速方法,右鍵桌面,見下圖。這個是我自己經常會用到的一個東西。

 

 

       下面是對於iOS設備間通信方式的一個總結小圖:

 

 

        圖片來源於  iOS近距離實時通信解決方案 這篇文章也能讓我們了解這個框架。

        官方文檔

68、NaturalLanguage、

       這是一個很有趣的框架,是在iOS12中新加入的,大家在發微信消息的時候比如說了句“我想你了”微信就會有小星星雨下落,當然不一定微信是利用這個框架實現的,但這個自然語言分析框架也的確能幫我們實現這一點。具體它的使用以及怎樣分析語言的就需要我們自己探索一下了。

       Apple NLP框架NaturalLanguage的應用實例

       官方文檔

69、NetWork  NetWorkExtension

      它可給系統WiFi列表列表裡邊的WiFi設置密碼 、標籤(副標題)。 還可獲取整個WiFi列表。獲取到WIFI列表之後呢,判斷有沒有連接上自己公司的WIFI,然後讓他打卡上班?這個我真沒試過,要有這種需求還真的是有點厲害!

     iOS 獲取系統wifi列表,wifi信號強度,並給wifi設置密碼,標籤(副標題)

     官方文檔

70、NewsstandKit ( deprecated 

71、NotificationCenter

      框架這東西整理的時候我發現兩個問題,最不常用的、最常用的反而是最難料理的。這個通知就是,不管是本地通知還是遠程通知我相信大家用的都很熟悉很熟悉了!所以關於它真的也只能一筆帶過了,不過還是提一句,通知框架里的東西的確需要我們掌握的,尤其是在iOS10之後蘋果在通知上是下了一份功夫的。

72、OpenAL

      它也是一個音頻播放的框架,我們前面說過的關於音頻播放的框架真的不少了,像 AudioToolbox ,但它們之間還是有區別的,在延時、緩存等方面存在着區別。

      OpenAL的一些知識點

73、OpenGLES

      iOS上繪製圖形的方式很多,UIKit,CoreGraphics,SpriteKit,OpenGL ES,Metal等。OpenGL ES是一套非常底層但使用非常廣泛的C語言API,專為移動設備定製,可在不同的手機系統或瀏覽器上使用,渲染效果非常好。

      iOS-OpenGLES  這是個系列文章,從這裏進去有好多的東西等着你學習呢。

74、PassKit

      PassKit 框架在您的應用程序中請求和處理Apple Pay付款。 創建,分發和更新电子錢包應用的通行證。

      iOS PassKit Wallet 開發

      官方文檔

75、PDFKit

       iOS 11 后蘋果在iOS平台開放了PDFKit SDK,可以使用這個框架显示和操作 pdf 文件,此項目應用PDFKit實現显示pdf、显示縮略圖、展開大綱和搜索文字的功能。這個框架還是值得我們好好學習一下的。

       iOS PDFKit框架講解

       官方文檔

76、PencilKit

       這個框架是在iOS13中加入的,PencilKit可讓您輕鬆快捷地將手繪內容整合到iOS或macOS應用中。 PencilKit為iOS應用程序提供了一個繪圖環境,該環境可以從Apple Pencil或用戶的手指中獲取輸入,並將其轉換為您在iOS或macOS中显示的高質量圖像。該環境附帶了用於創建,擦除和選擇線條的工具。

       官方文檔

77、Photos   PhotosUI

       這兩個框架是開發者比較熟悉常用的,它的最低適配版本是iOS 8,所以以前的相冊框架幾乎也都是不用了。關於它的資料網絡是哪個還真的不少,所以我們也就不多說了。

       官方文檔

78、PuskKit  (很慚愧,沒找到資料)

79、QuartzCore

       這個框架相信大家還是比較熟悉的,它裏面的內容我們在日常開發中也經常會用到,比如 CAAnimation(動畫),CADisplayLink(定時器),CAShapeLayer(圖層),CAGradientLayer(漸變)等等,一起拿我有寫文章大概的介紹過這個框架。

       iOS – QuartzCore

80、QuickLook  QuickLookThumbnailing (Thumbnail [ˈθʌmneɪl] 縮略圖)

       QuickLook幾乎可以預覽幾乎所有的文件,像圖片、音樂,視頻、PDF、Word等都是可以。但是其可定製部分比較少,樣式比較單一,這是它的缺點。

       iOS快速預覽——QuickLook

       QuickLook官方文檔

       QuickLookThumbnailing官方文檔

81、RealityKit

      RealityKit 是iOS 13 + 專為增強現實技術開發的一款新的高級框架,它可以處理渲染的所有方面,包括材質、陰影、反射,甚至相機的運動模糊。它還為多人AR應用程序處理網絡,這意味着開發人員不需要成為網絡工程師就可以來開發共享AR體驗,這個框架會和後面介紹的 SceneKit 和 ARKit 配合使用

      iOS ARKit,SceneKit,RealityKit總結

      官方文檔

82、ReplayKit

      這是一個錄製屏幕的框架,但在不同的iOS版本中確有許多不同的表現,這個大家可以看下面分享的文章看一下。這一塊的需求應該也有,主要應該還是集中在遊戲中吧。

      iOS端使用replaykit錄製屏幕的技術細節

      官方文檔

83、SafariServices

      這個框架看前面的Safari就知道和Safari瀏覽器相關了,你可以把瀏覽器集成到項目中然後瀏覽器上面能做的事你都可以做。具體的還是見官方文檔,在實際的項目中我們對這個框架的利用率感覺不是特別高。

      官方文檔

84、SceneKit

       在前面說RealityKit框架的時候有提過這個框架,還是那句話它和RealityKit還有ARKit都是處理AR方面的內容的,你了解其中一個的時候回自然的了解到別的框架。

       官方文檔

85、Security

      Security 框架用於保證應用程序所管理之數據的安全。該框架提供的接口可用於管理證書、公鑰、私鑰以及信任策略。它支持生成加密的安全偽隨機數。同時,它也支持對證書和Keychain密鑰進行保存,是用戶敏感數據的安全倉庫。

      關於它官方文檔最後面一個注意點說的挺明確的,內容如下:

       其實上面的大致意思就是說在iOS中我們平常使用的像URL等都是建立在安全框架基礎上的,所以我們沒必要刻意的使用這個安全框架,要視情況而定。

       官方文檔

86、Social

       這也是一個社會化分享框架,只不過的原生的,所以在一些簡單的分享中我覺得還是可以一試的,沒必要一個不怎麼沉重的功能上一把第三方的殺牛刀。

       ios原生社交分享實踐

       官方文檔

87、SoundAnalysis

       使用SoundAnalysis框架來分析音頻,並將其識別為特定類型,比如笑聲或掌聲。框架使用由MLSoundClassifier訓練的核心ML模型來執行分析。使用框架的能力分析流或基於文件的音頻,讓您添加智能音頻識別功能到您的應用程序。這個框架看介紹我覺得是一個很有意思的點,有空研究一下。

       官方文檔

88、Speech

       這是一個語音識別的框架,也是很有趣的一個框架。建議大家都了解學習一下。

       iOS-Speech Framework

       官方文檔

89、SpriteKit

       以前在接觸Cocos2d-JS的是有才有的“精靈”這個概念,你要不涉及這一塊那你知道那是一個和遊戲來發相關的框架就可以了,要是你是做遊戲的那我相信這個框架你也早都應該了解了。

       iOS SpriteKit 遊戲

       官方文檔

90、StoreKit

       蘋果的內購相信大家也都有了解,這個框架就是專門用來處理內容的,有條件的我建議還是好好了解一下關於內購的知識。你再找它的資料的時候不塌搜索這個框架名稱,你直接搜索iOS 內購即可,這樣找打的資源相對多一些。以前有寫過關於內購的內容,有興趣的可以翻翻我以前的博客。

      官方文檔

91、SwiftUI

      這個是一個全新的UI框架,它應該在以後也是一個趨勢,就像Swift一樣,它裏面的東西我們是有必要進行一個學習的。當然學習的資料也是相當的豐富。所以下面我們就只給出一個官方的文檔,具體的內容可以自己上網去篩選。

      官方文檔

92、SystemConfiguration

      看網上的資源說這個框架也是一個用來測試網絡連接狀態的框架,但具體的使用又似乎不多。但的確可以嘗試,要是效果不多的話我建議能用原生的盡量避免使用第三方。

93、Twiteer  UIKit  這兩個框架知道就行了,因為一個幾乎不用一個幾乎每天都用,的確沒有更多的可以說了。

94、UserNotifications UserNotificationsUI

       這兩個框架在iOS10給的最大的一個驚喜,的確在10以後把通知優化的很是強大。這兩個框架相信很多人都知道,就沒必要在細說,葯還有不知道該怎麼處理的的確是應該去好好的研究一下他們。

95、VideoSubscriberAccount

       iOS10引入了Video Subscriber Account框架(VideoSubscriberAccount.framework)來幫助應用支持流媒體認證或認證視頻點播(也被稱為TV Everywhere)與他們的有線電視或衛星電視供應商認證。 對於那些用戶註冊一次就能解鎖流媒體訂閱服務的應用來說,使用這個框架中的API可以幫助你支持單一登錄體驗。   

       這個框架的確我也沒有使用過,它是一個和AppleTV掛鈎的框架,具體的信息大家可以去看官方文檔。

       官方文檔

96、VideoToolbox

       這個框架使讓用戶可以自行對視頻進行硬編解碼操作。關於視頻的硬編碼和解碼我也在學習計劃的當中,建議還是過一遍裏面的東西。

       iOS 利用VideoToolBox對視頻進行編解碼

       iOS利用VideoToolbox實現視頻硬解碼

       官方文檔

97、Vision VisionKit ([ˈvɪʒn] 視力;美景;眼力;幻象)

       這個框架也是一個比較值得我們深入研究的框架,它是一個可以用來做識別圖像的框架。像面部檢測、矩陣碼/條形碼檢測等等,具體的可以在官方文檔裏面看到或者下面的文章都是可以看到的。

       iOS Vision 框架概覽

       iOS Vision的使用

       官方文檔

98、WatchConnectivity

       這個框架看名字就能很好的理解它的作用了,它是用於 Watch 應用和 iOS 設備傳輸數據的框架。

       WatchConnectivity 介紹:告別加載等待。

       官方文檔

99、WebKit

       這個框架也是日常中經常會用到的一個框架,WKWebView就是它裏面的Web頁面展示View,現在iOS端的網頁幾乎應該都是使用WK展示的吧,UIWebView已經被廢棄了,再用會影響到審核。這個框架具體的內容像和JS交互這個我們就不再提了,網上關於它的資料還真的不少。

 

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

【其他文章推薦】

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

FB行銷專家,教你從零開始的技巧

分類
發燒車訊

算法漫遊指北(第十一篇):歸併排序算法描述、動圖演示、代碼實現、過程分析、複雜度

一、歸併排序

歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為2-路歸併。

  • 所謂“分”,指的是將一個亂序數列不斷進行二分,得到許多短的序列。

  • 所謂“治”,指的是將這些短序列進行兩兩合併,然後將合併的結果作為新的序列,再與其他序列進行合併,最終得到一個新的序列。

歸併排序算法描述

 

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列;

  • 對這兩個子序列分別採用歸併排序;

  • 將兩個排序好的子序列合併成一個最終的排序序列。

 

歸併排序動圖演示

 

動畫演示圖2

 

 

歸併排序代碼實現

def merge_sort(alist):
    """歸併排序"""
    n = len(alist)
    #遞歸結束條件
    # 剩一個或沒有直接返回,不用排序
    if n <= 1:
        return alist
    # 拆分
    mid = n//2
​
    # left 採用歸併排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
​
    # right 採用歸併排序后形成的有序的新的列表
    right_li = merge_sort(alist[mid:])
​
    # 將兩個有序的子序列合併為一個新的整體
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []
​
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] <=  right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    
    #將兩個列表按順序融合為一個列表result
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result
​

  


歸併排序過程分析

示例 針對 arrli = [6,5,3,1,8,7,2,4]進行歸併排序

1、拆分數組

假設數組一共有 n 個元素,我們遞歸對數組進行折半拆分即n//2,直到每組只有一個元素為止。

 

2、合併數組

算法會從最小數組開始有序合併,這樣合併出來的數組一直是有序的,所以合併兩個有序數組是歸併算法的核心,這裏用兩個簡單數組示例:

步驟1:新建一個空數組存放合併結果,用left_pointerright_pointer兩個輔助指針記錄兩個數組當前操作位置;

 

步驟2:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到left_pointerright_pointer指針超出尾部;

 

步驟3:新建一個空數組存放合併結果,用lr兩個輔助指針記錄兩個數組當前操作位置;

 

步驟4:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到lr指針超出尾部;

 

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

 

指針尚未移到尾部的數組,說明還有剩餘元素,將剩餘元素合併到新數組尾部。

 

步驟5:新建一個空數組存放合併結果,用lr兩個輔助指針記錄兩個數組當前操作位置;

 

步驟6:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到lr指針超出尾部;

 

將較小的元素寫入到新數組

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

 

步驟7:右邊的指針尚未移到尾部的數組,說明還有剩餘元素,將剩餘元素合併到新數組尾部。

 

完成歸併排序,返回排好序的新數組

 

 

歸併排序複雜度

 

  • 時間複雜度:O(nlogn)

歸併排序把數組一層層折半分組,長度為 n 的數組,折半層數就是 logn,每一層進行操作的運算量是 n,得出時間複雜度 O(nlogn)。

  • 空間複雜度:O(n)

每次歸併操作需要創建額外的新數組,佔用空間為 n,但這部分額外空間會隨着方法的結束而釋放,所以只需要算單次歸併操作開闢的空間即可,得出空間複雜度 O(n)。

  • 穩定性:穩定

從算法中從左到右逐一比較,較小的先放入新數組,所以兩個值相同的元素,排序后依然保持原先後順序。

 

 

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

【其他文章推薦】

※別再煩惱如何寫文案,掌握八大原則!

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

網頁設計最專業,超強功能平台可客製化

分類
發燒車訊

這一次搞懂SpringMVC原理

@

目錄

  • 前言
  • 正文
    • 請求入口
    • 組件初始化
    • 調用Controller
    • 參數、返回值解析
  • 總結

前言

前面幾篇文章,學習了Spring IOC、Bean實例化過程、AOP、事務的源碼和設計思想,了解了Spring的整體運行流程,但如果是web開發,那麼必不可少的還有Spring MVC,本篇主要分析在請求調用過程中SpringMVC的實現原理,通過本篇要搞懂它是怎麼解決請求、參數、返回值映射等問題的。

正文

請求入口

我們都知道前端調用後端接口時,都會通過Servlet進行轉發,而Servlet的聲明周期包含下面四個階段:

  • 實例化(new)
  • 初始化(init)
  • 執行(service調用doGet/doPost)
  • 銷毀(destroy)

前兩個階段在Spring啟動階段就做好了(init根據配置可能是第一次請求時才會調用),銷毀是服務關閉的時候進行,本文主要分析的就是請求執行階段。我們知道SpringMVC的核心就是DispatcherServlet,該類是對Servlet的擴展,所以直接從該類的service方法開始,但在此類中沒有service方法,那肯定是在其父類中,我們先來看看其繼承體系:

逐個往上找,在FrameworkServlet方法中就有一個service方法:

	protected void service(HttpServletRequest request, HttpServletResponse response)
			throws ServletException, IOException {

		HttpMethod httpMethod = HttpMethod.resolve(request.getMethod());
		if (httpMethod == HttpMethod.PATCH || httpMethod == null) {
			processRequest(request, response);
		}
		else {
			super.service(request, response);
		}
	}

    protected void service(HttpServletRequest req, HttpServletResponse resp)
        throws ServletException, IOException
    {
        String method = req.getMethod();

        if (method.equals(METHOD_GET)) {
            long lastModified = getLastModified(req);
            if (lastModified == -1) {
                doGet(req, resp);
            } else {
                long ifModifiedSince = req.getDateHeader(HEADER_IFMODSINCE);
                if (ifModifiedSince < lastModified) {
                    maybeSetLastModified(resp, lastModified);
                    doGet(req, resp);
                } else {
                    resp.setStatus(HttpServletResponse.SC_NOT_MODIFIED);
                }
            }

        } else if (method.equals(METHOD_HEAD)) {
            long lastModified = getLastModified(req);
            maybeSetLastModified(resp, lastModified);
            doHead(req, resp);
        } else if (method.equals(METHOD_POST)) {
            doPost(req, resp);
        } else if (method.equals(METHOD_PUT)) {
            doPut(req, resp);
        } else if (method.equals(METHOD_DELETE)) {
            doDelete(req, resp);
        } else if (method.equals(METHOD_OPTIONS)) {
            doOptions(req,resp);
        } else if (method.equals(METHOD_TRACE)) {
            doTrace(req,resp);
        } else {
            String errMsg = lStrings.getString("http.method_not_implemented");
            Object[] errArgs = new Object[1];
            errArgs[0] = method;
            errMsg = MessageFormat.format(errMsg, errArgs);
            
            resp.sendError(HttpServletResponse.SC_NOT_IMPLEMENTED, errMsg);
        }
    }
   

但其主要還是調用父類HttpServlet中的方法,而該類又會根據不同的請求方式會調到子類中,最後的核心方法就是DispatcherServlet中的doDispatch方法:

	protected void doDispatch(HttpServletRequest request, HttpServletResponse response) throws Exception {
		HttpServletRequest processedRequest = request;
		HandlerExecutionChain mappedHandler = null;
		boolean multipartRequestParsed = false;

		//異步管理
		WebAsyncManager asyncManager = WebAsyncUtils.getAsyncManager(request);

		try {
			ModelAndView mv = null;
			Exception dispatchException = null;

			try {
				//文件上傳
				processedRequest = checkMultipart(request);
				multipartRequestParsed = (processedRequest != request);

				//這個方法很重要,重點看
				// Determine handler for the current request.
				mappedHandler = getHandler(processedRequest);
				if (mappedHandler == null) {
					noHandlerFound(processedRequest, response);
					return;
				}

				//獲取跟HandlerMethod匹配的HandlerAdapter對象
				// Determine handler adapter for the current request.
				HandlerAdapter ha = getHandlerAdapter(mappedHandler.getHandler());

				// Process last-modified header, if supported by the handler.
				String method = request.getMethod();
				boolean isGet = "GET".equals(method);
				if (isGet || "HEAD".equals(method)) {
					long lastModified = ha.getLastModified(request, mappedHandler.getHandler());
					if (new ServletWebRequest(request, response).checkNotModified(lastModified) && isGet) {
						return;
					}
				}

				//前置過濾器,如果為false則直接返回
				if (!mappedHandler.applyPreHandle(processedRequest, response)) {
					return;
				}

				//調用到Controller具體方法,核心方法調用,重點看看
				// Actually invoke the handler.
				mv = ha.handle(processedRequest, response, mappedHandler.getHandler());

				if (asyncManager.isConcurrentHandlingStarted()) {
					return;
				}

				applyDefaultViewName(processedRequest, mv);

				//中置過濾器
				mappedHandler.applyPostHandle(processedRequest, response, mv);
			}
			catch (Exception ex) {
				dispatchException = ex;
			}
			catch (Throwable err) {
				// As of 4.3, we're processing Errors thrown from handler methods as well,
				// making them available for @ExceptionHandler methods and other scenarios.
				dispatchException = new NestedServletException("Handler dispatch failed", err);
			}

			//視圖渲染及後置過濾器執行
			processDispatchResult(processedRequest, response, mappedHandler, mv, dispatchException);
		}
		catch (Exception ex) {
			triggerAfterCompletion(processedRequest, response, mappedHandler, ex);
		}
		catch (Throwable err) {
			triggerAfterCompletion(processedRequest, response, mappedHandler,
					new NestedServletException("Handler processing failed", err));
		}
		finally {
			if (asyncManager.isConcurrentHandlingStarted()) {
				// Instead of postHandle and afterCompletion
				if (mappedHandler != null) {
					mappedHandler.applyAfterConcurrentHandlingStarted(processedRequest, response);
				}
			}
			else {
				// Clean up any resources used by a multipart request.
				if (multipartRequestParsed) {
					cleanupMultipart(processedRequest);
				}
			}
		}
	}

MVC的所有處理邏輯都在這個方法中,先總結一下這個方法的實現邏輯,首先根據請求的url拿到緩存中的HandlerMethod對象和執行鏈對象,HandlerMethod中封裝了controller對象、方法對象和方法參數等信息,執行鏈則是包含了一個個HandlerInterceptor攔截器;然後再通過HandlerMethod拿到對應的HandlerAdapter,這個對象的作用就是去適配我們的controller;準備工作做完后,首先會執行前置過濾,如果被攔截則直接返回,否則就去調用controller中的方法執行我們的業務邏輯並返回一個ModelView對象;接着執行中置過濾器,以及處理全局異常捕獲器捕獲到異常;最後進行視圖渲染返回並執行後置過濾器進行資源釋放等工作。
以上就是MVC的整體執行流程,下面就逐個來分析,首先進入getHandler方法:

	protected HandlerExecutionChain getHandler(HttpServletRequest request) throws Exception {
		//handlerMappering實例
		if (this.handlerMappings != null) {
			for (HandlerMapping mapping : this.handlerMappings) {
				//獲取HandlerMethod和過濾器鏈的包裝類
				HandlerExecutionChain handler = mapping.getHandler(request);
				if (handler != null) {
					return handler;
				}
			}
		}
		return null;
	}

是委託給HandlerMapping對象的,這是一個接口,主要的實現類是RequestMappingHandlerMapping,同樣先來看看其繼承體系:

這個類是管理請求和處理類之間的映射關係的,你是否疑惑它是在哪裡實例化的呢?下面先來看看MVC組件的初始化。

組件初始化

這裏我以自動化配置的註解方式說明,Spring提供了一個@EnableWebMvc,通過前面的學習我們知道在這個註解中必定導入了一個配置類,點進去可以看到是DelegatingWebMvcConfiguration,這個類就是負責MVC的組件和擴展實現的初始化,其本身我們先不看,先看其父類WebMvcConfigurationSupport,這個類我們應該不陌生,要做一些自定義擴展時就需要繼承該類(如攔截器Interceptor),同樣作用的類還有WebMvcConfigurerAdapter,這個類是對前者相對安全的擴展,為什麼是相對安全呢?因為繼承前者會導致自動配置失效,而使用後者則不必擔心此問題,只需要在類上加上@EnableWebMvc註解。
WebMvcConfigurationSupport中我們可以看到很多@Bean標註的方法,也就是mvc組件的實例化,這裏主要看看requestMappingHandlerMapping,其餘的可自行閱讀理解,也就是一些Bean的註冊:

	public RequestMappingHandlerMapping requestMappingHandlerMapping() {
		RequestMappingHandlerMapping mapping = createRequestMappingHandlerMapping();
		mapping.setOrder(0);
		mapping.setInterceptors(getInterceptors());
		mapping.setContentNegotiationManager(mvcContentNegotiationManager());
		mapping.setCorsConfigurations(getCorsConfigurations());

		......省略

		return mapping;
	}

這裏主要看getInterceptors方法如何獲取攔截器的:

	protected final Object[] getInterceptors() {
		if (this.interceptors == null) {
			InterceptorRegistry registry = new InterceptorRegistry();
			//鈎子方法,需要自己定義
			addInterceptors(registry);
			registry.addInterceptor(new ConversionServiceExposingInterceptor(mvcConversionService()));
			registry.addInterceptor(new ResourceUrlProviderExposingInterceptor(mvcResourceUrlProvider()));
			this.interceptors = registry.getInterceptors();
		}
		return this.interceptors.toArray();
	}

第一次進來會調用addInterceptors添加攔截器,這是一個模板方法,在子類DelegatingWebMvcConfiguration中實現:

	private final WebMvcConfigurerComposite configurers = new WebMvcConfigurerComposite();
	
	protected void addInterceptors(InterceptorRegistry registry) {
		this.configurers.addInterceptors(registry);
	}

	public void addInterceptors(InterceptorRegistry registry) {
		for (WebMvcConfigurer delegate : this.delegates) {
			delegate.addInterceptors(registry);
		}
	}

可以看到最終是調用WebMvcConfigureraddInterceptors方法,也就是我們對WebMvcConfigurerAdapter的自定義擴展。看到這裏我們應該明白了MVC的組件是如何添加到IOC容器中的,但是DispatcherServlet又是怎麼獲取到它們的呢?回到之前的代碼中,在DispatcherServlet這個類中有一個onRefresh方法,這個方法又調用了initStrategies方法完成了MVC九大組件的註冊:

	protected void onRefresh(ApplicationContext context) {
		initStrategies(context);
	}

	protected void initStrategies(ApplicationContext context) {
		initMultipartResolver(context);
		initLocaleResolver(context);
		initThemeResolver(context);
		initHandlerMappings(context);
		initHandlerAdapters(context);
		initHandlerExceptionResolvers(context);
		initRequestToViewNameTranslator(context);
		initViewResolvers(context);
		initFlashMapManager(context);
	}

	private void initHandlerMappings(ApplicationContext context) {
		this.handlerMappings = null;

		if (this.detectAllHandlerMappings) {
			// Find all HandlerMappings in the ApplicationContext, including ancestor contexts.
			Map<String, HandlerMapping> matchingBeans =
					BeanFactoryUtils.beansOfTypeIncludingAncestors(context, HandlerMapping.class, true, false);
			if (!matchingBeans.isEmpty()) {
				this.handlerMappings = new ArrayList<>(matchingBeans.values());
				// We keep HandlerMappings in sorted order.
				AnnotationAwareOrderComparator.sort(this.handlerMappings);
			}
		}
		else {
			try {
				HandlerMapping hm = context.getBean(HANDLER_MAPPING_BEAN_NAME, HandlerMapping.class);
				this.handlerMappings = Collections.singletonList(hm);
			}
			catch (NoSuchBeanDefinitionException ex) {
				// Ignore, we'll add a default HandlerMapping later.
			}
		}
		
		if (this.handlerMappings == null) {
			this.handlerMappings = getDefaultStrategies(context, HandlerMapping.class);
		}
	}

initHandlerMappings為例,其它組件實現邏輯基本一樣。首先從IOC容器中拿到handlerMappings的所有實現類(WebMvcConfigurationSupport中注入的對象就在這裏被獲取到),若沒有,則從DispatcherServlet.properties配置文件中(這個配置在spring-webmvc工程下org/springframework/web/servlet/DispatcherServlet.properties)獲取默認的配置:

org.springframework.web.servlet.LocaleResolver=org.springframework.web.servlet.i18n.AcceptHeaderLocaleResolver

org.springframework.web.servlet.ThemeResolver=org.springframework.web.servlet.theme.FixedThemeResolver

org.springframework.web.servlet.HandlerMapping=org.springframework.web.servlet.handler.BeanNameUrlHandlerMapping,\
	org.springframework.web.servlet.mvc.method.annotation.RequestMappingHandlerMapping

org.springframework.web.servlet.HandlerAdapter=org.springframework.web.servlet.mvc.HttpRequestHandlerAdapter,\
	org.springframework.web.servlet.mvc.SimpleControllerHandlerAdapter,\
	org.springframework.web.servlet.mvc.method.annotation.RequestMappingHandlerAdapter

org.springframework.web.servlet.HandlerExceptionResolver=org.springframework.web.servlet.mvc.method.annotation.ExceptionHandlerExceptionResolver,\
	org.springframework.web.servlet.mvc.annotation.ResponseStatusExceptionResolver,\
	org.springframework.web.servlet.mvc.support.DefaultHandlerExceptionResolver

org.springframework.web.servlet.RequestToViewNameTranslator=org.springframework.web.servlet.view.DefaultRequestToViewNameTranslator

org.springframework.web.servlet.ViewResolver=org.springframework.web.servlet.view.InternalResourceViewResolver

org.springframework.web.servlet.FlashMapManager=org.springframework.web.servlet.support.SessionFlashMapManager

但是onRefresh又是在什麼時候調用的呢?有兩個地方,一個是Servlet初始化時會調用到initWebApplicationContext進行容器的初始化,這個方法中就會觸發onRefresh;另外還有一個,在FrameworkServlet中有一個onApplicationEvent方法,而這個方法又會被內部類ContextRefreshListener調用,這個類實現了ApplicationListener接口,表示會接收容器刷新事件。
以上就就是MVC HandlerMapping組件的初始化邏輯,其它組件實現邏輯相同,下面不再分析。

調用Controller

回到getHandler方法,其調用的是AbstractHandlerMapping類的方法:

	public final HandlerExecutionChain getHandler(HttpServletRequest request) throws Exception {
		//根據請求的uri拿到對應的HandlerMethod對象
		Object handler = getHandlerInternal(request);
		if (handler == null) {
			handler = getDefaultHandler();
		}
		if (handler == null) {
			return null;
		}
		// Bean name or resolved handler?
		if (handler instanceof String) {
			String handlerName = (String) handler;
			handler = obtainApplicationContext().getBean(handlerName);
		}

		//獲取HandlerMethod和過濾器鏈的包裝類
		HandlerExecutionChain executionChain = getHandlerExecutionChain(handler, request);

		if (logger.isTraceEnabled()) {
			logger.trace("Mapped to " + handler);
		}
		else if (logger.isDebugEnabled() && !request.getDispatcherType().equals(DispatcherType.ASYNC)) {
			logger.debug("Mapped to " + executionChain.getHandler());
		}

		//是否是跨域請求,就是查看request請求頭中是否有Origin屬性
		if (CorsUtils.isCorsRequest(request)) {
			//自定義的鈎子方法獲取跨域配置
			CorsConfiguration globalConfig = this.corsConfigurationSource.getCorsConfiguration(request);
			//註解獲取跨域配置
			CorsConfiguration handlerConfig = getCorsConfiguration(handler, request);
			CorsConfiguration config = (globalConfig != null ? globalConfig.combine(handlerConfig) : handlerConfig);
			//這裏設置了跨域的過濾器CorsInterceptor
			executionChain = getCorsHandlerExecutionChain(request, executionChain, config);
		}

		return executionChain;
	}

先看AbstractHandlerMethodMapping.getHandlerInternal

	protected HandlerMethod getHandlerInternal(HttpServletRequest request) throws Exception {
		//從request對象中獲取uri,/common/query2
		String lookupPath = getUrlPathHelper().getLookupPathForRequest(request);
		this.mappingRegistry.acquireReadLock();
		try {
			//根據uri從映射關係中找到對應的HandlerMethod對象
			HandlerMethod handlerMethod = lookupHandlerMethod(lookupPath, request);
			//把Controller類實例化
			return (handlerMethod != null ? handlerMethod.createWithResolvedBean() : null);
		}
		finally {
			this.mappingRegistry.releaseReadLock();
		}
	}

	protected HandlerMethod lookupHandlerMethod(String lookupPath, HttpServletRequest request) throws Exception {
		List<Match> matches = new ArrayList<>();
		// 根據url拿到對應的RequestMappingInfo
		List<T> directPathMatches = this.mappingRegistry.getMappingsByUrl(lookupPath);
		if (directPathMatches != null) {
			addMatchingMappings(directPathMatches, matches, request);
		}
		if (matches.isEmpty()) {
			// No choice but to go through all mappings...
			addMatchingMappings(this.mappingRegistry.getMappings().keySet(), matches, request);
		}

		if (!matches.isEmpty()) {
			Comparator<Match> comparator = new MatchComparator(getMappingComparator(request));
			matches.sort(comparator);
			Match bestMatch = matches.get(0);
			if (matches.size() > 1) {
				if (logger.isTraceEnabled()) {
					logger.trace(matches.size() + " matching mappings: " + matches);
				}
				if (CorsUtils.isPreFlightRequest(request)) {
					return PREFLIGHT_AMBIGUOUS_MATCH;
				}
				Match secondBestMatch = matches.get(1);
				//如果兩個RequestMappinginfo什麼都相同,報錯
				if (comparator.compare(bestMatch, secondBestMatch) == 0) {
					Method m1 = bestMatch.handlerMethod.getMethod();
					Method m2 = secondBestMatch.handlerMethod.getMethod();
					String uri = request.getRequestURI();
					throw new IllegalStateException(
							"Ambiguous handler methods mapped for '" + uri + "': {" + m1 + ", " + m2 + "}");
				}
			}
			request.setAttribute(BEST_MATCHING_HANDLER_ATTRIBUTE, bestMatch.handlerMethod);
			handleMatch(bestMatch.mapping, lookupPath, request);
			return bestMatch.handlerMethod;
		}
		else {
			return handleNoMatch(this.mappingRegistry.getMappings().keySet(), lookupPath, request);
		}
	}

	private void addMatchingMappings(Collection<T> mappings, List<Match> matches, HttpServletRequest request) {
		for (T mapping : mappings) {
			// 拿到匹配的RequestMappingInfo對象,有可能url相同,@RequestMapping的屬性(請求方式、參數等)匹配不上
			T match = getMatchingMapping(mapping, request);
			if (match != null) {
				//RequestMappingInfo對象和HandlerMethod對象封裝到Match對象中,其實就是註解屬性和Method對象的映射
				matches.add(new Match(match, this.mappingRegistry.getMappings().get(mapping)));
			}
		}
	}

這裏邏輯很簡單,就是通過請求url從urlLookup中拿到對應的RequestMappingInfo(每一個 @RequestMapping對應一個RequestMappingInfo對象)對象,再根據RequestMappingInfo對象從mappingLookup拿到對應的HandlerMethod並返回。
但這裏你可能會比較好奇urlLookupmappingLookup從哪裡來的,仔細觀察你會發現當前這個類實現了一個接口InitializingBean,實現了這個接口的類會在該類的Bean實例化完成后調用afterPropertiesSet方法,上面的映射關係就是在這個方法中做的。實際上這個方法不止完成了上面兩個映射關係,還有下面兩個:

  • corsLookup:handlerMethod -> corsConfig
  • registry:RequestMappingInfo -> MappingRegistration(包含url、handlerMethod、RequestMappingInfo、name等信息)

這裏就不展開分析了,奉上一張時序圖,讀者可根據下面的時序圖自行分析:

拿到HandlerMethod對象后,又會通過getHandlerExecutionChain方法去獲取到所有的HandlerInterceptor攔截器對象,並連同HandlerMethod對象一起封裝為HandlerExecutionChain。之後是獲取跨域配置,這裏不詳細分析。
拿到HandlerExecutionChain對象后返回到doDispatch方法,又調用了getHandlerAdapter
方法拿到HandlerAdapter

	protected HandlerAdapter getHandlerAdapter(Object handler) throws ServletException {
		//根據handlerMethod對象,找到合適的HandlerAdapter對象,這裏用到了策略模式
		if (this.handlerAdapters != null) {
			for (HandlerAdapter adapter : this.handlerAdapters) {
				if (adapter.supports(handler)) {
					return adapter;
				}
			}
		}
	}

這裏的handlerAdapters變量值從哪裡來?相信不用我再分析,主要看這裏的設計思想,典型的策略模式
之後調用完前置過濾器后,才是真正調用我們controller方法的邏輯,通過HandlerAdapter.handle去調用,最終會調用到ServletInvocableHandlerMethod.invokeAndHandle

	public void invokeAndHandle(ServletWebRequest webRequest, ModelAndViewContainer mavContainer,
			Object... providedArgs) throws Exception {

		//具體調用邏輯,重點看
		Object returnValue = invokeForRequest(webRequest, mavContainer, providedArgs);
		setResponseStatus(webRequest);

		if (returnValue == null) {
			if (isRequestNotModified(webRequest) || getResponseStatus() != null || mavContainer.isRequestHandled()) {
				mavContainer.setRequestHandled(true);
				return;
			}
		}
		else if (StringUtils.hasText(getResponseStatusReason())) {
			mavContainer.setRequestHandled(true);
			return;
		}

		mavContainer.setRequestHandled(false);
		Assert.state(this.returnValueHandlers != null, "No return value handlers");
		try {
			//返回值處理
			this.returnValueHandlers.handleReturnValue(
					returnValue, getReturnValueType(returnValue), mavContainer, webRequest);
		}
		catch (Exception ex) {
			if (logger.isTraceEnabled()) {
				logger.trace(formatErrorForReturnValue(returnValue), ex);
			}
			throw ex;
		}
	}

這個方法裏面主要看invokeForRequesthandleReturnValue的調用,前者是完成參數綁定並調用controller,後者則是對返回值進行處理並封裝到ModelAndViewContainer中。先來看invokeForRequest

	public Object invokeForRequest(NativeWebRequest request, @Nullable ModelAndViewContainer mavContainer,
			Object... providedArgs) throws Exception {

		//獲取參數數組
		Object[] args = getMethodArgumentValues(request, mavContainer, providedArgs);
		if (logger.isTraceEnabled()) {
			logger.trace("Arguments: " + Arrays.toString(args));
		}
		return doInvoke(args);
	}

doInvoke就是完成反射調用,主要還是看參數綁定的實現邏輯,在getMethodArgumentValues方法中:

	protected Object[] getMethodArgumentValues(NativeWebRequest request, @Nullable ModelAndViewContainer mavContainer,
			Object... providedArgs) throws Exception {

		if (ObjectUtils.isEmpty(getMethodParameters())) {
			return EMPTY_ARGS;
		}
		//入參的包裝類,裡面包裝了參數類型,參數名稱,參數註解等等信息
		MethodParameter[] parameters = getMethodParameters();
		Object[] args = new Object[parameters.length];
		for (int i = 0; i < parameters.length; i++) {
			MethodParameter parameter = parameters[i];
			//設置參數名稱解析器
			parameter.initParameterNameDiscovery(this.parameterNameDiscoverer);
			args[i] = findProvidedArgument(parameter, providedArgs);
			if (args[i] != null) {
				continue;
			}
			//典型的策略模式,根據parameter能否找到對應參數的處理類,能找到就返回true
			if (!this.resolvers.supportsParameter(parameter)) {
				throw new IllegalStateException(formatArgumentError(parameter, "No suitable resolver"));
			}
			try {
				//具體參數值解析過程,重點看看
				args[i] = this.resolvers.resolveArgument(parameter, mavContainer, request, this.dataBinderFactory);
			}
			catch (Exception ex) {
				// Leave stack trace for later, exception may actually be resolved and handled..
				if (logger.isDebugEnabled()) {
					String error = ex.getMessage();
					if (error != null && !error.contains(parameter.getExecutable().toGenericString())) {
						logger.debug(formatArgumentError(parameter, error));
					}
				}
				throw ex;
			}
		}
		return args;
	}

參數、返回值解析

因為參數類型非常多,同時還會伴隨各種註解,如:@RequestBody、@RequestParam、@PathVariable等,所以參數解析的工作是非常繁雜的,同時還要考慮到擴展性,所以SpringMVC依然採用了策略模式來完成對各種參數類型的解析綁定,其頂層接口就是HandlerMethodArgumentResolver,而默認SpringMVC提供的解析方式就高達20多種:

上面是類圖,讀者可根據自己熟悉的參數類型找到對應的類進行分析,最核心的還是要掌握這裏的設計思想。
接着方法調用完成后就是對返回值的處理,同樣的,返回值類型也是非常多,也可以使用各種註解標註,所以也是使用策略模式實現,其頂層接口是HandlerMethodReturnValueHandler,實現類如下:

調用完成之後就是執行後續操作了:執行中置過濾器、處理全局異常、視圖渲染以及執行後置過濾器,這些與主流程沒有太大關係,本篇不展開分析了,最後是MVC的執行時序圖:

總結

本篇是Spring核心原理系列的最後一篇,前前後后花了一個月時間,終於從宏觀上大致上理解了Spring的實現原理和運行機制,明白了之前項目中一些坑是如何產生的,最主要的是學到設計模式的運用以及如何利用Spring的一些常用的擴展點進行自定義擴展。但對於Spring這個龐大的體系來說,還有很多是要去理解學習的,尤其是設計思想,只有長期琢磨才能深刻的理解掌握。在我之前的文章中包括本篇還有很多沒分析到的細節,在後面我會不定期分享出來。

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

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

分類
發燒車訊

工欲善其事,必先利其器 — Mac 軟件推薦(序)

背景

工欲善其事,必先利其器。​後面我將陸陸續續推薦一些軟件利器幫助大家提高效率(主要針對 Mac 電腦)。

如果你在使用 Mac 電腦,並且沒有如某些人那樣安裝並使用 Windows 系統,那麼你可以嘗試使用以下這些軟件。

在 Mac 裝 Windows 使用,感覺有點“暴殄天物”(文化有限,只能找到這個詞),沒有惡意黑 Windows,Windows 有 Windows 的使用場景,對於普通人民群眾來說,確實使用 Windows 夠了,微軟現在也出了不錯的筆記本。但你確實不該買 Mac 然後確使用 Windows 系統,這樣其實裝 X 效果不好。

這些軟件都是我自己使用過且覺得還不錯的,這些軟件或者可以極大地提高效率或者偶爾也足夠裝13(哈哈,亂入了一兩款 App)。

整理下來太多了,因為太多圖,放在一篇文章裏面感覺加載都有點問題(是不是暗示我要換手機了?)。正好有讀者反饋說之前發的有的內容太長太干,都看不下去了,因此,我進行了拆分(技術乾貨花的時間也久,產出沒那麼快)。正好用類似的文章休息下,不用動腦筋,1~2分鐘搞定,並且也有收穫,​一舉兩得。​

主角登場 Alfred

今天的主角是 Alfred。這個軟件很多文章都在說,我這裏就不多做過多介紹了。其具體效果跟 Mac 自帶的 Spotlight 類似,但功能會強大 N 個數量級倍。

我差不多 12 年開始接觸 Mac,當時還是窮學生,托香港的同學幫忙買的教育版 MacBook Air,現在還偶爾服役。但使用這款軟件是我 15 年快工作了才用上,後悔沒早知道呀,不過現在也已經陪伴我走了這麼多年了,首推就是這款軟件了。如果你看到這篇文章且還沒有用過,就趕緊用起來吧,免費版本的功能也都已經挺強悍了。

舉例說下常用的幾個功能:

文件搜索

類似 Windows 版本的 everything。 設置某個標識(示例中為 “’”)開頭,後面為關鍵字就開始全盤索引(當然可以配置過濾)了,找到搜索到的文件后,按 “->” 出現二級菜單,可以選擇下一步的操作。

比如複製,以此命令行 cd 到文件/目錄(後面有類似的工具推薦),複製文件路徑(finder 不比 windows 能夠方便 copy 文件路徑)等。

alfred-file-search

剪貼板歷史

可以幫你保存你最近的剪貼板歷史,通過快捷鍵選取粘貼。實際工作中經常遇到,本來要複製一個東西已經 cmd+c 了,這個時候又來一個更優先需要複製粘貼的,前面那個又被覆蓋了,還得再去複製一遍。有了這個功能就不愁了。

alfred-paste

各種搜索

  • 搜索引擎搜索

同樣可以設置關鍵字,比如 “google keywords”,回車就能直接打開 google 搜索。默認的有google/wiki/等等,這個還可以自己方便添加更多的搜索引擎,比如 baidu,必應,stackoverflow 等等。

  • 各種快捷搜索

其他的比如聯繫人搜索,快捷功能(lock/sleep/shutdown)等等,計算器(直接輸入等式即可),輸入應用名稱快速打開應用等等。

alfred-quick-search

Workflow

Workflow 是其更強大的賣點。比如以下是一些或者極其高效或者很有意思的 workflow。

  • Dash

堪稱程序員神器啊。 結合 Dash,能夠非常方便快捷地搜索某種語言的某個 API,再也不用邊寫邊打開瀏覽器去搜索了。

遇到了 某個 API 不太清楚,直接 ctrl + blank 輸入關鍵字就直接模糊搜索某 API 了。

alfred-dash

  • stackoverflow

其實這個通過在上面的搜索引起那裡設置也 OK 的。這裡是一個單獨的 workflow,同樣可以設置關鍵字(例如 st keywords) 就能直接搜索 stackoverflow 上相關問題。相當於在 google 搜索中 keywords site:stackoverflow.com

alfred-stackoverflow

  • youdao 翻譯

遇到中英文翻譯問題不用再打開瀏覽器去搜索了。

當然 Mac 自帶的取詞翻譯功能也挺不錯的: 不知道? 選中關鍵字,三指輕點觸控板。

mac-translate

  • zhihu

知乎搜索及知乎日報,可以設置關鍵字直接知乎搜索,或者列出當天的知乎日報推薦列表。

  • douban

豆瓣的相關功能,豆瓣讀書/電影等。最近聽到同事談論某電影,想看豆瓣評分多少? 很簡答, 直接 movie 電影名 就出來結果了,如圖:

  • 天氣

調用百度的 API 實現的快捷天氣預報

alfred-weather

  • mail

快速搜索郵件(這裏直接用的以前的截圖)。

alfred-mail

  • 印象筆記(evernote)

快速搜索印象筆記/evernote 中保存的內容。這個得首先去 印象筆記官網 生成一個 token,然後安裝好 alfred-evernote后,配置好(es-token 你自己的generated-token) token 成功后就可以使用了。

查詢有不同的語法格式,詳情可以查閱evernote 搜索語法。

alfred-印象筆記 workflow

搜索后直接回車打開是默認在應用程序中打開,按住 cmd 後會在瀏覽器中打開(由於最開始開發的作者是國際版 evernote,中國版補丁的作者也忘記改這個鏈接了,所以在瀏覽器中打開的跳轉鏈接不對,直接下載我修改后 workflow 是 OK 的 github),其實就是修改一下其中的 app.js中的 get-link 方法。

當然還有更多其他好玩有用的 workflow,你可以直接到github AlfredWorkflow“選購”,沒有的也可以自己實現一個也貢獻出來哦。方法也相對比較簡單,用 php/python 等都可以實現,你打開 alfred 設置項,雙擊具體某個 workflow 就能看到源碼。

 

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

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

FB行銷專家,教你從零開始的技巧

分類
發燒車訊

新能源汽車需求井噴 助推鋰材料超預期大漲

據中國汽車工業協會最新發佈數據,今年前6個月我國新能源汽車產量達到7.6萬輛,這一產量同比增幅達到2.5倍。   然而,新能源整車產量快速增長的同時,配套動力電池的產量卻出現缺口。“現在動力電池基本上只要能造出來,銷售出去的問題不大。”乘用車市場資訊聯席會秘書長崔東樹向記者表示,這不僅大大制約了新能源汽車產能的釋放,同時也影響了動力電池技術的進步,“大家都忙著造,很難有人沉下心來做研發。”   實際上,據專家介紹,新能源汽車電池在生產上的技術門檻並不高,這直接導致的是動力電池產能處於快速擴張當中。然而,大批量技術含量較低電池企業的投產,則可能讓國內電池產能由短缺轉向過剩。業內人士預計,隨著產能的快速實現,電池產業可能將在2016年下半年迎來洗牌。  
研發上與日韓有較大差距   “國內電池企業在自動化和研發能力上都與日韓企業有較大差距。”華霆動力技術有限公司的一位負責人向記者介紹,目前日韓企業在生產成本和技術上都整體領先於國內動力電池企業。   一位電池技術專家告訴記者,現階段國內動力電池企業的生產成本大約是2元每瓦時,按照容量為25千瓦時的動力電池計算,成本大約在5萬元左右。   這樣的成本明顯高於LG、三星等韓國動力電池生產企業。據介紹,韓企的成本已降至1.8元每瓦時以下,這意味著同樣是25千瓦時的動力電池,其成本將會低於4.5萬元。   不僅如此,國內電池企業的能量密度也低於日韓企業。上述電池技術專家介紹,國內較好的動力電池模組的能量密度在130瓦時每千克,而松下等日本企業生產動力電池模組的能量密度則能超過200瓦時每千克,LG、三星等韓國企業所生產動力電池也能達到180瓦時每千克左右。   這意味著,國內電池企業生產容量25千瓦時的電池重量將超過190千克,而同樣容量的電池,韓企生產出來的重量為140千克左右,部分日企則能達到125千克。這對於新能源整車的輕量化影響不小。   “目前,在動力電池領域,松下領先LG和三星12~18個月,而LG和三星則領先國內企業12~18個月。”國內某動力電池企業的負責人向記者坦言,“國內電池企業的自動化程度不高,研發和製造水準都趕不上。”   乘聯會資料顯示,國內新能源整車企業除比亞迪擁有自己的配套電池廠外,大多數都通過外採的方式解決電池問題。  
明年底行業恐面臨洗牌   “現在國內電池企業的狀態普遍很浮躁。”上述電池企業負責人向記者表示,由於新能源車企對配套電池的需求持續旺盛,電池企業對產能投入的熱情已大於對研發和技術的追求。 隨著近年來新能源汽車產銷量高速增長,汽車電池產量的缺口也逐步展現出來。這激發了配套電池企業的投產熱情。   一位動力電池公司負責人向記者介紹,僅LG、三星、力神和CATL四家動力電池企業,明年將投產的產能就高達10吉瓦時以上,而每吉瓦時的電池產能可以滿足大約4萬輛新能源汽車的需要,也就是說,僅上述四家動力電池企業的產能就可以滿足40萬輛新能源車的裝配需要。“動力電池的技術門檻並不高。”一位充電設施企業的負責人告訴記者,目前動力電池的核心技術已相對成熟,因此企業實現投產並不難,這造成很多實力並不強大的電池企業紛紛上專案。   不過,“國內主流的12家新能源整車企業的採購,基本上都來自5家主要的動力電池廠家。”一位電池企業負責人向記者表示,隨著具備技術優勢的大電池企業產能的跟上,在技術和成本上都不具備優勢的小企業將很難生存,因此他預測“2016年底電池企業將面臨洗牌”。   乘聯會的資料顯示,目前電池企業CATL主要供應北汽、廣汽、長安和宇通等新能源車企;天津力神主要供應江淮、康迪、廣汽和宇通等;國軒高科則供應康迪、江淮、金龍、安凱和申沃等車企;萬向億能則供應上汽、奇瑞、廣汽、青年等車企。   文章來源:中財網

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

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

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

分類
發燒車訊

中國積極推動無補貼綠能專案,太陽能市場有望回穩

雖然中國政府在 2018 年中旬推出 531 新政,讓該國投資去年太陽能總投資下降 53%,重挫當地太陽能投資與建設發展,但該國政府目前已推出無補貼再生能源計畫,或許有望重振中國太陽能市場,彭博能源財經(BNEF)推測 2019 年中國太陽能新增裝置量仍可達到 34-44GW。

中國過去一直以來對當地太陽能產業發展相當優待,提供優渥的補貼金額與固定電價價格以鼓勵太陽能等再生能源發展,大量企業開始投資太陽能產業,形成一股靠補貼攀升的太陽能熱潮,造成產能過剩與補貼缺口過大,據統計,截至 2017 年底,再生能源補貼缺口已達 1,000 億人民幣(約新台幣 4,600 億元)。

因此中國政府在 2018 年中無預警推出新政策,大幅限制電廠建設與補助,為中國高速發展的太陽能產業踩下煞車踏板,未來也將採取嚴控指標方式,並積極鼓勵低價補貼或是無補貼專案。

無補貼專案優惠多

就好比中國在去年 8 月推出首項無補貼太陽能示範專案規劃,每省限定 300-500MW,並在 10 月開始申請、預計在 2019 年 3 月前後開工拚年底前併網發電。日前該政府也為了促進再生能源無補貼發展公布 12 項全新計畫,像是要做好風電、光電發電量檢測,不能在電力供過於求等預警紅色地區推行專案,廠商也要保證將來可以全額併網發電與不浪費。

中國此次將「無補貼專案」定義為無國家補貼、先導計畫不限規模、不佔用補貼指標的計畫,因此在政策方面也有釋出許多善意,要求地方政府對無補貼太陽能與風電在土地利用、成本上給予支持之餘,政府也會為綠色證書市場化交易指出明燈,未來無補貼或是低價補貼專案可以透過中國綠色電力證書交易獲益,與此同時也要求電力公司讓無補貼專案優先發電和全額收購電量,並鼓勵金融機構支持無補貼專案。

另外中國政府也將執行固定電價(FIT)政策,無補貼、低價補貼風電與太陽能專案可簽定 20 年以上的購電合約,提高電價的長期穩定性,也不要會求參與跨區電力市場化交易。

中國國家發改委表示,這些專案獲得核准後就能在 2020 年底前開始施工,但沒有在限定時間完工的專案將會被取消,為其他無補貼專案挪出空間。並明確指出,從現在到 2020 年底前獲準的專案都可採用這項政策,政府則會在 2020 年後依據技術與成本擬定新的政策。

只不過中國目前也有不少地方無法規劃無補貼專案,對此中國政府也表示,推動低價專案並非立即取消所有補貼,若無法達到無補貼或低價補貼仍可採競爭性配置專案政策,並希望這些專案可透過競爭降低電價以減少政府補貼。

BNEF 分析師 Jonathan Luan 表示,這些政策代表著未來中國將朝無補貼再生能源邁進,並有機會促成全新的太陽能專案,公司則對中國的太陽能市場樂觀看待,預測 2019 年新增裝置量可達 34-44GW。

(合作媒體:。首圖來源: CC BY 2.0)

延伸閱讀:

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

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

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

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

※教你寫出一流的銷售文案?

※超省錢租車方案

分類
發燒車訊

澳洲新南威爾斯省 無尾熊2050年恐滅絕

摘錄自2018年09月08日蘋果日報澳洲報導

澳洲動物保護生物學家泰勒(Martin Taylor)周五(7日)提出一份報告,指出新南威爾士省如果繼續目前的土地清理工作,至2050年左右,當地的無尾熊恐面臨滅絕。

《澳洲新聞網》報導,這份報告由澳洲世界自然基金會(WFF)與自然保護委員會(NCC)發布,分析新南威爾士省北部衛星圖像,評估土地清理工作對瀕危物種的影響。泰勒指出,如果清理速度沒有減緩,將會對當地野生動物造成嚴重後果。「我們看到無尾熊的棲地正以驚人的速度消失,每個人都在告訴我們,無尾熊的數量正在下降。如果速度不變,本世紀中葉,新南威爾士省將沒有野生無尾熊。」泰勒的研究發現,自2016年至今,完全或部分被清理的土地面積幾乎增加了2倍,從2845公頃增加到8194公頃。

然而新南威爾士省政府對這項警告提出反駁,當地環境廳長辦公室聲明指控,澳洲世界自然基金會(WFF)與自然保護委員會(NCC)正在散布恐慌。並強調「政府承諾會為無尾熊提供更多自然棲地,並改善道路殺手問題,也已投入4500萬澳幣的大量經費。」政府也強調「無尾熊的數量事實上高於預期。」

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

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

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

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

分類
發燒車訊

消滅太平洋垃圾帶 巨型垃圾搜集器正式上路

摘錄自2018年9月9日蘋果日報美國報導

位於美國加州和夏威夷之間有個全球最大的垃圾帶,聚集人類多年來不斷丟棄到大海中的垃圾。為了解決此生態浩劫,由荷蘭24歲青年研發的巨型垃圾蒐集器昨(8)日正式上場,將沿路「撿回」垃圾,還給大海一個乾淨空間。

這個長約600公尺的巨大垃圾搜集器周六從舊金山港口出發,朝著相當於40個台灣面積的太平洋垃圾帶(Great Pacific Garbage Patch)前進。搜集器呈U型漂浮設計,在海上攔截垃圾。裝置以低於水流的速度行進,讓潮汐和海浪產生推力,將海洋垃圾往裝置中心帶去。裝置底下設有網狀裝置,能攔下較小、沉降在水面下的海洋廢棄物。而過濾網產生的推力,則能使魚類和其他生物,得以輕鬆繞過網子底下、通過裝置而不被攔截。被攔下的海洋垃圾,再由團隊派出船隻定期載運回陸地,進行資源回收再利用。

此計畫由荷蘭青年斯萊特(Boyan Slat)所創立的「海洋清理計劃」(Ocean Cleanup Project)推動。該組織已募得3500萬美元(約10億7870萬元台幣)資金,預計在2020年前在太平洋海域上放置60個搜集器檔板。斯萊特說:「我們的目標是在5年內清理5成太平洋垃圾帶中的垃圾。」斯萊特還說,這些漂浮檔板可抵抗惡劣氣候,使用期限長達20年,可望蒐集到9成海面漂浮垃圾。

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

【其他文章推薦】

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

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

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

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

※教你寫出一流的銷售文案?

※超省錢租車方案

分類
發燒車訊

菲律賓巴丹群島群島 規模5以上地震連三起

摘錄自2019年7月27日新唐人亞太台、自由時報報導

27日清晨,菲律賓最北邊的巴丹群島接連發生三起規模五以上的地震,根據美國地質調查所數據,三起地震的規模分別為5.4、5.9和5.7,震源深度僅9.1公里,屬於極淺層地震;菲律賓地震局表示第二次地震規模為6.4。當地許多建築物倒塌,現全島因電力線的損壞處於停電狀態,目前估計已造成5人死亡,9人輕重傷。

當局沒有發布海嘯警報。目前已知至少8人死亡,60人受傷。事發之後,民眾住家內的物品散亂一地。還有居民從瓦礫堆當中搜救生還者。

巴丹群島位於台灣和呂宋島之間,菲律賓當局也派遣醫療救難隊前往巴丹群島。



菲律賓最北方巴丹群(Batanes)今日清晨發生連續兩次規模5以上的地震。(推特 )

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

【其他文章推薦】

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

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

南投搬家公司費用需注意的眉眉角角,別等搬了再說!

※教你寫出一流的銷售文案?