在上一篇文章中，我們詳細的介紹了Java，那麼這些Class文件是如何被加載到內存，由虛擬機來直接使用的呢？這就是本篇博客將要介紹的——類加載過程。

1、類的生命周期

　　類從被加載到虛擬機內存開始，到卸載出內存為止，其聲明周期流程如下：

　　

　　上圖中紅色的5個部分（加載、驗證、準備、初始化、卸載）順序是確定的，也就是說，類的加載過程必須按照這種順序按部就班的開始。這裏的“開始”不是按部就班的“進行”或者“完成”，因為這些階段通常是互相交叉混合的進行的，通常會在一個階段執行過程中調用另一個階段。

2、加載

　　“加載”階段是“類加載”生命周期的第一個階段。在加載階段，虛擬機要完成下面三件事：

　　①、通過一個類的全限定名來獲取定義此類的二進制字節流。

　　②、將這個字節流所代表的靜態存儲結構轉化為方法區的運行時數據結構。

　　③、在Java堆中生成一個代表這個類的java.lang.Class對象，作為方法區這些數據的訪問入口。

　　PS：類的全限定名可以理解為這個類存放的絕對路徑。方法區是JDK1.7以前定義的運行時數據區，而在JDK1.8以後改為元數據區（Metaspace），主要用於存放被Java虛擬機加載的類信息、常量、靜態變量、即時編譯器編譯后的代碼等數據。詳情可以參考這邊該系列的第二篇文章——。

　　另外，我們看第一點——通過類的權限定名來獲取定義此類的二進制流，這裏並沒有明確指明要從哪裡獲取以及怎樣獲取，也就是說並沒有明確規定一定要我們從一個 Class 文件中獲取。基於此，在Java的發展過程中，充滿創造力的開發人員在這個舞台上玩出了各種花樣：

　　1、從 ZIP 包中讀取。這稱為後面的 JAR、EAR、WAR 格式的基礎。

　　2、從網絡中獲取。比較典型的應用就是 Applet。

　　3、運行時計算生成。這就是動態代理技術。

　　4、由其它文件生成。比如 JSP 應用。

　　5、從數據庫中讀取。

　　加載階段完成后，虛擬機外部的二進制字節流就按照虛擬機所需的格式存儲在方法區中，然後在Java堆中實例化一個 java.lang.Class 類的對象，這個對象將作為程序訪問方法區中這些類型數據的外部接口。

　　注意，加載階段與連接階段的部分內容（如一部分字節碼文件的格式校驗）是交叉進行的，加載階段尚未完成，連接階段可能已經開始了。

3、驗證

　　驗證是連接階段的第一步，作用是為了確保 Class 文件的字節流中包含的信息符合當前虛擬機的要求，並且不會危害虛擬機自身的安全。

　　我們說Java語言本身是相對安全，因為編譯器的存在，純粹的Java代碼要訪問數組邊界外的數據、跳轉到不存在的代碼行之類的，是要被編譯器拒絕的。但是前面我們也說過，Class 文件不一定非要從Java源碼編譯過來，可以使用任何途徑，包括你很牛逼，直接用十六進制編輯器來編寫 Class 文件。

　　所以，如果虛擬機不檢查輸入的字節流，將會載入有害的字節流而導致系統崩潰。但是虛擬機規範對於檢查哪些方面，何時檢查，怎麼檢查都沒有明確的規定，不同的虛擬機實現方式可能都會有所不同，但是大致都會完成下面四個方面的檢查。

①、文件格式驗證

　　校驗字節流是否符合Class文件格式的規範，並且能夠被當前版本的虛擬機處理。

　　一、是否以魔數 0xCAFEBABE 開頭。

　　二、主、次版本號是否是當前虛擬機處理範圍之內。

　　三、常量池的常量中是否有不被支持的常量類型（檢查常量tag標誌）

　　四、指向常量的各種索引值中是否有指向不存在的常量或不符合類型的常量。

　　五、CONSTANT_Utf8_info 型的常量中是否有不符合 UTF8 編碼的數據。

　　六、Class 文件中各個部分及文件本身是否有被刪除的或附加的其他信息。

　　以上是一部分校驗內容，當然遠不止這些。經過這些校驗后，字節流才會進入內存的方法區中存儲，接下來後面的三個階段校驗都是基於方法區的存儲結構進行的。

②、元數據驗證

　　第二個階段主要是對字節碼描述的信息進行語義分析，以保證其描述的信息符合Java語言規範要求。

　　一、這個類是否有父類（除了java.lang.Object 類之外，所有的類都應當有父類）。

　　二、這個類的父類是否繼承了不允許被繼承的類（被final修飾的類）。

　　三、如果這個類不是抽象類，是否實現了其父類或接口之中要求實現的所有普通方法。

　　四、類中的字段、方法是否與父類產生了矛盾（例如覆蓋了父類的final字段、或者出現不符合規則的重載）

③、字節碼驗證

　　第三個階段字節碼驗證是整個驗證階段中最複雜的，主要是進行數據流和控制流分析。該階段將對類的方法進行分析，保證被校驗的方法在運行時不會做出危害虛擬機安全的行為。

　　一、保證任意時刻操作數棧中的數據類型與指令代碼序列都能配合工作。例如不會出現在操作數棧中放置了一個 int 類型的數據，使用時卻按照 long 類型來加載到本地變量表中。

　　二、保證跳轉指令不會跳轉到方法體以外的字節碼指令中。

　　三、保證方法體中的類型轉換是有效的。比如把一個子類對象賦值給父類數據類型，這是安全的。但是把父類對象賦值給子類數據類型，甚至賦值給完全不相干的類型，這就是不合法的。

④、符號引用驗證

　　符號引用驗證主要是對類自身以外（常量池中的各種符號引用）的信息進行匹配性的校驗，通常需要校驗如下內容：

　　一、符號引用中通過字符串描述的全限定名是否能夠找到相應的類。

　　二、在指定類中是否存在符合方法的字段描述符及簡單名稱所描述的方法和字段。

　　三、符號引用中的類、字段和方法的訪問性（private、protected、public、default）是否可以被當前類訪問。

4、準備

　　準備階段是正式為類變量分配內存並設置類變量初始值的階段，這些內存是在方法區中進行分配。

　　注意：

　　一、上面說的是類變量，也就是被 static 修飾的變量，不包括實例變量。實例變量會在對象實例化時隨着對象一起分配在堆中。

　　二、初始值，指的是一些數據類型的默認值。基本的數據類型初始值如下（引用類型的初始值為null）：

　　

 

 　　比如，定義 public static int value = 123 。那麼在準備階段過後，value 的值是 0 而不是 123,把 value 賦值為123 是在程序被編譯后，存放在類的構造器方法之中，是在初始化階段才會被執行。但是有一種特殊情況，通過final 修飾的屬性，比如 定義 public final static int value = 123，那麼在準備階段過後，value 就被賦值為123了。

5、解析

　　解析階段是虛擬機將常量池中的符號引用替換為直接引用的過程。

　　符號引用（Symbolic References）：符號引用以一組符號來描述所引用的目標，符號可以是任何形式的字面量，只要使用時能無歧義的定位到目標即可。符號引用與虛擬機實現的內存布局無關，引用的目標不一定已經加載到內存中。

　　直接引用（Direct References）：直接引用可以是直接指向目標的指針、相對偏移量或是一個能間接定位到目標的句柄。直接引用是與虛擬機實現內存布局相關的，同一個符號引用在不同虛擬機實例上翻譯出來的直接引用一般不會相同。如果有了直接引用，那麼引用的目標必定已經在內存中存在。

　　解析動作主要針對類或接口、字段、類方法、接口方法四類符號引用，分別對應於常量池的 CONSTANT_Class_info、CONSTANT_Fieldref_info、CONSTANT_Methodref_info、CONSTANTS_InterfaceMethodref_info四種類型常量。

6、初始化

 　　初始化階段是類加載階段的最後一步，前面過程中，除第一個加載階段可以通過用戶自定義類加載器參与之外，其餘過程都是完全由虛擬機主導和控制。而到了初始化階段，則開始真正執行類中定義的Java程序代碼（或者說是字節碼）。

　　在前面介紹的準備階段中，類變量已經被賦值過初始值了，而初始化階段，則根據程序員的編碼去初始化變量和資源。

　　換句話來說，初始化階段是執行類構造器<clinit>() 方法的過程。

　　①、<clinit>() 方法 是由編譯器自動收集類中的所有類變量的賦值動作和靜態語句塊（static{}）中的語句合併產生的，編譯器收集的順序是由語句在源文件中出現的順序所決定的，靜態語句塊中只能訪問到定義在靜態語句塊之前的變量，定義在它之後的變量，在前面的靜態語句塊中可以賦值，但是不能訪問。

　　比如如下代碼會報錯：

　　

 

 　　但是你把第 14 行代碼放到 static 靜態代碼塊的上面就不會報錯了。或者不改變代碼順序，將第 11 行代碼移除，也不會報錯。

　　②、<clinit>() 方法與類的構造函數（或者說是實例構造器<init>()方法）不同，它不需要显示的調用父類構造器，虛擬機會保證在子類的<init>()方法執行之前，父類的<init>()方法已經執行完畢。因此虛擬機中第一個被執行的<init>()方法的類肯定是 java.lang.Object。

