從零開始入門 | Kubernetes 中的服務發現與負載均衡

作者 | 阿里巴巴技術專家  溪恆

一、需求來源

為什麼需要服務發現

在 K8s 集群裏面會通過 pod 去部署應用,與傳統的應用部署不同,傳統應用部署在給定的機器上面去部署,我們知道怎麼去調用別的機器的 IP 地址。但是在 K8s 集群裏面應用是通過 pod 去部署的, 而 pod 生命周期是短暫的。在 pod 的生命周期過程中,比如它創建或銷毀,它的 IP 地址都會發生變化,這樣就不能使用傳統的部署方式,不能指定 IP 去訪問指定的應用。

另外在 K8s 的應用部署里,之前雖然學習了 deployment 的應用部署模式,但還是需要創建一個 pod 組,然後這些 pod 組需要提供一個統一的訪問入口,以及怎麼去控制流量負載均衡到這個組裡面。比如說測試環境、預發環境和線上環境,其實在部署的過程中需要保持同樣的一個部署模板以及訪問方式。因為這樣就可以用同一套應用的模板在不同的環境中直接發布。

Service:Kubernetes 中的服務發現與負載均衡

最後應用服務需要暴露到外部去訪問,需要提供給外部的用戶去調用的。我們上節了解到 pod 的網絡跟機器不是同一個段的網絡,那怎麼讓 pod 網絡暴露到去給外部訪問呢?這時就需要服務發現。

在 K8s 裏面,服務發現與負載均衡就是 K8s Service。上圖就是在 K8s 里 Service 的架構,K8s Service 向上提供了外部網絡以及 pod 網絡的訪問,即外部網絡可以通過 service 去訪問,pod 網絡也可以通過 K8s Service 去訪問。

向下,K8s 對接了另外一組 pod,即可以通過 K8s Service 的方式去負載均衡到一組 pod 上面去,這樣相當於解決了前面所說的複發性問題,或者提供了統一的訪問入口去做服務發現,然後又可以給外部網絡訪問,解決不同的 pod 之間的訪問,提供統一的訪問地址。

二、用例解讀

下面進行實際的一個用例解讀,看 pod K8s 的 service 要怎麼去聲明、怎麼去使用?

Service 語法

首先來看 K8s Service 的一個語法,上圖實際就是 K8s 的一個聲明結構。這個結構里有很多語法,跟之前所介紹的 K8s 的一些標準對象有很多相似之處。比如說標籤 label 去做一些選擇、selector 去做一些選擇、label 去聲明它的一些 label 標籤等。

這裡有一個新的知識點,就是定義了用於 K8s Service 服務發現的一個協議以及端口。繼續來看這個模板,聲明了一個名叫 my-service 的一個 K8s Service,它有一個 app:my-service 的 label,它選擇了 app:MyApp 這樣一個 label 的 pod 作為它的後端。

最後是定義的服務發現的協議以及端口,這個示例中我們定義的是 TCP 協議,端口是 80,目的端口是 9376,效果是訪問到這個 service 80 端口會被路由到後端的 targetPort,就是只要訪問到這個 service 80 端口的都會負載均衡到後端 app:MyApp 這種 label 的 pod 的 9376 端口。

創建和查看 Service

如何去創建剛才聲明的這個 service 對象,以及它創建之後是什麼樣的效果呢?通過簡單的命令:

  • kubectl apply -f service.yaml

或者是

  • kubectl created -f service.yaml

上面的命令可以簡單地去創建這樣一個 service。創建好之後,可以通過:

  • kubectl discribe service

去查看 service 創建之後的一個結果。

service 創建好之後,你可以看到它的名字是 my-service。Namespace、Label、Selector 這些都跟我們之前聲明的一樣,這裏聲明完之後會生成一個 IP 地址,這個 IP 地址就是 service 的 IP 地址,這個 IP 地址在集群裏面可以被其它 pod 所訪問,相當於通過這個 IP 地址提供了統一的一個 pod 的訪問入口,以及服務發現。

這裏還有一個 Endpoints 的屬性,就是我們通過 Endpoints 可以看到:通過前面所聲明的 selector 去選擇了哪些 pod?以及這些 pod 都是什麼樣一個狀態?比如說通過 selector,我們看到它選擇了這些 pod 的一個 IP,以及這些 pod 所聲明的 targetPort 的一個端口。

實際的架構如上圖所示。在 service 創建之後,它會在集群裏面創建一個虛擬的 IP 地址以及端口,在集群里,所有的 pod 和 node 都可以通過這樣一個 IP 地址和端口去訪問到這個 service。這個 service 會把它選擇的 pod 及其 IP 地址都掛載到後端。這樣通過 service 的 IP 地址訪問時,就可以負載均衡到後端這些 pod 上面去。

當 pod 的生命周期有變化時,比如說其中一個 pod 銷毀,service 就會自動從後端摘除這個 pod。這樣實現了:就算 pod 的生命周期有變化,它訪問的端點是不會發生變化的。

集群內訪問 Service

在集群裏面,其他 pod 要怎麼訪問到我們所創建的這個 service 呢?有三種方式:

  • 首先我們可以通過 service 的虛擬 IP 去訪問,比如說剛創建的 my-service 這個服務,通過 kubectl get svc 或者 kubectl discribe service 都可以看到它的虛擬 IP 地址是 172.29.3.27,端口是 80,然後就可以通過這個虛擬 IP 及端口在 pod 裏面直接訪問到這個 service 的地址。

  • 第二種方式直接訪問服務名,依靠 DNS 解析,就是同一個 namespace 里 pod 可以直接通過 service 的名字去訪問到剛才所聲明的這個 service。不同的 namespace 裏面,我們可以通過 service 名字加“.”,然後加 service 所在的哪個 namespace 去訪問這個 service,例如我們直接用 curl 去訪問,就是 my- 就可以訪問到這個 service。

  • 第三種是通過環境變量訪問,在同一個 namespace 里的 pod 啟動時,K8s 會把 service 的一些 IP 地址、端口,以及一些簡單的配置,通過環境變量的方式放到 K8s 的 pod 裏面。在 K8s pod 的容器啟動之後,通過讀取系統的環境變量比讀取到 namespace 裏面其他 service 配置的一個地址,或者是它的端口號等等。比如在集群的某一個 pod 裏面,可以直接通過 curl $ 取到一個環境變量的值,比如取到 MY_SERVICE_SERVICE_HOST 就是它的一個 IP 地址,MY_SERVICE 就是剛才我們聲明的 MY_SERVICE,SERVICE_PORT 就是它的端口號,這樣也可以請求到集群裏面的 MY_SERVICE 這個 service。

Headless Service

service 有一個特別的形態就是 Headless Service。service 創建的時候可以指定 clusterIP:None,告訴 K8s 說我不需要 clusterIP(就是剛才所說的集群裏面的一個虛擬 IP),然後 K8s 就不會分配給這個 service 一個虛擬 IP 地址,它沒有虛擬 IP 地址怎麼做到負載均衡以及統一的訪問入口呢?

它是這樣來操作的:pod 可以直接通過 service_name 用 DNS 的方式解析到所有後端 pod 的 IP 地址,通過 DNS 的 A 記錄的方式會解析到所有後端的 Pod 的地址,由客戶端選擇一個後端的 IP 地址,這個 A 記錄會隨着 pod 的生命周期變化,返回的 A 記錄列表也發生變化,這樣就要求客戶端應用要從 A 記錄把所有 DNS 返回到 A 記錄的列表裡面 IP 地址中,客戶端自己去選擇一個合適的地址去訪問 pod。

可以從上圖看一下跟剛才我們聲明的模板的區別,就是在中間加了一個 clusterIP:None,即表明不需要虛擬 IP。實際效果就是集群的 pod 訪問 my-service 時,會直接解析到所有的 service 對應 pod 的 IP 地址,返回給 pod,然後 pod 裏面自己去選擇一個 IP 地址去直接訪問。

向集群外暴露 Service

前面介紹的都是在集群裏面 node 或者 pod 去訪問 service,service 怎麼去向外暴露呢?怎麼把應用實際暴露給公網去訪問呢?這裏 service 也有兩種類型去解決這個問題,一個是 NodePort,一個是 LoadBalancer。

  • NodePort 的方式就是在集群的 node 上面(即集群的節點的宿主機上面)去暴露節點上的一個端口,這樣相當於在節點的一個端口上面訪問到之後就會再去做一層轉發,轉發到虛擬的 IP 地址上面,就是剛剛宿主機上面 service 虛擬 IP 地址。

  • LoadBalancer 類型就是在 NodePort 上面又做了一層轉換,剛才所說的 NodePort 其實是集群裏面每個節點上面一個端口,LoadBalancer 是在所有的節點前又掛一個負載均衡。比如在阿里雲上掛一個 SLB,這個負載均衡會提供一個統一的入口,並把所有它接觸到的流量負載均衡到每一個集群節點的 node pod 上面去。然後 node pod 再轉化成 ClusterIP,去訪問到實際的 pod 上面。

三、操作演示

下面進行實際操作演示,在阿里雲的容器服務上面進去體驗一下如何使用 K8s Service。

創建 Service

我們已經創建好了一個阿里雲的容器集群,然後並且配置好本地終端到阿里雲容器集群的一個連接。

首先可以通過 kubectl get cs ,可以看到我們已經正常連接到了阿里雲容器服務的集群上面去。

今天將通過這些模板實際去體驗阿里雲服務上面去使用 K8s Service。有三個模板,首先是 client,就是用來模擬通過 service 去訪問 K8s 的 service,然後負載均衡到我們的 service 裏面去聲明的一組 pod 上。

K8s Service 的上面,跟剛才介紹一樣,我們創建了一個 K8s Service 模板,裏面 pod,K8s Service 會通過前端指定的 80 端口負載均衡到後端 pod 的 80 端口上面,然後 selector 選擇到 run:nginx 這樣標籤的一些 pod 去作為它的後端。

然後去創建帶有這樣標籤的一組 pod,通過什麼去創建 pod 呢?就是之前所介紹的 K8s deployment,通過 deployment 我們可以輕鬆創建出一組 pod,然後上面聲明 run:nginx 這樣一個label,並且它有兩個副本,會同時跑出來兩個 pod。

先創建一組 pod,就是創建這個 K8s deployment,通過 kubectl create -f service.yaml。這個 deployment 也創建好了,再看一下 pod 有沒有創建出來。如下圖看到這個 deployment 所創建的兩個 pod 都已經在 running 了。通過 kubectl get pod -o wide 可以看到 IP 地址。通過 -l,即 label 去做篩選,run=nginx。如下圖所示可以看到,這兩個 pod 分別是 10.0.0.135 和 10.0.0.12 這樣一個 IP 地址,並且都是帶 run=nginx 這個 label 的。

下面我們去創建 K8s service,就是剛才介紹的通過 service 去選擇這兩個 pod。這個 service 已經創建好了。

根據剛才介紹,通過 kubectl describe svc 可以看到這個 service 實際的一個狀態。如下圖所示,剛才創建的 nginx service,它的選擇器是 run=nginx,通過 run=nginx 這個選擇器選擇到後端的 pod 地址,就是剛才所看到那兩個 pod 的地址:10.0.0.12 和 10.0.0.135。這裏可以看到 K8s 為它生成了集群裏面一個虛擬 IP 地址,通過這個虛擬 IP 地址,它就可以負載均衡到後面的兩個 pod 上面去。

現在去創建一個客戶端的 pod 實際去感受一下如何去訪問這個 K8s Service,我們通過 client.yaml 去創建客戶端的 pod,kubectl get pod 可以看到客戶端 pod 已經創建好並且已經在運行中了。

通過 kubectl exec 到這個 pod 裏面,進入這個 pod 去感受一下剛才所說的三種訪問方式,首先可以直接去訪問這個 K8s 為它生成的這個 ClusterIP,就是虛擬 IP 地址,通過 curl 訪問這個 IP 地址,這個 pod 裏面沒有裝 curl。通過 wget 這個 IP 地址,輸入進去測試一下。可以看到通過這個去訪問到實際的 IP 地址是可以訪問到後端的 nginx 上面的,這個虛擬是一個統一的入口。

第二種方式,可以通過直接 service 名字的方式去訪問到這個 service。同樣通過 wget,訪問我們剛才所創建的 service 名 nginx,可以發現跟剛才看到的結果是一樣的。

在不同的 namespace 時,也可以通過加上 namespace 的一個名字去訪問到 service,比如這裏的 namespace 為 default。

最後我們介紹的訪問方式裏面還可以通過環境變量去訪問,在這個 pod 裏面直接通過執行 env 命令看一下它實際注入的環境變量的情況。看一下 nginx 的 service 的各種配置已經註冊進來了。

可以通過 wget 同樣去訪問這樣一個環境變量,然後可以訪問到我們的一個 service。

介紹完這三種訪問方式,再看一下如何通過 service 外部的網絡去訪問。我們 vim 直接修改一些剛才所創建的 service。

最後我們添加一個 type,就是 LoadBalancer,就是我們前面所介紹的外部訪問的方式。

然後通過 kubectl apply,這樣就把剛剛修改的內容直接生效在所創建的 service 裏面。

現在看一下 service 會有哪些變化呢?通過 kubectl get svc -o wide,我們發現剛剛創建的 nginx service 多了一個 EXTERNAL-IP,就是外部訪問的一個 IP 地址,剛才我們所訪問的都是 CLUSTER-IP,就是在集群裏面的一個虛擬 IP 地址。

然後現在實際去訪問一下這個外部 IP 地址 39.98.21.187,感受一下如何通過 service 去暴露我們的應用服務,直接在終端裏面點一下,這裏可以看到我們直接通過這個應用的外部訪問端點,可以訪問到這個 service,是不是很簡單?

我們最後再看一下用 service 去實現了 K8s 的服務發現,就是 service 的訪問地址跟 pod 的生命周期沒有關係。我們先看一下現在的 service 後面選擇的是這兩個 pod IP 地址。

我們現在把其中的一個 pod 刪掉,通過 kubectl delete 的方式把前面一個 pod 刪掉。

我們知道 deployment 會讓它自動生成一個新的 pod,現在看 IP 地址已經變成 137。

現在再去 describe 一下剛才的 service,如下圖,看到前面訪問端點就是集群的 IP 地址沒有發生變化,對外的 LoadBalancer 的 IP 地址也沒有發生變化。在所有不影響客戶端的訪問情況下,後端的一個 pod IP 已經自動放到了 service 後端裏面。

這樣就相當於在應用的組件調用的時候可以不用關心 pod 在生命周期的一個變化。

以上就是所有演示。

四、架構設計

最後是對 K8s 設計的一個簡單的分析以及實現的一些原理。

Kubernetes 服務發現架構

如上圖所示,K8s 服務發現以及 K8s Service 是這樣整體的一個架構。

K8s 分為 master 節點和 worker 節點:

  • master 裏面主要是 K8s 管控的內容;
  • worker 節點裏面是實際跑用戶應用的一個地方。

在 K8s master 節點裏面有 APIServer,就是統一管理 K8s 所有對象的地方,所有的組件都會註冊到 APIServer 上面去監聽這個對象的變化,比如說我們剛才的組件 pod 生命周期發生變化,這些事件。

這裏面最關鍵的有三個組件:

  • 一個是 Cloud Controller Manager,負責去配置 LoadBalancer 的一個負載均衡器給外部去訪問;
  • 另外一個就是 Coredns,就是通過 Coredns 去觀測 APIServer 裏面的 service 後端 pod 的一個變化,去配置 service 的 DNS 解析,實現可以通過 service 的名字直接訪問到 service 的虛擬 IP,或者是 Headless 類型的 Service 中的 IP 列表的解析;
  • 然後在每個 node 裏面會有 kube-proxy 這個組件,它通過監聽 service 以及 pod 變化,然後實際去配置集群裏面的 node pod 或者是虛擬 IP 地址的一個訪問。

實際訪問鏈路是什麼樣的呢?比如說從集群內部的一個 Client Pod3 去訪問 Service,就類似於剛才所演示的一個效果。Client Pod3 首先通過 Coredns 這裏去解析出 ServiceIP,Coredns 會返回給它 ServiceName 所對應的 service IP 是什麼,這個 Client Pod3 就會拿這個 Service IP 去做請求,它的請求到宿主機的網絡之後,就會被 kube-proxy 所配置的 iptables 或者 IPVS 去做一層攔截處理,之後去負載均衡到每一個實際的後端 pod 上面去,這樣就實現了一個負載均衡以及服務發現。

