月份: 2021 年 1 月

  • 重學 Java 設計模式:實戰裝飾器模式(SSO單點登錄功能擴展,增加攔截用戶訪問方法範圍場景)

    重學 Java 設計模式:實戰裝飾器模式(SSO單點登錄功能擴展,增加攔截用戶訪問方法範圍場景)

    作者:小傅哥
    博客:https://bugstack.cn

    沉澱、分享、成長,讓自己和他人都能有所收穫!

    一、前言

    對於代碼你有編程感覺嗎

    很多人寫代碼往往是沒有編程感覺的,也就是除了可以把功能按照固定的流程編寫出流水式的代碼外,很難去思考整套功能服務的擴展性和可維護性。尤其是在一些較大型的功能搭建上,比較缺失一些駕馭能力,從而導致最終的代碼相對來說不能做到盡善盡美。

    江洋大盜與江洋大偷

    兩個本想描述一樣的意思的詞,只因一字只差就讓人覺得一個是好牛,一個好搞笑。往往我們去開發編程寫代碼時也經常將一些不恰當的用法用於業務需求實現中,當卻不能意識到。一方面是由於編碼不多缺少較大型項目的實踐,另一方面是不思進取的總在以完成需求為目標缺少精益求精的工匠精神。

    書從來不是看的而是用的

    在這個學習資料幾乎爆炸的時代,甚至你可以輕易就獲取幾個T的視頻,小手輕輕一點就收藏一堆文章,但卻很少去看。學習的過程從不只是簡單的看一遍就可以,對於一些實操性的技術書籍,如果真的希望學習到知識,那麼一定是把這本書用起來而絕對不是看起來。

    二、開發環境

    1. JDK 1.8
    2. Idea + Maven
    3. 涉及工程三個,可以通過關注公眾號bugstack蟲洞棧,回復源碼下載獲取(打開獲取的鏈接,找到序號18)
    工程 描述
    itstack-demo-design-9-00 場景模擬工程;模擬單點登錄類
    itstack-demo-design-9-01 使用一坨代碼實現業務需求
    itstack-demo-design-9-02 通過設計模式優化改造代碼,產生對比性從而學習

    三、裝飾器模式介紹

    初看上圖感覺裝飾器模式有點像俄羅斯套娃、某眾汽車,而裝飾器的核心就是再不改原有類的基礎上給類新增功能。不改變原有類,可能有的小夥伴會想到繼承、AOP切面,當然這些方式都可以實現,但是使用裝飾器模式會是另外一種思路更為靈活,可以避免繼承導致的子類過多,也可以避免AOP帶來的複雜性。

    你熟悉的場景很多用到裝飾器模式

    new BufferedReader(new FileReader(""));,這段代碼你是否熟悉,相信學習java開發到字節流、字符流、文件流的內容時都見到了這樣的代碼,一層嵌套一層,一層嵌套一層,字節流轉字符流等等,而這樣方式的使用就是裝飾器模式的一種體現。

    四、案例場景模擬

    在本案例中我們模擬一個單點登錄功能擴充的場景

    一般在業務開發的初期,往往內部的ERP使用只需要判斷賬戶驗證即可,驗證通過後即可訪問ERP的所有資源。但隨着業務的不斷髮展,團隊里開始出現專門的運營人員、營銷人員、數據人員,每個人員對於ERP的使用需求不同,有些需要創建活動,有些只是查看數據。同時為了保證數據的安全性,不會讓每個用戶都有最高的權限。

    那麼以往使用的SSO是一個組件化通用的服務,不能在裏面添加需要的用戶訪問驗證功能。這個時候我們就可以使用裝飾器模式,擴充原有的單點登錄服務。但同時也保證原有功能不受破壞,可以繼續使用。

    1. 場景模擬工程

    itstack-demo-design-9-00
    └── src
        └── main
            └── java
                └── org.itstack.demo.design
                    ├── HandlerInterceptor.java
                    └── SsoInterceptor.java
    
    • 這裏模擬的是spring中的類:HandlerInterceptor,實現起接口功能SsoInterceptor模擬的單點登錄攔截服務。
    • 為了避免引入太多spring的內容影響對設計模式的閱讀,這裏使用了同名的類和方法,盡可能減少外部的依賴。

    2. 場景簡述

    2.1 模擬Spring的HandlerInterceptor

    public interface HandlerInterceptor {
    
        boolean preHandle(String request, String response, Object handler);
    
    }
    
    • 實際的單點登錄開發會基於;org.springframework.web.servlet.HandlerInterceptor 實現。

    2.2 模擬單點登錄功能

    public class SsoInterceptor implements HandlerInterceptor{
    
        public boolean preHandle(String request, String response, Object handler) {
            // 模擬獲取cookie
            String ticket = request.substring(1, 8);
            // 模擬校驗
            return ticket.equals("success");
        }
    
    }
    
    • 這裏的模擬實現非常簡單隻是截取字符串,實際使用需要從HttpServletRequest request對象中獲取cookie信息,解析ticket值做校驗。
    • 在返回的裏面也非常簡單,只要獲取到了success就認為是允許登錄。

    五、用一坨坨代碼實現

    此場景大多數實現的方式都會採用繼承類

    繼承類的實現方式也是一個比較通用的方式,通過繼承后重寫方法,併發將自己的邏輯覆蓋進去。如果是一些簡單的場景且不需要不斷維護和擴展的,此類實現並不會有什麼,也不會導致子類過多。

    1. 工程結構

    itstack-demo-design-9-01
    └── src
        └── main
            └── java
                └── org.itstack.demo.design
                    └── LoginSsoDecorator.java
    
    • 以上工程結構非常簡單,只是通過 LoginSsoDecorator 繼承 SsoInterceptor,重寫方法功能。

    2. 代碼實現

    public class LoginSsoDecorator extends SsoInterceptor {
    
        private static Map<String, String> authMap = new ConcurrentHashMap<String, String>();
    
        static {
            authMap.put("huahua", "queryUserInfo");
            authMap.put("doudou", "queryUserInfo");
        }
    
        @Override
        public boolean preHandle(String request, String response, Object handler) {
            // 模擬獲取cookie
            String ticket = request.substring(1, 8);
            // 模擬校驗
            boolean success = ticket.equals("success");
    
            if (!success) return false;
    
            String userId = request.substring(9);
            String method = authMap.get(userId);
    
            // 模擬方法校驗
            return "queryUserInfo".equals(method);
        }
    
    }
    
    • 以上這部分通過繼承重寫方法,將個人可訪問哪些方法的功能添加到方法中。
    • 以上看着代碼還算比較清晰,但如果是比較複雜的業務流程代碼,就會很混亂。

    3. 測試驗證

    3.1 編寫測試類

    @Test
    public void test_LoginSsoDecorator() {
        LoginSsoDecorator ssoDecorator = new LoginSsoDecorator();
        String request = "1successhuahua";
        boolean success = ssoDecorator.preHandle(request, "ewcdqwt40liuiu", "t");
        System.out.println("登錄校驗:" + request + (success ? " 放行" : " 攔截"));
    }
    
    • 這裏模擬的相當於登錄過程中的校驗操作,判斷用戶是否可登錄以及是否可訪問方法。

    3.2 測試結果

    登錄校驗:1successhuahua 攔截
    
    Process finished with exit code 0
    
    • 從測試結果來看滿足我們的預期,已經做了攔截。如果你在學習的過程中,可以嘗試模擬單點登錄並繼承擴展功能。

    六、裝飾器模式重構代碼

    接下來使用裝飾器模式來進行代碼優化,也算是一次很小的重構。

    裝飾器主要解決的是直接繼承下因功能的不斷橫向擴展導致子類膨脹的問題,而是用裝飾器模式后就會比直接繼承顯得更加靈活同時這樣也就不再需要考慮子類的維護。

    在裝飾器模式中有四個比較重要點抽象出來的點;

    1. 抽象構件角色(Component) – 定義抽象接口
    2. 具體構件角色(ConcreteComponent) – 實現抽象接口,可以是一組
    3. 裝飾角色(Decorator) – 定義抽象類並繼承接口中的方法,保證一致性
    4. 具體裝飾角色(ConcreteDecorator) – 擴展裝飾具體的實現邏輯

    通過以上這四項來實現裝飾器模式,主要核心內容會體現在抽象類的定義和實現上。

    1. 工程結構

    itstack-demo-design-9-02
    └── src
        └── main
            └── java
                └── org.itstack.demo.design
                    ├── LoginSsoDecorator.java
                    └── SsoDecorator.java
    

    裝飾器模式模型結構

    • 以上是一個裝飾器實現的類圖結構,重點的類是SsoDecorator,這個類是一個抽象類主要完成了對接口HandlerInterceptor繼承。
    • 當裝飾角色繼承接口後會提供構造函數,入參就是繼承的接口實現類即可,這樣就可以很方便的擴展出不同功能組件。

    2. 代碼實現

    2.1 抽象類裝飾角色

    public abstract class SsoDecorator implements HandlerInterceptor {
    
        private HandlerInterceptor handlerInterceptor;
    
        private SsoDecorator(){}
    
        public SsoDecorator(HandlerInterceptor handlerInterceptor) {
            this.handlerInterceptor = handlerInterceptor;
        }
    
        public boolean preHandle(String request, String response, Object handler) {
            return handlerInterceptor.preHandle(request, response, handler);
        }
    
    }
    
    • 在裝飾類中有兩個重點的地方是;1)繼承了處理接口、2)提供了構造函數、3)覆蓋了方法preHandle
    • 以上三個點是裝飾器模式的核心處理部分,這樣可以踢掉對子類繼承的方式實現邏輯功能擴展。

    2.2 裝飾角色邏輯實現

    public class LoginSsoDecorator extends SsoDecorator {
    
        private Logger logger = LoggerFactory.getLogger(LoginSsoDecorator.class);
    
        private static Map<String, String> authMap = new ConcurrentHashMap<String, String>();
    
        static {
            authMap.put("huahua", "queryUserInfo");
            authMap.put("doudou", "queryUserInfo");
        }
    
        public LoginSsoDecorator(HandlerInterceptor handlerInterceptor) {
            super(handlerInterceptor);
        }
    
        @Override
        public boolean preHandle(String request, String response, Object handler) {
            boolean success = super.preHandle(request, response, handler);
            if (!success) return false;
            String userId = request.substring(8);
            String method = authMap.get(userId);
            logger.info("模擬單點登錄方法訪問攔截校驗:{} {}", userId, method);
            // 模擬方法校驗
            return "queryUserInfo".equals(method);
        }
    }
    
    • 在具體的裝飾類實現中,繼承了裝飾類SsoDecorator,那麼現在就可以擴展方法;preHandle
    • preHandle的實現中可以看到,這裏只關心擴展部分的功能,同時不會影響原有類的核心服務,也不會因為使用繼承方式而導致的多餘子類,增加了整體的靈活性。

    3. 測試驗證

    3.1 編寫測試類

    @Test
    public void test_LoginSsoDecorator() {
        LoginSsoDecorator ssoDecorator = new LoginSsoDecorator(new SsoInterceptor());
        String request = "1successhuahua";
        boolean success = ssoDecorator.preHandle(request, "ewcdqwt40liuiu", "t");
        System.out.println("登錄校驗:" + request + (success ? " 放行" : " 攔截"));
    }
    
    • 這裏測試了對裝飾器模式的使用,通過透傳原有單點登錄類new SsoInterceptor(),傳遞給裝飾器,讓裝飾器可以執行擴充的功能。
    • 同時對於傳遞者和裝飾器都可以是多組的,在一些實際的業務開發中,往往也是由於太多類型的子類實現而導致不易於維護,從而使用裝飾器模式替代。

    3.2 測試結果

    23:50:50.796 [main] INFO  o.i.demo.design.LoginSsoDecorator - 模擬單點登錄方法訪問攔截校驗:huahua queryUserInfo
    登錄校驗:1successhuahua 放行
    
    Process finished with exit code 0
    
    • 結果符合預期,擴展了對方法攔截的校驗性。
    • 如果你在學習的過程中有用到過單點登陸,那麼可以適當在裏面進行擴展裝飾器模式進行學習使用。
    • 另外,還有一種場景也可以使用裝飾器。例如;你之前使用某個實現某個接口接收單個消息,但由於外部的升級變為發送list集合消息,但你又不希望所有的代碼類都去修改這部分邏輯。那麼可以使用裝飾器模式進行適配list集合,給使用者依然是for循環后的單個消息。

    七、總結

    • 使用裝飾器模式滿足單一職責原則,你可以在自己的裝飾類中完成功能邏輯的擴展,而不影響主類,同時可以按需在運行時添加和刪除這部分邏輯。另外裝飾器模式與繼承父類重寫方法,在某些時候需要按需選擇,並不一定某一個就是最好。
    • 裝飾器實現的重點是對抽象類繼承接口方式的使用,同時設定被繼承的接口可以通過構造函數傳遞其實現類,由此增加擴展性並重寫方法里可以實現此部分父類實現的功能。
    • 就像夏天熱你穿短褲,冬天冷你穿棉褲,雨天挨澆你穿雨衣一樣,你的根本本身沒有被改變,而你的需求卻被不同的裝飾而實現。生活中往往比比皆是設計,當你可以融合這部分活靈活現的例子到代碼實現中,往往會創造出更加優雅的實現方式。

    八、推薦閱讀

    • 1. 重學 Java 設計模式:實戰工廠方法模式(多種類型商品發獎場景)
    • 2. 重學 Java 設計模式:實戰抽象工廠模式(替換Redis雙集群升級場景)
    • 3. 重學 Java 設計模式:實戰建造者模式(裝修物料組合套餐選配場景)
    • 4. 重學 Java 設計模式:實戰原型模式(多套試每人題目和答案亂序場景)
    • 5. 重學 Java 設計模式:實戰橋接模式(多支付渠道「微信、支付寶」與多支付模式「刷臉、指紋」場景)
    • 6. 重學 Java 設計模式:實戰組合模式(營銷差異化人群發券,決策樹引擎搭建場景)

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

    【其他文章推薦】

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

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

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

    ※超省錢租車方案

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

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

    ※回頭車貨運收費標準

  • 給女朋友講解什麼是Git

    給女朋友講解什麼是Git

    前言

    在周六發現了Linus去Google演講的一個視頻,當時還發了一條朋友圈:

    有興趣的同學也可以去看看,一點兒也不無聊,在線看Linus大佬懟人

    https://www.bilibili.com/video/BV1xb411A7ac?from=search&seid=4239535088233137638

    朋友圈的評論有幾個人問我女朋友

    我又恰好給我女朋友科普過什麼是Git,所以這篇文章就有了。

    Git介紹

    Git是幹啥用的?它是一個版本控制軟件。

    Git這個玩意三歪曾經還給女朋友給科普過(三歪會經常給女朋友說點技術的東西,我也不知道她到底聽懂了沒有,反正她每次都說好像有點懂了)。

    當時情況是這樣的,某一天她跟三歪說:我做的Excel還沒保存,電腦藍屏死機了,東西全丟了。

    於是三歪說:這…我也沒怎麼用過Excel這類的軟件,要不看看你用的WPS或者Office?有沒有相關的備份功能或者說是自動保存?

    三歪順手找了一下WPS是有備份(自動保存)功能的,時間什麼的要自己定義一下。

    三歪還補了一句:這種情況要是在程序員的手上感覺發生的概率會低一點,程序員習慣會按ctrl+s。甚至有的時候,看着看着網頁還會按ctrl+s。不過像我們寫代碼的工具(IDEA)都不用自己手動保存了….

    過了一會,她說藍屏之前做的東西找不回來了,沒設置自動保存。

    三歪又感嘆一句:我們寫代碼還有版本控制的軟件,在這個過程中會記錄每次修改的內容,誰改了什麼東西。誰改錯了,誰要背鍋,一個都不能跑

    女朋友聽着三歪一頓亂吹,貌似也有點感興趣:“版本控制是什麼東西?這麼厲害的嗎?會計就經常要背鍋”

    三歪:“其實也沒啥,就是我們一般寫代碼往往都是多人協作的。你們會計可能是每個人負責一張表(Excel),然後把已完成好的表傳給下一個人。而寫代碼的不一樣,我們都是在同一個項目裡邊編寫的,不會單獨等着某個人做完了,其他的人再開始動手”

    女朋友:“嗯?然後呢”

    三歪:“你可以理解成,我們多個人會在同一個目錄下編寫代碼,裡邊可能會做更改或者添加文件的操作。項目組裡的所有人都可以對這個目錄修改,改完了我們會提交,然後發布上線系統。”

    女朋友:“啥?你是不是偏題了?這跟發布上線系統有啥關係?”

    三歪:“哦,我還是舉個例子吧。就比如我們寫論文的時候可能要對論文不斷修改,我們的修改是基於原有的基礎上改的”

    三歪繼續補充:”因為我們怕在原來的基礎改錯了東西,沒法恢復,所以,我們可能會有多個「畢業論文」的文件。而我們寫代碼的時候本身就是「多人協作」的,修改是無法避免的,我們不希望有多個文件的產生,又希望能夠記錄每次更改的內容。“

    三歪:”更改的內容指的就是:基於原有的基礎上更改了什麼,以及提交者是誰。這樣子,我們就沒法甩鍋了。說白了就是,我們能知道的文件被改了什麼,以及誰改了“。

    三歪:“到這裏,有問題嗎?”

    女朋友:“嗯,沒問題,你繼續”

    三歪:“「每一次的修改」我們稱為一個版本,它能夠實現版本與版本之間的來回穿梭。打個比方,我有篇文章寫了一周,這期間有10個版本,我能隨意回到我想要的版本。所以它叫做版本控制軟件”

    女朋友:“我大致聽懂了,大概就是每一次修改都會被記錄下來,然後你們就可以知道每一次版本修改了什麼,是誰改的,如果做錯了,可以通過這個軟件回到想要的版本”

    三歪:“嗯,就是這個意思”

    女朋友:“那我想問個問題,你一直提到的「多人協作」是在同一個目錄下對文件修改的,然後可以看到彼此改了什麼。那你是在你的電腦上改,你的同事是在他的電腦上改的,你們是怎麼看到彼此改了什麼?這現在有這麼厲害的東西了嗎?“

    三歪:”哦~你的意思大概就是:我們又不聯網,怎麼知道對方改了什麼,是這個意思吧?“

    女朋友:“嗯,是的”

    三歪:“你的理解是沒錯的,我們之間不聯網,是沒辦法知道對方改了什麼的。我漏了一點沒說,我們在改到一定程度下(比如說這個功能我們做完了、也可能做得差不多了),我們會把當前版本提交到遠程倉庫上”

    三歪繼續補充:“可以發現的是,提交到遠程倉庫后,即便我們電腦壞了,我們可以從遠程倉庫再把這份數據拉取下來。”

    女朋友:“所以呢?遠程倉庫到我這聽起來就是一個備份的功能吧?你們怎麼知道對方改了什麼?”

    三歪:“是這樣的,我們從遠程倉庫拉取代碼的時候除了會把有變動的代碼同步到自己的電腦上,還會把所有修改的記錄也同步到自己的電腦上。所以說,我們會知道彼此修改的內容。”

    女朋友:”聽着很有用啊,我平時用的word和excel可以用這個軟件嗎?即便我電腦壞了,我還可以去『遠程倉庫』拿到上一次我提交的數據,並且還有你所說的『版本控制』功能。又能備份,又能知道每次修改了什麼,很好用啊!“

    三歪:”很可惜,像你們那種工作場景,可能用不上,也可以說不太適合用“

    女朋友:”為什麼?“

    三歪:”之前我也想要用定時任務+GitHub的方式去保存我在本地寫的文章,發出來之後,被一頓噴。GitHub你可以簡單理解為就是那個遠程倉庫,定時任務我就是讓它隔一段時間就保存一次“

    女朋友:”我聽明白了,你想要的是備份功能,對吧?為什麼被噴的呢?“

    三歪:”他們說我瞎整,這每隔一段時間就提交到GitHub,網絡開銷可多大啊。然後給我列出一系列的產品,比如說:「堅果雲」「Dropbox」「OneDrive」等等“

    女朋友:”那你怎麼不用?“

    三歪:”我哪知道啊,有信息差的呢。反正當時覺得自己寫個定時任務實現了,就沒多想了。“

    女朋友:”那你是真的菜“

    三歪:”哦“

    三歪:”除了上面說的自動同步,你們的word、excel在用我們的工具也沒法查到歷史的版本記錄“

    女朋友:”為啥?你不是說你們寫代碼都可以的嗎?為什麼word和excel就沒法查?“

    三歪:”我們寫代碼的文件類型都是屬於文本文件,而你的word、excel本質上屬於二進制文件,很難去比對每次修改的差異,所以不支持“

    女朋友:”那聽你這樣說,在我的場景里這個「版本控制軟件」沒啥用啊,它不能記錄像Word、Excel這種文件每次版本的差異,要想用它做備份,還不如現有的雲產品。“

    三歪:”嗯,是的。其實現在雲產品也能提供版本控制的功能了,你用它們就足夠了。還有一點很重要的是,它有學習成本,可不是每個人都會用的。“

    女朋友:”聽你說了這麼多,好像雲產品就很行啊,為啥你們還要「偏執」去用你說的那東西?“

    三歪:“主要是我們寫代碼時遇到的問題會更多,我們用的「版本控制軟件」會更加靈活,它支持的功能會更多。”

    女朋友:“對了,你都說了這麼久了,你們用的那個軟件叫啥啊?”

    三歪:“Git

    三歪瞎扯

    其實本來想着直接講一下在工作中常用到的Git命令,但發現不太好寫(琢磨了很久

    看三歪文章的人可能很多都是大學生,對Git本身了解可能就不太清楚,直接上Git的命令可能看不太懂,所以就分開了兩篇。

    下一篇講一下三歪在工作中使用Git的糗事以及工作中是怎麼用Git的。

    涵蓋Java後端所有知識點的開源項目(已有8K+ star):

    • GitHub
    • Gitee訪問更快

    我是三歪,一個想要變強的男人,感謝大家的點贊收藏和轉發,下期見。

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

    【其他文章推薦】

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

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

    ※超省錢租車方案

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

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

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

  • LeetCode 76,一題教會你面試算法時的思考套路

    LeetCode 76,一題教會你面試算法時的思考套路

    本文始發於個人公眾號:TechFlow,原創不易,求個關注

    今天是LeetCode專題的第45篇文章,我們一起來看看LeetCode的76題,最小窗口子串Minimum Window Substring。

    這題的官方難度是Hard,通過了也是34.2%,4202人點贊,299人反對。從通過率以及點贊比來看,這題的質量很高,稍稍有些偏難,所以小夥伴們請做好準備,這是一道有點挑戰的問題。

    題意和樣例

    我們一起來看下題意,這題的題意很短,給定兩個字符串S和T。要求設計一個複雜度為的算法,在S串當中找到一個子串,能夠包含T串當中的所有字符。要求返回合法且長度最小的窗口的內容。

    注意:

    • 如果不存在這樣的窗口,返回“”。
    • 如果窗口存在,題目保證有且只有一個。

    樣例:

    Input: S = "ADOBECODEBANC", T = "ABC"
    Output: "BANC"
    

    分析

    我們來分析一下這個問題,從題意當中大家應該都能感受到它的難度。因為上來題目當中就限定了我們使用的算法的複雜度必須是,然而我們遍歷字符串的複雜度就已經是了,也就是說我們不能引入額外的計算開銷,否則一定不滿足題目的要求。

    可能有些同學會想到傳說中在時間內判斷字符串匹配的KMP算法,如果你不知道這個算法也沒有關係,因為這個算法並不適用。因為我們要找的不是完全相等的子串的位置,而是找的是字符構成一樣的子串,所以並不能通過引入字符串匹配算法來解決。沒有學過KMP算法的同學可以松一口氣了,這題當中並不會引入新的算法。

    解題的套路

    一般來說當我們面臨一個算法問題的時候,我們常常的思考過程主要有兩種。一種是適配,說白了就是把可能可以用上的算法往問題上套。根據題意先感覺一下,大概會用到什麼樣的算法,然後詳細地推導適配的過程,看看是不是真的適用或者是有什麼坑,或者是會出現什麼新的問題。如果一切OK,能夠推理得通,那麼這個算法就是解。第二種方法是建模,也就是說從題意入手,對題意進行深入的分析,對問題進行建模和抽象,找到問題的核心,從而推導出用什麼樣的算法可以解決。

    舉個很簡單的例子,一般來說我們的動態規劃算法都是適配。都是我們先感覺或者是猜測出可以使用動態規劃,然後再去找狀態和轉移,最後建立狀態轉移方程。而一些搜索問題一般是建模,我們先對問題進行分析,然後找出需要搜索的解的存在空間,然後設計算法去搜索和剪枝,最後找到答案。

    據說一些頂級高手這兩種方法是一起使用的,所以才可以那麼快速地找到解。當然我不是頂級高手,所以這個也只是我的猜測。這個思考過程非常有用,特別是當我們面試的時候,遇到一個從未見過的問題,如果你什麼套路也沒有,頭腦一片空白或者是苦思冥想不得要領是很常見的事情。當你有了套路之後,你就可以試着慢慢找到答案了。

    回到這道題本身,我們剛才已經試過了,拿字符串匹配的算法網上套是不行的。在視野里似乎也沒有其他的算法可以套用,所以我們換一種思路,試試看建模。

    首先我們可以肯定一點,我們需要在遍歷的時候找到答案,這樣才可以保證算法的複雜度是。我們的目標是尋找子串,也就是說我們遍歷的過程應該對應一個子串,並且我們有方法可以快速判斷這個子串是否合法。這樣我們才可以做到遍歷的同時判斷答案的可行性。進而可以想到這是一個區間維護的問題,區間維護我們經常使用的方法就是two pointers。所以我們可以試試two pointers能否適用。

    實際上這道題的正解就是two pointers。

    題解

    我們維護了一個區間,我們需要判斷區間里的字符構成,這個很容易想到可以使用dict,維護每一個字符出現的次數。在這個題目當中,我們只需要考慮覆蓋的情況,也就是說字符多了並不會構成非法。所以我們可以維護一個dict,每次讀入一個字符更新它,當dict當中的字符滿足要求的時候,為了使得區間長度盡量短,我們可以試着移動區間的左側,盡量縮短區間的長度。

    從區間維護的角度來說,我們每次移動區間右側一個單位,只有當區間內已經滿足題意的時候才會移動左側。通過移動左側彈出元素來獲取能夠滿足題意的最佳區間。

    我們來看下主要的流程代碼:

    # 存儲區間內的字符
    segement = {}
    for i in range(n):
        segement[s[i]] += 1
        # 當滿足條件的時候移動區間左側
        while l <= i and satisified(segment):
            # 更新最佳答案
            if i - l + 1 < ans_len:
                ans_len = i - l + 1
                beg, end = l, i + 1
            # 彈出元素
      segement[s[l]] -= 1
            l += 1
    

    到這裏還有一個小問題,就是怎麼樣判斷這個segment是否合法呢?我們可以用一個数字matched來記錄目前已經匹配上的字符的數量。當某個字符在segment當中出現的次數和T中的次數相等的時候,matched加一。當matched的數量和T中字符種類的數量相等的時候,就可以認為已經合法了。

    我們把所有的邏輯串起來,就可以通過這題了。

    class Solution:
        def minWindow(self, s: str, t: str) -> str:
            from collections import Counter, defaultdict
            # 通過Counter直接獲取T當中的字符構成
            counter = Counter(t)
            n, m = len(s), len(counter)
            l, beg, end = 0, 0, 0
            cur = defaultdict(int)
            matched = 0
            flag = False
            # 記錄合法的字符串的長度
            ans_len = 0x3f3f3f3f
            
            for i in range(n):
                if s[i] not in counter:
                    continue
                    
                cur[s[i]] += 1
                # 當數量匹配上的時候,matched+1
                if cur[s[i]] == counter[s[i]]:
                    matched += 1
                    
                # 如果已經找到了合法的區間,嘗試縮短區間的長度
                while l <= i and matched == m:
                    if i - l + 1 < ans_len:
                        flag = True
                        beg, end = l, i+1
                        ans_len = i - l + 1
                        
                    # 彈出左側元素
                    c = s[l]
                    if c in counter:
                        cur[c] -= 1
                        if cur[c] < counter[c]:
                            matched -= 1
                            
                    l += 1
    
            
            return "" if not flag else s[beg: end]
    

    總結

    到這裏,這道題就算是解決了。很多同學可能會覺得疑惑,為什麼我們用到了兩重循環,但是它依然還是的算法呢?

    這個是two pointers算法的常見問題,也是老生常談的話題了。我們在分析複雜度的時候,不能只簡單地看用到了幾層循環,而是要抓住計算的核心。比如在這個問題當中,我們內部的while循環針對的變量是l,l這個變量對於i整體是遞增的。也就是說無論外面這個循環執行多少次,裏面的這個while循環一共最多累加只能執行n次。那麼,當然這是一個的算法。

    這題總體來說有些難度,特別是一開始的時候可能會覺得沒有頭緒無從下手。這個時候有一個清晰的頭腦以及靠譜的思考鏈非常重要,希望大家都能學到這個其中思維的過程,這樣以後才可以應付更多的算法問題。

    如果喜歡本文,可以的話,請點個關注,給我一點鼓勵,也方便獲取更多文章。

    本文使用 mdnice 排版

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

    【其他文章推薦】

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

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

    ※回頭車貨運收費標準

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

    ※超省錢租車方案

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

  • 真慘!連各大編程語言都擺起地攤了!

    真慘!連各大編程語言都擺起地攤了!

    困難年年有,今年特別多。

    公司要做一個新的網站,可預算有限,聽說為了生計,各大編程語言們都擺起了地攤兒,我決定去瞧瞧,看看能不能淘點做網站需要的東西。

    選擇靜態web服務器

    一進集市,這煙火氣就撲面而來,平時一個個端着架子的C++、Java、Python居然能放下身段,招呼叫賣,我還是頭一回見。

    “老哥,需要來點什麼?”,C語言給我打起了招呼。

    “我想要建個網站”,我回答到。

    “那你可算來對地方了”,C語言攤主起身說到,“建網站總得需要一個Web服務器吧,你看這裏,apacheweb服務器,賣的可好了”

    我搖了搖頭,“這個apache,之前有用過,是用的多進程模型,連接多了有些吃力啊?”

    “老哥是行家啊,來看這一款我們最新推出的nginx服務器,採用epoll多路復用+事件驅動,性能強勁!上萬連接不在話下”,C語言攤主自豪的說到。

    隨後攤主給我展示了這個nginx服務器的能力,果然不錯,我加入了購物車,繼續往前逛。

    挑選web應用開發框架

    沒走幾步來到 C# 的攤前。

    “喲,老哥,你這是要做網站啊?”,C#攤主主動給我打起了招呼。

    “你怎麼知道的?”,我好奇的問到。

    “你這購物車裡不是裝了一個nginx嘛!既然做網站,可得試試我們家的.NET Framework哦,各種裝備,應有盡有。”,C#熱情的拉着我過去。

    不過我還是拒絕了他:“實在不好意思,聽說你們家產品只能在Windows系統上面運行,不支持Linux,還是算了,我再看看別家”

    C#攤主不肯放棄,“別呀,我們已經支持Linux了,您再看看,現在搞活動,免費送IIS服務器哦,你把那nginx退了吧,喂,再考慮一下啊·····”

    不等他說完,我就溜走了,來到了Python的攤前。

    Python攤主也看出了我要做網站,也推銷起他家的產品來。

    “大哥,你做網站,肯定不想只做一個靜態的吧,來試試咱們家的Web框架做一個動態網站?咱Python家的產品,簡單、輕量又實惠。”,攤主熱情的說到。

    “有哪些推薦的呢?”,我問到。

    Python攤主指着攤位上的幾個產品說道:“有DjangoFlaskTornado這三款是現在主打拳頭產品,用了的都說好”

    我正想蹲下仔細看看,背後傳來一個聲音:“這位大哥,擱這選Web開發框架吶?快來我這邊看看”

    一邊說,一邊硬把我往後面拽。

    來到他的攤位上,我一看原來是PHP攤主。

    “咱PHP產品琳琅滿目,就是專門為做網站而生的,現在做活動,跳樓價只要9.9,錯過不再有!”

    這PHP攤主好生能說,一頓猛誇把我說的暈頭轉向,不知怎的竟然就加入了購物車。

    繼續向前,來到了Java的攤位,一個好大的攤位,擺放的東西也是看的人眼花繚亂。

    “你這個攤位不錯啊,又寬敞人流又多”

    “可不是咋的,剛為了搶這個攤位,跟PHP那傢伙還幹了一架呢。”,Java攤主笑着說到。

    看到我購物車裡的東西,Java攤主也開始推銷起來:“大哥,這年頭怎麼還用PHP那傢伙的東西,趕緊去退了吧,咱Java攤里的東西都是大品牌,質量有保障!”

    “這,不太好吧,這PHP也是大品牌啊”

    Java攤主搖了搖頭,“他一個腳本語言怎麼跟我們比啊?大哥你看,我們有Spring、SpringMVC、SpringBoot、SpringCloud等等明星產品,用戶眾多,售後工作也到位。而且現在搞活動可以送tomcat服務器,你要是用戶量不多都可以把nginx退掉,省一筆錢。”

    “看起來很厲害的樣子呢,我考慮一下”,我打算再去別的地方看看比較一下。

    Java攤主一把拉住了我,“大哥,不說了,咱今天碰到是緣分,你做網站有很多服務是吧,得用到RPC吧,你今天下單,我再送你一套netty框架,又能幫你省一筆了”

    Java攤主盛情難卻,我一時興起,買下了好幾個,購物車都裝滿了一大半了。

    挑選數據庫

    剛付完錢準備離開,背後又傳來一個聲音:“大哥,做網站你得用數據庫吧,快來這看看”

    我尋聲望去,原來是 C++ 攤主在叫我。

    “來看看我的MySQL數據庫,做網站必備!”

    我看了一下產品說明書,感覺還不錯,看了下錢包,剛才在Java攤主那裡花費不少,有些囊中羞澀了,問到:“能不能優惠一點”

    C++攤主一聽,臉上的笑容少了一半,“如果你選個MongoDB組個套餐,可以給你8折優惠”

    “MongoDB?我要這個幹嘛”

    攤主一聽來了勁頭,開始滔滔不絕:“有些數據啊他不適合存在數據庫里,比如文檔啊,JSON啊,這些東西你要用數據庫存儲,增加字段和查詢,可麻煩了,你用MongoDB就方便都多了······”

    被他說了一通,感覺是得要個這個玩意兒。

    攤主見我有些心動,又繼續推銷:“大哥看來真是行家,您做網站是不是有圖片音頻視頻需要存儲,我這裏還有一個對象存儲(OSS)系統CEPH,你看看要不要也一併帶上,我還是給您八折,怎麼樣?”

    “實在不好意思,我這預算有些吃緊了,這個就算了吧”,我婉拒到。

    “哎哎大哥您往這瞧,咱家也有對象存儲minio,現在市場推廣期,免費送了!”,旁邊的Golang攤主招呼了起來。

    居然有免費這好事,我倒是想去看看。

    C++攤主見狀小聲說到:“免費的你敢用,出了問題都找不到人,還是看看我的吧,直接給你六折,怎麼樣?”

    我一想也是,正想下單買下,背後傳來一聲“且慢”!

    我回頭一看,原來是剛才的Java攤主,“大哥,咱Java家的ElasticSearch也考慮一下唄。”

    我回到Java攤主這邊,問到:“這又是個什麼?我需要用到嗎?”

    Java攤主也開始給我掰扯起來:“咱家的ElasticSearch那可是搜索行家,你網站內容多了是不是需要個搜索功能啊,咱家的這個ES,全文搜索不在話下,秒級響應,做網站必備啊。看你是回頭客,給你九折!”

    我正想做一個搜索功能,看來這個也是必不可少,也一起拿下了。

    緩存服務器

    我推着購物車準備回家了,今天真是滿載而歸。

    來到集市出口,又碰到了一開始的C語言攤主,攤主一瞧揮着手喊道:“大哥,你還差個內存緩存系統,過來看看,Redis搞活動呢!哎,別走啊,Memcached虧本處理了,過來看看啊”

    我一摸錢包,完蛋,嚴重超支了!我加快了步伐,匆忙離開······

    彩蛋

    看着我採購回來的一堆東西,老闆是氣不打一處來。

    “咱們就做一個內網論壇,全公司不過100號人,你給我搞這麼多,幾個意思?”

    “老闆,您聽我解釋···”

    “解釋個啥,明天不用來了”

    哦豁,丟了飯碗,我也去擺地攤了···

    往期熱門回顧

    因為一個跨域請求,我差點丟了飯碗

    一個神秘URL釀大禍,差點讓我背鍋!

    就為了一個原子操作,其他CPU核心都罷工了

    完了!CPU一味求快出事兒了!

    可怕!CPU竟成了黑客的幫凶!

    哈希表哪家強?幾大編程語言吵起來了!

    震撼!全網第一張源碼分析全景圖揭秘Nginx

    一網打盡!每個程序猿都該了解的黑客技術大匯總

    DDoS攻擊:無限戰爭

    一個Java對象的回憶錄:垃圾回收

    誰動了你的HTTPS流量?

    路由器里的廣告秘密

    一個HTTP數據包的奇幻之旅

    我是一個流氓軟件線程

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

    【其他文章推薦】

    ※超省錢租車方案

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

    ※回頭車貨運收費標準

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

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

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

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

  • PBFT共識算法

    PBFT共識算法

    拜占庭將軍問題

    我們已知的共識算法,Paxos、Raft解決的都是非拜占庭問題,也就是可以容忍節點故障,消息丟失、延時、亂序等,但節點不能有惡意節點。但如何在有惡意節點存在的情況下達成共識呢?BFT共識算法就是解決這一問題的。即不但能容忍節點故障,還能容忍一定的惡意節點或者說拜占庭節點的存在。我們下面就學習一下BFT算法中的PBFT(Practical Byzantine Fault Tolerance)。BFT算法有非常多的變種,這裏只學習PBFT,其他的可以舉一反三。

    PBFT

    PBFT核心由3個協議組成:一致性協議、檢查點協議、視圖更換協議。系統正常運行在一致性協議和檢查點協議下,只有當主節點出錯或者運行緩慢的情況下才會啟動視圖更換協議,以維持系統繼續響應客戶端的請求。下面詳解這3個子協議。在講一致性協議之前,我們屏蔽算法細節先看一下正常情況下大致是怎麼工作的,大致流程如下:

    1. 客戶端發送請求給主節點(如果請求發送給了從節點,從節點會將該請求轉發給主節點或者將主節點的信息告知客戶端,讓客戶端發送給主節點)。
    2. 主節點將請求廣播給從節點。
    3. 主從節點經過2輪投票后執行客戶端的請求並響應客戶端。(協議細節見下面的一致性協議)
    4. 客戶端收集到來着\(f+1\)個不同節點的相同的響應后,確認請求執行成功。(因為最多有\(f\)個惡意節點,\(f+1\)個相同即能保證正確性)。

    一致性協議

    一致性協議的目標是使來自客戶端的請求在每個服務器上都按照一個確定的順序執行。 在協議中,一般有一個服務器被稱作主節點,負責將客戶端的請求排序;其餘的服務器稱作從節點,按照主節點提供的順序執行請求。所有的服務器都在相同的配置信息下工作,這個配置信息稱作視圖view,每更換一次主節點,視圖view就會隨之變化。協議主要分pre-preparepreparecommit三階段,如下圖所示:

    REQUEST:

    首先是客戶端發起請求, 請求<REQUEST,o,t,c>中時間戳t主要用來保證exactly-once語義,也就是說對同一客戶端請求不能有執行2次的情況,具體實現時也不一定非是時間戳,也可以是邏輯時鐘或者其他,只要能唯一標識這個請求就可以了。

    PRE-PREPARE:

    【1】 收到客戶端的請求消息后,先判斷當前正在處理的消息數量是否超出限制,如果超出限制,則先緩存起來,後面再打包一起處理。否則的話(當然,沒超過也可以緩存處理),對請求分配序列號n,並附加視圖號v等信息生成PRE-PREPARE消息<<PRE-PREPARE,v,n,d>,m>,廣播給其他節點。簡而言之就是對請求分配序號並告知所有節點。

    【2】 收到PRE-PREPARE的消息後進行如下處理:

    • 消息合法性檢查,消息簽名是否正確,消息摘要是否正確。
    • 視圖檢查,檢查是否是同一個視圖號v
    • 水線檢查,判斷n是否在hH之間。(h一般是系統穩定檢查點,H是上限,會隨着h的不斷提高而提高)

    如果都通過的話,就廣播PREPARE消息<PREPARE,v,n,d,i>給其他節點,表示自己收到並認可[n,v]這個請求,進入prepare階段。如果沒有通過,則忽略該消息。

    這裏想一個問題,從節點能不能收到PRE-PREPARE消息就執行請求呢?答案顯然是不能的,因為不能確認本節點與其他節點收到的是相同的請求消息,此時不能確定主節點是不是正常節點,如果主節點是惡意節點呢?比如,發送給從節點1的消息是m,而發送給從節點2的消息是m',如果直接執行就會出現從節點的不一致。因為不能確認本節點與其他節點收到的是相同的請求消息,所以要通過從節點與從節點交互的方式互相告知收到了請求消息,好讓後面階段對比一下,是否一致。

    PREPARE:
    收到PREPARE消息<PREPARE,v,n,d,i>后,進行如下處理:

    • 消息合法性檢查,消息簽名是否正確,消息摘要是否正確。
    • 視圖檢查,檢查是否是同一個視圖號v
    • 水線檢查,判斷n是否在hH之間。

    如果上面都通過,就將PREPARE消息加入到日誌中,並繼續收集PREPARE消息,如果收到正確的\(2f\)張(包括自己)PREPARE消息,這裏如何驗證是否正確呢?主要是收到的PREPARE要與PRE-PREPARE中的vnd等信息要匹配,就進入COMMIT階段,廣播COMMIT消息<COMMIT,v,n,D(m),i>

    這一階段一般也可以稱為第一輪投票,目的是什麼呢?論文中是這麼說的:The pre-prepare and prepare phases of the algorithm guarantee that non-faulty replicas agree on a total order for the requests within a view. 濃縮為兩個字就是定序,確定在同一視圖下足額的正常的節點都對來自客戶端的請求有相同的定序。再說的直白點,就是解決上面提到的,無法確認本節點與其他節點收到的消息是否一致的問題。通過檢查相同視圖號v及同一序號n下的消息摘要d是否一致來判斷同一視圖配置下的同一個序號請求的消息是否一致。同時也確保了有足夠數量的節點收到了一致的消息請求。

    可以再想一個問題,此時可以直接執行請求嗎?答案是不可以,因為此時,你只能確認自己收到了\(2f\)個一致的PREPARE消息,你無法確認其他節點是否也收到了\(2f\)個一致的PREPARE消息。也就是說,當前,你只能確認自己準備好了去執行序號為n的請求,但是你不能確認其他節點有沒有準備好,所以,還要再進行一次節點間的消息交互,互相告訴大家,我準備好了。

    COMMIT:

    在上一階段,節點收到足額PREPARE投票後會廣播COMMIT投票,過程類似,當節點收到其他節點的COMMIT投票消息后,會進行如下檢查:

    • 消息合法性檢查,檢查消息簽名是否正確,消息摘要正不正確有沒有被篡改。
    • 視圖檢查,view是否匹配。
    • 水線檢查,判斷n是否在hH之間。

    如果都通過則把收到的投票消息寫入日誌log中,如果收到的合法的COMMIT投票消息大於等於\(2f+1\)個(包括自己),意思就是,已經確認大多數節點都準備好了執行請求,就執行請求並回復REPLY消息給客戶端。這裏如同上面一樣,也是檢查視圖,序號及消息是否匹配。

    REPLY:

    客戶端收到REPLY后,會進行統計,如果收到\(f+1\)個相同時間戳t和響應值r,則認為請求響應成功。如果在規定的時間內沒有收到回應或者沒有收到足額回應怎麼辦?可以將該請求廣播給所有節點,節點收到請求后,如果該請求已經被狀態機執行了,則再次回復客戶端REPLY消息,如果沒有被狀態機執行,如果節點不是主節點,就將該請求轉發給主節點。如果主節點沒有正常的將該請求廣播給其他節點,則將會被懷疑是主節點故障或惡意節點,當有足夠的節點都懷疑時將會觸發視圖變更協議,更換視圖。

    我們進行進一步的分析,可以看到,如果是客戶端沒有收到任何回應,很有可能是主節點故障或主節點是惡意節點(我就故意不執行你的請求),沒有將請求足額廣播給其他節點,(當然還有消息丟失等原因,這裏不在詳細分析),這時,客戶端因一直沒有響應,所以將請求廣播給了所有節點,所有節點收到請求后,轉發給主節點后發現主節點怎麼什麼都不幹呀,懷疑主節點有問題,然後觸發視圖更換協議,換掉主節點。當然,客戶端沒有收到足額回應的一個原因還可能是消息丟失,那麼如果是已經執行了該請求的節點再次收到該請求後會再次回應REPLY,前提是該請求是在水線範圍內的合法請求,否則被拒絕。

    檢查點協議

    在上面的一致性協議中可以看到,系統每執行一個請求,服務器都需要記錄日誌(包括,request、pre-prepare、prepare、commit等消息)。如果日誌得不到及時的清理,就會導致系統資源被大量的日誌所佔用,影響系統性能及可用性。另一方面,由於拜占庭節點的存在,一致性協議並不能保證每一台服務器都執行了相同的請求,所以,不同服務器狀態可能不一致。例如,某些服務器可能由於網絡延時導致從某個序號開始之後的請求都沒有執行。因此,設置周期性的檢查點協議,將系統中的服務器同步到某一個相同的狀態。簡言之,主要作用有2個:1、同步服務器的狀態;2、定期清理日誌。

    同步服務器的狀態,比較容易理解與做到。比如在區塊鏈系統中,同步服務器的狀態,實際上就是追塊,即服務器節點會通過鏈定時廣播的鏈世界狀態或其他消息獲知到自己區塊落後了,然後啟動追塊流程。

    定期清理日誌,怎麼做呢?首先要明確哪些日誌可以被清理,哪些日誌仍然需要保留。如果一個請求已經被\(f+1\)台非拜占庭節點執行,並且某一服務器節點i可以向其他服務器節點證明這一點,那麼該i節點就可以將關於這個請求的日誌刪除。協議一般採用的方式是服務器節點每執行一定數量的請求就將自己的狀態發送給所有服務器並且執行一個該協議,如果某台服務器節點收到\(2f+1\)台服務器節點的狀態,那麼其中一致的部分就是至少有\(f+1\)台非拜占庭服務器節點經歷過的狀態,因此,這部分的日誌就可以刪除,同時更新為較新狀態。

    具體實現時可以聯想到上面的一致性協議總的水線檢查。上面的低水線h值等同於穩定檢查點,穩定檢查點之前的日誌都可被清理掉。高水線H=h+k,也就是接收請求序號上限值,因為穩定檢查點往往是間隔很多的序號才觸發一次,所以k一般要設置的足夠大。例如,每間隔100個請求就觸發一次檢查點協議,提升水線,k可以設置為200。

    這裏解釋一下穩定檢查點的概念,可以理解為當\(2f+1\)個節點都達到了某個請求序號,該請求序號就是穩定檢查點。所有穩定檢查點之前的消息都可以被丟棄,減少資源佔用。 對比Raft,Raft是通過快照的方式壓縮日誌,都需要一個清理日誌的機制,不然日誌無限增長下去會造成系統不可用

    視圖更換協議

    在一致性協議里,已經知道主節點在整個系統中擁有序號分配,請求轉發等核心能力,支配着這個系統的運行行為。然而一旦主節點自身發生錯誤,就可能導致從節點接收到具有相同序號的不同請求,或者同一個請求被分配多個序號等問題,這將直接導致請求不能被正確執行。視圖更換協議的作用就是在主節點不能繼續履行職責時,將其用一個從節點替換掉,並且保證已經被非拜占庭服務器執行的請求不會被篡改。即,核心有2點:1,主節點故障時,可能造成系統不可用,要更換主節點;2,當主節點是惡意節點時,要更換為誠實節點,不能讓作惡節點作為主節點。

    當檢測到主節點故障或為惡意節點觸發視圖更換時,下一任主節點應該選誰呢?PBFT的辦法是採用“輪流上崗”的方式,通過\((v+1) \ mod \ N\),其中\(v\)為當前視圖號,\(N\)為節點總數,通過這一方式確定下一個視圖的主節點。還有個更關鍵的問題,什麼時候觸發視圖更換協議呢?我們繼續往下討論。

    如果是主節點故障的情況,這種情況一般較好處理。具體實現時,一般從節點都會維護一個定時器,如果長時間沒有收到來自主節點的消息,就會認為主節點發生故障。此時可觸發視圖更換協議,當然具體實現時,細節可能會不同,比如,也可以是這種情況,客戶端發送請求給故障主節點必然導致長時間收不到響應,所以,客戶端將請求發送給了系統中所有從節點,從節點將請求轉發給主節點並啟動定時器,如果主節點長時間沒有將該請求分配序號發送PRE-PREPARE消息,認為主節點故障,觸發視圖更換協議。這2種情況比較好理解,但就這2種情況嗎?其實還有以下幾種情況也會觸發視圖更換協議:

    • 從節點廣播PREPARE消息后,在約定的時間內未收到來自其他節點的\(2f\)個一致合法消息。
    • 從節點廣播COMMIT消息后,在約定的時間內未收到來自其他節點的\(2f\)個一致合法消息。
    • 從節點收到異常消息,比如視圖、序號一致,但消息不一致。
      這三點,都有可能是主節點作惡導致的,但也有可能是消息丟失等原因導致的。雖然不一定是因為主節點異常導致的,但從另一個角度看,解決了從節點不能無限等待其他節點投票消息的問題。

    這裏補充一點,觸發視圖更換協議后,將不再接收除檢查點消息、VIEW-CHANGE消息、NEW-VIEW消息之外的消息。也就是視圖更換期間,不再接收客戶端請求,暫停服務。

    解決了什麼時候觸發的問題后,下一個問題就是具體怎麼實現呢?當因上面的情況觸發視圖更換協議時,從節點i就會廣播一個VIEW-CHANGE消息<VIEW-CHANGE,v+1,n,C,P,i>,序號n是節點i的最新穩定檢查點sC\(2f+1\)個有效檢查點消息,是為了證明穩定檢查點s的正確性,P是位於序號n之後的一系列消息的結合,這裏要包含這些信息可以理解為是證據,也就是說,從節點不能隨便就發送一個VIEW-CHANGE,什麼證據都沒有,別人怎麼能認同你更換視圖呢?。上面我們提到過下一任主節點是誰的問題?通過\((v+1) \ mod \ N\)確定的一下任主節點p(在圖中就是節點1),在收到\(2f\)個有效的VIEW-CHANGE消息后,就廣播<NEW-VIEW,v+1,V,O>消息,這裏VO具體的生成方法參考原論文,主要是VIEW-CHANGEPRE-PREPARE等消息構成的集合,主要目的是為了讓從節點去驗證當前新的主節點的合法性以及解決下面這個問題,還有要處理未確認消息和投票消息。

    視圖更換協議需要解決的問題是如何保證已經被非拜占庭服務器執行的請求不被更改。由於系統達成一致性之後至少有\(f+1\)台非拜占庭服務器節點執行了請求,所以目前採用的方法是:由新的主節點收集至少\(2f+1\)台服務器節點的狀態信息(也就是上面在構造消息時所需的各種消息集合),這些狀態信息中一定包含所有執行過的請求;然後,新主節點將這些狀態信息發送給所有的服務器,服務器按照相同的原則將在上一個主節點完成的請求同步一遍,同步之後,所有的節點都處於相同的狀態,這時就可以開始執行新的請求。

    若干細節問題的思考

    在3階段協議中,對收到的消息都要進行消息合法性檢查、視圖檢查、水線檢查這3項檢查,為什麼呢?

    這3項檢查是十分有必要的,添加消息簽名是為了驗證投票是否合法,正確統計合法票數,不能是隨便一個不知道的節點都能投票,那我怎麼驗證到底是誰投的呀。也就是說,要通過消息簽名的方式確認消息來源,通過消息摘要的方式,確認消息沒有被篡改。當然,考慮到性能因素,也可以使用消息認證碼(MAC),以節省大量加解密的性能開銷。PBFT算法,可以容忍節點作惡,消息丟失、延時、亂序,但消息不能被篡改。

    視圖檢查比較容易理解,所有節點必須在同一個配置下才能正常工作。如果節點的視圖配置不一致,比如主節點不一致、節點數量不一致,那統計合法票數的時候,真沒法幹了。

    水線檢查,是檢查點協議的一部分,在工程實現時,不是所有的請求我都有處理,比如,你收到一個歷史投票信息,你還有必要處理嗎?當然,它的作用不止於此,還可以防止惡意節點選擇一個非常大的序列號而耗盡序列號空間,例如,當一個節點分配了超過H上限的序列號,這時,正常節點會拒絕這個請求從而阻止了惡意節點分配的遠超過H的序列號。

    3階段協議中每一階段的意義是什麼?

    論文中有如下錶述:

    The three phases are pre-prepare, prepare, and commit.The pre-prepare and prepare phases are used to totally order requests sent in the same view even when the primary, which proposes the ordering of requests, is faulty. The prepare and commit phases are used to ensure that requests that commit are totally ordered across views.

    即,pre-prepareprepare階段,主要的作用就是定序,個人理解就是要確認有足夠數量的節點收到同一請求,並且與自己所收到的請求相一致。prepare以及commit階段是確認大家執行的同一請求。

    為什麼是\(3f+1\)

    我們知道PBFT的容錯能力為不超過三分之一,即\(n=3f+1\)\(f\)為拜占庭節點數量。但這個公式是怎麼來的呢?論文中有這麼一段論述可以幫助我們去理解:

    The resiliency of our algorithm is optimal: \(3f+1\) is the minimum number of replicas that allow an asynchronous system to provide the safety and liveness properties when up to \(f\) replicas are faulty. This many replicas are needed because it must be possible to proceed after communicating with \(n-f\) replicas, since \(f\) replicas might be faulty and not responding. However, it is possible that the \(f\) replicas that did not respond are not faulty and, therefore, \(f\) of those that responded might be faulty. Even so, there must still be enough responses that those from non-faulty replicas outnumber those from faulty ones, i.e., \(n-2f>f\). Therefore \(n>3f\).

    意思就是,在一個容忍\(f\)個錯誤節點的系統中,系統至少要\(3f+1\)個節點才能保證系統安全可靠。為什麼呢?因為在所有\(n\)個節點中,有\(f\)個節點可能因故障而沒有回應(或者投票),而在回應的\(n-f\)中又有可能有\(f\)個是惡意節點的回應,即使如此,也要保證正常節點的投票要多於惡意節點的投票數量,即\(n-f-f>f\),推出\(n>3f\)

    PBFT對比Raft

    PBFT對比Raft,最大的不同在於解決的問題不一樣,雖然都是共識算法,但一個解決的拜占庭問題,另一個則解決的非拜占庭問題。從算法細節上來看,Raft中的領導者是強領導者,即,一切領導者說了算,但PBFT中對應的主節點卻不是,因為不能保證主節點不是拜占庭節點,萬一主節點作惡,從節點要有發現主節點是惡意節點的能力,並及時觸發視圖更換協議更換主節點。從算法消耗的資源來看,明顯PBFT要更複雜,投票數明顯多於Raft,不但要主從節點交互,還有從節點與從節點互相交互,所以,其性能也一定比Raft低,這是肯定的,因為PBFT解決的問題比Raft更複雜,一定程度上可以認為Raft是PBFT的子集,如果你把PBFT三階段協議中從節點與從節點交互的那部分去掉,只保留主節點與從節點交互的那部分,你會發現,好像還蠻像的。從另一個方面說,Raft算法,因為沒有拜占庭節點的存在,領導者節點一定是對的,從節點一切聽領導的就是。但是在PBFT中,從節點就不能光聽主節點的,萬一主節點也是壞人咋辦?怎麼解決這個問題呢?顯然,只聽主節點肯定是不行的,我還要看看其他節點的意見,如果有足額的節點認為是對的,就同意。怎麼確定足額節點數到底是多少呢?上面有講到過。所以,相比Raft,PBFT多了從節點與從節點的消息交互。

    PBFT的時間複雜度分析

    PBFT有比較明顯的兩輪投票,所以時間複雜度\(O(n^2)\),節點數量較大時,一次共識協商所需的消息太多,這也決定了PBFT只能適用於節點數量不大的系統中,比如區塊鏈中的許可鏈,公鏈節點數量太多,並不適用PBFT算法。

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

    【其他文章推薦】

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

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

    ※回頭車貨運收費標準

    ※推薦評價好的iphone維修中心

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

  • 8000字長文讓你徹底了解 Java 8 的 Lambda、函數式接口、Stream 用法和原理

    8000字長文讓你徹底了解 Java 8 的 Lambda、函數式接口、Stream 用法和原理

    我是風箏,公眾號「古時的風箏」。一個兼具深度與廣度的程序員鼓勵師,一個本打算寫詩卻寫起了代碼的田園碼農!
    文章會收錄在 JavaNewBee 中,更有 Java 後端知識圖譜,從小白到大牛要走的路都在裏面。公眾號回復『666』獲取高清大圖。

    就在今年 Java 25周歲了,可能比在座的各位中的一些少年年齡還大,但令人遺憾的是,竟然沒有我大,不禁感嘆,Java 還是太小了。(難道我會說是因為我老了?)

    而就在上個月,Java 15 的試驗版悄悄發布了,但是在 Java 界一直有個神秘現象,那就是「你發你發任你發,我的最愛 Java 8」.

    據 Snyk 和 The Java Magazine 聯合推出發布的 2020 JVM 生態調查報告显示,在所有的 Java 版本中,仍然有 64% 的開發者使用 Java 8。另外一些開發者可能已經開始用 Java 9、Java 11、Java 13 了,當然還有一些神仙開發者還在堅持使用 JDK 1.6 和 1.7。

    儘管 Java 8 發布多年,使用者眾多,可神奇的是竟然有很多同學沒有用過 Java 8 的新特性,比如 Lambda表達式、比如方法引用,再比如今天要說的 Stream。其實 Stream 就是以 Lambda 和方法引用為基礎,封裝的簡單易用、函數式風格的 API。

    Java 8 是在 2014 年發布的,實話說,風箏我也是在 Java 8 發布后很長一段時間才用的 Stream,因為 Java 8 發布的時候我還在 C# 的世界中掙扎,而使用 Lambda 表達式卻很早了,因為 Python 中用 Lambda 很方便,沒錯,我寫 Python 的時間要比 Java 的時間還長。

    要講 Stream ,那就不得不先說一下它的左膀右臂 Lambda 和方法引用,你用的 Stream API 其實就是函數式的編程風格,其中的「函數」就是方法引用,「式」就是 Lambda 表達式。

    Lambda 表達式

    Lambda 表達式是一個匿名函數,Lambda表達式基於數學中的λ演算得名,直接對應於其中的lambda抽象,是一個匿名函數,即沒有函數名的函數。Lambda表達式可以表示閉包。

    在 Java 中,Lambda 表達式的格式是像下面這樣

    // 無參數,無返回值
    () -> log.info("Lambda")
    
     // 有參數,有返回值
    (int a, int b) -> { a+b }
    

    其等價於

    log.info("Lambda");
    
    private int plus(int a, int b){
      	return a+b;
    }
    

    最常見的一個例子就是新建線程,有時候為了省事,會用下面的方法創建並啟動一個線程,這是匿名內部類的寫法,new Thread需要一個 implements 自Runnable類型的對象實例作為參數,比較好的方式是創建一個新類,這個類 implements Runnable,然後 new 出這個新類的實例作為參數傳給 Thread。而匿名內部類不用找對象接收,直接當做參數。

    new Thread(new Runnable() {
        @Override
        public void run() {
            System.out.println("快速新建並啟動一個線程");
        }
    }).run();
    

    但是這樣寫是不是感覺看上去很亂、很土,而這時候,換上 Lambda 表達式就是另外一種感覺了。

    new Thread(()->{
        System.out.println("快速新建並啟動一個線程");
    }).run();
    

    怎麼樣,這樣一改,瞬間感覺清新脫俗了不少,簡潔優雅了不少。

    Lambda 表達式簡化了匿名內部類的形式,可以達到同樣的效果,但是 Lambda 要優雅的多。雖然最終達到的目的是一樣的,但其實內部的實現原理卻不相同。

    匿名內部類在編譯之後會創建一個新的匿名內部類出來,而 Lambda 是調用 JVM invokedynamic指令實現的,並不會產生新類。

    方法引用

    方法引用的出現,使得我們可以將一個方法賦給一個變量或者作為參數傳遞給另外一個方法。::雙冒號作為方法引用的符號,比如下面這兩行語句,引用 Integer類的 parseInt方法。

    Function<String, Integer> s = Integer::parseInt;
    Integer i = s.apply("10");
    

    或者下面這兩行,引用 Integer類的 compare方法。

    Comparator<Integer> comparator = Integer::compare;
    int result = comparator.compare(100,10);
    

    再比如,下面這兩行代碼,同樣是引用 Integer類的 compare方法,但是返回類型卻不一樣,但卻都能正常執行,並正確返回。

    IntBinaryOperator intBinaryOperator = Integer::compare;
    int result = intBinaryOperator.applyAsInt(10,100);
    

    相信有的同學看到這裏恐怕是下面這個狀態,完全不可理喻嗎,也太隨便了吧,返回給誰都能接盤。

    先別激動,來來來,現在咱們就來解惑,解除蒙圈臉。

    Q:什麼樣的方法可以被引用?

    A:這麼說吧,任何你有辦法訪問到的方法都可以被引用。

    Q:返回值到底是什麼類型?

    A:這就問到點兒上了,上面又是 Function、又是Comparator、又是 IntBinaryOperator的,看上去好像沒有規律,其實不然。

    返回的類型是 Java 8 專門定義的函數式接口,這類接口用 @FunctionalInterface 註解。

    比如 Function這個函數式接口的定義如下:

    @FunctionalInterface
    public interface Function<T, R> {
        R apply(T t);
    }
    

    還有很關鍵的一點,你的引用方法的參數個數、類型,返回值類型要和函數式接口中的方法聲明一一對應才行。

    比如 Integer.parseInt方法定義如下:

    public static int parseInt(String s) throws NumberFormatException {
        return parseInt(s,10);
    }
    

    首先parseInt方法的參數個數是 1 個,而 Function中的 apply方法參數個數也是 1 個,參數個數對應上了,再來,apply方法的參數類型和返回類型是泛型類型,所以肯定能和 parseInt方法對應上。

    這樣一來,就可以正確的接收Integer::parseInt的方法引用,並可以調用Funcitonapply方法,這時候,調用到的其實就是對應的 Integer.parseInt方法了。

    用這套標準套到 Integer::compare方法上,就不難理解為什麼即可以用 Comparator<Integer>接收,又可以用 IntBinaryOperator接收了,而且調用它們各自的方法都能正確的返回結果。

    Integer.compare方法定義如下:

    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
    

    返回值類型 int,兩個參數,並且參數類型都是 int

    然後來看ComparatorIntBinaryOperator它們兩個的函數式接口定義和其中對應的方法:

    @FunctionalInterface
    public interface Comparator<T> {
        int compare(T o1, T o2);
    }
    
    @FunctionalInterface
    public interface IntBinaryOperator {
        int applyAsInt(int left, int right);
    }
    

    對不對,都能正確的匹配上,所以前面示例中用這兩個函數式接口都能正常接收。其實不止這兩個,只要是在某個函數式接口中聲明了這樣的方法:兩個參數,參數類型是 int或者泛型,並且返回值是 int或者泛型的,都可以完美接收。

    JDK 中定義了很多函數式接口,主要在 java.util.function包下,還有 java.util.Comparator 專門用作定製比較器。另外,前面說的 Runnable也是一個函數式接口。

    自己動手實現一個例子

    1. 定義一個函數式接口,並添加一個方法

    定義了名稱為 KiteFunction 的函數式接口,使用 @FunctionalInterface註解,然後聲明了具有兩個參數的方法 run,都是泛型類型,返回結果也是泛型。

    還有一點很重要,函數式接口中只能聲明一個可被實現的方法,你不能聲明了一個 run方法,又聲明一個 start方法,到時候編譯器就不知道用哪個接收了。而用default 關鍵字修飾的方法則沒有影響。

    @FunctionalInterface
    public interface KiteFunction<T, R, S> {
    
        /**
         * 定義一個雙參數的方法
         * @param t
         * @param s
         * @return
         */
        R run(T t,S s);
    }
    

    2. 定義一個與 KiteFunction 中 run 方法對應的方法

    在 FunctionTest 類中定義了方法 DateFormat,一個將 LocalDateTime類型格式化為字符串類型的方法。

    public class FunctionTest {
        public static String DateFormat(LocalDateTime dateTime, String partten) {
            DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern(partten);
            return dateTime.format(dateTimeFormatter);
        }
    }
    

    3.用方法引用的方式調用

    正常情況下我們直接使用 FunctionTest.DateFormat()就可以了。

    而用函數式方式,是這樣的。

    KiteFunction<LocalDateTime,String,String> functionDateFormat = FunctionTest::DateFormat;
    String dateString = functionDateFormat.run(LocalDateTime.now(),"yyyy-MM-dd HH:mm:ss");
    

    而其實我可以不專門在外面定義 DateFormat這個方法,而是像下面這樣,使用匿名內部類。

    public static void main(String[] args) throws Exception {
      
        String dateString = new KiteFunction<LocalDateTime, String, String>() {
            @Override
            public String run(LocalDateTime localDateTime, String s) {
                DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern(s);
                return localDateTime.format(dateTimeFormatter);
            }
        }.run(LocalDateTime.now(), "yyyy-MM-dd HH:mm:ss");
        System.out.println(dateString);
    }
    

    前面第一個 Runnable的例子也提到了,這樣的匿名內部類可以用 Lambda 表達式的形式簡寫,簡寫后的代碼如下:

    public static void main(String[] args) throws Exception {
    
            KiteFunction<LocalDateTime, String, String> functionDateFormat = (LocalDateTime dateTime, String partten) -> {
                DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern(partten);
                return dateTime.format(dateTimeFormatter);
            };
            String dateString = functionDateFormat.run(LocalDateTime.now(), "yyyy-MM-dd HH:mm:ss");
            System.out.println(dateString);
    }
    

    使用(LocalDateTime dateTime, String partten) -> { } 這樣的 Lambda 表達式直接返回方法引用。

    Stream API

    為了說一下 Stream API 的使用,可以說是大費周章啊,知其然,也要知其所以然嗎,追求技術的態度和姿勢要正確。

    當然 Stream 也不只是 Lambda 表達式就厲害了,真正厲害的還是它的功能,Stream 是 Java 8 中集合數據處理的利器,很多本來複雜、需要寫很多代碼的方法,比如過濾、分組等操作,往往使用 Stream 就可以在一行代碼搞定,當然也因為 Stream 都是鏈式操作,一行代碼可能會調用好幾個方法。

    Collection接口提供了 stream()方法,讓我們可以在一個集合方便的使用 Stream API 來進行各種操作。值得注意的是,我們執行的任何操作都不會對源集合造成影響,你可以同時在一個集合上提取出多個 stream 進行操作。

    我們看 Stream 接口的定義,繼承自 BaseStream,機會所有的接口聲明都是接收方法引用類型的參數,比如 filter方法,接收了一個 Predicate類型的參數,它就是一個函數式接口,常用來作為條件比較、篩選、過濾用,JPA中也使用了這個函數式接口用來做查詢條件拼接。

    public interface Stream<T> extends BaseStream<T, Stream<T>> {
      
      Stream<T> filter(Predicate<? super T> predicate);
      
      // 其他接口
    }  
    

    下面就來看看 Stream 常用 API。

    of

    可接收一個泛型對象或可變成泛型集合,構造一個 Stream 對象。

    private static void createStream(){
        Stream<String> stringStream = Stream.of("a","b","c");
    }
    

    empty

    創建一個空的 Stream 對象。

    concat

    連接兩個 Stream ,不改變其中任何一個 Steam 對象,返回一個新的 Stream 對象。

    private static void concatStream(){
        Stream<String> a = Stream.of("a","b","c");
        Stream<String> b = Stream.of("d","e");
        Stream<String> c = Stream.concat(a,b);
    }
    

    max

    一般用於求数字集合中的最大值,或者按實體中数字類型的屬性比較,擁有最大值的那個實體。它接收一個 Comparator<T>,上面也舉到這個例子了,它是一個函數式接口類型,專門用作定義兩個對象之間的比較,例如下面這個方法使用了 Integer::compareTo這個方法引用。

    private static void max(){
        Stream<Integer> integerStream = Stream.of(2, 2, 100, 5);
        Integer max = integerStream.max(Integer::compareTo).get();
        System.out.println(max);
    }
    

    當然,我們也可以自己定製一個 Comparator,順便複習一下 Lambda 表達式形式的方法引用。

    private static void max(){
        Stream<Integer> integerStream = Stream.of(2, 2, 100, 5);
        Comparator<Integer> comparator =  (x, y) -> (x.intValue() < y.intValue()) ? -1 : ((x.equals(y)) ? 0 : 1);
        Integer max = integerStream.max(comparator).get();
        System.out.println(max);
    }
    

    min

    與 max 用法一樣,只不過是求最小值。

    findFirst

    獲取 Stream 中的第一個元素。

    findAny

    獲取 Stream 中的某個元素,如果是串行情況下,一般都會返回第一個元素,并行情況下就不一定了。

    count

    返回元素個數。

    Stream<String> a = Stream.of("a", "b", "c");
    long x = a.count();
    

    peek

    建立一個通道,在這個通道中對 Stream 的每個元素執行對應的操作,對應 Consumer<T>的函數式接口,這是一個消費者函數式接口,顧名思義,它是用來消費 Stream 元素的,比如下面這個方法,把每個元素轉換成對應的大寫字母並輸出。

    private static void peek() {
        Stream<String> a = Stream.of("a", "b", "c");
        List<String> list = a.peek(e->System.out.println(e.toUpperCase())).collect(Collectors.toList());
    }
    

    forEach

    和 peek 方法類似,都接收一個消費者函數式接口,可以對每個元素進行對應的操作,但是和 peek 不同的是,forEach 執行之後,這個 Stream 就真的被消費掉了,之後這個 Stream 流就沒有了,不可以再對它進行後續操作了,而 peek操作完之後,還是一個可操作的 Stream 對象。

    正好藉著這個說一下,我們在使用 Stream API 的時候,都是一串鏈式操作,這是因為很多方法,比如接下來要說到的 filter方法等,返回值還是這個 Stream 類型的,也就是被當前方法處理過的 Stream 對象,所以 Stream API 仍然可以使用。

    private static void forEach() {
        Stream<String> a = Stream.of("a", "b", "c");
        a.forEach(e->System.out.println(e.toUpperCase()));
    }
    

    forEachOrdered

    功能與 forEach是一樣的,不同的是,forEachOrdered是有順序保證的,也就是對 Stream 中元素按插入時的順序進行消費。為什麼這麼說呢,當開啟并行的時候,forEachforEachOrdered的效果就不一樣了。

    Stream<String> a = Stream.of("a", "b", "c");
    a.parallel().forEach(e->System.out.println(e.toUpperCase()));
    

    當使用上面的代碼時,輸出的結果可能是 B、A、C 或者 A、C、B或者A、B、C,而使用下面的代碼,則每次都是 A、 B、C

    Stream<String> a = Stream.of("a", "b", "c");
    a.parallel().forEachOrdered(e->System.out.println(e.toUpperCase()));
    

    limit

    獲取前 n 條數據,類似於 MySQL 的limit,只不過只能接收一個參數,就是數據條數。

    private static void limit() {
        Stream<String> a = Stream.of("a", "b", "c");
        a.limit(2).forEach(e->System.out.println(e));
    }
    

    上述代碼打印的結果是 a、b。

    skip

    跳過前 n 條數據,例如下面代碼,返回結果是 c。

    private static void skip() {
        Stream<String> a = Stream.of("a", "b", "c");
        a.skip(2).forEach(e->System.out.println(e));
    }
    

    distinct

    元素去重,例如下面方法返回元素是 a、b、c,將重複的 b 只保留了一個。

    private static void distinct() {
        Stream<String> a = Stream.of("a", "b", "c","b");
        a.distinct().forEach(e->System.out.println(e));
    }
    

    sorted

    有兩個重載,一個無參數,另外一個有個 Comparator類型的參數。

    無參類型的按照自然順序進行排序,只適合比較單純的元素,比如数字、字母等。

    private static void sorted() {
        Stream<String> a = Stream.of("a", "c", "b");
        a.sorted().forEach(e->System.out.println(e));
    }
    

    有參數的需要自定義排序規則,例如下面這個方法,按照第二個字母的大小順序排序,最後輸出的結果是 a1、b3、c6。

    private static void sortedWithComparator() {
        Stream<String> a = Stream.of("a1", "c6", "b3");
        a.sorted((x,y)->Integer.parseInt(x.substring(1))>Integer.parseInt(y.substring(1))?1:-1).forEach(e->System.out.println(e));
    }
    

    為了更好的說明接下來的幾個 API ,我模擬了幾條項目中經常用到的類似數據,10條用戶信息。

    private static List<User> getUserData() {
        Random random = new Random();
        List<User> users = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            User user = new User();
            user.setUserId(i);
            user.setUserName(String.format("古時的風箏 %s 號", i));
            user.setAge(random.nextInt(100));
            user.setGender(i % 2);
            user.setPhone("18812021111");
            user.setAddress("無");
            users.add(user);
        }
        return users;
    }
    

    filter

    用於條件篩選過濾,篩選出符合條件的數據。例如下面這個方法,篩選出性別為 0,年齡大於 50 的記錄。

    private static void filter(){
        List<User> users = getUserData();
        Stream<User> stream = users.stream();
        stream.filter(user -> user.getGender().equals(0) && user.getAge()>50).forEach(e->System.out.println(e));
    
        /**
         *等同於下面這種形式 匿名內部類
         */
    //    stream.filter(new Predicate<User>() {
    //        @Override
    //        public boolean test(User user) {
    //            return user.getGender().equals(0) && user.getAge()>50;
    //        }
    //    }).forEach(e->System.out.println(e));
    }
    

    map

    map方法的接口方法聲明如下,接受一個 Function函數式接口,把它翻譯成映射最合適了,通過原始數據元素,映射出新的類型。

    <R> Stream<R> map(Function<? super T, ? extends R> mapper);
    

    Function的聲明是這樣的,觀察 apply方法,接受一個 T 型參數,返回一個 R 型參數。用於將一個類型轉換成另外一個類型正合適,這也是 map的初衷所在,用於改變當前元素的類型,例如將 Integer 轉為 String類型,將 DAO 實體類型,轉換為 DTO 實例類型。

    當然了,T 和 R 的類型也可以一樣,這樣的話,就和 peek方法沒什麼不同了。

    @FunctionalInterface
    public interface Function<T, R> {
    
        /**
         * Applies this function to the given argument.
         *
         * @param t the function argument
         * @return the function result
         */
        R apply(T t);
    }
    

    例如下面這個方法,應該是業務系統的常用需求,將 User 轉換為 API 輸出的數據格式。

    private static void map(){
        List<User> users = getUserData();
        Stream<User> stream = users.stream();
        List<UserDto> userDtos = stream.map(user -> dao2Dto(user)).collect(Collectors.toList());
    }
    
    private static UserDto dao2Dto(User user){
        UserDto dto = new UserDto();
        BeanUtils.copyProperties(user, dto);
        //其他額外處理
        return dto;
    }
    

    mapToInt

    將元素轉換成 int 類型,在 map方法的基礎上進行封裝。

    mapToLong

    將元素轉換成 Long 類型,在 map方法的基礎上進行封裝。

    mapToDouble

    將元素轉換成 Double 類型,在 map方法的基礎上進行封裝。

    flatMap

    這是用在一些比較特別的場景下,當你的 Stream 是以下這幾種結構的時候,需要用到 flatMap方法,用於將原有二維結構扁平化。

    1. Stream<String[]>
    2. Stream<Set<String>>
    3. Stream<List<String>>

    以上這三類結構,通過 flatMap方法,可以將結果轉化為 Stream<String>這種形式,方便之後的其他操作。

    比如下面這個方法,將List<List<User>>扁平處理,然後再使用 map或其他方法進行操作。

    private static void flatMap(){
        List<User> users = getUserData();
        List<User> users1 = getUserData();
        List<List<User>> userList = new ArrayList<>();
        userList.add(users);
        userList.add(users1);
        Stream<List<User>> stream = userList.stream();
        List<UserDto> userDtos = stream.flatMap(subUserList->subUserList.stream()).map(user -> dao2Dto(user)).collect(Collectors.toList());
    }
    

    flatMapToInt

    用法參考 flatMap,將元素扁平為 int 類型,在 flatMap方法的基礎上進行封裝。

    flatMapToLong

    用法參考 flatMap,將元素扁平為 Long 類型,在 flatMap方法的基礎上進行封裝。

    flatMapToDouble

    用法參考 flatMap,將元素扁平為 Double 類型,在 flatMap方法的基礎上進行封裝。

    collection

    在進行了一系列操作之後,我們最終的結果大多數時候並不是為了獲取 Stream 類型的數據,而是要把結果變為 List、Map 這樣的常用數據結構,而 collection就是為了實現這個目的。

    就拿 map 方法的那個例子說明,將對象類型進行轉換后,最終我們需要的結果集是一個 List<UserDto >類型的,使用 collect方法將 Stream 轉換為我們需要的類型。

    下面是 collect接口方法的定義:

    <R, A> R collect(Collector<? super T, A, R> collector);
    

    下面這個例子演示了將一個簡單的 Integer Stream 過濾出大於 7 的值,然後轉換成 List<Integer>集合,用的是 Collectors.toList()這個收集器。

    private static void collect(){
        Stream<Integer> integerStream = Stream.of(1,2,5,7,8,12,33);
        List<Integer> list = integerStream.filter(s -> s.intValue()>7).collect(Collectors.toList());
    }
    

    很多同學表示看不太懂這個 Collector是怎麼一個意思,來,我們看下面這段代碼,這是 collect的另一個重載方法,你可以理解為它的參數是按順序執行的,這樣就清楚了,這就是個 ArrayList 從創建到調用 addAll方法的一個過程。

    private static void collect(){
        Stream<Integer> integerStream = Stream.of(1,2,5,7,8,12,33);
        List<Integer> list = integerStream.filter(s -> s.intValue()>7).collect(ArrayList::new, ArrayList::add,
                ArrayList::addAll);
    }
    

    我們在自定義 Collector的時候其實也是這個邏輯,不過我們根本不用自定義, Collectors已經為我們提供了很多拿來即用的收集器。比如我們經常用到Collectors.toList()Collectors.toSet()Collectors.toMap()。另外還有比如Collectors.groupingBy()用來分組,比如下面這個例子,按照 userId 字段分組,返回以 userId 為key,List 為value 的 Map,或者返回每個 key 的個數。

    // 返回 userId:List<User>
    Map<String,List<User>> map = user.stream().collect(Collectors.groupingBy(User::getUserId));
    
    // 返回 userId:每組個數
    Map<String,Long> map = user.stream().collect(Collectors.groupingBy(User::getUserId,Collectors.counting()));
    

    toArray

    collection是返回列表、map 等,toArray是返回數組,有兩個重載,一個空參數,返回的是 Object[]

    另一個接收一個 IntFunction<R>類型參數。

    @FunctionalInterface
    public interface IntFunction<R> {
    
        /**
         * Applies this function to the given argument.
         *
         * @param value the function argument
         * @return the function result
         */
        R apply(int value);
    }
    

    比如像下面這樣使用,參數是 User[]::new也就是new 一個 User 數組,長度為最後的 Stream 長度。

    private static void toArray() {
        List<User> users = getUserData();
        Stream<User> stream = users.stream();
        User[] userArray = stream.filter(user -> user.getGender().equals(0) && user.getAge() > 50).toArray(User[]::new);
    }
    

    reduce

    它的作用是每次計算的時候都用到上一次的計算結果,比如求和操作,前兩個數的和加上第三個數的和,再加上第四個數,一直加到最後一個數位置,最後返回結果,就是 reduce的工作過程。

    private static void reduce(){
        Stream<Integer> integerStream = Stream.of(1,2,5,7,8,12,33);
        Integer sum = integerStream.reduce(0,(x,y)->x+y);
        System.out.println(sum);
    }
    

    另外 Collectors好多方法都用到了 reduce,比如 groupingByminBymaxBy等等。

    并行 Stream

    Stream 本質上來說就是用來做數據處理的,為了加快處理速度,Stream API 提供了并行處理 Stream 的方式。通過 users.parallelStream()或者users.stream().parallel() 的方式來創建并行 Stream 對象,支持的 API 和普通 Stream 幾乎是一致的。

    并行 Stream 默認使用 ForkJoinPool線程池,當然也支持自定義,不過一般情況下沒有必要。ForkJoin 框架的分治策略與并行流處理正好契合。

    雖然并行這個詞聽上去很厲害,但並不是所有情況使用并行流都是正確的,很多時候完全沒這個必要。

    什麼情況下使用或不應使用并行流操作呢?

    1. 必須在多核 CPU 下才使用并行 Stream,聽上去好像是廢話。
    2. 在數據量不大的情況下使用普通串行 Stream 就可以了,使用并行 Stream 對性能影響不大。
    3. CPU 密集型計算適合使用并行 Stream,而 IO 密集型使用并行 Stream 反而會更慢。
    4. 雖然計算是并行的可能很快,但最後大多數時候還是要使用 collect合併的,如果合併代價很大,也不適合用并行 Stream。
    5. 有些操作,比如 limit、 findFirst、forEachOrdered 等依賴於元素順序的操作,都不適合用并行 Stream。

    最後

    Java 25 周歲了,有多少同學跟我一樣在用 Java 8,還有多少同學再用更早的版本,請說出你的故事。

    壯士且慢,先給點個贊吧,總是被白嫖,身體吃不消!

    我是風箏,公眾號「古時的風箏」。一個兼具深度與廣度的程序員鼓勵師,一個本打算寫詩卻寫起了代碼的田園碼農!你可選擇現在就關注我,或者看看歷史文章再關注也不遲。

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

    【其他文章推薦】

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

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

    ※回頭車貨運收費標準

    ※推薦評價好的iphone維修中心

    ※超省錢租車方案

  • 業界也認了 不是所有生質能都是碳中性 歐盟面臨減碳新挑戰

    環境資訊中心綜合外電;姜唯 編譯;林大利 審校

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

    【其他文章推薦】

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

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

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

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

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

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

  • 日企研發寒天製的透明可食薄膜 成塑膠減量新選擇

    文:宋瑞文

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

    【其他文章推薦】

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

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

    ※台北網頁設計公司全省服務真心推薦

    ※想知道最厲害的網頁設計公司"嚨底家"!

    ※推薦評價好的iphone維修中心

  • 伊朗火災與爆炸頻傳 伊斯法罕省電廠也傳事故

    摘錄自2020年7月19日中央社報導

    伊朗中部伊斯法罕省一座電廠今天(19日)發生爆炸。所幸沒有人員傷亡。電廠過了約兩小時恢復正常運作,伊斯法罕省供電不受影響。

    伊朗各地的軍事與民用設施近幾週頻傳火災與爆炸事故,讓伊朗境內人士懷疑可能是宿敵以色列在搞破壞。以色列指控伊朗試圖發展核彈,伊朗則堅稱本身的核子計畫完全是為了和平目的。

    首都德黑蘭(Tehran)6月下旬就發生兩起爆炸,其中一起發生在軍事用地附近,另一起衛生中心的火災則奪走19人性命。本月稍早,伊朗南部一座造船廠、德黑蘭南方一座工廠,以及伊朗中部的納坦茲(Natanz)核設施,也分別發生火災或爆炸事故。其中工廠事故奪走兩人性命。伊朗當局形容納坦茲核設施起火是意外,他們基於「安全理由」不公布事發原因及細節。

    土地利用
    能源轉型
    國際新聞
    伊朗
    火力發電廠
    火災
    災害
    核能

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

    【其他文章推薦】

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

    台北網頁設計公司這麼多該如何選擇?

    ※智慧手機時代的來臨,RWD網頁設計為架站首選

    ※評比南投搬家公司費用收費行情懶人包大公開

    ※回頭車貨運收費標準

  • 可愛的負擔…美國爆發「花栗鼠之亂」 到處打洞居民快瘋了

    可愛的負擔…美國爆發「花栗鼠之亂」 到處打洞居民快瘋了

    摘錄自2020年7月19日自由時報報導

    據《福斯新聞》報導,緬因州內陸漁業與野生動植物小型哺乳動物專家韋伯(Shevenell Webb)表示,去(2019)年秋天產出大量的橡實,讓花栗鼠在春季繁衍後代時在地面上到處都可以找到食物,就這樣造成如今的花栗鼠嬰兒潮。韋伯說,花栗鼠真的很可愛,但同時也是破壞狂,不僅會挖洞破壞草坪和花園,有時還會溜進屋內造反。

    佛蒙特州魚類和野生動物部門野生動植物多樣性主任帕倫(Steven Parren)則說,他監控的地區有太多橡實,以至於囓齒動物無法在冬天把它們全都藏起來,到了今(2020)年春天地面上還留有很多橡實,除了花栗鼠之外也造成松鼠、兔子等族群增加。

    不過,人們不用太擔心這次的花栗鼠狂潮,因為小型哺乳類動物族群本來就很容易出現物種激增的事件,隨後就會迎來一陣消寂,更何況花栗鼠很容易成為貓頭鷹、老鷹、蛇類、狐狸和浣熊的獵物,野生花栗鼠平均只有3年壽命,比最高壽命少了許多。

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

    生物多樣性
    國際新聞
    美國
    食物鏈
    生態平衡
    處變不驚──與野生動物相遇
    人與動物衝突事件簿

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

    【其他文章推薦】

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

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

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

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

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

    ※超省錢租車方案