　　③、由於父類的<clinit>() 方法先執行，所以父類中定義的靜態語句塊要優先於子類的變量賦值操作。

　　④、<clinit>() 方法對於接口來說並不是必須的，如果一個類中沒有靜態語句塊，也沒有對變量的賦值操作，那麼編譯器可以不為這個類生成<clinit>() 方法。

　　⑤、接口中不能使用靜態語句塊，但仍然有變量初始化的賦值操作，因此接口與類一樣都會生成<clinit>() 方法。但接口與類不同的是，執行接口中的<clinit>() 方法不需要先執行父接口的<clinit>() 方法。只有當父接口中定義的變量被使用時，父接口才會被初始化。

　　⑥、接口的實現類在初始化時也一樣不會執行接口的<clinit>() 方法。

　　⑦、虛擬機會保證一個類的<clinit>() 方法在多線程環境中被正確的加鎖和同步。如果多個線程同時去初始化一個類，那麼只會有一個線程去執行這個類的<clinit>() 方法，其他的線程都需要阻塞等待，直到活動線程執行<clinit>() 方法完畢。如果在一個類的<clinit>() 方法中有很耗時的操作，那麼可能造成多個進程的阻塞。

　　比如對於如下代碼：

package com.yb.carton.controller;

/**
 * Create by YSOcean
 */
public class ClassLoadInitTest {


    static class Hello{
        static {
            if(true){
                System.out.println(Thread.currentThread().getName() + "init");
                while(true){}
            }
        }
    }

    public static void main(String[] args) {
        new Thread(()->{
            System.out.println(Thread.currentThread().getName()+"start");
            Hello h1 = new Hello();
            System.out.println(Thread.currentThread().getName()+"run over");
        }).start();


        new Thread(()->{
            System.out.println(Thread.currentThread().getName()+"start");
            Hello h2 = new Hello();
            System.out.println(Thread.currentThread().getName()+"run over");
        }).start();
    }

}

View Code

　　運行結果如下：

　　

 

 　　線程1搶到了執行<clinit>() 方法，但是該方法是一個死循環，線程2將一直阻塞等待。

　　知道了類的初始化過程，那麼類的初始化何時被觸發呢？JVM大概規定了如下幾種情況：

　　①、當虛擬機啟動時，初始化用戶指定的類。

　　②、當遇到用以新建目標類實例的 new 指令時，初始化 new 指定的目標類。

　　③、當遇到調用靜態方法的指令時，初始化該靜態方法所在的類。

　　④、當遇到訪問靜態字段的指令時，初始化該靜態字段所在的類。

　　⑤、子類的初始化會觸發父類的初始化。

　　⑥、如果一個接口定義了 default 方法，那麼直接實現或間接實現該接口的類的初始化，會觸發該接口的初始化。

　　⑦、使用反射 API 對某個類進行反射調用時，會初始化這個類。

　　⑧、當初次調用 MethodHandle 實例時，初始化該 MethodHandle 指向的方法所在的類。

 

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

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

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

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

文章來源：

一、前言

日常開發過程有時需要在應用啟動之後加載某些資源，或者在應用關閉之前釋放資源。Spring 框架提供相關功能，圍繞 Spring Bean 生命周期，可以在 Bean 創建過程初始化資源，以及銷毀 Bean 過程釋放資源。Spring 提供多種不同的方式初始化/銷毀 Bean，如果同時使用這幾種方式，Spring 如何處理這幾者之間的順序？

有沒有覺得標題很熟悉，沒錯標題模仿二哥 「@沉默王二」 文章。

二、姿勢剖析

首先我們先來回顧一下 Spring 初始化/銷毀 Bean 幾種方式，分別為：

• init-method/destroy-method
• InitializingBean/DisposableBean
• @PostConstruct/@PreDestroy
• ContextStartedEvent/ContextClosedEvent

PS: 其實還有一種方式，就是繼承 Spring Lifecycle 接口。不過這種方式比較繁瑣，這裏就不再分析。

2.1、init-method/destroy-method

這種方式在配置文件文件指定初始化/銷毀方法。XML 配置如下

<bean id="demoService" class="com.dubbo.example.provider.DemoServiceImpl"  destroy-method="close"  init-method="initMethod"/>

或者也可以使用註解方式配置：

@Configurable
public class AppConfig {

    @Bean(initMethod = "init", destroyMethod = "destroy")
    public HelloService hello() {
        return new HelloService();
    }
}

還記得剛開始接觸學習 Spring 框架，使用就是這種方式。

2.2、InitializingBean/DisposableBean

這種方式需要繼承 Spring 接口 InitializingBean/DisposableBean，其中 InitializingBean 用於初始化動作，而 DisposableBean 用於銷毀之前清理動作。使用方式如下：

@Service
public class HelloService implements InitializingBean, DisposableBean {
    
    @Override
    public void destroy() throws Exception {
        System.out.println("hello destroy...");
    }

    @Override
    public void afterPropertiesSet() throws Exception {
        System.out.println("hello init....");
    }
}

2.3、@PostConstruct/@PreDestroy

這種方式相對於上面兩種方式來說，使用方式最簡單，只需要在相應的方法上使用註解即可。使用方式如下：

@Service
public class HelloService {


    @PostConstruct
    public void init() {
        System.out.println("hello @PostConstruct");
    }

    @PreDestroy
    public void PreDestroy() {
        System.out.println("hello @PreDestroy");
    }
}

這裏踩過一個坑，如果使用 JDK9 之後版本 ，@PostConstruct/@PreDestroy 需要使用 maven 單獨引入 javax.annotation-api，否者註解不會生效。

2.4、ContextStartedEvent/ContextClosedEvent

這種方式使用 Spring 事件機制，日常業務開發比較少見，常用與框架集成中。Spring 啟動之後將會發送 ContextStartedEvent 事件，而關閉之前將會發送 ContextClosedEvent 事件。我們需要繼承 Spring ApplicationListener 才能監聽以上兩種事件。

@Service
public class HelloListener implements ApplicationListener {

    @Override
    public void onApplicationEvent(ApplicationEvent event) {
        if(event instanceof ContextClosedEvent){
            System.out.println("hello ContextClosedEvent");
        }else if(event instanceof ContextStartedEvent){
            System.out.println("hello ContextStartedEvent");
        }

    }
}

也可以使用 @EventListener註解，使用方式如下：

public class HelloListenerV2 {
    
    @EventListener(value = {ContextClosedEvent.class, ContextStartedEvent.class})
    public void receiveEvents(ApplicationEvent event) {
        if (event instanceof ContextClosedEvent) {
            System.out.println("hello ContextClosedEvent");
        } else if (event instanceof ContextStartedEvent) {
            System.out.println("hello ContextStartedEvent");
        }
    }
}

PS:只有調用 ApplicationContext#start 才會發送 ContextStartedEvent。若不想這麼麻煩，可以監聽 ContextRefreshedEvent 事件代替。一旦 Spring 容器初始化完成，就會發送 ContextRefreshedEvent。

三、綜合使用

回顧完上面幾種方式，這裏我們綜合使用上面的四種方式，來看下 Spring 內部的處理順序。在看結果之前，各位讀者大人可以猜測下這幾種方式的執行順序。

public class HelloService implements InitializingBean, DisposableBean {


    @PostConstruct
    public void init() {
        System.out.println("hello @PostConstruct");
    }

    @PreDestroy
    public void PreDestroy() {
        System.out.println("hello @PreDestroy");
    }

    @Override
    public void destroy() throws Exception {
        System.out.println("bye DisposableBean...");
    }

    @Override
    public void afterPropertiesSet() throws Exception {
        System.out.println("hello InitializingBean....");
    }

    public void xmlinit(){
        System.out.println("hello xml-init...");
    }

    public void xmlDestory(){
        System.out.println("bye xmlDestory...");
    }

    @EventListener(value = {ContextClosedEvent.class, ContextStartedEvent.class})
    public void receiveEvents(ApplicationEvent event) {
        if (event instanceof ContextClosedEvent) {
            System.out.println("bye ContextClosedEvent");
        } else if (event instanceof ContextStartedEvent) {
            System.out.println("hello ContextStartedEvent");
        }
    }

}

xml 配置方式如下：

    <context:annotation-config />
    <context:component-scan base-package="com.dubbo.example.demo"/>
    
    <bean class="com.dubbo.example.demo.HelloService" init-method="xmlinit" destroy-method="xmlDestory"/>

應用啟動方法如下：

ClassPathXmlApplicationContext context = new ClassPathXmlApplicationContext("spring/dubbo-provider.xml");
context.start();
context.close();

程序輸出結果如下所示：

最後採用圖示說明總結以上結果：

四、源碼解析

不知道各位讀者有沒有猜對這幾種方式的執行順序，下面我們就從源碼角度解析 Spring 內部處理的順序。

4.1、初始化過程

使用 ClassPathXmlApplicationContext 啟動 Spring 容器，將會調用 refresh 方法初始化容器。初始化過程將會創建 Bean 。最後當一切準備完畢，將會發送 ContextRefreshedEvent。當容器初始化完畢，調用 context.start() 就發送 ContextStartedEvent 事件。