對於外部的流量,比如說剛才通過公網訪問的一個請求。它是通過外部的一個負載均衡器 Cloud Controller Manager 去監聽 service 的變化之後,去配置的一個負載均衡器,然後轉發到節點上的一個 NodePort 上面去,NodePort 也會經過 kube-proxy 的一個配置的一個 iptables,把 NodePort 的流量轉換成 ClusterIP,緊接着轉換成後端的一個 pod 的 IP 地址,去做負載均衡以及服務發現。這就是整個 K8s 服務發現以及 K8s Service 整體的結構。

後續進階

後續再進階部分我們還會更加深入地去講解 K8s Service 的實現原理,以及在 service 網絡出問題之後,如何去診斷以及去修復的技巧。

本文總結

本文的主要內容就到此為止了,這裏為大家簡單總結一下:

  1. 為什麼雲原生的場景需要服務發現和負載均衡,
  2. 在 Kubernetes 中如何使用 Kubernetes 的 Service 做服務發現和負載均衡
  3. Kubernetes 集群中 Service 涉及到的組件和大概實現原理

相信經過本文的學習與把握,大家能夠通過 Kubernetes Service 將複雜的企業級應用快速並標準地編排起來。

“阿里巴巴雲原生微信公眾號(ID:Alicloudnative)關注微服務、Serverless、容器、Service Mesh等技術領域、聚焦雲原生流行技術趨勢、雲原生大規模的落地實踐,做最懂雲原生開發者的技術公眾號。”

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

收購3c,收購IPHONE,收購蘋果電腦-詳細收購流程一覽表

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

※想要讓你的商品成為最夯、最多人討論的話題?網頁設計公司讓你強力曝光

※高價收購3C產品,價格不怕你比較

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

十年風雨,一個普通程序員的成長之路(九)一眼望到頭,一眼望不到頭

還有十幾天就是我的32歲生日,然後,33了,要過年了。

古人三十而立,我卻在這狹窄的圈子里兜兜轉轉。

多年前的喊的一句創業口號,現在還是口號。

焦慮、迷茫。

這两天一場網易的暴力裁員事件,犹如一盆涼水當頭澆下。

讓我又陷入了一年前的時刻。

渾身提不起勁。什麼都不想做。

不知前路在哪裡?

 

回過頭來看,對於當事人來說曲折圓轉的半生,之於他人,不過又是一個復讀機的普通人生而已。

上學、畢業、工作、買房、結婚、生子、還貸。

沒有家庭是形單影只,凄凄涼涼。

有了家庭卻只能蠅營狗苟,負重而行。

一眼望到頭的路罷了。

 

我們都只是這庸碌的銅爐里,亂糟糟破爛爛的一塊廢銅爛鐵而已。

所以財富神話才那麼多捧臭腳的雇從。

因為世間大多的煩惱,便是沒錢的煩惱。

所以我們信努力改變命運、知識改變命令、堅持改變命運。

其實是金錢改變命運。

 

滿是一些交錢的APP,讓你堅持下去,給你鼓勵。永遠溫馨對你。

你會改變命運的,你會財富自由的。

我們如飢似渴,似乎覺得比身邊的人多get了一門技能,升職加薪也是指日可待了。

如果你沒有升職加薪、財富自由、改變命運,那不過是你還不夠努力罷了。

不過是,交的錢還不夠多罷了。

一眼望不到頭。

 

什麼時候是個頭?

寫博客、開公眾號、寫小說。尋找出路。

我們永遠相信自己是天命之子。

堂吉訶德騎着馬,夾着騎士長槍,無知無畏地沖向了風車。

大風車吱喲喲地轉,這裏的風景呀真好看……哦,畫風跑偏了。

大風車吱喲喲地轉,不為堂吉訶德所動,不為騎士長槍所動。似能流轉萬世。

 

天地不仁,以萬物為芻狗。

你又憑什麼跳出世間這個熔爐呢?

只能在時間的鐵鎚下越來越彎曲自己的身子。

在夕陽里傴僂着身子,苟延殘喘。

一眼望到頭,又一眼望不到頭。

 

在這條短暫卻又無盡的路上,那麼多的大V與培訓機構告訴你:

劉強東曾跟你一樣賣過盜版盤跟電腦。

馬雲還沒你強,曾被肯德基拒絕臨時工。

比爾蓋茨中途就退了學,你跟惠普也就差個車庫而已了。

遺憾的是,給你上課的老師,可能正兒八經的資金來源還沒有你多。

你以為打開了得到,便真能得道。

你以為買了極客時間,便真成了極客。

你以為加了大V,便算是有了人脈。

你以為入了知識星球,便真學到了知識。

遺憾的是,大多時候,它們與書架上落灰的書籍沒什麼兩樣。

 

家庭的壓力也讓你學習的時間慢慢變少。

有了一點獨處的時間,你卻又想打兩把遊戲,松一松這命運壓迫的喉嚨,大口地喘息兩聲。

在遊戲中,孩子的哭鬧、老婆的絮絮叨叨,都已變成遙遠的過去。

可是玩了一會,你卻又充滿了負罪感。空虛與寂寞隨之而來。

因為普通人改變命運的機會太少了。

所以只能讀書改變命運。

 

在兩千年的中華文明史中,知識改變命運的箴言已印刻在了基因里。

犹如稻草。

給溺水的人,最後一點光芒與希望。

因為你這一生,我這一生。一眼便已能看到頭。

所以佛度來生。

所以道修逍遙。

若有仙人撫我頂,怎可結髮受長生?

我願化為北冥之鯤,潛於九淵,扶搖九天,逍遙星河之外。

只是一聲“爸爸,我要尿尿”。夢,便醒了。

 

你心裏嘆了一口氣,便把兒子從你跟你老婆身邊抱下了床。

穿衣、洗漱,照了照鏡子,才刮的鬍子又長了出來。

算了,反正是非單身的程序員,也沒什麼可講究的。

關上門,復讀機的一天又開始了。

可是我還是渾身提不起勁,總感覺失去了什麼。

於是,寫下此文。

一眼望到頭,一眼望不到頭。

 

——————————————————–
歡迎關注我的公眾號:姚毛毛的博客

這裡有我的編程生涯感悟與總結,有Java、Linux、Oracle、mysql的相關技術,有工作中進行的架構設計實踐和讀書理論,有JVM、Linux、數據庫的性能調優,有……

有技術,有情懷,有溫度

歡迎關注我:姚毛毛& 妖生

 

 

 

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

大型科技團隊的管理

介紹了高效科技組織的特點及管理經驗,指出科技團隊的定位和使命在於支持業務、賦能業務、最終引領業務,同時,還介紹了面向未來的科技組織的特點及對管理者提出的能力要求。

內容來源 | LeaTech全球CTO領導力峰會宜信公司CTO 高級副總裁向江旭分享《大型科技團隊的管理》

主講人 | 宜信公司CTO 高級副總裁向江旭

實錄整理 | 宜信技術學院成芳

引言:11月16日,由51CTO旗下CTO訓練營品牌精心打造的LeaTech全球CTO領導力峰會在北京粵財JW萬豪酒店拉開序幕。作為CTO、技術VP、技術總監等技術管理者人群的高端社交圈,本屆峰會現場聚集了CTO訓練營歷屆校友、CTO導師,以及行業中的資深技術管理者。600多位與會嘉賓在現場充分交流了有關技術性視野、技術領導力、技術團隊組織建設等精彩話題的觀點與思考,藉助峰會這個線下平台,技術管理者們积極探索了更多商業可能,開拓管理視野,令自身領導力再上新台階。

本次峰會邀請到宜信公司CTO 高級副總裁向江旭先生,帶來主題為《大型科技團隊的管理》的分享,向江旭先生在分享中提到科技團隊的定位和使命在於支持業務、賦能業務、最終引領業務,同時,他還介紹了面向未來的科技組織的特點及對管理者提出的能力要求。

以下為本次演講的分享實錄。

各位朋友下午好,今天我分享的主題是《大型科技團隊的管理》,非常高興能跟大家分享一些關於大型科技團隊管理的經驗和觀察。

去年12月,我在另一個峰會的分享中提到經濟寒冬、金融寒冬,今年這個時候也開始進入冬季,但是不管外面的大環境如何,技術人/技術圈都非常幸運,在科技賦能的市場中,技術人總是被需要的,技術圈也總是熱情高漲的。我認為,關於技術團隊的管理經驗非常值得與大家一起分享和交流。

一、大型科技團隊的特點及定位

大型科技團隊一般都有以下幾個特點:

  • 一定規模。顧名思義,談到大型科技團隊首先想到的特點肯定是團隊成員眾多。
  • 地域分佈廣。科技團隊的成員可能分佈在不同的地方。
  • 團隊背景多元。這種多元包括兩個層面的含義:一是角色背景多元,有的成員甚至不是做技術(這裏特指軟件研發)的,而是從其他行業轉過來的,比如行業數據分析師等角色。二是團隊成員的種族、國家背景多元。

一定規模、團隊背景多元化、分佈在不同地域等特點,使得大型科技團隊在管理上面臨着非常大的挑戰。

1.1 大型科技公司的科技團隊組織架構

上圖是一些大家耳熟能詳的漫畫,介紹了幾種典型的科技公司的科技團隊架構形式。

  • “Google式團隊架構”:最上面是兩個創始人和一個CEO,下面是部門負責人,其特點是下一級有多個彙報對象,這是谷歌的內部架構和管理方式,從一個層面代表了某個歷史階段科技組織的團隊構造。
  • “Amazon式團隊架構”:典型的層級式管理,逐級彙報。
  • “Oracle式團隊架構”:特點是有一個專門的法務團隊,因為Oracle收購了很多公司,某種程度上它是一個法務或銷售導向的公司。
  • “Facebook式團隊架構”:Facebook的團隊結構和它的業務一樣,是社交網絡形式的網狀結構。
  • “Apple式團隊架構”:(這是一張比較早期的圖)其特點是最核心的靈魂人物的觸角深入到公司的方方面面,事無巨細都是他在親自主導。
  • “Microsoft式團隊結構”:最後這張也是之前的圖,代表的是我服務過的公司-微軟。三大版塊部門沒有交集,很深的部門牆,互相之間存在比較激烈的內部鬥爭。

由此可見,大型科技公司的文化基因決定了其科技團隊的組織架構形式,而科技組織架構的設計和管理很大程度上決定了組織的效能。

1.2 科技團隊的使命和定位

在討論科技團隊的管理之前,有一個很重要的前提,要知道科技團隊的使命和定位是什麼。

很多非科技驅動的公司,比如銀行、保險公司、地產公司等,都在計劃或嘗試轉型成為一家科技公司。我認為在這樣的背景下,科技從業人員反而應該更清楚自己的定位。

1)支持業務

首先我們是支持業務的,要把業務放在最核心的位置,如果公司是靠產品和服務生存的,業務沒做好,科技也不一定能做好。當然公司類型不一樣,不能一概而論。比如純科技公司微軟,產品和服務本身就是技術,技術的好壞決定了公司業務的好壞。

2)賦能業務

科技團隊通過開發一些工具,幫助業務、銷售等部門實現業務流程信息化、智能化,使得業務流轉的過程更為暢通和友好。甚至更進一步,開發一個好的技術平台,使得生態圈、合作夥伴、第三方公司能夠在平台上發展業務、共建生態,這時科技團隊就起到了賦能業務的作用。

3)引領業務

科技團隊還可以通過技術創新、產品創新來拓展新的業務領域,催生新的業務模式,增加新的收入來源,成為引領業務的力量。

這三點是相輔相成的,支持業務、賦能業務,最後引領業務,不論是在技術驅動的公司,還是在業務驅動的公司,技術團隊的使命和定位都是如此。

1.3 技術和業務的關係

定位決定地位,業務發展是終極目標,當面臨整體技術戰略與商業戰略衝突、技術實施節點選擇、技術與業務路徑匹配等問題時,技術管理者可以從以下方面進行思考。

1)解決技術戰略與商業戰略的衝突。

技術和業務除了相輔相成的關係外,還存在一定的衝突。其實技術和業務的衝突在大家平時的工作中經常見到,比如業務同事着急上線一個功能來做活動;而技術覺得要達到同樣的目的,我們可能需要好的設計和架構,而不是簡單做一個臨時補丁式的功能,這就是很常見的技術和業務的衝突。

雖然技術負責人要對未來中長期的戰略布局保持持續思考,但這取決於公司的大小、規模和階段。如果是初創公司,首要任務是生存,那麼業務需求是最高優先級,首先要考慮解決系統不穩定、安全或其他問題;但對於有一定體量的企業,公司業務已經發展到一定階段,技術團隊也有一定的規模,當存在業務需求和技術戰略的衝突時,在滿足最緊迫的業務需求的同時,將一定精力投入到基礎技術研發中去,必須要做中長期的項目預研,做一些底層、甚至風險較高的研究。

2)技術變革的實施節點

我們永遠在高速公路上奔跑,一邊行駛一邊換輪子或換部件的事情一直在發生。技術重構、技術變革、技術債務償還的時機和節點和對業務產生的影響,是我們面臨的又一個挑戰,也是需要我們長期考慮的問題。

什麼節點選擇什麼樣的技術?技術負責人具體把握新技術引入節點,其實難度很大。如果新技術距離實現商用價值僅有一年時間,那麼必須要進行布局,申請預算,建立團隊推進;如果新技術商業化已經迫在眉睫,競爭對手已經在布局了,那麼採取的措施就不是從頭做起,更好的應對方式可能是進行併購或資本運作。

3)技術與業務路徑匹配

新技術來臨,對業務的影響和衝擊會分短、中、長期,有的技術在短期內對新的業態有幫助,有的技術需要一個比較長的周期才會對業務產生影響。這時技術領導人要評估技術本身,並將其與業務的戰略路徑進行匹配,如果對長期業務有幫助,新技術仍然要引入,只是選擇時間點、投入範圍等可能會不一樣。

同時,在引入新技術進行技術創新時,還要注意新技術對當前業務產生的影響。舉個例子,宜信是一家金融科技公司,有自己的催收部門,我們一方面通過規範催收人員的行為來進行催收,一方面自己研發催收機器人。催收機器人的出現意味着部分催收人員的工作將會被替代,同時,機器人的特點之一是沒有情緒,它會按照程序設定禮貌地和用戶溝通,這就會在一定程度對催收效果和業務產生影響。因此我們還要考慮在哪個環節使用機器人這個技術,帶來的效果會更好。這也是技術和業務相輔相成又存在矛盾衝突關係的體現。

1.4 科技戰略

對於大型科技團隊而言,科技戰略思維也非常重要。舉幾個例子。

舉例提到的是我工作過的幾家公司,它們在不同的時間點做了一些不同的戰略調整。

很多年以前,在中國90%的Windows都不是正版的,於是微軟內部提出一個計劃,希望Windows在中國免費。這個計劃現在看起來非常簡單,也很容易理解,正版Windows免費帶來的好處顯而易見:它是一個非常好的終端用戶觸點、可以獲取更多用戶,可以基於這些用戶數據做數據分析和精準營銷等。但是當時微軟Windows的老大極力反對這件事,他認為這會影響Windows的營收,因此這個計劃最終沒有實行。這就是戰略思維的問題,如果不是在中國本地親身體驗這個環境和市場,可能做出的戰略決策就不一定是準確的,帶來的結果可能是痛失更大的發展機會。

微軟後來的雲戰略轉型是成功的,而移動轉型卻是失敗的。移動轉型時期,微軟收購諾基亞旗下的大部分手機業務,並基於Windows自研出一個Windows操作系統放在手機硬件上。因為微軟覺得沒有推出自己的手機這是一個缺憾,還認為佔領移動終端必須基於Windows,因此作出這樣的決策,結果以失敗告終。Windows使微軟一度成為桌面系統垄斷的贏家,也使得微軟在移動轉型失敗,成為下一步發展的絆腳石,可謂是成也Windows,敗也Windows。

再看蘇寧,蘇寧受到阿里巴巴、京東等電商的衝擊,痛下決心必須做電商,它採取的戰略是結合自己線下門店的優勢做O2O智慧門戶,實行線上下單、線下體驗、送貨到家,這種全渠道、全觸點的用戶交互與服務形式,使得蘇寧成為“中國傳統行業数字化轉型互聯網”為數不多的成功案例之一。

現在金融行業正處於嚴監管的環境,金融公司該何去何從?在這裏分享一些我的看法。

縱觀改革開放以來的歷史,每個行業在開始初期都是開放的,任何人都可以參与進來,魚龍混雜,一旦行業出現亂象,就會有監管介入,那些能力不強的、不合規的會被淘汰,等到監管后再開放、行業再成熟時,最後存活下來的才能健康發展。金融行業也是如此。

科技同仁不僅要埋頭做好自己的工作,也要抬頭看看歷史和未來,思考我們身處的這個行業,我們從事的科技工作對公司、對行業的作用是什麼?行業未來的發展趨勢是什麼,這對我們未來的職業發展也有幫助。

二、大型科技團隊的管理實踐

2.1 成功科技組織的特點

無論是前面提到的國際科技巨頭,還是國內優秀的互聯網公司,成功的科技組織都具備一些共同的特點。

1)高效、敏捷

優秀的科技團隊一定是一個高效、敏捷的團隊,能夠快速響應用戶和市場的需求變化,快速上線產品、得到反饋、不斷迭代更新,滿足或超過用戶的預期。

2)商業思維

科技團隊一定要有商業頭腦、商業思維,因為無論是搭建系統,還是做APP,一定有用戶,我們需要真正洞察到用戶的痛點和問題,幫他們及時解決問題,給他們創造價值。

3)數據驅動

如果科技團隊的工作只圍繞產品經理提出的需求,未來的產品路線圖還不夠,一定要基於用戶反饋、市場反饋、日活、月活、留存、轉化等數據來驅動產品走向、技術走向。

4)變革創新

很多公司都在強調變革和創新,我認為這是科技團隊必須要打造的環境和氛圍,方式很多,比如組織各種各樣的黑客馬拉松、團隊之間的交流分享等。我們公司也在組織黑客馬拉松,每個月業務部門都有比較棘手或緊迫的項目,技術團隊與業務團隊聯合把這些業務痛點解決,成果馬上應用到業務環境中去。

2.2 績效管理

績效管理的機制在微軟實行了很多年,其強制5%、10%的淘汰機制,一直被人詬病,因為它使得很多團隊互相指責、互相拆台,有的員工為了績效“寧當雞頭不當鳳尾”,組織內形成不好的文化和結果。後來改成了5%、10%的獎勵,從懲罰後進者變成鼓勵先進者,取得的效果好很多。

2.3 溝通

溝通每天都在進行,比如各種大大小小的會議。我發現不管開多少會,高層領導的想法、思路並不一定能被所有同事理解,因為溝通方式、溝通渠道的原因,信息不能觸達到所有人,需要重複很多遍。

我們可以利用一些非正式場合或社交媒體來進行交流。比如我們公司有每月的CTO午餐會,抽籤的方式,各團隊都有機會可以坐下來跟我一起吃午餐,通過這種面對面的交流,我會向團隊成員提出一些我的看法,或者推薦一本書,他們會向我反饋當時的痛點、想法等。我覺得這是一種非常好的機制,大家能夠在一個寬鬆的環境下面對面地交流。記得以前在思科工作的時候,也有CEO早餐會,每個月過生日的員工可以跟CEO吃早餐,也是一種很好的溝通互動的方式。

2.4 團隊文化

團隊文化包含很多要素,我對這幾點的認同感比較深:主人翁意識、緊迫感、同理心。

2.5 技術決策

商業世界充滿了選擇和決策。作為一個技術決策人,有時很難做決定,難做決定就意味着拖延,這一點對於大型科技團隊的決策人來說是比較忌諱的,很多時候不在於你做的決策是對還是錯,而是在於你做不做決定。如果你是一個不敢做決定的人,帶領的團隊就會缺乏方向感,你做的決定就會受到團隊的質疑和挑戰。

有時候即使你做出了錯誤的決定,但大家一起努力執行的時候,可能可以逐步調整轉變從而達成正確的結果。技術管理人一定要懂得取捨,通過大腦計算,明確目標,了解關聯方,分析可選項和利弊,基於目標、數據和對未來的預期做出決策。

2.6 執行力

執行的時候要不忘初心,一步步地大處着眼、小處着手,小步快跑,快速迭代,及時反饋,及時調整,朝着設定的目標專心致志、心無旁騖。

2.7 終極目標

最後的終極目標是,希望科技團隊能夠做到比業務更懂業務,比用戶更懂用戶,讓技術本身變成公司核心的業務。我認為如果能做到科技團隊在公司起到了核心的作用,這才是永生的價值。

三、面向未來的科技組織

3.1 回顧微軟的3任CEO和3種組織

就微軟而言,同一家公司,文化和技術氛圍在不同階段是不一樣的。

第一個階段,CEO比爾蓋茨,技術為王,認為技術改變世界,代碼可以改變千萬人的生活。這一階段造就了好的產品,同時也存在一些負面影響,比如垄斷等。

第二個階段,CEO鮑爾默,業績為王,要求所有設備,包括手機、電視、車等,都跑到Windows上,還和海爾合作推出基於Windows的智能電視,當時所有跟Windows衝突的想法和計劃基本都被扼殺在搖籃里,這也導致公司錯失了很多發展的機會。

第三個階段,CEO納德拉,公司文化變得更加包容、強調同理心、開放透明,包括技術開源、提供雲服務、和蘋果/谷歌等競爭對手合作。這種開放包容的氛圍,讓微軟得以浴火重生。

3.2 面向未來的科技組織

面向未來的科技組織應該是什麼樣的?

1)跨界融合

不同背景的人,融合到一個跨界的氛圍和組織中,一起發力。

2)数字化轉型

傳統公司也在做数字化轉型,這時會引入很多科技人才,利用科技幫助公司完成轉型,並在行業實現快速發展。

3)全球共享、全球分佈

團隊組成全球化,來自不同國家、不同種族的人組成一個全球化的團隊。東南亞有一個集美團、滴滴、螞蟻金服為一體的公司,解決出行、支付、快遞的問題,這家公司有一個幾千人的科技團隊,團隊成員來自50多個種族,分佈在美國、新加坡、北京、印尼、印度等國家和地區。

4)技術引領

未來科技團隊不僅要做到賦能業務,還要能實現引領業務。

這樣的科技團隊需要跨界、全球化、複合型的領導人,只有既懂科技、又懂管理;既要懂業務,又懂行業的管理人才才能適合於領導面向未來的科技組織。

以上就是今天跟大家分享的全部內容,時間很短,主要介紹了一些在不同公司不同行業的大型科技團隊的管理經驗,希望大家在面向未來的科技組織中找到自己的定位,成為一個優秀的領導者。謝謝大家。

本文根據向江旭老師在LeaTech全球CTO領導力峰會上的分享內容整理所得,轉載請聯繫授權。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

3c收購,鏡頭 收購有可能以全新價回收嗎?

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

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

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

賣IPHONE,iPhone回收,舊換新!教你怎麼賣才划算?

文件與文件系統壓縮

目錄

在Linux下面有相當多的壓縮命令可以運行,這些壓縮命令可以讓我們更方便地從網絡上面下載容量較大的文件。此外,我們知道在Linux下面,擴展名沒有什麼特殊的意義。 不過,針對這些壓縮命令所產生的壓縮文件,為了方便記憶,還是會有一些特殊的命名方式,就讓我們來看看吧!

文件壓縮

什麼是文件壓縮呢?我們稍微談一談它的原理,目前我們使用的計算機系統中都是使用所謂的字節單位來計量。不過,事實上,計算機最小的計量單位應該是bit才對,此外,我們也知道 1字節=8比特(1Byte=8bit),但是如果今天我們只是記錄一個数字,即1這個数字,它會如何記錄?假設一個字節可以看成下面的模樣:

由於 1Byte=8bit,所以每個字節當中會有8個空格,而每個空格只可以是0、1

由於我們記錄的数字是1,考慮計算機所謂的二進制,如此一來,1會在最右邊佔據1個位,而其他的7個位將會自動地被填上0.如下圖所示

你看看,其實在這樣的例子中,那7個位應該是空的才對。不過,為了要滿足目前我們的操作系統數據的讀寫,所以就會將該數據轉為字節的形式來記錄。而一些聰明的計算機工程師就利用一些複雜的計算方式,將這些沒有使用到的空間【丟】出來,以讓文件佔用的空間變小,這就是壓縮的技術。
另一種壓縮技術也很有趣,它是將重複的數據進行統計記錄。舉例來說,如果你的數據為【111······】共有100個1時,那麼壓縮技術會記錄為【100個1】而不是真的有100個1的位存在。這樣也能夠精簡文件記錄的容量,非常有趣吧!
簡單地說,你可以將它想成,其實文件裏面有相當多的空間存在,並不是完全填滿的,而壓縮技術就是將這些空間填滿,以讓整個文件佔用的容量下降。不過,這些壓縮過的文件並無法直接被我們的操作系統所使用,因此,若要使用這些被壓縮過的文件數據,則必須將它還原回未壓縮前的模樣,那就是所謂的解壓縮。而至於壓縮后與壓縮的文件所佔用的磁盤空間大小,就可以被稱為是壓縮比
這個壓縮與解壓縮的操作有什麼好處呢?
1.最大的好處就是壓縮過的文件容量變小了,所以你的硬盤無形之中就可以容納更多的數據。
2.此外,在一些網絡數據的傳輸中,也會由於數據量的降低,好讓網絡帶寬可以用來做更多的工作,而不是老卡在一些大型文件傳輸上面。

Linux系統常見壓縮命令

在Linux的環境中,壓縮文件的擴展名大多是: *.tar、*.tar.gz、*.gz、*.Z、*.bz2、*.xz。為什麼會有這樣的擴展名?不是說Linux的擴展名沒有什麼作用嗎?
這是因為Linux支持的壓縮命令非常多,且不同的命令所用的壓縮技術並不相同,當然彼此之間可能就無法互通/解壓縮文件。所以,當你下載到某個文件時,自然就需要知道該文件是由哪種壓縮命令所製作出來的,好用來對照對照着解壓縮,也就是說,雖然Linux文件的屬性基本上是與文件名沒有絕對關係的,但是為了幫助我們人類小小的腦袋,所以適當的擴展名還是必要的,下面我們就列出幾個常見的壓縮文件擴展名:

*.gz         gzip程序壓縮的文件
*.bz2        bzip2程序壓縮的文件
*.xz         xz程序壓縮的文件
*.zip        zip程序壓縮的文件
*.Z          compress程序壓縮的文件
*.tar        tar程序打包的文件,並沒有壓縮過
*.tar.gz     tar程序打包的文件,並且經過gzip的壓縮
*.tar.bz2    tar程序打包的文件,並且經過bzip2的壓縮
*.tar.xz     tar程序打包的文件,並且經過xz的壓縮

Linux常見的壓縮命令就是gzip、bzip2以及最新的xz,至於compress已經不流行了。為了支持windows常見的zip,其實Linux也早就有zip命令了。gzip是由GNU計劃所開發出來的壓縮命令,該命令支持已經替換了compress。後台GNU又開發出了bzip2及xz這幾個壓縮比更好的壓縮命令。不過,這些命令通常僅能針對一個文件來壓縮與解壓縮,如此一來,每次壓縮與解壓縮都要一大堆文件,豈不煩人?此時,這個所謂的【打包軟件,tar】就顯得很重要。
這個tar可以將很多文件打包成一個文件,甚至是目錄也可以這麼玩。不過,單純的tar功能僅僅是打包而已,即將很多文件結合為一個文件,事實上,它並沒有提供壓縮的功能,後台,GNU計劃中,將整個tar與壓縮的功能結合在一起,如此一來,提供用戶更方便且更強大的壓縮與打包功能,下面我們就來談一談這些在Linux下面基本的壓縮命令。

gzip

gzip可以說是應用最廣的壓縮命令了,目前gzip可以解開compress、zip和gzip等軟件所壓縮的文件,至於gzip所建立的壓縮文件為*.gz,讓我們來看看這個命令的語法:

gzip [-cdtvn] 文件名
選項與參數:
-c: 將壓縮的數據輸出到屏幕上,可通過數據流重定向來處理;
-d: 解壓縮的參數;
-t: 可以用來檢驗一個壓縮文件的一致性,看看文件有無錯誤;
-v: 可以显示出原文件/壓縮文件的壓縮比等信息;
-n: n為数字的意思,代表壓縮等級,-1最快,但壓縮比最差,-9最慢,但是壓縮比最好,默認是-6

示例1:壓縮文件(gzip -v 文件名)

示例2:解壓縮文件(gzip -d 文件名)

示例3:按照指定壓縮比壓縮(gzip -9 文件名)

示例4:查看壓縮文件的內容(zcat 文件名)

示例5:壓縮為指定文件名(gzip -c 文件名 > 指定文件名)

當你使用gzip進行壓縮時,在默認的狀態下原本的文件會被壓縮成為.gz後綴的文件,源文件就不存在了,這點與一般習慣使用Windows做壓縮的朋友所熟悉的情況不同,要注意。cat/more/less可以使用不同的方式來讀取純文本文件,那麼zcat/zmore/zless則可以對應於cat/more/less的方式來讀取純文件文件被壓縮后的壓縮文件。

bzip2

若說gzip是為了替換compress並提供更好的壓縮比而成立的,那麼bzip2則是為了替換gzip並提供更加的壓縮比而來。bzip2真是很不錯的東西,這玩意的壓縮比竟然比gzip還要好,至於bzip2的用法幾乎與gzip相同,看看下面的用法吧!

bzip2 [-cdkzvn] 文件名
選項與參數:
-c: 將壓縮的數據輸出到屏幕上,可通過數據流重定向來處理;
-d: 解壓縮的參數;
-k: 保留原始文件,而不是刪除原始文件;
-z: 壓縮的參數(默認值,可以不加);
-v: 可以显示出原文件/壓縮文件的壓縮比等信息;
-n: n為数字的意思,代表壓縮等級,-1最快,但壓縮比最差,-9最慢,但是壓縮比最好,默認是-6

示例:

bzip2 -v 待壓縮文件名
bzip2 -d 壓縮后的文件名
bzip2 -9 -c 待壓縮的文件名 > 自定義壓縮文件名

xz

雖然bzip2已經具有很棒的壓縮比,不過顯然某些自由軟件開發者還不滿足,因此後來還推出了xz這個壓縮比更高的軟件。這個軟件的用法也跟gzip/bzip2幾乎一模一樣,那我們就來看一看。

xz [-cdtlkn] 文件名
選項與參數:
-c: 將壓縮的數據輸出到屏幕上,可通過數據流重定向來處理;
-d: 解壓縮的參數;
-k: 保留原始文件,而不是刪除原始文件;
-l: 列出壓縮文件的相關信息;
-t: 測試壓縮文件的完整性,看看有沒有錯誤;
-z: 壓縮的參數(默認值,可以不加);
-n: n為数字的意思,代表壓縮等級,-1最快,但壓縮比最差,-9最慢,但是壓縮比最好,默認是-6

示例:

xz -v 待壓縮的文件名
xz -l 壓縮后的文件名
xz -d 壓縮后的文件名
xz -k 待壓縮的文件名

打包命令

前面談到的命令大多僅能針對單一文件來進行壓縮,雖然gzip、bzip2、xz也能夠針對目錄來進行壓縮,不過,這幾個命令對目錄的壓縮指的是將目錄內的所有文件【分別】進行壓縮的操作。而不像在Windows的系統,可以使用類似WinRAR這一類的壓縮軟件來將好多數據包成一個文件的樣式。
這種將多個文件或目錄包成一個大文件的命令功能,我們可以稱它是一種打包命令,那Linux有沒有這種打包命令?有,那就是大名鼎鼎的tar,tar可以將多個目錄或文件打包成一個大文件,同時還可以通過gzip、bzip2、xz的支持,將該文件同時進行壓縮。更有趣的是,由於tar的使用太廣泛了,目前Windows的WinRAR也支持.tar.gz文件名的解壓縮。

tar

tar的選項與參數特別多,我們只講幾個常用的選項,更多選項您可以自行man tar查詢。

tar [-z|-j|-J] [cv] [-f 待建立的新文件名] filename... <== 打包與壓縮。
tar [-z|-j|-J] [cv] [-f 既有的tar文件名]  <== 查看文件名
tar [-z|-j|-J] [xv] [-f 既有的tar文件名]  <== 解壓縮
選項與參數:
-c: 建立打包文件,可搭配-v來查看過程中被打包的文件名(filename);
-t: 查看打包文件的內容含有那些文件名,重點在查看【文件名】;
-x: 解包或解壓縮功能,可以搭配-C(大寫)在特定目錄解壓,特別留意的是,-c、-t、-x不可同時出現在一串命令行中;
-z: 通過gzip的支持進行壓縮/解壓縮: 此時文件名最好為*.tar.gz;
-j: 通過bzip2的支持進行壓縮/解壓縮:此時文件名最好為*.tar.bz2;
-J: 通過xz的支持進行壓縮/解壓縮: 此時文件名最好為 *.tar.xz,特別留意,-z、-j、-J不可以同時出現在一串命令行中;
-v: 在壓縮/解壓縮的過程中,將正在處理的文件名显示出來;
-f filename: -f後面要立刻接要被處理的文件名,建議-f單獨寫一個選項(比較不會忘記)。
-C 目錄: 這個選項用在解壓縮,若要在特定目錄解壓縮,可以使用這個選項
-p(小寫): 保留備份數據的原本權限與屬性,常用於備份(-c)重要的配置文件;
-P(大寫): 保留絕對路徑,亦即允許備份數據中含有根目錄存在之意