refresh 方法源碼如下：

public void refresh() throws BeansException, IllegalStateException {
    synchronized (this.startupShutdownMonitor) {
            //... 忽略無關代碼

            // 初始化所有非延遲初始化的 Bean
            finishBeanFactoryInitialization(beanFactory);

            // 發送 ContextRefreshedEvent
            finishRefresh();

            //... 忽略無關代碼
    }
}

一路跟蹤 finishBeanFactoryInitialization 源碼，直到 AbstractAutowireCapableBeanFactory#initializeBean，源碼如下：

protected Object initializeBean(final String beanName, final Object bean, RootBeanDefinition mbd) {
    Object wrappedBean = bean;
    if (mbd == null || !mbd.isSynthetic()) {
        // 調用 BeanPostProcessor#postProcessBeforeInitialization 方法
        wrappedBean = applyBeanPostProcessorsBeforeInitialization(wrappedBean, beanName);
    }

    try {
        // 初始化 Bean
        invokeInitMethods(beanName, wrappedBean, mbd);
    }
    catch (Throwable ex) {
        throw new BeanCreationException(
                (mbd != null ? mbd.getResourceDescription() : null),
                beanName, "Invocation of init method failed", ex);
    }
}

BeanPostProcessor 將會起着攔截器的作用，一旦 Bean 符合條件，將會執行一些處理。這裏帶有 @PostConstruct 註解的 Bean 都將會被 CommonAnnotationBeanPostProcessor 類攔截，內部將會觸發 @PostConstruct 標註的方法。

接着執行 invokeInitMethods ，方法如下:

protected void invokeInitMethods(String beanName, final Object bean, RootBeanDefinition mbd)
        throws Throwable {

    boolean isInitializingBean = (bean instanceof InitializingBean);
    if (isInitializingBean && (mbd == null || !mbd.isExternallyManagedInitMethod("afterPropertiesSet"))) {
        // 省略無關代碼
        // 如果是 Bean 繼承 InitializingBean，將會執行  afterPropertiesSet 方法
        ((InitializingBean) bean).afterPropertiesSet();
    }

    if (mbd != null) {
        String initMethodName = mbd.getInitMethodName();
        if (initMethodName != null && !(isInitializingBean && "afterPropertiesSet".equals(initMethodName)) &&
                !mbd.isExternallyManagedInitMethod(initMethodName)) {
            // 執行 XML 定義 init-method
            invokeCustomInitMethod(beanName, bean, mbd);
        }
    }
}

如果 Bean 繼承 InitializingBean 接口，將會執行 afterPropertiesSet 方法，另外如果在 XML 中指定了 init-method ，也將會觸發。

上面源碼其實都是圍繞着 Bean 創建的過程，當所有 Bean 創建完成之後，調用 context#start 將會發送 ContextStartedEvent 。這裏源碼比較簡單，如下：

public void start() {
    getLifecycleProcessor().start();
    publishEvent(new ContextStartedEvent(this));
}

4.2、銷毀過程

調用 ClassPathXmlApplicationContext#close 方法將會關閉容器，具體邏輯將會在 doClose 方法執行。

doClose 這個方法首先發送 ContextClosedEvent，然再后開始銷毀 Bean。

靈魂拷問:如果我們顛倒上面兩者順序，結果會一樣嗎？

doClose 源碼如下：

protected void doClose() {
    if (this.active.get() && this.closed.compareAndSet(false, true)) {
        // 省略無關代碼

        try {
            // Publish shutdown event.
            publishEvent(new ContextClosedEvent(this));
        }
        catch (Throwable ex) {
            logger.warn("Exception thrown from ApplicationListener handling ContextClosedEvent", ex);
        }


        // 銷毀 Bean
        destroyBeans();

        // 省略無關代碼
    }
}

destroyBeans 最終將會執行 DisposableBeanAdapter#destroy，@PreDestroy、DisposableBean、destroy-method 三者定義的方法都將會在內部被執行。

首先執行 DestructionAwareBeanPostProcessor#postProcessBeforeDestruction，這裏方法類似與上面 BeanPostProcessor。

@PreDestroy 註解將會被 CommonAnnotationBeanPostProcessor 攔截，這裏類同時也繼承了 DestructionAwareBeanPostProcessor。

最後如果 Bean 為 DisposableBean 的子類，將會執行 destroy 方法，如果在 xml 定義了 destroy-method 方法，該方法也會被執行。

public void destroy() {
    if (!CollectionUtils.isEmpty(this.beanPostProcessors)) {
        for (DestructionAwareBeanPostProcessor processor : this.beanPostProcessors) {
            processor.postProcessBeforeDestruction(this.bean, this.beanName);
        }
    }

    if (this.invokeDisposableBean) {
        // 省略無關代碼
        // 如果 Bean 繼承 DisposableBean，執行 destroy 方法
        ((DisposableBean) bean).destroy();
        
    }

    if (this.destroyMethod != null) {
        // 執行 xml 指定的  destroy-method 方法
        invokeCustomDestroyMethod(this.destroyMethod);
    }
    else if (this.destroyMethodName != null) {
        Method methodToCall = determineDestroyMethod();
        if (methodToCall != null) {
            invokeCustomDestroyMethod(methodToCall);
        }
    }
}

五、總結

init-method/destroy-method 這種方式需要使用 XML 配置文件或單獨註解配置類，相對來說比較繁瑣。而InitializingBean/DisposableBean 這種方式需要單獨繼承 Spring 的接口實現相關方法。@PostConstruct/@PreDestroy 這種註解方式使用方式簡單，代碼清晰，比較推薦使用這種方式。

另外 ContextStartedEvent/ContextClosedEvent 這種方式比較適合在一些集成框架使用，比如 Dubbo 2.6.X 優雅停機就是用改機制。

六、Spring 歷史文章推薦

歡迎關注我的公眾號：程序通事，獲得日常乾貨推送。如果您對我的專題內容感興趣，也可以關注我的博客：

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

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

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

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

本文源碼： ||

一、生活場景

1、場景描述

電競是遊戲比賽達到“競技”層面的體育項目。利用电子設備作為運動器械進行的、人與人之間的智力對抗運動。通過電競，可以提高人的反應能力、協調能力、團隊精神等。但是不同人群的對電競的持有的觀念不一樣，有的人認為電競就是沉迷網絡，持反對態度，而有的人就比較贊同。下面基於訪問者模式來描述該場景。

2、場景圖解

3、代碼實現

public class C01_InScene {
    public static void main(String[] args) {
        DataSet dataSet = new DataSet() ;
        dataSet.addCrowd(new Youth());
        dataSet.addCrowd(new MiddleAge());
        CrowdView crowdView = new Against() ;
        dataSet.display(crowdView);
        crowdView = new Approve() ;
        dataSet.display(crowdView);
    }
}
/**
 * 雙分派,不同人群管理
 */
abstract class Crowd {
    abstract void accept(CrowdView action);
}
class Youth extends Crowd {
    @Override
    public void accept(CrowdView view) {
        view.getYouthView(this);
    }
}
class MiddleAge extends Crowd {
    @Override
    public void accept(CrowdView view) {
        view.getMiddleAgeView (this);
    }
}
/**
 * 不同人群觀念的管理
 */
abstract class CrowdView {
    // 青年人觀念
    abstract void getYouthView (Youth youth);
    // 中年人觀念
    abstract void getMiddleAgeView (MiddleAge middleAge);
}
class Approve extends CrowdView {
    @Override
    public void getYouthView(Youth youth) {
        System.out.println("青年人贊同電競");
    }
    @Override
    public void getMiddleAgeView(MiddleAge middleAge) {
        System.out.println("中年人贊同電競");
    }
}
class Against extends CrowdView {
    @Override
    public void getYouthView(Youth youth) {
        System.out.println("青年人反對電競");
    }
    @Override
    public void getMiddleAgeView(MiddleAge middleAge) {
        System.out.println("中年人反對電競");
    }
}
/**
 * 提供一個數據集合
 */
class DataSet {
    private List<Crowd> crowdList = new ArrayList<>();
    public void addCrowd (Crowd crowd) {
        crowdList.add(crowd);
    }
    public void display(CrowdView crowdView) {
        for(Crowd crowd : crowdList) {
            crowd.accept(crowdView);
        }
    }
}

二、訪問者模式

1、基礎概念

訪問者模式是對象的行為模式，把作用於數據結構的各元素的操作封裝，操作之間沒有關聯。可以在不改變數據結構的前提下定義作用於這些元素的不同的操作。主要將數據結構與數據操作分離，解決數據結構和操作耦合問題核心原理：被訪問的類裏面加對外提供接待訪問者的接口。

2、模式圖解

3、核心角色

• 抽象訪問者角色

聲明多個方法操作，具體訪問者角色需要實現的接口。

• 具體訪問者角色

實現抽象訪問者所聲明的接口，就是各個訪問操作。

• 抽象節點角色

聲明接受操作，接受訪問者對象作為參數。

• 具體節點角色

實現抽象節點所規定的具體操作。

• 結構對象角色

能枚舉結構中的所有元素，可以提供一個高層的接口，用來允許訪問者對象訪問每一個元素。