其實最簡單的使用tar就只要記住下面的命令即可:

  • 壓縮: tar -jcv -f filename.tar.bz2 要被壓縮的文件或目錄名稱;
  • 查詢: tar -jtv -f filename.tar.bz2
  • 解壓縮: tar -jxv -f filename.tar.bz2 -C 欲解壓縮的目錄

示例:

tar -zcvf 文件名.tar.gz 文件名(目錄)

tar -ztvf 文件名.tar.gz

tar -zxvf 文件名.tar.gz

資料:

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※公開收購3c價格,不怕被賤賣!

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

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

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

Orleans 3.0 為我們帶來了什麼

 

原文:https://devblogs.microsoft.com/dotnet/orleans-3-0/

作者:Reuben BondOrleans首席軟件開發工程師

翻譯:艾心

這是一篇來自Orleans團隊的客座文章,Orleans是一個使用.NET創建分佈式應用的跨平台框架。獲取更多信息,請查看https://github.com/dotnet/orleans。

我們激動的宣布Orleans3.0的發布。自Orleans2.0以來,加入了大量的改進與修復,以及一些新特性。這些變化是由許多人在生產環境的大量場景中運行基於Orleans應用程序的經驗,以及全球Orleans社區的智慧和熱情推動的,他們致力於使代碼庫更好、更快、更靈活。非常感謝所有以各種方式為這個版本做出貢獻的人。

自Orleans 2.0以來的關鍵變化:

Orleans 2.0發佈於18個多月前,從那時起Orleans便取得了巨大的進步。以下是自Orleans 2.0以來的重大變化:

  • 分佈式ACID事務-多個Grains加入到一個事務中,不管他們的狀態存儲在哪裡
  • 一個新的調度器,在某些情況下,僅它就可以將性能提升30%以上
  • 一種基於Roslyn代碼分析的新的代碼生成器
  • 重寫集群成員以提升恢復速度
  • 聯合(Co-hosting)支持

還有很多其他的提升以及修復。

自從致力於開發Orleans2.0以來,團隊就建立了一套實現或者繼承某些功能的良性循環,包括通用主機、命名選項,在準備將這些功能好成為.NETCore的一部分之前與.NET團隊密切合作、提供反饋和改進“upstream”,在以後的版本中會切換到.NET版本附帶的最終實現。在開發Orleans 3.0期間,這個循環繼續着,在最終發布為.NET Core 3.0的一部分之前,Orleans 3.0.0-beta1使用了Bedrock代碼。類似的,TCP套接字連接對TLS的支持是作為Orleans 3.0的一部分實現的,並計劃成為.NET Core未來版本的一部分。我們把這種持續的合作視為是我們對更大的.NET生態系統的貢獻,這是真正的開源精神。

使用ASP.NET Bedrock替換網絡層

一段時間以來,社區和內部合作夥伴一直要求支持與TLS的安全通信。在3.0版本中,我們引入了TLS支持,可以通過Microsoft.Orleans.Connections.Security包獲取。有關更多信息,請查看TransportLayerSecurity範例。實現TLS支持之所以是一個重大任務要歸因於上一個版本中Orleans網絡層的實現方式:它並不容易適應使用SslStream的方式,而SslStream又是實現TLS最常用的方法。在TLS的推動下,我們着手重寫Orleans的網絡層。

Orleans 3.0使用了一個來自ASP.NET團隊倡議的基於Bedrock項目構建的網絡層替換了自己的整個網絡層,Bedrock旨在幫助開發者構建快速的、健壯的網絡客戶端和服務器。

ASP.NET團隊和Orleans團隊一同合作設計了同時支持網絡客戶端和服務端的抽象,這些抽象與傳輸無關,並且可以通過中間件實現定製化。這些抽象允許我們通過配置修改網絡,而不用修改內部的、特定於Orleans的網絡代碼。Orleans的TLS支持是作為Bedrock中間件實現的,我們的目的是使之通用,以便與.NET生態圈的其他人共享。

儘管這項工作是的動力是啟用TLS支持,但是在夜間負載測試中,我們看到了平均吞吐量提升了大約30%。

網絡層重寫還包括藉助使用MemoryPool<byte>替換我們的自定義緩存池,在進行這項修改時,序列化更多的使用到了Span<T>。有一些代碼路徑之前是依靠調用BlockingCollection<T>的專有線程進行阻塞,現在使用Channel<T>來異步傳輸消息。這將導致更少的專有線程佔用,同時將工作移動到了.NET線程池。

Orleans的核心連接協議自發布以來一直都是固定的。在Orleans3.0中,我們已經增加了通過協議協商(negotiation)逐步更新網絡層的支持。Orleans 3.0中添加的協議協商支持未來的功能增強,如定製核心序列化器,同時向後保持兼容性。新的網絡協議的一個優點是支持全雙工Silo到Silo的連接,而不是以前在Silo之間建立的單工連接對。協議版本可以通過ConnectionOptions.ProtocolVersion進行配置。

通過通用主機進行聯合託管

Orleans與其他框架共同進行聯合託管,如ASP.NETCore,得益於.NET通用主機,相同的進程中(使用聯合託管)現在要比以前容易多了。

下面是一個使用UseOrleans將Orleans和ASP.NETCore一起添加到主機的例子:

 1 var host = new HostBuilder()
 2   .ConfigureWebHostDefaults(webBuilder =>
 3   {
 4     // Configure ASP.NET Core
 5     webBuilder.UseStartup<Startup>();
 6   })
 7   .UseOrleans(siloBuilder =>
 8   {
 9     // Configure Orleans
10     siloBuilder.UseLocalHostClustering();
11   })
12   .ConfigureLogging(logging =>
13   {
14     /* Configure cross-cutting concerns such as logging */
15   })
16   .ConfigureServices(services =>
17   {
18     /* Configure shared services */
19   })
20   .UseConsoleLifetime()
21   .Build();
22 
23 // Start the host and wait for it to stop.
24 await host.RunAsync();

使用通過主機構建器,Orleans將與其他託管程序共享同一個服務提供者。這使得這些服務可以訪問Orleans。例如,一個開發者可以注入IClusterClient或者IGrainFactory到ASP.NETCore MVC Controller中,然後從MVC應用中直接調用Grains。

這個功能可以簡化你的部署拓撲或者向現有程序中額外添加功能。一些團隊內部使用聯合託管,通過ASP.NET Core健康檢查將Kubernetes活躍性和就緒性探針添加到其Orleans Silo中。

可靠性提高

得益於擴展了Gossip,集群現在可以更快的從失敗中恢復。在以前的Orleans版本中,Silo會向其他Silo發送成員Gossip信息,指示他們更新成員信息。現在Gossip消息包括集群成員的版本化、不可變快照。這樣可以縮短Silo加入或者離開集群的收斂時間(例如在更新、擴展或者失敗后),並減輕共享成員存儲上的爭用,從而加快集群轉換的速度。故障檢測也得到了改進,利用更多的診斷信息和改進功能以確保更快、更準確的檢測。故障檢測涉及集群中的Silo,他們相互監控,每個Silo會定期向其他Silo的子集發送健康探測。Silo和客戶端現在還主動與已聲明為已失效的Silo的連接斷開,它們將拒絕與此類Silo的連接。

現在,消息錯誤得到了更一致的處理,從而將錯誤提示信息傳播回調用者。這有助於開發者更快地發現錯誤。例如,當消息無法被完全序列化或者反序列化時,詳細的異常信息將會被返回到原始調用方。

可擴展性增強

現在,Streams可以有自定義的數據適配器,從而允許他們以任何格式提取數據。這使得開發人員更好的控制Streamitems在存儲中的表示方式。他還使Stream提供者可以控制如何寫入數據,從而允許Streams與老的系統和Orleans服務集成。

Grain擴展允許通過自己的通信接口附件新的組件,從而在運行時向Grain添加其他行為。例如,Orleans事務使用Grain擴展對用戶透明的向Grain中添加事務生命周期方法,如“準備”、“提交”和“中止”。Grain擴展現在也可用於Grain服務和系統目標。

現在,自定義事務狀態可以聲明其在事務中能夠扮演的角色。例如,將事務生命周期事件寫入服務總線隊列的事務狀態實現不能滿足事務管理器的職責,因為它(該事務狀態的職責)是只寫的。

由於預定義的放置策略現在可以公開訪問,因此在配置期間可以替換任何放置控制器。

共同努力

既然Orleans 3.0已經發布,我們也就會將注意力轉向未來的版本-我們有一些令人興奮的計劃!快來加入我們在GitHub和Gitter上的社區,幫助我們實現這些計劃。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

收購3c,收購IPHONE,收購蘋果電腦-詳細收購流程一覽表

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

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

※公開收購3c價格,不怕被賤賣!

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

【Spring】簡述@Configuration配置類註冊BeanDefinition到Spring容器的過程

概述

本文以SpringBoot應用為基礎,嘗試分析基於註解@Configuration的配置類是如何向Spring容器註冊BeanDefinition的過程

其中主要分析了 ConfigurationClassPostProcessor 這個BeanDefinitionRegistryPostProcessor 即Bean定義註冊後置處理器,在Spring啟動過程中對@Configuration配置類的處理,主要體現在 解析並發現所有配置類,處理配置類的相關邏輯(如配置類上的@ComponentScan、@Import、@Bean註解等),註冊其中的BeanDefinition

SpringBoot版本:2.0.9.RELEASE

Spring版本:5.0.13.RELEASE

ConfigurationClassPostProcessor如何被引入

首先看一下ConfigurationClassPostProcessor的類繼承關係

從紅框中可以看出ConfigurationClassPostProcessorBeanDefinitionRegistryPostProcessor接口的實現類,即是一個Bean定義註冊的後置處理器,會在Spring容器啟動時被調用,具體時機為

// 調用鏈
AbstractApplicationContext.refresh()
    => invokeBeanFactoryPostProcessors()
    => PostProcessorRegistrationDelegate#invokeBeanFactoryPostProcessors()

invokeBeanFactoryPostProcessors()會先調用所有的BeanDefinitionRegistryPostProcessor之後,再調用所有的BeanFactoryPostProcessor

ConfigurationClassPostProcessor又是如何被引入Spring的呢??

SpringBoot應用會在ApplicationContext應用上下文被創建的構造函數中new AnnotatedBeanDefinitionReader這個用於註冊基於註解的BeanDefinition的Reader,在其構造中又會調用AnnotationConfigUtils.registerAnnotationConfigProcessors(this.registry)使用工具類向Spring容器中註冊一些所謂的註解配置處理器,其中就包含ConfigurationClassPostProcessor

// ConfigurationClassPostProcessor被註冊
AnnotationConfigServletWebServerApplicationContext構造
    => new AnnotatedBeanDefinitionReader(registry)
        => AnnotationConfigUtils.registerAnnotationConfigProcessors(registry)
            => 註冊ConfigurationClassPostProcessor到Spring容器

ConfigurationClassPostProcessor處理過程簡述

首先,ConfigurationClassPostProcessor後置處理器的處理入口為postProcessBeanDefinitionRegistry()方法。其主要使用了ConfigurationClassParser配置類解析器解析@Configuration配置類上的諸如@ComponentScan@Import@Bean等註解,並嘗試發現所有的配置類;還使用了ConfigurationClassBeanDefinitionReader註冊所發現的所有配置類中的所有Bean定義;結束執行的條件是所有配置類都被發現和處理,相應的bean定義註冊到容器

大致流程如下:

1、通過BeanDefinitionRegistry查找當前Spring容器中所有BeanDefinition

2、通過ConfigurationClassUtils.checkConfigurationClassCandidate() 檢查BeanDefinition是否為 “完全配置類”“簡化配置類”,並對配置類做標記,放入集合待後續處理

Spring配置類的分類可以

3、通過 ConfigurationClassParser解析器 parse解析配置類集合,嘗試通過它們找到其它配置類

4、使用 ConfigurationClassBeanDefinitionReader 註冊通過所發現的配置類中找到的所有beanDefinition

5、處理完一輪配置類后,查看BeanDefinitionRegistry中是否存在新加載的且還未被處理過的 “完全配置類”“簡化配置類”,有的話繼續上面步驟

其中第3、4步後面重點分析

ConfigurationClassParser#parse():解析構建配置類

對於SpringBoot應用來說,參与解析的種子配置文件即為SpringBoot的Application啟動類

解析構建配置類流程

通過ConfigurationClassParser解析器parse解析配置類集合,嘗試通過它們找到其它配置類

  • 循環解析所有配置類 ConfigurationClassParser#processConfigurationClass()

    • 根據@Conditional的ConfigurationPhase.PARSE_CONFIGURATION階段條件判斷是否跳過配置類

      注意:有些@Conditional是在當前這個PARSE_CONFIGURATION解析配置階段使用的,有些是在REGISTER_BEAN註冊beanDefinition階段使用的

    • 【重點】調用ConfigurationClassParser#doProcessConfigurationClass()循環解析配置類,直到不存在未處理過的父類

      • 1、處理配置類的成員內部類: 檢查其是否為“完全/簡化配置類”,是則對其繼續分析處理並將其放入分析器的屬性configurationClasses
      • 2、處理@PropertySource: 將找到的PropertySource添加到environment的PropertySource集合
      • 3、處理@ComponentScan: 掃描到的@Component類BeanDefinition就直接註冊到Spring容器;如果組件為配置類,繼續分析處理並將其放入分析器的屬性configurationClasses
      • 4、處理@Import:
        • (1)處理ImportSelector: 如果是DeferredImportSelector,如SpringBoot的自動配置導入,添加到deferredImportSelectors,延遲進行processImports();其它通過ImportSelector找到的類,繼續調用processImports(),要麼是@Configuration配置類繼續解析,要麼是普通組件導入Spring容器
        • (2)處理ImportBeanDefinitionRegistrar: 調用當前配置類的addImportBeanDefinitionRegistrar(),後面委託它註冊其它bean定義
        • (3)其它Import:調用processConfigurationClass()繼續解析,最終要麼是配置類放入configurationClasses,要麼是普通組件導入Spring容器
      • 5、處理@ImportResource: 添加到配置類的importedResources集合,後續ConfigurationClassBeanDefinitionReader#loadBeanDefinitions()時再使用這些導入的BeanDefinitionReader讀取Resource中的bean定義並註冊
      • 6、處理@Bean: 獲取所有@Bean方法,並添加到配置類的beanMethods集合
      • 7、處理配置類接口上的default methods
      • 8、檢查是否有未處理的父類: 如果配置類有父類,且其不在解析器維護的knownSuperclasses中,對其調用doProcessConfigurationClass()重複如上檢查,直到不再有父類或父類在knownSuperclasses中已存在
  • processDeferredImportSelectors():處理推遲的ImportSelector集合,其實就是延遲調用了processImports()

    SpringBoot的自動配置類就是被DeferredImportSelector推遲導入的

解析構建配置類源碼分析

ConfigurationClassParser#processConfigurationClass()

包含了處理單個配置類的大體流程,先根據ConfigurationPhase.PARSE_CONFIGURATION解析配置階段的@Conditional條件判斷當前配置類是否應該解析,之後調用ConfigurationClassParser#doProcessConfigurationClass()循環解析配置類,直到不存在未處理過的父類

/**
 * 解析單個配置類
 * 解析的最後會將當前配置類放到configurationClasses
 */
protected void processConfigurationClass(ConfigurationClass configClass) throws IOException {
    /**
     * 根據@Conditional條件判斷是否跳過配置類
     * 注意:當前這個PARSE_CONFIGURATION解析配置階段只會使用這個階段的@Conditional條件,有些REGISTER_BEAN註冊beanDefinition階段的條件不會在此時使用
     */
    if (this.conditionEvaluator.shouldSkip(configClass.getMetadata(), ConfigurationPhase.PARSE_CONFIGURATION)) {
        return;
    }

    ConfigurationClass existingClass = this.configurationClasses.get(configClass);
    // 如果configClass在已經分析處理的配置類記錄中已存在
    if (existingClass != null) {
        //如果配置類是被@Import註冊的,return
        if (configClass.isImported()) {
            if (existingClass.isImported()) {
                existingClass.mergeImportedBy(configClass);
            }
            // Otherwise ignore new imported config class; existing non-imported class overrides it.
            return;
        }
        // 否則,清除老的記錄,在來一遍
        else {
            // Explicit bean definition found, probably replacing an import.
            // Let's remove the old one and go with the new one.
            this.configurationClasses.remove(configClass);
            this.knownSuperclasses.values().removeIf(configClass::equals);
        }
    }

    // Recursively process the configuration class and its superclass hierarchy.
    /**
     * 遞歸處理配置類及其超類層次結構
     * 從當前配置類configClass開始向上沿着類繼承結構逐層執行doProcessConfigurationClass,直到遇到的父類是由Java提供的類結束循環
     */
    SourceClass sourceClass = asSourceClass(configClass);
    /**
     * 循環處理配置類configClass直到sourceClass變為null,即父類為null
     * doProcessConfigurationClass的返回值是其參數configClass的父類
     * 如果該父類是由Java提供的類或者已經處理過,返回null
     */
    do {
        sourceClass = doProcessConfigurationClass(configClass, sourceClass);
    }
    while (sourceClass != null);

    this.configurationClasses.put(configClass, configClass);
}

ConfigurationClassParser#doProcessConfigurationClass():真正解析配置類

通過解析配置類上的註解、內部成員類和方法構建一個完整的ConfigurationClass配置類,過程中如果發現了新的配置類可以重複調用此方法

真正解析過程中會處理成員內部類@PropertySource@ComponentScan@Import@ImportSource@Bean方法等,流程如下:

  • 1、處理配置類的成員內部類: 檢查其是否為“完全/簡化配置類”,是則對其繼續分析處理並將其放入分析器的屬性configurationClasses
  • 2、處理@PropertySource: 將找到的PropertySource添加到environment的PropertySource集合
  • 3、處理@ComponentScan: 掃描到的@Component類BeanDefinition就直接註冊到Spring容器;如果組件為配置類,繼續分析處理並將其放入分析器的屬性configurationClasses
  • 4、處理@Import:
    • (1)處理ImportSelector: 如果是DeferredImportSelector,如SpringBoot的自動配置導入,添加到deferredImportSelectors,延遲進行processImports();其它通過ImportSelector找到的類,繼續調用processImports(),要麼是@Configuration配置類繼續解析,要麼是普通組件導入Spring容器
    • (2)處理ImportBeanDefinitionRegistrar: 調用當前配置類的addImportBeanDefinitionRegistrar(),後面委託它註冊其它bean定義
    • (3)其它Import: 調用processConfigurationClass()繼續解析,最終要麼是配置類放入configurationClasses,要麼是普通組件導入Spring容器
  • 5、處理@ImportResource: 添加到配置類的importedResources集合,後續ConfigurationClassBeanDefinitionReader#loadBeanDefinitions()時再使用這些導入的BeanDefinitionReader讀取Resource中的bean定義並註冊
  • 6、處理@Bean: 獲取所有@Bean方法,並添加到配置類的beanMethods集合
  • 7、處理配置類接口上的default methods
  • 8、檢查是否有未處理的父類: 如果配置類有父類,且其不在解析器維護的knownSuperclasses中,對其調用doProcessConfigurationClass()重複如上檢查,直到不再有父類或父類在knownSuperclasses中已存在
/**
 * Apply processing and build a complete {@link ConfigurationClass} by reading the
 * annotations, members and methods from the source class. This method can be called
 * multiple times as relevant sources are discovered.
 * @param configClass the configuration class being build
 * @param sourceClass a source class
 * @return the superclass, or {@code null} if none found or previously processed
 */
@Nullable
protected final SourceClass doProcessConfigurationClass(ConfigurationClass configClass, SourceClass sourceClass)
        throws IOException {

    // Recursively process any member (nested) classes first
    /**
     * 1、處理配置類的成員類(配置類內嵌套定義的類)
     * 內部嵌套類也可能是配置類,遍歷這些成員類,檢查是否為"完全/簡化配置類"
     * 有的話,調用processConfigurationClass()處理它們,最終將配置類放入configurationClasses集合
     */
    processMemberClasses(configClass, sourceClass);

    // Process any @PropertySource annotations
    /**
     * 2、處理 @PropertySource
     * 將找到的PropertySource添加到environment的PropertySource集合
     */
    for (AnnotationAttributes propertySource : AnnotationConfigUtils.attributesForRepeatable(
            sourceClass.getMetadata(), PropertySources.class,
            org.springframework.context.annotation.PropertySource.class)) {
        if (this.environment instanceof ConfigurableEnvironment) {
            processPropertySource(propertySource);
        }
        else {
            logger.warn("Ignoring @PropertySource annotation on [" + sourceClass.getMetadata().getClassName() +
                    "]. Reason: Environment must implement ConfigurableEnvironment");
        }
    }

    // Process any @ComponentScan annotations
    /**
     * 3、處理 @ComponentScan
     * 處理用戶手工添加的@ComponentScan,SpringBoot創建ApplicationContext時的ClassPathBeanDefinitionScanner是為了掃描啟動類下的包
     * 為的是找到滿足條件的@ComponentScan,即@Component相關的組件,先掃描一下,掃描到的就註冊為BeanDefinition
     * 看其中是否還有配置類,有的話parse()繼續分析處理,配置類添加到configurationClasses集合
     */
    Set<AnnotationAttributes> componentScans = AnnotationConfigUtils.attributesForRepeatable(
            sourceClass.getMetadata(), ComponentScans.class, ComponentScan.class);
    // 如果當前配置類上有@ComponentScan,且使用REGISTER_BEAN註冊beanDefinition的條件判斷也不跳過的話
    if (!componentScans.isEmpty() &&
            !this.conditionEvaluator.shouldSkip(sourceClass.getMetadata(), ConfigurationPhase.REGISTER_BEAN)) {
        for (AnnotationAttributes componentScan : componentScans) {
            // The config class is annotated with @ComponentScan -> perform the scan immediately
            // 立即掃描,掃描到的就註冊為BeanDefinition,並獲得掃描到的所有beanDefinition
            // 在處理SpringBoot啟動類上的@ComponentScan時,雖然指指定了excludeFilters,但會根據啟動類所在包推測basePackage,就會掃描到SpringBoot啟動類包以下的Bean並註冊
            Set<BeanDefinitionHolder> scannedBeanDefinitions =
                    this.componentScanParser.parse(componentScan, sourceClass.getMetadata().getClassName());

            // Check the set of scanned definitions for any further config classes and parse recursively if needed
            // 檢查掃描到的beanDefinition中是否有配置類,有的話parse()繼續分析處理,,配置類添加到configurationClasses集合
            for (BeanDefinitionHolder holder : scannedBeanDefinitions) {
                BeanDefinition bdCand = holder.getBeanDefinition().getOriginatingBeanDefinition();
                if (bdCand == null) {
                    bdCand = holder.getBeanDefinition();
                }
                if (ConfigurationClassUtils.checkConfigurationClassCandidate(bdCand, this.metadataReaderFactory)) {
                    parse(bdCand.getBeanClassName(), holder.getBeanName());
                }
            }
        }
    }

    // Process any @Import annotations
    /**
     * 4、處理 @Import
     * (1)處理ImportSelector
     * 如果是DeferredImportSelector,如SpringBoot的自動配置導入,添加到deferredImportSelectors,延遲進行processImports()
     * 其它通過ImportSelector找到的類,繼續調用processImports(),要麼是@Configuration配置類繼續解析,要麼是普通組件導入Spring容器
     * (2)處理ImportBeanDefinitionRegistrar
     * 調用當前配置類的addImportBeanDefinitionRegistrar(),後面委託它註冊其它bean定義
     * (3)其它
     * 調用processConfigurationClass()繼續解析,最終要麼是配置類放入configurationClasses,要麼是普通組件導入Spring容器
     */
    processImports(configClass, sourceClass, getImports(sourceClass), true);

    // Process any @ImportResource annotations
    /**
     * 5、處理 @ImportResource
     * 添加到配置類的importedResources集合,後續loadBeanDefinitions()加載bean定義時再讓這些導入BeanDefinitionReader自行讀取bean定義
     */
    AnnotationAttributes importResource =
            AnnotationConfigUtils.attributesFor(sourceClass.getMetadata(), ImportResource.class);
    if (importResource != null) {
        String[] resources = importResource.getStringArray("locations");
        Class<? extends BeanDefinitionReader> readerClass = importResource.getClass("reader");
        for (String resource : resources) {
            String resolvedResource = this.environment.resolveRequiredPlaceholders(resource);
            configClass.addImportedResource(resolvedResource, readerClass);
        }
    }

    // Process individual @Bean methods
    /**
     * 6、處理個別@Bean方法
     * 獲取所有@Bean方法,並添加到配置類的beanMethods集合
     */
    Set<MethodMetadata> beanMethods = retrieveBeanMethodMetadata(sourceClass);
    for (MethodMetadata methodMetadata : beanMethods) {
        configClass.addBeanMethod(new BeanMethod(methodMetadata, configClass));
    }

    // Process default methods on interfaces
    /**
     * 7、處理配置類接口上的default methods
     */
    processInterfaces(configClass, sourceClass);

    // Process superclass, if any
    /**
     * 8、檢查父類是否需要處理,如果父類需要處理返回父類,否則返回null
     * 如果存在父類,且不在knownSuperclasses已經分析過的父類列表裡,返回並繼續分析
     */
    if (sourceClass.getMetadata().hasSuperClass()) {
        String superclass = sourceClass.getMetadata().getSuperClassName();
        if (superclass != null && !superclass.startsWith("java") &&
                !this.knownSuperclasses.containsKey(superclass)) {
            this.knownSuperclasses.put(superclass, configClass);
            // Superclass found, return its annotation metadata and recurse
            return sourceClass.getSuperClass();
        }
    }

    // No superclass -> processing is complete
    return null;
}

ConfigurationClassBeanDefinitionReader#loadBeanDefinitions():讀取配置類,基於配置信息註冊BeanDefinition

讀取配置類,基於配置信息註冊BeanDefinition流程

在上面解析配置類的過程中,除了構建了一個完整的ConfigurationClass配置類,其實已經向BeanDefinitionRegistry中添加了一些beanDefinition了,比如在處理@ComponentScan時,掃描到的@Component相關組件就已經註冊了

ConfigurationClassBeanDefinitionReader會繼續讀取已經構建好的ConfigurationClass配置類中的成員變量,從而註冊beanDefinition

構建好的ConfigurationClass配置類中在本階段可用的成員變量包括:

  1. Set<BeanMethod> beanMethods: @Bean的方法
  2. Map<String, Class<? extends BeanDefinitionReader>> importedResources:配置類上@ImportResource註解的類存入此集合,會使用BeanDefinitionReader讀取Resource中的BeanDefinition並註冊
  3. Map<ImportBeanDefinitionRegistrar, AnnotationMetadata> importBeanDefinitionRegistrars:ImportBeanDefinitionRegistrar集合

通過構建好的配置類的配置信息,使用ConfigurationClassBeanDefinitionReader註冊所有能夠讀取到的beanDefinition:

  • 根據ConfigurationPhase.REGISTER_BEAN階段條件判斷配置類是否需要跳過

    循環判斷配置類以及導入配置類的類,使用ConfigurationPhase.REGISTER_BEAN階段條件判斷是否需要跳過只要配置類或導入配置類的類需要跳過即返回跳過​

  • 如果configClass.isImported(),將配置類自身註冊為beanDefinition

  • 註冊配置類所有@Bean方法為beanDefinition

  • 註冊由@ImportedResources來的beanDefinition,即通過其它類型Resource的BeanDefinitionReader讀取BeanDefinition並註冊,如xml格式的配置源 XmlBeanDefinitionReader

  • 註冊由ImportBeanDefinitionRegistrars來的beanDefinition

讀取配置類,基於配置信息註冊BeanDefinition源碼分析

/**
 * Read a particular {@link ConfigurationClass}, registering bean definitions
 * for the class itself and all of its {@link Bean} methods.
 * 讀取特定配置類,根據配置信息註冊bean definitions
 */
private void loadBeanDefinitionsForConfigurationClass(
        ConfigurationClass configClass, TrackedConditionEvaluator trackedConditionEvaluator) {

    /**
     * 根據ConfigurationPhase.REGISTER_BEAN階段條件判斷配置類是否需要跳過
     * 循環判斷配置類以及導入配置類的類,使用ConfigurationPhase.REGISTER_BEAN階段條件判斷是否需要跳過
     * 只要配置類或導入配置類的類需要跳過即返回跳過
     */
    if (trackedConditionEvaluator.shouldSkip(configClass)) {
        String beanName = configClass.getBeanName();
        if (StringUtils.hasLength(beanName) && this.registry.containsBeanDefinition(beanName)) {
            this.registry.removeBeanDefinition(beanName);
        }
        this.importRegistry.removeImportingClass(configClass.getMetadata().getClassName());
        return;
    }

    // 1、如果當前配置類是通過內部類導入 或 @Import導入,將配置類自身註冊為beanDefinition
    if (configClass.isImported()) {
        registerBeanDefinitionForImportedConfigurationClass(configClass);
    }

    // 2、註冊配置類所有@Bean方法為beanDefinition
    for (BeanMethod beanMethod : configClass.getBeanMethods()) {
        loadBeanDefinitionsForBeanMethod(beanMethod);
    }

    // 3、註冊由@ImportedResources來的beanDefinition
    // 即通過其它類型Resource的BeanDefinitionReader讀取BeanDefinition並註冊
    loadBeanDefinitionsFromImportedResources(configClass.getImportedResources());

    // 4、註冊由ImportBeanDefinitionRegistrars來的beanDefinition
    loadBeanDefinitionsFromRegistrars(configClass.getImportBeanDefinitionRegistrars());
}

思維導圖

請放大觀看

參考

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※高價收購3C產品,價格不怕你比較

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

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

3c收購,鏡頭 收購有可能以全新價回收嗎?

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

[ch02-02] 非線性反向傳播

系列博客,原文在筆者所維護的github上:,
點擊star加星不要吝嗇,星越多筆者越努力。

2.2 非線性反向傳播

2.2.1 提出問題

在上面的線性例子中,我們可以發現,誤差一次性地傳遞給了初始值w和b,即,只經過一步,直接修改w和b的值,就能做到誤差校正。因為從它的計算圖看,無論中間計算過程有多麼複雜,它都是線性的,所以可以一次傳到底。缺點是這種線性的組合最多只能解決線性問題,不能解決更複雜的問題。這個我們在神經網絡基本原理中已經闡述過了,需要有激活函數連接兩個線性單元。

下面我們看一個非線性的例子,如圖2-8所示。

圖2-8 非線性的反向傳播

其中\(1<x<=10,0<y<2.15\)。假設有5個人分別代表x、a、b、c、y:

正向過程

  1. 第1個人,輸入層,隨機輸入第一個x值,x取值範圍(1,10],假設第一個數是2
  2. 第2個人,第一層網絡計算,接收第1個人傳入x的值,計算:\(a=x^2\)
  3. 第3個人,第二層網絡計算,接收第2個人傳入a的值,計算b:\(b=\ln (a)\)
  4. 第4個人,第三層網絡計算,接收第3個人傳入b的值,計算c:\(c=\sqrt{b}\)
  5. 第5個人,輸出層,接收第4個人傳入c的值

反向過程

  1. 第5個人,計算y與c的差值:\(\Delta c = c – y\),傳回給第4個人
  2. 第4個人,接收第5個人傳回\(\Delta c,計算\Delta b:\Delta b = \Delta c \cdot 2\sqrt{b}\)
  3. 第3個人,接收第4個人傳回\(\Delta b,計算\Delta a:\Delta a = \Delta b \cdot a\)
  4. 第2個人,接收第3個人傳回\(\Delta a,計算\Delta x:\Delta x = \Delta a / 2x\)
  5. 第1個人,接收第2個人傳回\(\Delta x,更新x:x = x – \Delta x\),回到第1步

提出問題:假設我們想最後得到c=2.13的值,x應該是多少?(誤差小於0.001即可)

2.2.2 數學解析解

\[c=\sqrt{b}=\sqrt{\ln(a)}=\sqrt{\ln(x^2)}=2.13\]
\[x = 9.6653\]

2.2.3 梯度迭代解

\[ \frac{da}{dx}=\frac{d(x^2)}{dx}=2x=\frac{\Delta a}{\Delta x} \tag{1} \]
\[ \frac{db}{da} =\frac{d(\ln{a})}{da} =\frac{1}{a} = \frac{\Delta b}{\Delta a} \tag{2} \]
\[ \frac{dc}{db}=\frac{d(\sqrt{b})}{db}=\frac{1}{2\sqrt{b}}=\frac{\Delta c}{\Delta b} \tag{3} \]
因此得到如下一組公式,可以把最後一層\(\Delta c\)的誤差一直反向傳播給最前面的\(\Delta x\),從而更新x值:
\[ \Delta c = c – y \tag{4} \]
\[ \Delta b = \Delta c \cdot 2\sqrt{b} \tag{根據式3} \]
\[ \Delta a = \Delta b \cdot a \tag{根據式2} \]
\[ \Delta x = \Delta a / 2x \tag{根據式1} \]