4、源碼實現

public class C02_Visitor {
    public static void main(String[] args) {
        ObjectStructure obs = new ObjectStructure();
        obs.add(new NodeA());
        obs.add(new NodeB());
        Visitor visitor = new VisitorA();
        obs.doAccept(visitor);
    }
}
/**
 * 抽象訪問者角色
 */
interface Visitor {
    /**
     * NodeA的訪問操作
     */
    void visit(NodeA node);
    /**
     * NodeB的訪問操作
     */
    void visit(NodeB node);
}
/**
 * 具體訪問者角色
 */
class VisitorA implements Visitor {
    @Override
    public void visit(NodeA node) {
        node.operationA() ;
    }
    @Override
    public void visit(NodeB node) {
        node.operationB() ;
    }
}
class VisitorB implements Visitor {
    @Override
    public void visit(NodeA node) {
        node.operationA() ;
    }
    @Override
    public void visit(NodeB node) {
        node.operationB() ;
    }
}
/**
 * 抽象節點角色
 */
abstract class Node {
    /**
     * 接收訪問者
     */
    abstract void accept(Visitor visitor);
}
/**
 * 具體節點角色
 */
class NodeA extends Node{
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }
    public void operationA(){
        System.out.println("NodeA.operationA");
    }
}
class NodeB extends Node{
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }
    public void operationB(){
        System.out.println("NodeB.operationB");
    }
}
/**
 * 結構對象角色類
 */
class ObjectStructure {
    private List<Node> nodes = new ArrayList<>();
    public void detach(Node node) {
        nodes.remove(node);
    }
    public void add(Node node){
        nodes.add(node);
    }
    public void doAccept(Visitor visitor){
        for(Node node : nodes) {
            node.accept(visitor);
        }
    }
}

三、Spring框架應用

1、Bean結構的訪問

BeanDefinitionVisitor類，遍歷bean的各個屬性；接口 BeanDefinition，定義Bean的各樣信息，比如屬性值、構造方法、參數等等。這裏封裝操作bean結構的相關方法，但卻沒有改變bean的結構。

2、核心代碼塊

public class BeanDefinitionVisitor {
    public void visitBeanDefinition(BeanDefinition beanDefinition) {
        this.visitParentName(beanDefinition);
        this.visitBeanClassName(beanDefinition);
        this.visitFactoryBeanName(beanDefinition);
        this.visitFactoryMethodName(beanDefinition);
        this.visitScope(beanDefinition);
        if (beanDefinition.hasPropertyValues()) {
            this.visitPropertyValues(beanDefinition.getPropertyValues());
        }
        if (beanDefinition.hasConstructorArgumentValues()) {
            ConstructorArgumentValues cas = beanDefinition.getConstructorArgumentValues();
            this.visitIndexedArgumentValues(cas.getIndexedArgumentValues());
            this.visitGenericArgumentValues(cas.getGenericArgumentValues());
        }
    }
}

四、模式總結

1、優點描述

(1) 訪問者模式符合單一職責原則、使程序具有良好的擴展性、靈活性；

(2) 訪問者模式適用與攔截器與過濾器等常見功能，數據結構相對穩定的場景；

2、缺點描述

(1) 訪問者關注其他類的內部細節，依賴性強，違反迪米特法則,這樣導致具體元素更新麻煩；

(2) 訪問者依賴具體元素，不是抽象元素，面向細節編程，違背依賴倒轉原則；

五、源代碼地址

GitHub·地址
https://github.com/cicadasmile/model-arithmetic-parent
GitEE·地址
https://gitee.com/cicadasmile/model-arithmetic-parent

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

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

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

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

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

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

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

焦慮、迷茫。

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

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

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

不知前路在哪裡？

 

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

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

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

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

一眼望到頭的路罷了。

 

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

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

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

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

其實是金錢改變命運。

 

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

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

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

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

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

一眼望不到頭。

 

什麼時候是個頭？

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

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

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

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

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

 

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

所以只能讀書改變命運。

 

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

犹如稻草。

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

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

所以佛度來生。

所以道修逍遙。

若有仙人撫我頂，怎可結髮受長生？

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

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

 

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

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

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

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

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

於是，寫下此文。

一眼望到頭，一眼望不到頭。

 

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

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

有技術，有情懷，有溫度

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

 

 

 

 

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

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

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

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

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

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

本文首發於：

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

持續乾貨 歡迎關注！

看似青銅實則王者

很多人提起快排和二分都覺得很容易的樣子，但是讓現場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網頁設計已成為網頁設計推薦首選

碼農當自強

導航

• 初出茅廬
• 跳槽才能漲薪
• 力拔山兮氣蓋世
• 止步中層
• 契約精神?聯盟
• 技工?匠人

• 碼農當自強

  有人的地方就有江湖。有江湖必有俠客。IT人的江湖水生草闊,從來都盛產俠客和隱士。很多人離開這片江湖,沒有留下自己的故事,而那些有故事的終究成了傳說。

初出茅廬

  本文的主人公木木君,2011年畢業於一個普通二本大學的計算機專業。那年六月，他懷揣夢想,來到西部的一座准一線城市。

  “天高任鳥飛,海闊憑魚游”。同大多數應屆畢業生一樣,木木君懷揣夢想,滿腔熱心,對未來充滿希冀,希望能夠在這座大城市打拚出自己的一片天地。“求突破,求提高,求發展”,這是他給自己設定的未來五年計劃,分三個步驟執行。

  IT行業的門檻向來很高,大多數民企很少招生應屆生,特別是非985，211大學的童鞋,容易碰壁。木木君面試了20家大大小小的公司,花了一個多月,總算找了個正規公司。這是一家生產機頂盒的工廠,幾千人的公司,僅有不到50人的研發團隊。木木君在這裏開啟了自己的IT職業生涯。團隊不比正規的軟件公司,但同事和睦相處,也能夠接觸到實際的開發項目,總算有所突破。

  “笨鳥先飛”。木木君憑藉自己的努力,半年之內就把部門內部的項目都摸了一遍,並在原有基礎上增加了很多功能。

跳槽才能漲薪

  IT江湖潛規則之跳槽才能漲薪。

  有一天,木木君和往常一樣正在配合運維同事改進新的OA系統。“滴滴滴～”,一波QQ消息來襲。木木君點開消息,是師兄。木木君和這個師兄其實不是一個專業,師兄比他高一個年級,因為大學被同一個老師帶着一起做過項目，經常串寢室,比較熟悉。師兄告訴他,他換工作了,這是他兩年來第三次換工作,在軟件園,月薪8K。聊天完畢,木木君沉思良久,開始對高大上的軟件園產生嚮往。

  在第一家公司待了11個月,木木君選擇了離開,換到了一家軟件園的公司,並有機會和華為的工程師一起合作開發項目。值得一提的是,這次跳槽工資幾乎翻了一倍。

  新公司是行業里排名靠前的,公司制度規範,開發流程標準。團隊里研發同事嚴謹,當然壓力也很大。

  剛進公司的前兩個月,壓力挺大,見識了以前沒有接觸過的框架和組件,以及很多聽不懂的術語。每晚和同事加班到8點半,有時甚至11點才從公司離開,儘管很累,但是能夠感受的技術和經驗上的進步。

  在這家公司待了兩年。見識 了一些牛人,甚至有些一個人頂一個小團隊的人。華為的狼性文化在木木君心中打下烙印,深入血液,變成做事風格的一部分。在以後的工作中,也是秉持了這種文化。

力拔山兮氣蓋世

  大多數碼農,在工作三年左右能夠迎來自己的一個技術上的小高峰。

  木木君在第二家公司待了兩年感覺就像到山上跟了一個武林高手學了一身本領,瞬間有了自信。離職的時候,我和我同事還開玩笑說,出去之後至少都是8K…

  “移動互聯網時代已經來臨,站在風口上豬也能飛”。那一年,手機APP大行其道,獨領風騷,是個公司都想做APP。y也是在那一年小米火了,華為剛開始邁入手機領域。進入第三家公司,是一個不到一百人的軟件公司,做旅遊APP的,期望在這裡能夠接觸到移動端。

  “圈子不同,不硬融”。木木君在這家公司真正見識了什麼是公司內耗。小幫派林立,你再努力也無法融入。一年不到,領導換了幾茬,還玩的是家天下。

止步中層

  對大多數人而言,職場的中層就是天花板。

  “天下之大,竟無用武之地”。就像一個武林俠客,讓他困惑不是練武的孤獨和寂寞,而是竟然沒有用武之地。

  “此處不留爺,自有留爺處”。很快,木木君便進入一件互聯網產品公司,主營電商相關Saas軟件。這裏部門分工明確,需求,產品研發,安全,運維,DBA,測試一應俱全。公司產品成熟,客戶穩定,可以學習真正的大數據和自動化運維。

  在這裏團隊從零開始搭建自動化平台,並逐步迭代,一路摸爬滾打,基本能夠滿足公司100多台服務器的自動化運維。

  木木君一腔熱情,終於受到領導器重,升入中層。團隊不大,但是業務不少,支撐多個部門的系統研發和運維,幾乎人人都掛了2+項目。身為leader的木木君,更是不在話下。特殊時期,幾乎一人承擔一個團隊開發任務。甚至非常時期通宵支持…

  四年過去,木木君也進入了而立之年。2018年,經濟不景氣的一年…公司漲薪已經渺茫…陸續身邊逐漸有人跳槽。不到半年,身邊已經有三個人跳槽，其中一個老領導走了留下一句“待了六年,已經沒有上升空間”。