我們給定初始值\(x=2,\Delta x=0\),依次計算結果如表2-2。

表2-2 正向與反向的迭代計算

方向 公式 迭代1 迭代2 迭代3 迭代4 迭代5
正向 \(x=x-\Delta x\) 2 4.243 7.344 9.295 9.665
正向 \(a=x^2\) 4 18.005 53.934 86.404 93.233
正向 \(b=\ln(a)\) 1.386 2.891 3.988 4.459 4.535
正向 \(c=\sqrt{b}\) 1.177 1.700 1.997 2.112 2.129
標籤值y 2.13 2.13 2.13 2.13 2.13
反向 \(\Delta c = c – y\) -0.953 -0.430 -0.133 -0.018
反向 \(\Delta b = \Delta c \cdot 2\sqrt{b}\) -2.243 -1.462 -0.531 -0.078
反向 \(\Delta a = \Delta b \cdot a\) -8.973 -26.317 -28.662 -6.698
反向 \(\Delta x = \Delta a / 2x\) -2.243 -3.101 -1.951 -0.360

表2-2,先看“迭代-1”列,從上到下是一個完整的正向+反向的過程,最後一行是-2.243,回到“迭代-2”列的第一行,2-(-2.243)=4.243,然後繼續向下。到第5輪時,正向計算得到的c=2.129,非常接近2.13了,迭代結束。

運行示例代碼的話,可以得到如下結果:

how to play: 1) input x, 2) calculate c, 3) input target number but not faraway from c
input x as initial number(1.2,10), you can try 1.3:
2
c=1.177410
input y as target number(0.5,2), you can try 1.8:
2.13
forward...
x=2.000000,a=4.000000,b=1.386294,c=1.177410
backward...
delta_c=-0.952590, delta_b=-2.243178, delta_a=-8.972712, delta_x=-2.243178
......
forward...
x=9.655706,a=93.232666,b=4.535098,c=2.129577
backward...
done!

為節省篇幅只列出了第一步和最後一步(第5步)的結果,第一步時c=1.177410,最後一步時c=2.129577,停止迭代。

代碼位置

ch02, Level2

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

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

平板收購,iphone手機收購,二手筆電回收,二手iphone收購-全台皆可收購

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

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

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

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

PL真有意思(四):控制流

前言

對大多數計算模型而言,順序都是基本的東西,它確定了為完成所期望的某種工作,什麼事情應該最先做,什麼事應該隨後做,我們可以將語言規定順序的機制分為幾個類別:

  • 順序執行
  • 選擇
  • 迭代
  • 過程抽象
  • 遞歸
  • 併發
  • 異常處理和推斷
  • 非確定性

對於不同類別的語言對不同類別的控制流的重要性也不盡相同,比如順序執行相比於函數式對於命令式則更加重要。而命令式中更傾向用迭代,函數則更強調遞歸

表達式求值

在討論控制流之前先討論下錶達式的問題,先明確兩個概念:運算符通常是指那些採用特殊語法形式的內部函數(比如+-*/等),運算對象指的是運算符的參數(如2+3,2和3就是運算對象),那麼運算符和運算對象的組合就是表達式。一般根據運算符出現的位置(相對於運算對象而言),可以分為3類表示形式:前綴、中綴和後綴。比如Lisp就運用前綴語法:

(+ 1 3 4 6)      
(* (+ 1 7) 8)    

大多數命令式語言對二元運算符都使用中綴記法,而對一元運算符和其它函數使用前綴激發。但是像Lisp就全部統一使用中綴記法

優先級和結合性

大多數程序設計語言都提供豐富的內部算術。在用中綴方式(沒有括號)寫出就可能出現歧義。所以就需要優先級和結合性來解決歧義性,但是我覺得

媽的你寫括號就完事兒了

而且不同語言的優先級和結合性也不盡相同

賦值

在純函數式語言中,程序的基本組成部分是表達式,計算也僅是對表達式求值。任何一個表達式對於整個計算的影響也僅限於這個表達式所處的上下文環境。

而命令式語言的情況與此截然不同,計算通常是通過對內存中變量值的一系列修改操作來完成,賦值就是這種修改的最基本手段。每一次賦值都表示一個值被放入一個對應的變量中。

一般來說,如果語言中的一個結構除了返回一個值供其外圍環境所使用,還能以其他方式影響後續計算(並最終影響程序輸出),那麼我們就說這種結構有副作用。而副作用也是命令式語言里最核心的部分

而在純函數語言中沒有任何的副作用,表達式的值只依賴於輸入

但是現在許多語言都是混合的,像Python和Ruby主要是命令式的,但是也提供了很多的函數式的特徵,現在連Java都提供了對函數式的支持

引用和值

考慮一下下面的C語言的賦值:

d = a;
a = b + c;

第一個語句中,賦值語句右部引用了a的值,並希望把這個值放入d。第二個語句左部引用了a的位置,希望把b+c的結果放進去。這兩種解釋(值和位置)都是可行的,因為c語言中變量就是能保存值的命名容器,所以我們會說類似的語言的變量是值模型。由於指示位置的表達式被放在賦值語句的左部,所以這種指示位置的表達式成為左值表達式。表示一個值的表達式稱為右值。在變量的值模型下,同一表達式也可能是左值或者右值,比如(a=a+1),左部的a是左值,用於表示存放結果的位置;右部的a是右值,用於代表a具體所指的值。

在採用了變量的引用模型的語言中,這種左值和右值的差異就更加明顯了。

b = 2;
c = b;
a = b + c;

在值模型語言中程序員會說:“把2放入b,然後複製到c,然後用它們兩個的值相加,把結果4放入a。”。;

在引用模型語言中的程序員會說:“讓b引用2,讓c也引用2,然後把這兩個引用送給+運算,並讓a引用算出的結果,也是4“。

而在Java中,對於內部類型使用值模型,而類使用引用模型

裝箱

對於內部類型使用值模型,就無法以統一的方式將它們傳給要求類類型的參數的方法,所以這裏就需要一個裝箱過程

比如Java提供的Integer類

Integer i = new Integer(12);

多路賦值

我們知道賦值操作有右結合性,這使得我們可以寫出a=b=c的簡練代碼,在一些語言中(Ruby,Go,Python)我們可以進一步這樣寫:

a, b = 1, 2;
//上面的語句結果就是a等於1,b等於2。

a, b = b, a;
//交換兩個值,如果沒有這種語言特性,那麼就需要引入臨時變量了。

a, b , c = funx(d, e, f);

這種記法也消除了大多數程序設計語言中函數的非對稱性,這些語言可以允許任意多個參數,但只能返回一個返回值。但是其實在Python中的返回多個值,就是將多個值封裝為元組,在賦值的時候又拆箱而已

初始化

並不是所有語言都提供聲明變量時指定初始值的方式,但是至少有這幾點可以證明提供初始值的機制是有益的

  • 局部靜態變量需要一個初始值才能使用
  • 使用靜態分配的變量,可以由編譯器放入全局內存,避免了在運行時賦予吃數值所造成的開銷
  • 可以避免意外的使用未初始的變量

如果聲明時沒有明確的給定變量的初始值,語言也可以給定一個默認值。像C、Java和C#也都提供了類似的機制

動態檢查

除了可以指定默認值之外,還可以採用另外一種方式,將對為初始化的變量的使用作為動態語義錯誤,在運行時捕獲這種錯誤。但是在運行時捕獲所有使用到未初始化的情況的代價非常高

定義性賦值

在Java和C#中提供了一種定義性賦值的表示形式,意思就是由編譯器來檢查在達到一個表達式的所有可能控制路徑上,都必須為這個表達式中的每個變量賦過值

構造函數

許多面向對象語言都提供了為用戶定義的類型的自動初始化方法,也就是構造函數

在C++中,還區分了初始化和賦值,它將初始化賦值解釋為調用變量所屬類型的構造函數,以初始值作為調用參數。在沒有強制的情況下,賦值被解釋為調用相關類型的賦值運算符,如果沒有定義賦值運算符,就默認將賦值右部的值簡單的按位複製過來

區分初始化和賦值的好處是,可以區分在賦值前是不是需要先釋放空間

表達式的順序問題

雖然優先級和結合性規則定義了表達式里二元中綴運算符的應用順序,但卻沒有明確說明特定運算符的各運算對象的求值順序。舉例來說,如下錶達式:

 a - f(b) - c * d

根據結合性可知a-f(b)將在第二個減法前執行,根據優先級可知第二個減法的右運算對象是cd這個整體而不是c。但是如果沒有進一步的規則描述,我們無法得知a-f(b)是否在cd之前運行。諸如此類:對於f(a,g(b),c)這個子程序調用,我們也不知這三個參數的求值順序。

求值順序之所以重要:

  • 副作用:如果f(b)這個子程序可能會修改c的值,那麼a-f(b)-cd的求值結果將依賴f(b)和cd哪一個先執行;類似的,如果g(b)修改了a或者c的值,那麼f(a,g(b),c)的結果也是依賴於參數的求值順序。

  • 代碼改進:子表達式的求值順序對於寄存器分配和指令調度都有重要的影響。比如(ab+f(c)),我們可能會希望在執行ab之前調用f(c)。因為如果先計算乘法,則在調用f(c)之前就要先保存起來乘積,因為f(c)可能會用光所有的寄存器。

短路求值

對於布爾表達式,如果編譯器可以對其執行短路求值,那麼它生成的代碼可以在表達式前一半的結果可以確定整個表達式的值的情況下跳過後一半的計算。

比如(a<b) and(b<c),如果a>b,那麼完全沒必要去檢查b是否小於c就可以確定這個表達式一定為假。在一些特殊情況下,短路求值可節省大量時間,比如if(func&&func())。實際上這種情況下短路求值已經改變了布爾表達式的語義,如果非短路求值,那麼在func不存在的情況下去執行func(),程序是會拋出錯誤的。

我們常見的語法表現形式是&&和||這種布爾運算符身兼多職,既是布爾運算符又會觸發短路求值,但是有一些語言針對短路求值是有單獨的語法形式的,比如Clu語言中布爾運算符是and和or,短路運算符是cand和cor。這是為何呢,因為有些代碼邏輯是不需要這種短路求值的優化的。

結構化和非結構化的流程

彙編語言中的控制流通過有條件的或無條件的跳轉(分支)指令來完成,早期的高級語言模仿這種方式(如Fortran),主要依賴goto來描述大部分非過程化控制流,比如下面代碼:

if A < B goto label1;

label1;

但是如今goto像在Java、Clu和Eiffel里已經完全被禁止了,在其它語言也是受限了或者只是為了向前兼容而已

goto的結構化替代品

對於goto被廢棄,各種使用goto的地方也被結構的方案給代替了

  • 循環中的退出和繼續

break和contiune這兩個關鍵字大家應該很熟悉了

  • 從子程序提前返回

return

  • 多層返回

上面的兩個問題都可以有很好的替代品,但是對於多層返回就會比較麻煩一點。return或”局部的goto“只能在子程序中返回,如果遇到多層嵌套的子程序,想從內層的子程序返回來結束外圍子程序的執行,那return和局部的goto就無能為力了。這種情況下,語言實現要保證能恰當的恢復棧上的子程序調用信息,這種修復工作稱為”回卷”,為完成此事,不僅必須釋放需要跳出的所有子程序的棧幀,還要執行一些信息管理工作,比如恢復寄存器內容。

Common Lisp提供了return-from語句來明確指定需要退出的詞法外圍函數或嵌套塊,還可以提供一個返回值:

Common Lisp和另外一個語言Ruby中還內置一個throw/catch語法來支持這種多層返回,注意這種結構並不是所謂的異常處理,而是一種多層返回的語法結構,直白點說是一種功能強大的變相”goto“,看下面代碼:

//定義一個方法
def search_file(filename,pattern)
   file=File.Open(filename)
   //遍歷文件每一行
   file.each{|line|
        //根據parrern匹配模式查找,如果匹配就返回到定義found標籤的位置
        throw :found,line if line=~/#{pattern}/
   }
end

//用catch定義一個found標籤
math=catch:found do
   serach_file("f1",key) 
   serach_file("f2",key)    //如果f2文件找到了則就會返回line至math
   serach_file("f3",key)
   ”not fount“              //找不到就執行到此處了
end

print match
  • 錯誤和異常

多層返回的概念假定了被調用方知道調用方期的是什麼,並且能返回一個適當的值。還存在一種情況,其中深層嵌套的子程序中發生了一些情況,導致無法繼續執行下去,而且因為沒有足夠的環境信息,甚至無法合適的結束自己的工作,這種情況下,唯一能做的就是”退回去“,一直回退到能夠恢復執行的地方,這種要求程序退回去的條件通常稱為叫做”異常“。常見的結構化的異常處理和多層返回有很大的相似性,兩者都需要從某一個內層上下文回退到外層的上下文。具體的差異則是多層返回是內層的上下文正常的完成計算然後根據需要返回正確的值,然後轉移到外層上下文,並不需要後續處理。而異常中的內層上下文已經是無法進行正常的計算,必須以一種非正常的退出一直回卷,然後觸發某個特殊的處理流程直到catch到它。

  • 繼續

如果進一步推廣上一小節中造成棧回卷的非局部goto概念,則可以定義一種稱為繼續(Continuations)的概念。從底層來看,一個繼續是由一個代碼地址與其關聯的一個引用環境組成的,如果跳轉到這個地址,就該恢復這個引用環境。從抽象層面看,它描述一個可能由此繼續下去的執行上下文。在Scheme和Ruby中,繼續是基本的一等公民,我們可以利用這種機制有效的擴充流程控制結構集合。

Scheme中支持繼續由一個通常稱為call-with-current-continuation的函數實現,有時簡稱”call/cc”。該函數有一個參數f,f也是一個函數;”call/cc”調用函數f,把一個記錄著當前程序計數器和引用環境的“繼續(暫時稱為是c)c”傳遞給f,這種”繼續c”由一個閉包來表示(通過參數傳遞的子程序的表示的閉包並無不同)。在將來任何時候,f都可以調用c,然後可以用c來重新建立其保存的上下文。一般的應用情況是我們把這個c賦值給一個變量,則可重複的調用它,甚至我們可以在f中返回它,即使f已經執行完畢,仍然可以調用c。

順序執行

選擇

現在大部分命令式語言中採用的選擇語句,都是從Algol 60引進過的 if…then…else 的某種演進變形:

if condition then statement
else if condition then statement
else if condition then statement
...
else statement

短路條件

雖然 if…then…else 語句的條件是一個布爾表達式,但是通常沒有必要求出這個表達式的值放入寄存器。大部分機器都提供了條件分支指令(如上面提到的IL指令brtrue.s),因為這個表達式求值的目的並不是為了值,而是為了跳轉到合適的位置。這種看法使得可以對短路求值的表達式生成高效的代碼(稱為跳轉碼)。跳轉碼不但可以用於選擇語句,也可用在“邏輯控制的循環”中。如下面代碼:

if((A>B)&&(C<D)||(E!=F)){
    then_clause
}
else{
    else_clause
}

在不使用短路求值的Pascal中,生成的代碼大致如下(它會計算每個表達式的結果並放入寄存器r1…,然後再決定跳轉):

     r1=A
     r2=B
     r1=r1>r2
     r2=C
     r3=D
     r2=r2>r3
     r1=r1&r2
     r2=E
     r3=F
     r2=r2!=r3
     r1=r1|r2
     if r1=0 goto L2
L1: then_clause
    goto L3
L2: else_clause
L3:

跳轉碼的情況於此不同,它不會把表達式的值存入寄存器,而是直接跳轉(只用到了r1和r2兩個寄存器,明顯也不會針對整個表達式進行求值,比上面的要高效一些):

     r1=A
     r2=B
     if r1<=r2 goto L4
     r1=C
     r2=D
     if r1>r2 goto L1
L4: r1=E
     r2=F
     if r1=r2 goto L2
L1: then_clause
    goto L3
L2: else_clause
L3:

case/switch語句

對於if else結構來說,如果嵌套的層數過多、或者是用於判斷的條件表達式是基於一些有限的簡單值(或編譯時常量),那麼出現了一種更為優雅的語法結構“case語句”,有很多ifelse都可以很輕鬆的改寫成case/switch語句

對於case/switch的優勢還不只是語法上的優雅,有時還可以生成更高效的代碼

T: &L1
   &L2
   &L3
   &L4
   &L5
   &L6
L1: clause_A
    goto L7
L2: clause_B
    goto L7
L3: clause_C
    goto L7
L4: clause_D
    goto L7
L5: clause_E
    goto L7
L6: clause_F
    goto L7
L7:

這樣其實T就是一個地址跳轉表

迭代

迭代和遞歸是計算機能夠重複執行一些操作的兩種機制;命令式語言傾向於使用迭代、函數式語言則更看重遞歸。大多數語言中的迭代都是以循環的形式出現的,和複合語句中的語句一樣,迭代的執行通常也是為了副作用,也就是修改一些變量的值。根據用何種方式控制迭代的次數來看,循環有兩個主要變種”枚舉控制的循環”和“邏輯控制的循環”。前者是在給定的某個有限的集合中執行,後者則是不確定要執行多少次(直到它所依賴的表達式結果被改變)。對於這兩種結構,大多數的語言都提供了不同的語法結構來表示。

枚舉控制的循環

枚舉控制的循環最初來自Fortran的do循環,

do i = 1, 10, 2
  ...
enddo

等號後面的表達式分別是i的初始值,邊界值和步長

像這種枚舉循環可以說的不多,但是如果前幾次迭代的執行會導致迭代的次數或下標值的發生變化,那麼我們就需要一個更通用的實現

思考幾個問題:

  • 控制是否可以通過枚舉之外的任何方式進入和離開循環呢?
  • 如果循環體修改了用於計算循環結束邊界的變量,會發生什麼?
  • 如果循環體修改了下標變量,會發生?
  • 程序是否可以在循環結束後讀取下標變量,如果可以,它的值將是什麼?
  1. 現在的大多數語言都提供了,break類似的機制來離開循環。Fortran IV允許通過goto跳入到一個循環中,但是這個通常被認為是一個語言缺陷
  2. 同樣的,在大多數語言中,邊界值只在第一次計算,並且保存在一個臨時寄存器中,所以對於之後的修改並不會起作用
  3. 早期的大部分語言都禁止在枚舉控制的循環中修改下邊變量。但是剛剛試驗了一下,許多的語言好像都放開了這個禁止,也就是按照修改后的正常邏輯繼續執行
  4. 首先這是一個語言實現的問題,現在的大多數語言應該都是將循環下標的作用域限定在循環體內了,所以出了循環體是訪問不到的

當然在之後出現了C的for循環

for (int i = first; i < last; i += step) {
  ...
}

這樣有關結束條件、溢出和循環方向的問題全都交由程序員來掌控

迭代器

上面描述的循環都是在算術值的序列上迭代。不過一般而言,我們還希望可以在任何定義的良好的集合的元素上迭代。在C++和Java里叫做迭代器

真迭代器

Clu,Ruby等語言允許任何容器對象提供一個枚舉自己元素的迭代器,這種迭代器就像是允許包含yield語句的子程序,每次yield生成一個循環下標

在Python里就可以這樣寫

for i in range(first, last, step):
    ...

在被調用時,這個迭代器算出循環的第一個下標值,然後通過yield語句返回給調用者,yield語句很像return,但是不同的是再每次循環結束后控制權會再次的交給迭代器,重新開始下一次yield,直到迭代器沒有元素可yield為止才結束for循環。從效果上看迭代器就像是另外一個控制線程,有它自己的程序計數器,它的執行與為它提供下標值的for循環交替執行,這一類通常稱為真迭代器。

迭代器

在許多面向對象語言里,用了更加面向對象的方法來實現迭代器。它們的迭代器就是一個常規對象,它提供了一套方法,用來初始化、生成下一個下標值和檢測結束條件

BinTree<Integer> myTree;

for (Integer i : myTreee) {

}

上面的這段代碼其實是下面這段的一個語法糖

for(Iterator<Integer> it = myTree.iterator();it.hasNext();) {

}

用一級函數來實現迭代器

實現是將循環的體寫成一個函數,用循環的下標作為函數的參數,然後將這函數作為參數傳遞給一個迭代器