契約精神?聯盟

  我們是一個團隊，不是一個家庭。

  企業跟員工應該是一種什麼樣的關係?

  領英的執行總裁在《聯盟》這本書中開頭就寫道：“我們是一個團隊，不是一個家庭”。

  近期屢屢爆出的HR被辭退事件和員工因患病被辭退事件,引起了輿論共鳴。但是希望大家認識到員工和公司的關係是合作和聯盟關係。未來更是如此…

技工?匠人

  碼農,一群靠技術謀生的人。只是在互聯網的光環加持下,變得“高精尖”。但是,放在歷史的長河中來看,也不過是特定時代的勞動者。他們和上一個時代的磚瓦工,木匠其實沒有太大差別。是社會生產力發展到一定階段,一種工種對另一種工種的替代。

  互聯網給技術人帶來紅利,容易讓技術人感到天生的優越感,再加上身處大廠就容易自我感覺良好。

  吳軍博士對的碼農層級的分類,可以看出,技術人的發展方向不只是在技術本身,還要具備綜合能力。

• 第五級：能獨立解決問題，完成工程工作。

• 第四級：能指導和帶領其他人一同完成更有影響力的工作。

• 第三級：能獨立設計和實現產品，並且在市場上獲得成功。

• 第二級：能設計和實現別人不能做出的產品，也就是說他的作用很難取代。

• 第一級：開創一個產業。

  試問諸君在第幾層?

  說到底,技術人應該秉持匠人精神。

碼農當自強

  生活不止眼前的苟且,還有詩和遠方。

  2019年各大公司的財報,都反應很多公司效益差強人意。很多互聯網公司也在尋找新的風口和增長點。而立之年的木木君,雖然躊躇滿志,但再次陷入迷茫。深處IT行業多年,幾乎五年一個風口,技術行業更新快,玩的是創新和顛覆。移動互聯網時代是如何革傳統行業的命,木木君歷歷在目…

  同時,各大媒體充斥着中年危機的推文,一時間人人自危,催生了各種打着知識旗號販賣焦慮的二道販子。不禁讓木木君想起了之前有個大神的文章《屌絲的出路》。那個大神也是一段傳奇。

  很多碼農都在焦慮,但是又不知道如何做？技術人有一個通病,純粹。這不是缺點,但是生活是多元的,要多主動接觸技術之外的世界。

• 副業

  同時,可以多一些副業嘗試。比如,和朋友一起接一些項目。創建自己的博客。口才好的,可以錄一些技術教學視頻放到網上。

• 健身

  身體是革命的本錢,這裏的健身不是一定要去健身房,而是要學會鍛煉身體和合理作息。

• 投資

  年輕的時候,做一點投資和理財。投資房產也是不錯的選擇。投資可以為未來增加一筆資產。

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

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

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

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

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

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

一、摘要

在集合系列的第一章，咱們了解到，Map 的實現類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。

應該有很多人不知道 IdentityHashMap 的存在，其中不乏工作很多年的 Java 開發者，本文主要從數據結構和算法層面，探討 IdentityHashMap 的實現。

二、簡介

IdentityHashMap 的數據結構很簡單，底層實際就是一個 Object 數組，但是在存儲上並沒有使用鏈表來存儲，而是將 K 和 V 都存放在 Object 數組上。

當添加元素的時候，會根據 Key 計算得到散列位置，如果發現該位置上已經有改元素，直接進行新值替換；如果沒有，直接進行存放。當元素個數達到一定閾值時，Object 數組會自動進行擴容處理。

打開 IdentityHashMap 的源碼，可以看到 IdentityHashMap 繼承了AbstractMap 抽象類，實現了Map接口、可序列化接口、可克隆接口。

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable
{
    /**默認容量大小*/
    private static final int DEFAULT_CAPACITY = 32;
    
    /**最小容量*/
    private static final int MINIMUM_CAPACITY = 4;
    
    /**最大容量*/
    private static final int MAXIMUM_CAPACITY = 1 << 29;
    
    /**用於存儲實際元素的表*/
    transient Object[] table;
    
    /**數組大小*/
    int size;

    /**對Map進行結構性修改的次數*/
    transient int modCount;

    /**key為null所對應的值*/
    static final Object NULL_KEY = new Object();
    
    ......
}

可以看到類的底層，使用了一個 Object 數組來存放元素；在對象初始化時，IdentityHashMap 容量大小為64；

public IdentityHashMap() {
        //調用初始化方法
        init(DEFAULT_CAPACITY);
}

private void init(int initCapacity) {
        //數組大小默認為初始化容量的2倍
        table = new Object[2 * initCapacity];
}

三、常用方法介紹

3.1、put方法

put 方法是將指定的 key, value 對添加到 map 里。該方法首先會對map做一次查找，通過==判斷是否存在key，如果有，則將舊value返回，將新value覆蓋舊value；如果沒有，直接插入，數組長度+1，返回null。

源碼如下：

public V put(K key, V value) {
        //判斷key是否為空，如果為空，初始化一個Object為key
        final Object k = maskNull(key);

        retryAfterResize: for (;;) {
            final Object[] tab = table;
            final int len = tab.length;
            //通過key、length獲取數組小編
            int i = hash(k, len);
            
            //循環遍歷是否存在指定的key
            for (Object item; (item = tab[i]) != null;
                 i = nextKeyIndex(i, len)) {
                 //通過==判斷，是否數組中是否存在key
                if (item == k) {
                        V oldValue = (V) tab[i + 1];
                        //新value覆蓋舊value
                    tab[i + 1] = value;
                    //返回舊value
                    return oldValue;
                }
            }
            
            //數組長度 +1
            final int s = size + 1;
            //判斷是否需要擴容
            if (s + (s << 1) > len && resize(len))
                continue retryAfterResize;

            //更新修改次數
            modCount++;
            //將k加入數組
            tab[i] = k;
            //將value加入數組
            tab[i + 1] = value;
            size = s;
            return null;
        }
}

maskNull 函數，判斷 key 是否為空

private static Object maskNull(Object key) {
        return (key == null ? NULL_KEY : key);
}

hash 函數，通過 key 獲取 hash 值，結合數組長度通過位運算獲取數組散列下標

private static int hash(Object x, int length) {
        int h = System.identityHashCode(x);
        // Multiply by -127, and left-shift to use least bit as part of hash
        return ((h << 1) - (h << 8)) & (length - 1);
}

nextKeyIndex 函數，通過 hash 函數計算得到的數組散列下標，進行加2；因為一個 key、value 都存放在數組中，所以一個 map 對象佔用兩個數組下標，所以加2。

private static int nextKeyIndex(int i, int len) {
        return (i + 2 < len ? i + 2 : 0);
}

resize 函數，通過數組長度，進行擴容處理，擴容之後的長度為當前長度的2倍

private boolean resize(int newCapacity) {
        //擴容后的數組長度，為當前數組長度的2倍
        int newLength = newCapacity * 2;

        Object[] oldTable = table;
        int oldLength = oldTable.length;
        if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
            if (size == MAXIMUM_CAPACITY - 1)
                throw new IllegalStateException("Capacity exhausted.");
            return false;
        }
        if (oldLength >= newLength)
            return false;

        Object[] newTable = new Object[newLength];
        //將舊數組內容轉移到新數組
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        table = newTable;
        return true;
}

3.2、get方法

get 方法根據指定的 key 值返回對應的 value。同樣的，該方法會循環遍曆數組，通過==判斷是否存在key，如果有，直接返回value，因為 key、value 是相鄰的存儲在數組中，所以直接在當前數組下標+1，即可獲取 value；如果沒有找到，直接返回null。

值得注意的地方是，在循環遍歷中，是通過==判斷當前元素是否與key相同，如果相同，則返回value。咱們都知道，在 java 中，==對於對象類型參數，判斷的是引用地址，確切的說，是堆內存地址，所以，這裏判斷的是key的引用地址是否相同，如果相同，則返回對應的 value；如果不相同，則返回null。

源碼如下：

public V get(Object key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);
        
        //循環遍曆數組，直到找到key或者，數組為空為值
        while (true) {
            Object item = tab[i];
            //通過==判斷，當前數組元素與key相同
            if (item == k)
                return (V) tab[i + 1];
            //數組為空
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
}

3.3、remove方法

remove 的作用是通過 key 刪除對應的元素。該方法會循環遍曆數組，通過==判斷是否存在key，如果有，直接將key、value設置為null，對數組進行重新排列，返回舊 value。

源碼如下：