(define uptoby
    (lambda (low high step f)
        (if (<= low higt)
            (begin
                (f low)
                (uptoby (+ low step) high step f))
            '())))

不用迭代器的迭代

在那些沒有真迭代器或者迭代器對象的語言中,還是可以通過編程方式實現集合枚舉和使用元素之間的解耦的,用C語言做例子:

tree_node *my_tree;    
tree_iter ti:                 
...
for(ti_create(my_tree,&ti);
              !ti_done(ti);
              ti_next(&ti)){
     tree_node *n=ti_val(ti);
     ...
}
ti_delete(&ti);

邏輯控制的循環

和枚舉循環相比,邏輯控制的循環關注點只在結束條件上

前置檢測

由Algol W引進,後來被Pascal保留

while cond do stat

後置檢測

這種的循環體不管是否滿足循環條件,都至少會執行一次循環體。如C語言的do while語句

do{
   line=read_line();
   //...代碼
} while line[0]!='$'; 

中置檢測

中置檢測一般依賴if

for(;;){
   line=read_line();
   if line[0]!='$' break;
}

遞歸

遞歸和上述討論的其他控制流都不同,它不依賴特殊的語法形式,只要語言允許函數直接或間接的調用自身,那麼就是支持遞歸的。大部分情況下遞歸和迭代都可以互相用對方重寫的。

迭代和遞歸

早期的一些語言不支持遞歸(比如Fortan77以前的版本),也有一些函數式語言不允許迭代,然而大部分現代語言都是同時支持兩者的。在命令式語言中,迭代在某種意義上顯得更自然一些,因為它們的核心就是反覆修改一些變量;對於函數式語言,遞歸更自然一些,因為它們並不修改變量。如果是要計算gcd(更相減損法),遞歸更自然一些:

int gcd(int a,int b){
  if(a==b) return a;
  else if (a>b) return gcd(a-b,b);
  else return gcd(a,b-a);
}

用迭代則是這樣:

int gcd(int a,int b){
   while(a!=b){
      if(a>b) a=a-b;
      else  b=b-a;
   }
   return a;
}

尾遞歸

經常有人說迭代比遞歸效率更高,其實更準確的說法應該是,迭代的樸素實現的(無優化)效率通常比遞歸的樸素實現的效率要高。如上面gcd的例子,如果遞歸的實現確實是實實在在的子程序調用,那麼這種子程序調用所帶來的棧的分配等的開銷確實要比迭代要大。然而一個“優化”的編譯器(通常是專門為函數式語言設計的編譯器),常常能對遞歸函數生成優異的代碼,如上面的gcd尾遞歸(尾遞歸函數是指在遞歸調用之後再無其他計算的函數,其返回值就是遞歸調用的返回值)。對這種函數完全不必要進行動態的棧分配,編譯器在做遞歸調用時可以重複使用當前的棧空間,從效果上看,好的編譯器可以把上面遞歸的gcd函數改造為:

int gcd(int a,int b){
start:
   if (a==b) return a;
   else if (a>b){
     a=a-b;
     goto start;  
   }
   else{
     b=b-a;
     goto start;
  }
}

即使是那些非尾遞歸函數,通過簡單的轉換也可能產生出尾遞歸代碼。

應用序和正則序求值

在上述的討論中,我們都假定所有參數在傳入子程序之前已經完成了求值,但是實際中這並不是必須的。完全可以採用另外一種方式,把為求值的之際參數傳遞給子程序,僅在需要某個值得時候再去求它。前一種在調用前求值的方案稱為應用序求值;后一種到用時方求值的方式稱為正則序求值。正則序求值在宏這個概念中是自然而然的方式,前面討論的短路求值、以及後面要討論的按名調用參數也是應用的正則序求值,一些函數式語言中偶爾也會出現這種方式。

但是我們來看一個例子:

#define MAX(a,b) ((a)>(b)?(a):(b))

如果我這麼調用MAX(i++,j++),導致i和j都執行兩次++,產生了兩次副作用,這是我們不願意看到的結果。總結來說,只有在表達式求值不會產生副作用的情況下正則序才是安全的。

惰性求值

從清晰性和高效的角度看,應用序求值通常會比正則序合適一些,一次大部分語言都採用如此的方式。然而也確實有一些特殊情況下正則序更高效一些,而應用序會造成一些錯誤出現,這種情況的出現時因為一些參數的值實際上並不會被需要,但是還是被求值了,應用序求值有時也成為非惰性求值,比如下面的JavaScript代碼就會是一個死循環:

function while1() {
    while (true) { console.log('死循環')}
}
function NullFunction() { }
console.log(NullFunction(1,2,3,while1()));

Scheme通過內部函數delay和force提供可選的正則序求值功能,這兩個函數提供的實際上是惰性求值的一種實現

惰性求值最常見的一種用途就是用來創建無窮數據結構

(define naturals
    (letrec ((next (lambda (n) (cons n (delay (next (+ n 1)))))))
    (next 1)))

這樣就可以用Scheme表述所有的自然數

小結

本篇首先從表達式開始,介紹了表達式(語句)中的一些基本概念;然後從討論了從彙編時代到結構化程序設計時代語言中的控制流程的演進以及發展;有了前面兩個基礎,後面就詳細的介紹了程序中的三大基本流程控制結構順序、選擇、循環(遞歸和迭代)。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

收購3c,收購IPHONE,收購蘋果電腦-詳細收購流程一覽表

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

※想要讓你的商品成為最夯、最多人討論的話題?網頁設計公司讓你強力曝光

※高價收購3C產品,價格不怕你比較

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

【決戰西二旗】|你真的懂快速排序?

本文首發於:

微信公眾號:後端技術指南針

持續乾貨 歡迎關注!

看似青銅實則王者

很多人提起快排和二分都覺得很容易的樣子,但是讓現場Code很多就翻車了,就算可以寫出個遞歸版本的代碼,但是對其中的複雜度分析、邊界條件的考慮、非遞歸改造、代碼優化等就無從下手,填鴨背誦基本上分分鐘就被面試官擺平了。

 

那年初識快速排序

快速排序Quicksort又稱劃分交換排序partition-exchange sort,簡稱快排,一種排序算法。最早由東尼·霍爾(C. A. R. Hoare)教授在1960年左右提出,在平均狀況下,排序n個項目要O(nlogn)次比較。

在最壞狀況下則需要O(n^2)次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他算法更快,因為它的內部循環可以在大部分的架構上很有效率地達成。

快速排序的核心思想

在計算機科學中,分治法(Divide&Conquer)是建基於多項分支遞歸的一種很重要的算法範式,快速排序是分治思想在排序問題上的典型應用。

所謂分治思想D&C就是把一個較大規模的問題拆分為若干小規模且相似的問題。再對小規模問題進行求解,最終合併所有小問題的解,從而形成原來大規模問題的解。

字面上的解釋是”分而治之”,這個技巧是很多高效算法的基礎,如排序算法(歸併排序、快速排序)、傅立恭弘=叶 恭弘變換(快速傅立恭弘=叶 恭弘變換)。

分治法中最重要的部分是循環遞歸的過程,每一層遞歸有三個具體步驟:

  • 分解:將原問題分解為若干個規模較小,相對獨立,與原問題形式相同的子問題。
  • 解決:若子問題規模較小且易於解決時,則直接解。否則,遞歸地解決各子問題。
  • 合併:將各子問題的解合併為原問題的解。

快速排序的發明者

查爾斯·安東尼·理查德·霍爾爵士(Sir Charles Antony Richard Hoare縮寫為C. A. R. Hoare,1934年1月11日-),昵稱為東尼·霍爾(Tony Hoare),生於大英帝國錫蘭可倫坡(今斯里蘭卡),英國計算機科學家,圖靈獎得主。

他設計了快速排序算法、霍爾邏輯、交談循序程式。在操作系統中,他提出哲學家就餐問題,併發明用來作為同步程序的監視器(Monitors)以解決這個問題。他同時證明了監視器與信號標(Semaphore)在邏輯上是等價的。

1980年獲頒圖靈獎、1982年成為英國皇家學會院士、2000年因為他在計算機科學與教育方面的傑出貢獻,獲得英國王室頒贈爵士頭銜、2011年獲頒約翰·馮諾依曼獎,現為牛津大學榮譽教授,並在劍橋微軟研究院擔任研究員。

快速排序的基本過程

快速排序使用分治法來把一個序列分為小於基準值和大於基準值的兩個子序列。

遞歸地排序兩個子序列,直至最小的子序列長度為0或者1,整個遞歸過程結束,詳細步驟為:

  • 挑選基準值: 從數列中挑出一個元素稱為基準pivot,選取基準值有數種具體方法,此選取方法對排序的時間性能有決定性影響。
  • 基準值分割: 重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面,與基準值相等的數可以到任何一邊,在這個分割結束之後,對基準值的排序就已經完成。
  • 遞歸子序列: 遞歸地將小於基準值元素的子序列和大於基準值元素的子序列排序,步驟同上兩步驟,遞歸終止條件是序列大小是0或1,因為此時該數列顯然已經有序。

快速排序的遞歸實現

    • 版本一 C實現
#include<stdio.h>

int a[9]={5,1,9,6,7,11,3,8,4};

void exchange(int *p,int *q){
    int temp=*p;
    *p=*q;
    *q=temp;
}

int quicksort(int left,int right){
    if(left>=right){
        return 0;
    }

    int i,j,temp;
    temp=a[left];
    i=left;
    j=right;

    while(i!=j){
        while(i<j&&a[j]>=temp){
            j--;
        }
        exchange(&a[i],&a[j]); 
        while(i<j&&a[i]<=temp){
            i++; 
        }
        exchange(&a[i],&a[j]);
    }
    quicksort(i+1,right);
    quicksort(left,i-1); 
}

int main(){
    quicksort(0,8);
    for(int i=0;i<=8;i++){
        printf("%d ",a[i]);
    }
}
    • 版本二 C++實現
 1 #include<iostream>
 2 using namespace std;
 3 
 4 template <typename T>
 5 void quick_sort_recursive(T arr[], int start, int end) {
 6     if (start >= end)
 7         return;
 8     T mid = arr[end];
 9     int left = start, right = end - 1;
10     //整個範圍內搜尋比樞紐值小或大的元素,然後左側元素與右側元素交換
11     while (left < right) {
12             //試圖在左側找到一個比樞紐元更大的元素
13         while (arr[left] < mid && left < right)
14             left++;
15                 //試圖在右側找到一個比樞紐元更小的元素
16         while (arr[right] >= mid && left < right)
17             right--;
18                 //交換元素
19         std::swap(arr[left], arr[right]);
20     }
21         //這一步很關鍵
22     if (arr[left] >= arr[end])
23         std::swap(arr[left], arr[end]);
24     else
25         left++;
26     quick_sort_recursive(arr, start, left - 1);
27     quick_sort_recursive(arr, left + 1, end);
28 }
29 
30 //模板化
31 template <typename T> 
32 void quick_sort(T arr[], int len) {
33     quick_sort_recursive(arr, 0, len - 1);
34 }
35 
36 int main()
37 {
38     int a[9]={5,1,9,6,7,11,3,8,4};
39     int len = sizeof(a)/sizeof(int);
40     quick_sort(a,len-1);
41     for(int i=0;i<len-1;i++)
42         cout<<a[i]<<endl;
43 }

兩個版本均可正確運行,但代碼有一點差異:

  • 版本一 使用雙指針交替從左(右)兩邊分別開始尋找大於基準值(小於基準值),然後與基準值交換,直到最後左右指針相遇。
  • 版本二 使用雙指針向中間集合,左指針遇到大於基準值時則停止,等待右指針,右指針遇到小於基準值時則停止,與左指針指向的元素交換,最後基準值放到合適位置。

過程說起來比較抽象,穩住別慌!靈魂畫手大白會畫圖來演示這兩個過程。

快速排序的遞歸演示

  • 版本一遞歸代碼的排序過程示意圖:

第一次遞歸循環為例:

步驟1: 選擇第一個元素為基準值pivot=a[left]=5,right指針指向尾部元素,此時先由right自右向左掃描直至遇到<5的元素,恰好right起步元素4<5,因此需要將4與5互換位置;

步驟2: 4與5互換位置之後,輪到left指針從左向右掃描,注意一下left的起步指針指向了由步驟1交換而來的4,新元素4不滿足停止條件,因此left由綠色虛箭頭4位置遊走到元素9的位置,此時left找到9>5,因此將此時left和right指向的元素互換,也就是元素5和元素9互換位置;

步驟3: 互換之後right指針繼續向左掃描,從藍色虛箭頭9位置遊走到3的位置,此時right發現3<5,因此將此時left和right指向的元素互換,也就是元素3和元素5互換位置;

步驟4: 互換之後left指針繼續向右掃描,從綠色虛箭頭3位置遊走到6的位置,此時left發現6>5,因此將此時left和right指向的元素互換,也就是元素6和元素5互換位置;

步驟5: 互換之後right指針繼續向左掃描,從藍色虛箭頭6位置一直遊走到與left指針相遇,此時二者均停留在了pivot=5的新位置上,且左右兩邊分成了兩個相對於pivot值的子序列;

循環結束:至此出現了以5為基準值的左右子序列,接下來就是對兩個子序列實施同樣的遞歸步驟。

第二次和第三次左子序列遞歸循環為例:

步驟1-1:選擇第一個元素為基準值pivot=a[left]=4,right指針指向尾部元素,此時先由right指針向左掃描,恰好起步元素3<4,因此將3和4互換;

步驟1-2:互換之後left指針從元素3開始向右掃描,一直遊走到與right指針相遇,此時本次循環停止,特別注意這種情況下可以看到基準值4隻有左子序列,無右子序列,這種情況是一種退化,就像冒泡排序每次循環都將基準值放置到最後,因此效率將退化為冒泡的O(n^2);

步驟1-3:選擇第一個元素為基準值pivot=a[left]=3,right指針指向尾部元素,此時先由right指針向左掃描,恰好起步元素1<3,因此將1和3互換;

步驟1-4:互換之後left指針從1開始向右掃描直到與right指針相遇,此時注意到pivot=3無右子序列且左子序列len=1,達到了遞歸循環的終止條件,此時可以認為由第一次循環產生的左子序列已經全部有序。

循環結束:至此左子序列已經排序完成,接下來對右子序列實施同樣的遞歸步驟,就不再演示了,聰明的你一定get到了。

特別注意:

以上過程中left和right指針在某個元素相遇,這種情況在代碼中是不會出現的,因為外層限制了i!=j,圖中之所以放到一起是為了直觀表達終止條件。

  • 版本二C++版本動畫演示:

 

分析一下:

個人覺得這個版本雖然同樣使用D&C思想但是更加簡潔,從動畫可以看到選擇pivot=a[end],然後左右指針分別從index=0和index=end-1向中間靠攏。

過程中掃描目標值並左右交換,再繼續向中間靠攏,直到相遇,此時再根據a[left]和a[right]以及pivot的值來進行合理置換,最終實現基於pivot的左右子序列形式。

腦補場景:

上述過程讓我覺得很像統帥命令左右兩路軍隊從兩翼會和,並且在會和過程中消滅敵人有生力量(認為是交換元素),直到兩路大軍會師。

此時再將統帥王座擺到正確的位置,此過程中沒有統帥王座的反覆變換,只有最終會師的位置,以王座位中心形成了左翼子序列和右翼子序列。

再重複相同的過程,直至完成大一統。

腦補不過癮 於是湊圖一張:

快速排序的多種版本

吃瓜時間:

印象中2017年初換工作的時候去CBD一家公司面試手寫快排,我就使用C++模板化的版本二實現的,但是面試官質疑說這不是快排,爭辯之下讓我們彼此都覺得對方很Low,於是很快就把我送出門SayGoodBye了^_^。

我想表達的意思是,雖然快排的遞歸版本是基於D&C實現的,但是由於pivot值的選擇不同、交換方式不同等諸多因素,造成了多種版本的遞歸代碼。

並且內層while循環裏面判斷>=還是>(即是否等於的問題),外層循環判斷本序列循環終止條件等寫法都會不同,因此在寫快排時切忌死記硬背,要不然邊界條件判斷不清楚很容易就死循環了。

看下上述我貼的兩個版本的代碼核心部分:

//版本一寫法
while(i!=j){
    while(i<j&&a[j]>=temp){
        j--;
    }
    exchange(&a[i],&a[j]); 
    while(i<j&&a[i]<=temp){
        i++; 
    }
    exchange(&a[i],&a[j]);
}

//版本二寫法
while (left < right) {
    while (arr[left] < mid && left < right)
        left++;
    while (arr[right] >= mid && left < right)
        right--;
    std::swap(arr[left], arr[right]);
}

覆蓋or交換:

代碼中首先將pivot的值引入局部變量保存下來,這樣就認為A[L]這個位置是個坑,可以被其他元素覆蓋,最終再將pivot的值填到最後的坑裡。

這種做法也沒有問題,因為你只要畫圖就可以看到,每次坑的位置是有相同元素的位置,也就是被備份了的元素。

個人感覺 與其叫坑不如叫備份,但是如果你代碼使用的是基於指針或者引用的swap,那麼就沒有坑的概念了。

這就是覆蓋和交換的區別,本文的例子都是swap實現的,因此沒有坑位被最後覆蓋一次的過程。

快速排序的迭代實現

所謂迭代實現就是非遞歸實現一般使用循環來實現,我們都知道遞歸的實現主要是藉助系統內的棧來實現的。

如果調用層級過深需要保存的臨時結果和關係會非常多,進而造成StackOverflow棧溢出。

Stack一般是系統分配空間有限內存連續速度很快,每個系統架構默認的棧大小不一樣,筆者在x86-CentOS7.x版本使用ulimit -s查看是8192Byte。

避免棧溢出的一種辦法是使用循環,以下為筆者驗證的使用STL的stack來實現的循環版本,代碼如下:

#include <stack>
#include <iostream>
using namespace std;

template<typename T>
void qsort(T lst[], int length) {
    std::stack<std::pair<int, int> > mystack;
    //將數組的首尾下標存儲 相當於第一輪循環
    mystack.push(make_pair(0, length - 1));

    while (!mystack.empty()) {
        //使用棧頂元素而後彈出
        std::pair<int,int> top = mystack.top();
        mystack.pop();

        //獲取當前需要處理的子序列的左右下標
        int i = top.first;
        int j = top.second;

        //選取基準值
        T pivot = lst[i];

        //使用覆蓋填坑法 而不是交換哦
        while (i < j) {
            while (i < j and lst[j] >= pivot) j--;
            lst[i] = lst[j];
            while (i < j and lst[i] <= pivot) i++;
            lst[j] = lst[i];
        }
        //注意這個基準值回填過程
        lst[i] = pivot;

        //向下一個子序列進發
        if (i > top.first) mystack.push(make_pair(top.first, i - 1));
        if (j < top.second) mystack.push(make_pair(j + 1, top.second));
    }
}

int main()
{
    int a[9]={5,1,9,6,7,11,3,8,4};
    int len = sizeof(a)/sizeof(int);
    qsort(a,len);
    for(int i=0;i<len-1;i++)
        cout<<a[i]<<endl;
}

下期精彩

由於篇幅原因,目前文章已經近6000字,因此筆者決定將快排算法的優化放到另外一篇文章中,不過可以提前預告一下會有哪些內容:

  • 基準值選擇對性能的影響
  • 基準值選擇的多種策略
  • 尾遞歸的概念原理和優勢
  • 基於尾遞歸實現快速排序
  • STL中sort函數的底層實現
  • glibc中快速排序的實現

參考資料

 

   本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

結合RBAC模型講解權限管理系統需求及表結構創建

在本號之前的文章中,已經為大家介紹了很多關於Spring Security的使用方法,也介紹了RBAC的基於角色權限控制模型。但是很多朋友雖然已經理解了RBAC控制模型,但是仍有很多的問題阻礙他們進一步開發。比如:

  • RBAC模型的表結構該如何創建?
  • 具體到某個頁面,某個按鈕權限是如何控制的?
  • 為了配合登錄驗證表,用戶表中應該包含哪些核心字段?
  • 這些字段與登錄驗證或權限分配的需求有什麼關係?

那麼本文就希望將這些問題,與大家進行一下分享。

一、回顧RBAC權限模型

  • 用戶與角色之間是多對多的關係,一個用戶有多個角色,一個角色包含多個用戶
  • 角色與權限之間是多對多關係,一個角色有多種權限,一個權限可以屬於多個角色

上圖中:

  • User是用戶表,存儲用戶基本信息
  • Role是角色表,存儲角色相關信息
  • Menu(菜單)是權限表,存儲系統包含哪些菜單及其屬性
  • UserRole是用戶和角色的關係表
  • RoleMenu是角色和權限的關係表

本文講解只將權限控制到菜單的訪問級別,即控制頁面的訪問權限。如果想控制到頁面中按鈕級別的訪問,可以參考Menu與RoleMenu的模式同樣的實現方式。或者乾脆在menu表裡面加上一個字段區別該條記錄是菜單項還是按鈕。

為了有理有據,我們參考一個比較優秀的開源項目:若依後台管理系統。

二、組織部門管理

2.1.需求分析

之所以先將部門管理提出來講一下,是因為部門管理沒有在我們上面的RBAC權限模型中進行提現。但是部門這樣一個實體仍然是,後端管理系統的一個重要組成部分。通常有如下的需求:

  • 部門要能體現出上下級的結構(如上圖中的紅框)。在關係型數據庫中。這就需要使用到部門id及上級部門id,來組合成一個樹形結構。這個知識是SQL學習中必備的知識,如果您還不知道,請自行學習。
  • 如果組織與用戶之間是一對多的關係,就在用戶表中加上一個org_id標識用戶所屬的組織。原則是:實體關係在多的那一邊維護。比如:是讓老師記住自己的學生容易,還是讓學生記住自己的老師更容易?
  • 如果組織與用戶是多對多關係,這種情況現實需求也有可能存在。比如:某人在某單位既是生產部長,又是技術部長。所以他及歸屬於技術部。也歸屬於生產部。對於這種情況有兩種解決方案,把該人員放到公司級別,而不是放到部門級別。另外一種就是從數據庫結構上創建User與Org組織之間的多對多關係。
  • 組織信息包含一些基本信息,如組織名稱、組織狀態、展現排序、創建時間
  • 另外,要有基本的組織的增刪改查功能

2.2 組織部門表的CreateSQL

以下SQL以MySQL為例:

CREATE TABLE `sys_org` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `org_pid` INT(11) NOT NULL COMMENT '上級組織編碼',
    `org_pids` VARCHAR(64) NOT NULL COMMENT '所有的父節點id',
    `is_leaf` TINYINT(4) NOT NULL COMMENT '0:不是恭弘=叶 恭弘子節點,1:是恭弘=叶 恭弘子節點',
    `org_name` VARCHAR(32) NOT NULL COMMENT '組織名',
    `address` VARCHAR(64) NULL DEFAULT NULL COMMENT '地址',
    `phone` VARCHAR(13) NULL DEFAULT NULL COMMENT '電話',
    `email` VARCHAR(32) NULL DEFAULT NULL COMMENT '郵件',
    `sort` TINYINT(4) NULL DEFAULT NULL COMMENT '排序',
    `level` TINYINT(4) NOT NULL COMMENT '組織層級',
    `status` TINYINT(4) NOT NULL COMMENT '0:啟用,1:禁用',
    PRIMARY KEY (`id`)
)
COMMENT='系統組織結構表'
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;

注意:mysql沒有oracle中的start with connect by的樹形數據匯總SQL。所以通常需要為了方便管理組織之間的上下級樹形關係,需要加上一些特殊字段,如:org_pids:該組織所有上級組織id逗號分隔,即包括上級的上級;is_leaf是否是恭弘=叶 恭弘子結點;level組織所屬的層級(1,2,3)。

三、菜單權限管理

3.1 需求分析

  • 由上圖可以看出,菜單仍然是樹形結構,所以數據庫表必須有id與menu_pid字段
  • 必要字段:菜單跳轉的url、是否啟用、菜單排序、菜單的icon矢量圖標等
  • 最重要的是菜單要有一個權限標誌,具有唯一性。通常可以使用菜單跳轉的url路徑作為權限標誌。此標誌作為權限管理框架識別用戶是否具有某個頁面查看權限的重要標誌
  • 需要具備菜單的增刪改查基本功能
  • 如果希望將菜單權限和按鈕超鏈接相關權限放到同一個表裡面,可以新增一個字段。用戶標誌該權限記錄是菜單訪問權限還是按鈕訪問權限。

3.2 菜單權限表的CreateSQL

CREATE TABLE `sys_menu` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `menu_pid` INT(11) NOT NULL COMMENT '父菜單ID',
    `menu_pids` VARCHAR(64) NOT NULL COMMENT '當前菜單所有父菜單',
    `is_leaf` TINYINT(4) NOT NULL COMMENT '0:不是恭弘=叶 恭弘子節點,1:是恭弘=叶 恭弘子節點',
    `name` VARCHAR(16) NOT NULL COMMENT '菜單名稱',
    `url` VARCHAR(64) NOT NULL COMMENT '跳轉URL',
    `icon` VARCHAR(45) NULL DEFAULT NULL,
    `icon_color` VARCHAR(16) NULL DEFAULT NULL,
    `sort` TINYINT(4) NULL DEFAULT NULL COMMENT '排序',
    `level` TINYINT(4) NOT NULL COMMENT '菜單層級',
    `status` TINYINT(4) NOT NULL COMMENT '0:啟用,1:禁用',
    PRIMARY KEY (`id`)
)
COMMENT='系統菜單表'
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;

四、角色管理

上圖為角色修改及分配權限的頁面

4.1.需求分析

  • 角色本身的管理需要注意的點非常少,就是簡單的增刪改查。重點在於角色分配該如何做。
  • 角色表包含角色id,角色名稱,備註、排序順序這些基本信息就足夠了
  • 為角色分配權限:以角色為基礎勾選菜單權限或者操作權限,然後先刪除sys_role_menu表內該角色的所有記錄,在將新勾選的權限數據逐條插入sys_role_menu表。
  • sys_role_menu的結構很簡單,記錄role_id與menu_id,一個角色擁有某一個權限就是一條記錄。
  • 角色要有一個全局唯一的標識,因為角色本身也是一種權限。可以通過判斷角色來判斷某用戶的操作是否合法。
  • 通常的需求:不會在角色管理界面為角色添加用戶,而是在用戶管理界面為用戶分配角色。

4.2.角色表與角色菜單權限關聯表的的CreateSQL

CREATE TABLE `sys_role` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `role_id` VARCHAR(16) NOT NULL COMMENT '角色ID',
    `role_name` VARCHAR(16) NOT NULL COMMENT '角色名',
    `role_flag` VARCHAR(64) NULL DEFAULT NULL COMMENT '角色標識',
    `sort` INT(11) NULL DEFAULT NULL COMMENT '排序',
    PRIMARY KEY (`id`)
)
COMMENT='系統角色表'
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;
CREATE TABLE `sys_role_menu` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `role_id` VARCHAR(16) NOT NULL COMMENT '角色ID',
    `menu_id` INT(11) NOT NULL COMMENT '菜單ID',
    PRIMARY KEY (`id`)
)
COMMENT='角色菜單多對多關聯表'
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;

五、用戶管理

5.1.需求分析

  • 上圖中點擊左側的組織菜單樹結點,要能显示出該組織下的所有人員(系統用戶)。在組織與用戶是一對多的關係中,需要在用戶表加上org_id字段,用於查詢某個組織下的所有用戶。
  • 用戶表中要保存用戶的用戶名、加密后的密碼。頁面提供密碼修改或重置的功能。
  • 角色分配:實際上為用戶分配角色,與為角色分配權限的設計原則是一樣的。所以可以參考。
  • 實現用戶基本信息的增刪改查功能

5.2.sys_user 用戶信息表及用戶角色關係表的CreateSQL

CREATE TABLE `sys_user` (
        `id` INT(11) NOT NULL AUTO_INCREMENT,
        `org_id` INT(11) NOT NULL,
        `username` VARCHAR(64) NULL DEFAULT NULL COMMENT '用戶名',
        `password` VARCHAR(64) NULL DEFAULT NULL COMMENT '密碼',
        `enabled` INT(11) NULL DEFAULT '1' COMMENT '用戶賬戶是否可用',
        `locked` INT(11) NULL DEFAULT '0' COMMENT '用戶賬戶是否被鎖定',
        `lockrelease_time` TIMESTAMP NULL  '用戶賬戶鎖定到期時間',
        `expired_time` TIMESTAMP NULL  '用戶賬戶過期時間',
        `create_time` TIMESTAMP NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '用戶賬戶創建時間',
    PRIMARY KEY (`id`)
)
COMMENT='用戶信息表'
ENGINE=InnoDB
;
CREATE TABLE `sys_user_role` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `role_id` VARCHAR(16) NULL DEFAULT NULL,
    `user_id` VARCHAR(18) NULL DEFAULT NULL,
    PRIMARY KEY (`id`)
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;

在用戶的信息表中,體現了一些隱藏的需求。如:多次登錄鎖定與鎖定到期時間的關係。賬號有效期的設定規則等。

當然用戶表中,根據業務的不同還可能加更多的信息,比如:用戶頭像等等。但是通常在比較大型的業務系統開發中,業務模塊中使用的用戶表和在權限管理模塊使用的用戶表通常不是一個,而是根據某些唯一字段弱關聯,分開存放。這樣做的好處在於:經常發生變化的業務需求,不會去影響不經常變化的權限模型。

期待您的關注

  • 向您推薦博主的系列文檔:
  • 本文轉載註明出處(必須帶連接,不能只轉文字):。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

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

平板收購,iphone手機收購,二手筆電回收,二手iphone收購-全台皆可收購

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

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

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

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