public V remove(Object key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        while (true) {
            Object item = tab[i];
            if (item == k) {
                modCount++;
                //數組長度減1
                size--;
                    V oldValue = (V) tab[i + 1];
                //將key、value設置為null
                tab[i + 1] = null;
                tab[i] = null;
                //刪除該元素后，需要把原來有衝突往後移的元素移到前面來
                closeDeletion(i);
                return oldValue;
            }
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
}

closeDeletion 函數，刪除該元素后，需要把原來有衝突往後移的元素移到前面來，對數組進行重寫排列；

private void closeDeletion(int d) {
        // Adapted from Knuth Section 6.4 Algorithm R
        Object[] tab = table;
        int len = tab.length;

        Object item;
        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
             i = nextKeyIndex(i, len) ) {
            int r = hash(item, len);
            if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
                tab[d] = item;
                tab[d + 1] = tab[i + 1];
                tab[i] = null;
                tab[i + 1] = null;
                d = i;
            }
        }
}

四、總結

1. IdentityHashMap 的實現不同於HashMap，雖然也是數組，不過IdentityHashMap中沒有用到鏈表，解決衝突的方式是計算下一個有效索引，並且將數據key和value緊挨着存在map中，即table[i]=key、table[i+1]=value；

2. IdentityHashMap 允許key、value都為null，當key為null的時候，默認會初始化一個Object對象作為key；

3. IdentityHashMap在保存、刪除、查詢數據的時候，以key為索引，通過==來判斷數組中元素是否與key相同，本質判斷的是對象的引用地址，如果引用地址相同，那麼在插入的時候，會將value值進行替換；

IdentityHashMap 測試例子：

public static void main(String[] args) {
        Map<String, String> identityMaps = new IdentityHashMap<String, String>();

        identityMaps.put(new String("aa"), "aa");
        identityMaps.put(new String("aa"), "bb");
        identityMaps.put(new String("aa"), "cc");
        identityMaps.put(new String("aa"), "cc");
        //輸出添加的元素
        System.out.println("數組長度："+identityMaps.size() + "，輸出結果：" + identityMaps);
    }

輸出結果：

數組長度：4，輸出結果：{aa=aa, aa=cc, aa=bb, aa=cc}

儘管key的內容是一樣的，但是key的堆地址都不一樣，所以在插入的時候，插入了4條記錄。

五、參考

1、JDK1.7&JDK1.8 源碼

2、

3、

作者：炸雞可樂
出處：

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

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

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

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

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

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

鈣素

Canvas 是在HTML5中新增的標籤用於在網頁實時生成圖像，並且可以操作圖像內容，基本上它是一個可以用JavaScript操作的位圖。也就是說我們將通過JS完成畫圖而不是css。

canvas 默認布局為 inline-block，可以認為是一種特殊的圖片。

走起 ~

canvas 劃線

<canvas id="can" width="800" height="800"></canvas>

（寬高不能放在style裏面，否則比例不對）

canvas裏面的width和height相當於圖片的原始尺寸，加了外部style的寬高，就相當於對圖片進行壓縮和拉伸。

// 1、獲取原生dom對象
let dom = document.getElementById('can');

// 2、獲取繪圖對象
let can = dom.getContext('2d'); // 3d是webgl

// 定義線條起點
can.moveTo(0,0);

// 定義線條中點（非終點）
can.lineTo(400,400);
can.lineTo(800,0);

// 對標記範圍進行描邊
can.stroke()

// 對標記範圍進行填充
can.fill();

設置線條屬性

線條默認寬度是 1。

（一定要在繪圖之前設置。）

can.lineWidth = 2; //設置線條寬度
can.strokeStyle = '#f00';  // 設置線條顏色

can.fillStyle = '#f00';  // 設置填充區域顏色

折線樣式

• miter：尖角（當尖角長度值過長時會自動變成折角，如果強制显示尖角：can.miterLimit = 100 設置尖角長度閾值。
• round：圓角
• bevel：折角

can.lineJoin = 'miter';
can.moveTo(100, 100);
can.lineTo(300, 100);
can.lineTo(100, 200);
can.stroke()

can.lineJoin = 'round';
can.moveTo(400, 100);
can.lineTo(600, 100);
can.lineTo(400, 200);
can.stroke()

can.lineJoin = 'bevel';
can.moveTo(700, 100);
can.lineTo(900, 100);
can.lineTo(700, 200);
can.stroke()

設置線帽

• round：加圓角線帽
• square：加直角線帽
• butt：不加線帽

    can.lineCap = 'round';
    can.moveTo(100, 100);
    can.lineTo(300, 100);
    can.stroke()
    
     // 新建繪圖，使得上一次的繪畫樣式不會影響下面的繪畫樣式（代碼加在上一次繪畫和下一次繪畫中間。）
    can.beginPath()
    
    can.lineCap = 'square';
    can.moveTo(100, 200);
    can.lineTo(300, 200);
    can.stroke()
    
    can.beginPath()
    
    can.lineCap = 'butt';
    can.moveTo(100, 300);
    can.lineTo(300, 300);
    can.stroke()

畫矩形

// 參數：x,y,寬，高

can.rect(100,100,100,100);
can.stroke();

// 畫完即填充
can.fillRect(100,100,100,100);

畫圓弧

// 參數：圓心x，圓心y，半徑，圓弧起點與圓心的夾角度數，圓弧終點與圓心的夾角度數，true（逆時針繪畫）

can.arc(500,300,200,0,2*Math.PI/360*90,false);
can.stroke()

示例：

can.moveTo(500,300);
can.lineTo(500 + Math.sqrt(100), 300 + Math.sqrt(100))
can.arc(500, 300, 100, 2 * Math.PI / 360 *startDeg, 2 * Math.PI / 360 *endDeg, false);
can.closePath()//將圖形起點和終點用線連接起來使之成為封閉的圖形
can.fill()

Tips:

1、can.beginPath() // 新建繪圖，使得上一次的繪畫樣式不會影響下面的繪畫樣式（代碼加在上一次繪畫和下一次繪畫中間。）

2、can.closePath() //將圖形起點和終點用線連接起來使之成為封閉的圖形。

旋轉畫布

can.rotate(2*Math.PI/360*45); // 一定要寫在開始繪圖之前
can.fillRect(0,0,200, 10);

旋轉整個畫布的坐標系（參考坐標為畫布的(0,0)位置）

縮放畫布

can.scale(0.5,2);
can.fillRect(0,0,200, 10);

示例：

整個畫布：x方向縮放為原來的0.5，y方向拉伸為原來的2倍。

畫布位移

can.translate(100,100)
can.fillRect(0,0,200, 10);

保存與恢復畫布狀態

can.save() // 存檔：保存當前畫布坐標系狀態
can.restore() // 讀檔：恢復之前保存的畫布坐標系狀態

需要正確坐標系繪圖的時候，再讀檔之前的正確坐標系。

can.restore() // 將當前的畫布坐標系狀態恢復成上一次保存時的狀態
can.fillRect(dom.width/2, dom.height/2, 300, 100)

指針時鐘（案例）

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>clock</title>
    <style type="text/css">
        #can {
            width: 1000px;
            height: 600px;
            background: linear-gradient(45deg, green, skyblue);
        }
    </style>
</head>

<body>
    <canvas id="can" width="2000" height="1200"></canvas>
</body>

<script type="text/javascript">
    let dom = document.getElementById('can');

    let can = dom.getContext('2d');

    // 把畫布的圓心移動到畫布的中心
    can.translate(dom.width / 2, dom.height / 2);
    // 保存當前的畫布坐標系
    can.save()


    run();



    function run() {
        setInterval(function() {
            clearCanvas();
            draw();
        }, 10);
    }

    // 繪圖
    function draw() {
        let time = new Date();
        let hour = time.getHours();
        let min = time.getMinutes();
        let sec = time.getSeconds();
        let minSec = time.getMilliseconds();

        drawPannl();
        drawHour(hour, min, sec);
        drawMin(min, sec);
        drawSec(sec, minSec);
        drawPoint();
    }

    // 最簡單的方法：由於canvas每當高度或寬度被重設時，畫布內容就會被清空
    function clearCanvas() {
        dom.height = dom.height;
        can.translate(dom.width / 2, dom.height / 2);
        can.save()
    }

    // 畫錶盤
    function drawPannl() {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 10;
        can.strokeStyle = 'skyblue';
        can.arc(0, 0, 400, 0, 2 * Math.PI);
        can.stroke();

        for (let i = 0; i < 12; i++) {
            can.beginPath();
            can.lineWidth = 16;
            can.strokeStyle = 'greenyellow';

            can.rotate(2 * Math.PI / 12)

            can.moveTo(0, -395);
            can.lineTo(0, -340);
            can.stroke();
        }

        for (let i = 0; i < 60; i++) {
            can.beginPath();
            can.lineWidth = 10;
            can.strokeStyle = '#fff';

            can.rotate(2 * Math.PI / 60)

            can.moveTo(0, -395);
            can.lineTo(0, -370);
            can.stroke();
        }
    }

    // 畫時針
    function drawHour(h, m, s) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 24;
        can.strokeStyle = 'palevioletred';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (12 * 60 * 60) * (h * 60 * 60 + m * 60 + s))
        can.moveTo(0, 0);
        can.lineTo(0, -200);
        can.stroke();
    }

    // 畫分針
    function drawMin(m, s) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 14;
        can.strokeStyle = '#09f';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (60 * 60) * (m * 60 + s))
        can.moveTo(0, 0);
        can.lineTo(0, -260);
        can.stroke();
    }

    // 畫秒針
    function drawSec(s, ms) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 8;
        can.strokeStyle = '#f00';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (60 * 1000) * (s * 1000 + ms));
        can.moveTo(0, 50);
        can.lineTo(0, -320);
        can.stroke();
    }


    // 畫中心點
    function drawPoint() {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 10;
        can.fillStyle = 'red';
        can.arc(0, 0, 12, 0, 2 * Math.PI);
        can.fill();
    }
</script>

</html>

圓弧時鐘（案例）

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>clock</title>
    <style type="text/css">
        #can {
            width: 1000px;
            height: 600px;
            background: linear-gradient(45deg, rgb(94, 53, 6), black);
        }
    </style>
</head>

<body>
    <canvas id="can" width="2000" height="1200"></canvas>
</body>

<script type="text/javascript">
    let dom = document.getElementById('can');

    let can = dom.getContext('2d');

    // 把畫布的圓心移動到畫布的中心
    can.translate(dom.width / 2, dom.height / 2);
    // 保存當前的畫布坐標系
    can.save();

    // 圓形指針起始角度
    let startDeg = 2 * Math.PI / 360 * 270;


    run();
    // draw();


    function run() {
        setInterval(function() {
            clearCanvas();
            draw();
        }, 20);
    }

    // 繪圖
    function draw() {
        let time = new Date();
        // let hour = time.getHours();
        let hour = time.getHours() > 10 ? time.getHours() - 12 : time.getHours();
        let min = time.getMinutes();
        let sec = time.getSeconds();
        let minSec = time.getMilliseconds();

        drawPannl();
        drawTime(hour, min, sec, minSec);
        drawHour(hour, min, sec);
        drawMin(min, sec);
        drawSec(sec, minSec);
        drawPoint();
    }

    // 最簡單的方法：由於canvas每當高度或寬度被重設時，畫布內容就會被清空
    function clearCanvas() {
        dom.height = dom.height;
        can.translate(dom.width / 2, dom.height / 2);
        can.save()
    }

    // 畫錶盤
    function drawPannl() {

        can.restore()
        can.save()

        // 設置時錶盤
        can.beginPath();
        can.lineWidth = 50;
        can.strokeStyle = 'rgba(255,23,87,0.2)';
        can.arc(0, 0, 400, 0, 2 * Math.PI);
        can.stroke();
        // 設置分錶盤
        can.beginPath();
        can.strokeStyle = 'rgba(169,242,15,0.2)';
        can.arc(0, 0, 345, 0, 2 * Math.PI);
        can.stroke();
        // 設置秒錶盤
        can.beginPath();
        can.strokeStyle = 'rgba(21,202,230,0.2)';
        can.arc(0, 0, 290, 0, 2 * Math.PI);
        can.stroke();


        // 小時刻度
        // for (let i = 0; i < 12; i++) {
        //     can.beginPath();
        //     can.lineWidth = 16;
        //     can.strokeStyle = 'rgba(0,0,0,0.2)';

        //     can.rotate(2 * Math.PI / 12)

        //     can.moveTo(0, -375);
        //     can.lineTo(0, -425);
        //     can.stroke();
        // }

        // 分針刻度
        // for (let i = 0; i < 60; i++) {
        //     can.beginPath();
        //     can.lineWidth = 10;
        //     can.strokeStyle = '#fff';

        //     can.rotate(2 * Math.PI / 60)

        //     can.moveTo(0, -395);
        //     can.lineTo(0, -370);
        //     can.stroke();
        // }
    }

    // 畫時針
    function drawHour(h, m, s) {

        let rotateDeg = 2 * Math.PI / (12 * 60 * 60) * (h * 60 * 60 + m * 60 + s);

        can.beginPath();
        can.restore()
        can.save()

        // 時針圓弧
        can.lineWidth = 50;
        can.strokeStyle = 'rgb(255,23,87)';
        can.lineCap = 'round';
        can.shadowColor = "rgb(255,23,87)"; // 設置陰影顏色
        can.shadowBlur = 20; // 設置陰影範圍
        can.arc(0, 0, 400, startDeg, startDeg + rotateDeg);
        can.stroke();

        // 時針指針
        can.beginPath();
        can.lineWidth = 24;
        can.strokeStyle = 'rgb(255,23,87)';
        can.lineCap = 'round'
        can.rotate(rotateDeg)
        can.moveTo(0, 0);
        can.lineTo(0, -100);
        can.stroke();



    }

    // 畫分針
    function drawMin(m, s) {

        let rotateDeg = 2 * Math.PI / (60 * 60) * (m * 60 + s);

        can.beginPath();
        can.restore()
        can.save()

        // 分針圓弧
        can.lineWidth = 50;
        can.strokeStyle = 'rgb(169,242,15)';
        can.lineCap = 'round'
        can.shadowColor = "rgb(169,242,15)";
        can.shadowBlur = 20;
        can.arc(0, 0, 345, startDeg, startDeg + rotateDeg);
        can.stroke();

        // 分針指針
        can.beginPath();
        can.lineWidth = 14;
        can.strokeStyle = 'rgb(169,242,15)';
        can.lineCap = 'round'
        can.rotate(rotateDeg)
        can.moveTo(0, 0);
        can.lineTo(0, -160);
        can.stroke();
    }

    // 畫秒針
    function drawSec(s, ms) {

        let rotateDeg = 2 * Math.PI / (60 * 1000) * (s * 1000 + ms);

        can.beginPath();
        can.restore()
        can.save()

        can.lineWidth = 50;
        can.strokeStyle = 'rgb(21,202,230)';
        can.lineCap = 'round'
        can.arc(0, 0, 290, startDeg, startDeg + rotateDeg);
        can.stroke();

        can.beginPath();
        can.lineWidth = 8;
        can.strokeStyle = 'rgb(21,202,230)';
        can.lineCap = 'round'
        can.shadowColor = "rgb(21,202,230)";
        can.shadowBlur = 20;
        can.rotate(rotateDeg);
        can.moveTo(0, 50);
        can.lineTo(0, -220);
        can.stroke();
    }


    // 畫中心點
    function drawPoint() {
        can.beginPath();
        can.restore()
        can.save()

        can.lineWidth = 10;
        can.fillStyle = 'red';
        can.arc(0, 0, 12, 0, 2 * Math.PI);
        can.fill();
    }

    // 显示数字時鐘
    function drawTime(h, m, s, ms) {
        can.font = '60px Calibri';
        can.fillStyle = '#0f0'
        can.shadowColor = "#fff";
        can.shadowBlur = 20;
        can.fillText(`${h}:${m}:${s}.${ms}`, -140, -100);
    }
</script>

</html>

（啾咪 ^.<）

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

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

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

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

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

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

之前我們介紹過BERT+CRF來進行命名實體識別，並對其中的BERT和CRF的概念和作用做了相關的介紹，然對於CRF中的最優的標籤序列的計算原理，我們只提到了維特比算法，並沒有做進一步的解釋，本文將對維特比算法做一個通俗的講解，以便大家更好的理解CRF為什麼能夠得到最優的標籤序列。

通過閱讀本文你將能回答如下問題：

• 什麼是維特比算法？
• 為什麼說維特比算法是一種動態規劃算法？
• 維特比算法具體怎麼實現？

首先，讓我們簡單回顧一下BERT和CRF在命名實體識別中各自的作用：
命名實體識別中，BERT負責學習輸入句子中每個字和符號到對應的實體標籤的規律，而CRF負責學習相鄰實體標籤之間的轉移規則。詳情可以參考這篇文章。該文章中我們對CRF做了簡單易懂的介紹，其中提到CRF的損失函數計算要用到最優路徑，因為CRF的損失函數是求最優路徑的概率占所有路徑概率和的比例，而我們的目標是最大化這個比例。那麼這裏就涉及到計算最優路徑的問題。這裏的路徑在命名實體識別的例子中，就是最終輸出的與句子中的字或符號一 一對應的標籤序列。不同標籤序列的順序組成了不同的路徑。而CRF就是要找出最正確的那條標籤序列路徑，也就是說這條標籤路徑的概率將是所有路徑中最大的，那麼我們可以窮舉出所有可能的標籤路徑，計算出每條路徑的概率和，然後比較出最大的那條，但是這樣做的代價太大了，所以crf選擇了一種稱為維特比的算法來求解此類問題。

維特比算法（英語：Viterbi algorithm）是一種動態規劃算法。它用於尋找最有可能產生觀測事件序列的維特比路徑。

看看下面這個命名實體識別的例子：

上圖共有5層(觀測序列的長度)，每層3個節點(狀態的個數)，我們的目標就是找到從第一層到第五層的最優路徑。
首先，我們分別計算紅、黃、藍三個節點的輸入連線的概率，以紅色節點舉例，我們先假設紅色節點在最優路徑上，那麼輸入到該節點的三條連線中，概率最大的那條一定在最優路徑上，同理，我們再分別假設黃色和藍色節點在最優路徑上，我們也能各找到一條概率最大的連線，這樣就得到了下面的圖：

然後，我們接着剛才的思路繼續找後面一層的三條最優的連線：

假設找到的最優連線如下：

然後，接着在後面的層應用這個方法：

此時，看上面最後一張圖，我們有了3條候選最優路徑，分別是棕色、綠色和紫色，用標籤來表達如下：

那麼哪條才是最優路徑呢？
就是看哪條路徑的概率和最大，那條路徑就是最優路徑。
但是在實際實現的時候，一般會在計算各層的最優候選連線的時候，就記錄下前繼連線的概率和，並記錄下對應的狀態節點索引(這裏將已經計算出的結果記錄下來供後續使用的方式，就是維特比算法被稱為動態規劃算法的原因)，這樣到最後一層的時候，最後一層各候選連線中概率最大的，就是在最優路徑上的那條連線了，然後從這條連線回溯，找出完整的路徑就是最優路徑了。

一直在說概率最大的路徑，那麼這個概率具體指什麼呢？
還記得上一篇文章介紹條件隨機場(CRF)的時候提到，條件隨機場其實是給定了觀測序列的馬爾可夫隨機場，在一階馬爾可夫模型中，定義了以下三個概念：

• 狀態集合Q，對應到上面的例子就是：
  {B-P, I-P, O}
• 初始狀態概率向量Π，對應到上面的例子就是：
  {B-P:0.3, I-P:0.2, O:0.5}
  這裏的概率數值是隨便假設的，僅為了方便舉例說明。
• 狀態轉移概率矩陣A：

CRF中給定了觀測序列做為先驗條件，對應到上面的例子就是：

其中的概率數值同樣是隨便假設的，為了方便舉例。

下圖中紅色節點的概率(可以看成是一個虛擬的開始節點到該節點的連線的概率)的計算方式如下：
初始狀態為B-P的概率Π(B-P) * 該節點的觀測概率P(小|B-P)

下圖中紅色節點的三條連線概率的計算方式如下：
上一層對應節點的概率 * 上層對應節點到該節點的轉移概率 * 該節點的觀測概率P(明|B-P)

其它層之間的節點連線的概率同理計算可得，然後通過上面介紹的維特比算法過程就可以計算出最優路徑了。

ok,本篇就這麼多內容啦~，感謝閱讀O(∩_∩)O。

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

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

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

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

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

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

此篇參考：

 我們在lightning中在前台會經常碰到獲取picklist的values然後使用select option進行渲染成下拉列表，此篇用於實現針對指定的sObject以及fieldName(Picklist類型)獲取此字段對應的所有可用的values的公用組件。因為不同的record type可能設置不同的picklist values，所以還有另外的參數設置針對指定的record type developer name去獲取指定的record type對應的Picklist values.

一. PicklistService公用組件聲明實現

Common_PicklistController.cls:有三個形參，其中objectName以及fieldName是必填參數，recordTypeDeveloperName為可選參數。

 1 public without sharing class Common_PicklistController {
 2     
 3     @AuraEnabled(cacheable=true)
 4     public static List<Map<String,String>> getPicklistValues(String objectName, String fieldName,String recordTypeDeveloperName) {
 5         //1. use object and field name get DescribeFieldResult and also get all the picklist values
 6         List<Schema.PicklistEntry> allPicklistValuesByField;
 7         try {
 8             List<Schema.DescribeSobjectResult> objDescriptions = Schema.describeSObjects(new List<String>{objectName});
 9             Schema.SObjectField field = objDescriptions[0].fields.getMap().get(fieldName);
10             Schema.DescribeFieldResult fieldDescribeResult = field.getDescribe();
11             allPicklistValuesByField = fieldDescribeResult.getPicklistValues();
12         } catch (Exception e) {
13             throw new AuraHandledException('Failed to retrieve values : '+ objectName +'.'+ fieldName +': '+ e.getMessage());
14         }
15         
16         //2. get all active field name -> label map
17         List<Map<String,String>> activeOptionMapList = new List<Map<String,String>>();
18         Map<String,String> optionValue2LabelMap = new Map<String,String>();
19         List<String> optionValueList;
20         for(Schema.PicklistEntry entry : allPicklistValuesByField) {
21             if (entry.isActive()) {
22                 System.debug(LoggingLevel.INFO, '*** entry: ' + JSON.serialize(entry));
23                 optionValue2LabelMap.put(entry.getValue(), entry.getLabel());
24             }
25         }
26 
27         //3. generate list with option value(with/without record type)
28         if(String.isNotBlank(recordTypeDeveloperName)) {
29             optionValueList = PicklistDescriber.describe(objectName,recordTypeDeveloperName,fieldName);
30         } else {
31             optionValueList = new List<String>(optionValue2LabelMap.keySet());
32         }
33 
34         //4. generate and format result
35         if(optionValueList != null) {
36             for(String option : optionValueList) {
37                 String optionLabel = optionValue2LabelMap.get(option);
38                 Map<String,String> optionDataMap = new Map<String,String>();
39                 optionDataMap.put('value',option);
40                 optionDataMap.put('label', optionLabel);
41                 activeOptionMapList.add(optionDataMap);
42             }
43         }
44 
45         return activeOptionMapList;
46     }
47 }

 Common_PicklistService.cmp:聲明了getPicklistInfo方法，有以下三個主要參數.objectName對應sObject的API名字，fieldName對應的此sObject中的Picklist類型的字段，recordTypeDeveloperName對應這個sObject的record type的developer name

1 <aura:component access="global" controller="Common_PicklistController">
2     <aura:method access="global" name="getPicklistInfo"  description="Retrieve active picklist values and labels mapping with(without) record type" action="{!c.getPicklistInfoAction}">
3         <aura:attribute type="String" name="objectName" required="true" description="Object name"/>
4         <aura:attribute type="String" name="fieldName" required="true" description="Field name"/>
5         <aura:attribute type="String" name="recordTypeDeveloperName" description="record type developer name"/>
6         <aura:attribute type="Function" name="callback" required="true" description="Callback function that returns the picklist values and labels mapping as [{value: String, label: String}]"/>
7     </aura:method>
8 </aura:component>

 Common_PicklistServiceController.js: 獲取傳遞過來的參數，調用後台方法並對結果放在callback中。

 1 ({
 2     getPicklistInfoAction : function(component, event, helper) {
 3         const params = event.getParam('arguments');
 4         const action = component.get('c.getPicklistValueList');
 5         action.setParams({
 6             objectName : params.objectName,
 7             fieldName : params.fieldName,
 8             recordTypeDeveloperName : params.recordTypeDeveloperName
 9         });
10         action.setCallback(this, function(response) {
11             const state = response.getState();
12             if (state === 'SUCCESS') {
13                 params.callback(response.getReturnValue());
14             } else if (state === 'ERROR') {
15                 console.error('failed to retrieve picklist values for '+ params.objectName +'.'+ params.fieldName);
16                 const errors = response.getError();
17                 if (errors) {
18                     console.error(JSON.stringify(errors));
19                 } else {
20                     console.error('Unknown error');
21                 }
22             }
23         });
24 
25         $A.enqueueAction(action);
26     }
27 })

二. 公用組件調用

 上面介紹了公用組件以後，下面的demo是如何調用。

SimplePicklistDemo引入Common_PicklistService，設置aura:id用於後期獲取到此component，從而調用方法

 1 <aura:component implements="flexipage:availableForAllPageTypes">
 2     <!-- include common picklist service component -->
 3     <c:Common_PicklistService aura:id="service"/>
 4     <aura:handler name="init" value="{!this}" action="{!c.doInit}"/>
 5 
 6     <aura:attribute name="accountTypeList" type="List"/>
 7     <aura:attribute name="accountTypeListByRecordType" type="List"/>
 8 
 9     <lightning:layout verticalAlign="center" class="x-large">
10         <lightning:layoutItem flexibility="auto" padding="around-small">
11             <lightning:select label="account type">
12                 <aura:iteration items="{!v.accountTypeList}" var="type">
13                     <option value="{!type.value}" text="{!type.label}"></option>
14                 </aura:iteration>
15             </lightning:select>
16         </lightning:layoutItem>
17 
18         <lightning:layoutItem flexibility="auto" padding="around-small">
19             <lightning:select label="account type with record type">
20                 <aura:iteration items="{!v.accountTypeListByRecordType}" var="type">
21                     <option value="{!type.value}" text="{!type.label}"></option>
22                 </aura:iteration>
23             </lightning:select>
24         </lightning:layoutItem>
25     </lightning:layout>
26     
27 </aura:component>

SimplePicklistDemoController.js：初始化方法用於獲取到公用組件component然後獲取Account的type的values，第一個是獲取所有的values/labels，第二個是獲取指定record type的values/labels。

 1 ({
 2     doInit : function(component, event, helper) {
 3         const service = component.find('service');
 4         service.getPicklistInfo('Account','type','',function(result) {
 5             component.set('v.accountTypeList', result);
 6         });
 7 
 8         service.getPicklistInfo('Account','type','Business_Account',function(result) {
 9             component.set('v.accountTypeListByRecordType',result);
10         });
11     }
12 })

三.效果展示：

1. account type的展示方式

 

 2. account type with record type的展示方式。

 

 總結：篇中介紹了Picklist values針對with/without record type的公用組件的使用，感興趣的可以進行優化，篇中有錯誤的歡迎指出，有不懂的歡迎留言。

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

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

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

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

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

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