【併發編程】synchronized的使用場景和原理簡介

1. synchronized使用

1.1 synchronized介紹

在多線程併發編程中synchronized一直是元老級角色,很多人都會稱呼它為重量級鎖。但是,隨着Java SE 1.6對synchronized進行了各種優化之後,有些情況下它就並不那麼重了。

synchronized可以修飾普通方法,靜態方法和代碼塊。當synchronized修飾一個方法或者一個代碼塊的時候,它能夠保證在同一時刻最多只有一個線程執行該段代碼。

  • 對於普通同步方法,鎖是當前實例對象(不同實例對象之間的鎖互不影響)。

  • 對於靜態同步方法,鎖是當前類的Class對象。

  • 對於同步方法塊,鎖是Synchonized括號里配置的對象。

當一個線程試圖訪問同步代碼塊時,它首先必須得到鎖,退出或拋出異常時必須釋放鎖。

1.2 使用場景

synchronized最常用的使用場景就是多線程併發編程時線程的同步。這邊還是舉一個最常用的列子:多線程情況下銀行賬戶存錢和取錢的列子。

public class SynchronizedDemo {


    public static void main(String[] args) {
        BankAccount myAccount = new BankAccount("accountOfMG",10000.00);
        for(int i=0;i<100;i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        int var = new Random().nextInt(100);
                        Thread.sleep(var);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    double deposit = myAccount.deposit(1000.00);
                    System.out.println(Thread.currentThread().getName()+" balance:"+deposit);
                }
            }).start();
        }
        for(int i=0;i<100;i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        int var = new Random().nextInt(100);
                        Thread.sleep(var);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    double deposit = myAccount.withdraw(1000.00);
                    System.out.println(Thread.currentThread().getName()+" balance:"+deposit);

                }
            }).start();
        }
    }

    private static class BankAccount{
        String accountName;
        double balance;

        public BankAccount(String accountName,double balance){
            this.accountName = accountName;
            this.balance = balance;
        }

        public double deposit(double amount){
            balance = balance + amount;
            return balance;
        }

        public double  withdraw(double amount){
            balance = balance - amount;
            return balance;
        }

    }
}

上面的列子中,首先初始化了一個銀行賬戶,賬戶的餘額是10000.00,然後開始了200個線程,其中100個每次向賬戶中存1000.00,另外100個每次從賬戶中取1000.00。如果正常執行的話,賬戶中應該還是10000.00。但是我們執行多次這段代碼,會發現執行結果基本上都不是10000.00,而且每次結果 都是不一樣的。

出現上面這種結果的原因就是:在多線程情況下,銀行賬戶accountOfMG是一個共享變量,對共享變量進行修改如果不做線程同步的話是會存在線程安全問題的。比如說現在有兩個線程同時要對賬戶accountOfMG存款1000,一個線程先拿到賬戶的當前餘額,並且將餘額加上1000。但是還沒將餘額的值刷新回賬戶,另一個線程也來做相同的操作。此時賬戶餘額還是沒加1000之前的值,所以當兩個線程執行完畢之後,賬戶加的總金額還是只有1000。

synchronized就是Java提供的一種線程同步機制。使用synchronized我們可以非常方便地解決上面的銀行賬戶多線程存錢取錢問題,只需要使用synchronized修飾存錢和取錢方法即可:

private static class BankAccount{
        String accountName;
        double balance;

        public BankAccount(String accountName,double balance){
            this.accountName = accountName;
            this.balance = balance;
        }
        //這邊給出一個編程建議:當我們對共享變量進行同步時,同步代碼塊最好在共享變量中加
        public synchronized double deposit(double amount){
            balance = balance + amount;
            return balance;
        }
        
        public synchronized double  withdraw(double amount){
            balance = balance - amount;
            return balance;
        }

    }

2. Java對象頭

上面提到,當線程進入synchronized方法或者代碼塊時需要先獲取鎖,退出時需要釋放鎖。那麼這個鎖信息到底存在哪裡呢?

Java對象保存在內存中時,由以下三部分組成:

  • 對象頭
  • 實例數據
  • 對齊填充字節

而對象頭又由下面幾部分組成:

  • Mark Word
  • 指向類的指針
  • 數組長度(只有數組對象才有)

1. Mark Word
Mark Word記錄了對象和鎖有關的信息,當這個對象被synchronized關鍵字當成同步鎖時,圍繞這個鎖的一系列操作都和Mark Word有關。Mark Word在32位JVM中的長度是32bit,在64位JVM中長度是64bit。

Mark Word在不同的鎖狀態下存儲的內容不同,在32位JVM中是這麼存的:

其中無鎖和偏向鎖的鎖標誌位都是01,只是在前面的1bit區分了這是無鎖狀態還是偏向鎖狀態。Epoch是指偏向鎖的時間戳。

JDK1.6以後的版本在處理同步鎖時存在鎖升級的概念,JVM對於同步鎖的處理是從偏向鎖開始的,隨着競爭越來越激烈,處理方式從偏向鎖升級到輕量級鎖,最終升級到重量級鎖。

JVM一般是這樣使用鎖和Mark Word的:

  • step1:當沒有被當成鎖時,這就是一個普通的對象,Mark Word記錄對象的HashCode,鎖標誌位是01,是否偏向鎖那一位是0。

  • step2:當對象被當做同步鎖並有一個線程A搶到了鎖時,鎖標誌位還是01,但是否偏向鎖那一位改成1,前23bit記錄搶到鎖的線程id,表示進入偏向鎖狀態。

  • step3:當線程A再次試圖來獲得鎖時,JVM發現同步鎖對象的標誌位是01,是否偏向鎖是1,也就是偏向狀態,Mark Word中記錄的線程id就是線程A自己的id,表示線程A已經獲得了這個偏向鎖,可以執行同步鎖的代碼。

  • step4:當線程B試圖獲得這個鎖時,JVM發現同步鎖處於偏向狀態,但是Mark Word中的線程id記錄的不是B,那麼線程B會先用CAS操作試圖獲得鎖,這裏的獲得鎖操作是有可能成功的,因為線程A一般不會自動釋放偏向鎖。如果搶鎖成功,就把Mark Word里的線程id改為線程B的id,代表線程B獲得了這個偏向鎖,可以執行同步鎖代碼。如果搶鎖失敗,則繼續執行步驟5。

  • step5:偏向鎖狀態搶鎖失敗,代表當前鎖有一定的競爭,偏向鎖將升級為輕量級鎖。JVM會在當前線程的線程棧中開闢一塊單獨的空間,裏面保存指向對象鎖Mark Word的指針,同時在對象鎖Mark Word中保存指向這片空間的指針。上述兩個保存操作都是CAS操作,如果保存成功,代表線程搶到了同步鎖,就把Mark Word中的鎖標誌位改成00,可以執行同步鎖代碼。如果保存失敗,表示搶鎖失敗,競爭太激烈,繼續執行步驟6。

  • step6:輕量級鎖搶鎖失敗,JVM會使用自旋鎖,自旋鎖不是一個鎖狀態,只是代表不斷的重試,嘗試搶鎖。從JDK1.7開始,自旋鎖默認啟用,自旋次數由JVM決定。如果搶鎖成功則執行同步鎖代碼,如果失敗則繼續執行步驟7。

  • step7:自旋鎖重試之後如果搶鎖依然失敗,同步鎖會升級至重量級鎖,鎖標誌位改為10。在這個狀態下,未搶到鎖的線程都會被阻塞。

2. 指向類的指針
該指針在32位JVM中的長度是32bit,在64位JVM中長度是64bit。Java對象的類數據保存在方法區。

3. 數組長度
只有數組對象保存了這部分數據。該數據在32位和64位JVM中長度都是32bit。

synchronized對鎖的優化

Java 6中為了減少獲得鎖和釋放鎖帶來的性能消耗,引入了“偏向鎖”和“輕量級鎖”的概念。在Java 6中,鎖一共有4種狀態,級別從低到高依次是:無鎖狀態、偏向鎖狀態、輕量級鎖狀態和重量級鎖狀態,這幾個狀態會隨着競爭情況逐漸升級。鎖可以升級但不能降級,意味着偏向鎖升級成輕量級鎖后不能降級成偏向鎖。

在聊偏向鎖、輕量級鎖和重量級鎖之前我們先來聊下鎖的宏觀分類。鎖從宏觀上來分類,可以分為悲觀鎖與樂觀鎖。注意,這裏說的的鎖可以是數據庫中的鎖,也可以是Java等開發語言中的鎖技術。悲觀鎖和樂觀鎖其實只是一類概念(對某類具體鎖的總稱),不是某種語言或是某個技術獨有的鎖技術。

樂觀鎖是一種樂觀思想,即認為讀多寫少,遇到併發寫的可能性低,每次去拿數據的時候都認為別人不會修改,所以不會上鎖,但是在更新的時候會判斷一下在此期間別人有沒有去更新這個數據,採取在寫時先讀出當前版本號,然後加鎖操作(比較跟上一次的版本號,如果一樣則更新),如果失敗則要重複讀-比較-寫的操作。java中的樂觀鎖基本都是通過CAS操作實現的,CAS是一種更新的原子操作,比較當前值跟傳入值是否一樣,一樣則更新,否則失敗。數據庫中的共享鎖也是一種樂觀鎖。

悲觀鎖是就是悲觀思想,即認為寫多,遇到併發寫的可能性高,每次去拿數據的時候都認為別人會修改,所以每次在讀寫數據的時候都會上鎖,這樣別人想讀寫這個數據就會block直到拿到鎖。java中典型的悲觀鎖就是Synchronized,AQS框架下的鎖則是先嘗試cas樂觀鎖去獲取鎖,獲取不到,才會轉換為悲觀鎖,如ReentrantLock。數據庫中的排他鎖也是一種悲觀鎖。

偏向鎖

Java 6之前的synchronized會導致爭用不到鎖的線程進入阻塞狀態,線程在阻塞狀態和runnbale狀態之間切換是很耗費系統資源的,所以說它是java語言中一個重量級的同步操縱,被稱為重量級鎖。為了緩解上述性能問題,Java 6開始,引入了輕量鎖與偏向鎖,默認啟用了自旋,他們都屬於樂觀鎖

偏向鎖更準確的說是鎖的一種狀態。在這種鎖狀態下,系統中只有一個線程來爭奪這個鎖。線程只要簡單地通過Mark Word中存放的線程ID和自己的ID是否一致就能拿到鎖。下面簡單介紹下偏向鎖獲取和升級的過程。

還是就着這張圖講吧,會清楚點。

當系統中還沒有訪問過synchronized代碼時,此時鎖的狀態肯定是“無鎖狀態”,也就是說“是否是偏向鎖”的值是0,“鎖標誌位”的值是01。此時有一個線程1來訪問同步代碼,發現鎖對象的狀態是”無鎖狀態”,那麼操作起來非常簡單了,只需要將“是否偏向鎖”標誌位改成1,再將線程1的線程ID寫入Mark Word即可。

如果後續系統中一直只有線程1來拿鎖,那麼只要簡單的判斷下線程1的ID和Mark Word中的線程ID,線程1就能非常輕鬆地拿到鎖。但是現實往往不是那麼簡單的,現在假設線程2也要來競爭同步鎖,我們看下情況是怎麼樣的。

  • step1:線程2首先根據“是否是偏向鎖”和“鎖標誌位”的值判斷出當前鎖的狀態是“偏向鎖”狀態,但是Mark Word中的線程ID又不是指向自己(此時線程ID還是指向線程1),所以此時回去判斷線程1還是否存在;
  • step2:假如此時線程1已經不存在了,線程2會將Mark Word中的線程ID指向自己的線程ID,鎖不升級,仍為偏向鎖;
  • step3:假如此時線程1還存在(線程1還沒執行完同步代碼,【不知道這樣理解對不對,姑且先這麼理解吧】),首先暫停線程1,設置鎖標誌位為00,鎖升級為“輕量級鎖”,繼續執行線程1的代碼;線程2通過自旋操作來繼續獲得鎖。

在JDK6中,偏向鎖是默認啟用的。它提高了單線程訪問同步資源的性能。但試想一下,如果你的同步資源或代碼一直都是多線程訪問的,那麼消除偏向鎖這一步驟對你來說就是多餘的。事實上,消除偏向鎖的開銷還是蠻大的。
所以在你非常熟悉自己的代碼前提下,大可禁用偏向鎖:

 -XX:-UseBiasedLocking=false

輕量級鎖

“輕量級鎖”鎖也是一種鎖的狀態,這種鎖狀態的特點是:當一個線程來競爭鎖失敗時,不會立即進入阻塞狀態,而是會進行一段時間的鎖自旋操作,如果自旋操作拿鎖成功就執行同步代碼,如果經過一段時間的自旋操作還是沒拿到鎖,線程就進入阻塞狀態。

1. 輕量級鎖加鎖流程
線程在執行同步塊之前,JVM會先在當前線程的棧楨中創建用於存儲鎖記錄的空間,並將對象頭中的Mark Word複製到鎖記錄中,官方稱為Displaced Mark Word。然後線程嘗試使用CAS將對象頭中的Mark Word替換為指向鎖記錄的指針。如果成功,當前線程獲得鎖,如果失敗,表示其他線程競爭鎖,當前線程便嘗試使用自旋來獲取鎖。

2. 輕量級鎖解鎖流程
輕量級解鎖時,會使用原子的CAS操作將Displaced Mark Word替換回到對象頭,如果成功,則表示沒有競爭發生。如果失敗,表示當前鎖存在競爭,鎖就會膨脹成重量級鎖。

重量級鎖

因為自旋會消耗CPU,為了避免無用的自旋(比如獲得鎖的線程被阻塞住了),一旦鎖升級成重量級鎖,就不會再恢復到輕量級鎖狀態。當鎖處於這個狀態下,其他線程試圖獲取鎖時,都會被阻塞住,當持有鎖的線程釋放鎖之後會喚醒這些線程,被喚醒的線程就會進行新一輪的奪鎖之爭。

鎖自旋

自旋鎖原理非常簡單,如果持有鎖的線程能在很短時間內釋放鎖資源,那麼那些等待競爭鎖的線程就不需要做內核態和用戶態之間的切換進入阻塞掛起狀態,它們只需要等一等(自旋),等持有鎖的線程釋放鎖后即可立即獲取鎖,這樣就避免用戶線程和內核的切換的消耗。

但是線程自旋是需要消耗CPU的,說白了就是讓CPU在做無用功,線程不能一直佔用CPU自旋做無用功,所以需要設定一個自旋等待的最大時間。如果持有鎖的線程執行的時間超過自旋等待的最大時間扔沒有釋放鎖,就會導致其它爭用鎖的線程在最大等待時間內還是獲取不到鎖,這時爭用線程會停止自旋進入阻塞狀態。

自旋鎖盡可能的減少線程的阻塞,這對於鎖的競爭不激烈,且佔用鎖時間非常短的代碼塊來說性能能大幅度的提升,因為自旋的消耗會小於線程阻塞掛起操作的消耗!但是如果鎖的競爭激烈,或者持有鎖的線程需要長時間佔用鎖執行同步塊,這時候就不適合使用自旋鎖了,因為自旋鎖在獲取鎖前一直都是佔用cpu做無用功,線程自旋的消耗大於線程阻塞掛起操作的消耗,其它需要cup的線程又不能獲取到cpu,造成cpu的浪費。

JDK7之後,鎖的自旋特性都是由JVM自身控制的,不需要我們手動配置。

鎖對比

鎖的優化

  • 減少鎖的時間:不需要同步的代碼不加鎖;
  • 使用讀寫鎖:讀操作加讀鎖,可以併發讀,寫操作使用寫鎖,只能單線程寫;
  • 鎖粗化:假如有一個循環,循環內的操作需要加鎖,我們應該把鎖放到循環外面,否則每次進出循環,都進出一次臨界區,效率是非常差的;

參考

  • https://blog.csdn.net/lkforce/article/details/81128115
  • 《併發編程藝術》

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

【其他文章推薦】

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

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

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

台灣寄大陸海運貨物規則及重量限制?

大陸寄台灣海運費用試算一覽表

Java編程思想——第14章 類型信息(二)反射

六、反射:運行時的類信息

  我們已經知道了,在編譯時,編譯器必須知道所有要通過RTTI來處理的類。而反射提供了一種機制——用來檢查可用的方法,並返回方法名。區別就在於RTTI是處理已知類的,而反射用於處理未知類。Class類與java.lang.reflect類庫一起對反射概念進行支持,該類庫包含Field、Method以及Constructor(每個類都實現了Member接口)。這些類型是由JVM運行時創建的,用來表示未知類種對應的成員。使用Constructor(構造函數)創建新的對象,用get(),set()方法讀取和修改與Field對象(字段)關聯的字段,用invoke()方法調用與Method對象(方法)關聯的方法。這樣,匿名對象的類信息就能在運行時被完全確定下來,而在編譯時不需要知道任何事情。

  其實,當反射與一個未知類型的對象打交道時,JVM只是簡單地檢查這個對象,在做其他事情之前必須先加載這個類的Class對象。因此,那個類的.class文件對於JVM來說必須時可獲取的(在本地或網絡上)所以反射與RTTI的區別只在於:對於RTTI來說,編譯器在編譯時打開和檢查.class文件,而對於反射來說,.class文件在編譯時是不可獲得的,所以是運行時打開和檢查.class文件。反射在需要創建更動態的代碼時很有用。

七、動態代理

  代理是基本的設計模式:為其他對象提供一種代理,以便控制對象,而在對象前或后加上自己想加的東西。

interface Interface {
    void doSomething();

    void doSomeOtherThing(String args);
}

class RealObject implements Interface {

    @Override
    public void doSomething() {
        System.out.println("doSomething");
    }

    @Override
    public void doSomeOtherThing(String args) {
        System.out.println("doSomeOtherThing" + args);
    }
}

class SimpleProxy implements Interface {

    private Interface proxyId;

    public SimpleProxy(Interface proxyId) {
        this.proxyId = proxyId;
    }

    @Override
    public void doSomething() {
        //將原有的doSomething 方法添加上了一個輸出 這就是代理之後新增的東西
        //就好比某公司代理遊戲后加的內購
        System.out.println("SimpleProxy doSomething");
        proxyId.doSomething();
    }

    @Override
    public void doSomeOtherThing(String args) {
        proxyId.doSomeOtherThing(args);
        //新增的東西可以在原有之前或之後都行
        System.out.println("SimpleProxy doSomeOtherThing" + args);
    }
}

public class SimpleProxyDemo {
    static void consumer(Interface i) {
        i.doSomething();
        i.doSomeOtherThing(" yi gi woli giao");
    }

    public static void main(String[] args) {
        consumer(new RealObject());
        System.out.println("-----  -----  -----");
        consumer(new SimpleProxy(new RealObject()));
    }
}

結果:

doSomething
doSomeOtherThing yi gi woli giao
-----  -----  -----
SimpleProxy doSomething
doSomething
doSomeOtherThing yi gi woli giao
SimpleProxy doSomeOtherThing yi gi woli giao

  因為consumer()接受的Interface,所以無論是RealObject還是SimpleProxy,都可以作為參數,而SimpleProxy插了一腳 代理了RealObject加了不少自己的東西。

  java的動態代理更前進一步,因為它可以動態創建代理並動態地處理對所代理方法的調用。在動態代理上所做的所有調用都會被重定向到單一的調用處理器上,它的工作是揭示調用的類型並確定相應的對策。

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;

interface Interface {
    void doSomething();

    void doSomeOtherThing(String args);
}

class RealObject implements Interface {

    @Override
    public void doSomething() {
        System.out.println("doSomething");
    }

    @Override
    public void doSomeOtherThing(String args) {
        System.out.println("doSomeOtherThing" + args);
    }
}

class DynamicProxyHandler implements InvocationHandler {
    private Object proxyId;

    public DynamicProxyHandler(Object proxyId) {
        this.proxyId = proxyId;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("**** proxy:" + proxy.getClass() + ", method" + method + ", args:" + args);
        if (args != null) {
            for (Object arg : args) {
                System.out.println(" " + arg);
            }
        }
        return method.invoke(proxyId, args);
    }
}

public class SimpleProxyDemo {
    static void consumer(Interface i) {
        i.doSomething();
        i.doSomeOtherThing(" yi gi woli giao");
    }

    public static void main(String[] args) {
        RealObject realObject = new RealObject();
        consumer(realObject);
        System.out.println("-----  -----  -----");
     //動態代理 可以代理任何東西 Interface proxy
= (Interface) Proxy.newProxyInstance(Interface.class.getClassLoader(), new Class[]{Interface.class}, new DynamicProxyHandler(realObject)); consumer(proxy); } }

結果:

doSomething
doSomeOtherThing yi gi woli giao
-----  -----  -----
**** proxy:class $Proxy0, methodpublic abstract void Interface.doSomething(), args:null
doSomething
**** proxy:class $Proxy0, methodpublic abstract void Interface.doSomeOtherThing(java.lang.String), 
args:[Ljava.lang.Object;@7ea987ac  yi gi woli giao
doSomeOtherThing yi gi woli giao

通過Proxy.newProxyInstance()可以創建動態代理,這個方法需要三個參數:

1. 類加載器:可以從已經被加載的對象中獲取其類加載器;

2. 你希望該代理實現的接口列表(不可以是類或抽象類,只能是接口);

3. InvocationHandler接口的一個實現;

在 invoke 實現中還可以根據方法名處對不同的方法進行處理,比如:

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("**** proxy:" + proxy.getClass() + ", method" + method + ", args:" + args);
        if (args != null) {
            for (Object arg : args) {
                System.out.println(" " + arg);
            }
        }
        if (method.getName().equals("doSomething")) { System.out.println("this is the proxy for doSomething"); } return method.invoke(proxyId, args);
    }

還可以對參數或方法進行更多的操作因為 你已經得到了他們 盡情的使用你的代理權吧 ~~ 先加它十個內購。

九、接口與類型信息

  interface關鍵字的一種重要目標就是允許程序員隔離構件,進而降低耦合。反射,可以調用所有方法,甚至是private。唯獨final是無法被修改的,運行時系統會在不拋任何異常的情況接受任何修改嘗試,但是實際上不會發生任何修改。

    void callMethod(Object a, String methodName) throws Exception {
        Method method = a.getClass().getDeclaredMethod(methodName);
        method.setAccessible(true);
        method.invoke(a);
    }

 

 

  

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

【其他文章推薦】

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

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

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

大陸寄台灣空運注意事項

大陸海運台灣交貨時間多久?

在校生如何面向面試地學習Java,匹馬行天下之思維決定高度篇——大學再努力,培訓機構做兄弟,你的簡歷能幫你爭取到面試機會嗎

    最近我在博客園裡,看到不少在校的同學在學java,而且,在我最近舉辦的一次直播活動中,也有不少在校生同學來提問,java該怎麼學。

    對於那些已經工作的同學,哪怕才工作不久,畢竟也能從項目實踐里總結和探索java的學習途徑和相關方法。但在校生同學由於沒機會接觸實際項目,在學習內容、進階途徑和學成標準這些方面都是兩眼一抹黑,而大學里的內容可能偏重於理論,講述的技術往往也和軟件公司里常用的技術不匹配。

    這就導致了很多上心的在校生,雖然很努力,但到畢業時,才發現自己起早貪黑學成的技能並不能幫他們找到工作。在本文里,就將結合我面試實習生和畢業生的標準,專門給在校生這個群體一些學習Java方面的建議。

1 明確目標,先說下公司面試應屆生的標準

    我最近可能都在大公司,到畢業季,會到一些學校去校招,校招的標準描述起來很簡單:Java方面能幹活,或者能經短期幫帶后能幹活,具體標準如下。

    1 Web框架方面,需要以全棧的形式,了解SSM,或Spring Boot或Spring Cloud從前端到後端的基本語法,至少能在項目經理短期幫助下,能照着別人的例子寫代碼。應屆生候選人只要能講清楚相關框架的語法點和流程即可,最多再附帶說明下mybatis等組件的用法,至於redis,dubbo,根本沒要求。

    2 數據庫方面,能會基本的增刪改查即可,外帶一些基本概念,比如事務怎麼處理,JDBC里批處理怎麼處理。

    3 Java語法(也就是核心方面),其實如果能講清楚SSM等Web框架技能,這塊只要刷題就能過,比如就問些ArrayList和LinkedList的差別,以及多線程等的概念。

    4 人看上去聽話,想法少,學習能力強,責任心強,不是刺頭,這塊其實大多數人都可以達標。

    以上不要求有商業項目經驗,當然如果有,絕對是加分項,而且這還是大公司的面試應屆生的標準。至於一些小公司,或者是一些外包公司,有時候能招到人就阿彌陀佛了(至於有些能力比較強的一本的應屆生願不願意去還難說)。有些在招收應屆生的時候,不少小公司甚至在“項目經驗”方面沒要求,哪怕沒學習項目經驗也不要緊,只會問些網上比較大路的面試題,能說上來即可。

2 面試中大多數應屆生的實際表現

    從面試官角度來看,招收應屆生的標準其實是很低的,對應的,在招初級開發時,多少都需要有商業項目經驗。從這個角度來看,應屆生最好在校期間就找到工作,畢業后兩三個月找不到工作問題還不怎麼大,但如果半年後再找不到工作,那麼到時候被面試的標準就高於“應屆生”的標準了。

    這裏我無意貶低應屆生的水平,畢竟我們都是從這個階段過來的,但從面試情況來看,至少有將近一半的應屆生達不到標準,下面列些具體的表現。

    1 沒有框架開發的經驗,這裏最低要求是能自行搭建個SSM項目,但不少同學根本沒有。

    2 數據庫方面,就知道理論上的增刪改查,甚至不會在MySQL, Oracle和SQL Server平台上運行過SQL語句。

    3 Java核心方面,掌握了一大堆項目里一定不會用的,比如Swing之類的界面編程技術,但該掌握的多線程集合等,一些常用的概念也不清楚。

    論動手能力,有些同學甚至沒有在Eclipse等IDE上運行通Java代碼,或者出了基本的語法錯誤不知道如何自行解決,至於沒有debug調試經驗的,就更加見怪不怪了,而在代碼里需要加必要的try…catch異常處理語句,這就更加鳳毛麟角了。

    在一些一本大學里,理論和實際操作能力較差的同學雖然不多,但也有,就更別提其它大學和大專了。我也和一些大學老師打過交道,也看過一些大學里用的Java和數據庫等編程方面的教材,再結合諸多應屆生在面試時的表現,我的感受是,或許大學階段更會培養學生的理論素養,但大學生朋友在讀大學階段,一定要提升實際的編程能力,包含但不限於(SSM)框架的編程能力,數據庫實際操作能力和Java核心部分代碼的開發和調試能力 。 

3 哪些大學里學到的知識點面試大概率不問(根本不用太費精力看的技術有哪些)

     前幾天我看到篇大學生朋友寫的文章,,或許很多大學生朋友也知道上進,平時也在不斷看各種資料,但可能苦於方法不當,可能有些大學老師也沒真在公司里干過,也沒法給出合適的學習建議,所以導致最終畢業找工作時,能力沒達到基本的期望要求。

    也就是說,大學教育和公司面試需求之間存在差距,這就給一些培訓機構帶來了商機。但培訓機構收的錢也不便宜,而培訓班也不是一定能保證學生能找到工作,關鍵要靠自己。從這裏開始,就將給出有實際操作性的學習建議。

    我最近接觸到不少大學生朋友,發現他們努力正在學的知識,面試時未必會問,也就是說,這些點白學了。之前已經提到了面試的標準,這裏就將結合具體的知識點,列出面試時需要掌握的最低技能標準,除此之外,大概率不會問的。

    1  Java核心方面,集合,多線程,異常處理,IO,JDBC,面向對象技能,大概率會問到,其它的沒提到的,比如圖形化界面,NIO,Socket網絡編程,甚至Applet之類的,不會問到。

    2 數據庫方面,會寫增刪改查的SQL語句,知道存儲過程之類的概念,會通過索引優化查詢條件,會建表,會些諸如子查詢,group by,having,表關聯查詢等基本SQL技能,這裏請注意,至少得用過一種商業化數據庫。

    3 框架方面,需要有Spring+Spring MVC+mybatis框架的實際操作能力(不是商業項目開發能力),至於有Spring Boot或Spring Cloud,那更好了。

    4 綜合技能方面,能知道基本的數據結構知識(線性表外帶排序外帶一些樹的技能),基本的操作系統知識(一般僅限於線程進程概念),基本網絡通訊知識(一般僅限於網絡通訊模型和tcp udp協議),但這僅僅是“需要知道”而已。

     大家其實也可以通過看各種職位描述和招聘需求,看下哪些技能實際上是不會問的,對於這些知識,就不用學,從而把精力用到學實際Java相關技能上。

     這裏需要說明,在大學階段學的很多知識,不能說沒用。比如網絡通訊里的tcp底層通訊細節,這些技能或者要等到工作5年後升級到高級開發或架構師的時候才會用到,而且以高級開發視角觀察需要掌握的通訊協議細節知識,絕對要比大學階段要複雜。

    換句話說,很多技能,在大學階段也就“需要了解有這事”,以在大學階段的經歷,再多用時間學,估計也無法達到“實際項目的需求”,而且等到有實際項目經驗時,再學這類技能也就是一兩周的事情。兩廂一對比,結論就很明確了:在校階段應該更多積累實際開發能力,因為更得靠這個找工作。 

4 用一個月的時間了解Java核心部分的內容

    通過上文,大家大致可以了解到畢業時找工作的目標,如果再不了解,可以實際看下招聘要求,甚至直接多去參加招聘會和面試,總之優先考察實際的開發能力,具體在Java核心部分,該如何高效學習呢?

    1 在電腦上裝jdk,eclipse,別用editplus之類的工具,最好再用eclipse的自動編譯功能。這方面,其實是鍛煉自己的動手搭建環境的能力,工作后,開發是一方面,搭建環境的能力同樣重要。

    2 剛開始,一定得去找兩三本Java入門書,先通過運行現有代碼,理解代碼的含義。別光看書不運行,開始階段,也多運行別人的代碼,別自己敲代碼。這裏建議直接找書,因為相比一些視頻教材,畢竟書上的知識很系統,而且能正式出版的書一般沒代碼問題,能直接運行。不建議自己敲代碼,是因為自己敲代碼時,多少會遇到問題,遇到問題后延誤學習進度是小,因為一直得不到解決從而影響學習信心,甚至終止學習了,事情就大了。

    3 如果找到兩三本Java入門書,一般其中涵蓋的知識系統大多很相似,大家可以先運行一遍所有代碼,這樣就能大致掌握代碼結構和基本知識點,而且由於書上代碼一般問題不大,而且質量也不會低,至少不會有太大的阻礙性問題。

    4 當運行好以後,着重觀察集合,面向對象,多線程,IO處理,JDBC,異常處理相關章節,這個階段,是以掌握API用法為主,在這基本上再看下諸如接口,抽象類,異常處理流程,垃圾回收之類的高級知識點。 

    在上述基礎上,如果可以通過資料的幫助,用Java實現堆棧,鏈表,隊列,散列表,樹等的數據結構,同時操練各種排序算法,這對找工作也有些幫助。

5 用半個月的時間,以MySQL為例,了解數據庫的大致操作

    在數據庫方面,最好也去找本書,同時在MYSQL上實踐。為什麼選MYSQL?因為這比較輕,相比Oracle而言,好安裝,當然如果有條件裝SQL Server之類的,那就更好了。 

    1 在MySQL數據庫上,實踐各種增刪改查的SQL語句,實踐建表,建索引能技巧,同時實踐一下諸如子查詢,with as等等複雜的SQL語句。

    2  用JDBC連同MYSQL,在Java代碼里做各種增刪改查的操作。

    3  在此基礎上,了解諸如索引,範式和鎖等概念,這時候雖然認識也會很膚淺,但至少不會一頭霧水了。

    這樣,在數據庫方面,好歹有實際操作經驗了,這為之後的項目實踐,能打下很好的基礎。

6 用一個月的時間,了解基於Spring的web框架

    面試時更看重的是框架經驗,這塊學習的建議如下。

    1 先通過運行代碼,了解Spring里IOC, AOP,這時應該注意各種配置。

    2 熟悉Spring的基本概念后,可以嘗試跑一個SSM的小例子,這個例子可以非常簡答,就一個頁面也行,但要包含Spring MVC和Mybatis諸多要素,這樣大家好歹能知道框架的構成,在這個基礎上,可以繼續擴展,加些必要的業務,從而進一步了解這個框架。

    在這個階段,還是最好看書上的例子,因為書上的例子一定能通,而且還會帶部署和運行的步驟,還是不建議自己敲代碼,因為SSM框架相對複雜,在這個階段如果自己敲,很有可能會因為問題太多而放棄。

    3 在自己機器上跑通SSM框架的案例后,可以網上找個帶業務的系統,比如圖書管理系統等,從中看些前端和後端交互數據的流程,同時,結合業務看Mybatis里的ORM過程,以及Spring里的常用註解。     

7 在學習過程中,可以避免的誤區

    Java方面,本人按照上述步驟輔導過不少在校的同學,只要肯上心練習,效果不會太差,不過很多同學在實踐過程中會走彎路,這裏列些普遍存在的問題,請大家在操練的過程中盡量避免。

    1 別鑽牛角尖,先面再點。比如有同學對一個知識點不理解,或者一段代碼運行有問題,就會在這個點上耗費很多時間,不解決就不繼續。其實在這個過程中,首先需要全方位掌握SSM框架、Java技術和數據庫,個別點如果有問題,可以跳過,或者一個案例運行不通可以運行其它類似的,總之別在一個點上花費太多的時間。

    2 再啰嗦一下,最好先照着書上代碼運行,開始階段的學習方法是“複製粘貼運行理解”,在自己已經有一定的基礎后,再嘗試自己寫代碼。

    3 在操練SSM項目時,有些同學會照着視頻上提到步驟做,如果有些視頻步驟不對,這樣就會有問題,所以還是建議照着書做。

    4 工具要選對,剛開始就eclipse,或者Idea,別用editplus或命令行。

    上述是方法上的誤區,其實最大的問題出在態度上,上述學習過程持續時間不會短,快則兩三個月,慢則半年,如果中途因為效果不明顯而放棄,那就很可惜了。 

8 有學習項目經驗后,爭取找些商業項目的實踐機會

    按照上述步驟,讓自己擁有最基本的SSM以及其它Java和數據庫相關技能后,要做的絕不是繼續積累學習項目經驗,而是盡可能去找實習的機會,以積累商業項目的經驗。在找實習經驗方面,大家可以參照如下的建議。

    1 在我之前的博文里也提到,大三時,打聽計算機學院里哪些老師和外面公司有合作,一般碩導都有這樣的項目,然後直接去找老師,剛開始不要錢,只求經驗,或許對各位在校生同學而言,這種方式是比較可行的,本人第一個商業項目經驗也是由此得到的。

    2 一般學校里都會安排實習,實習的過程中,一定要重視,這個是實打實的商業項目經驗。

    3 寒暑假,找軟件公司,這可能會比較艱辛,因為在校階段自己非常難找相關實習機會,但要去找。

    4 這個大家根據自己的實際情況自己斟酌:如果報培訓班,多少能積累些項目經驗,但這僅僅是學習項目經驗,不過在培訓班裡,可以找相關老師推薦實習的機會。

    5 如果實在找不到實習的機會,那麼盡可能通過各種渠道,去找商業項目經驗的案例,我知道有些網站有,但不做廣告。雖然靠這種方式積累的商業項目經驗質量就打折扣了,但好歹聊勝於無,而且畢竟很多畢業生,連學習項目經驗都沒。 

    不少在校的同學發現,哪怕實際只幹了三個月的商業項目經驗,自己的技能也會很大程度提升,而且實際的商業項目經驗,會讓大家掌握書本上根本不會多提但項目里一定會用的技能,比如JVM內存調優或多線程併發。從這意義上來講,只要有條件,大學生朋友應該擠破頭去找商業項目的經驗,而不是悠哉游哉地坐在機房裡敲代碼。只要你有商業項目的經驗,哪怕就三個月,找工作時你就有代差優勢。

9 畢業生準備簡歷的要點

    按照上述步驟,大家在畢業時,多少會有些商業項目經驗,再不濟也能有學習項目經驗,請記住,在招聘畢業生時,第一看項目經驗,第二看項目里包含的技能,第三再問算法和理論問題,至於邏輯題和情商題,只供參考。

     對此,畢業生在簡歷中,一定得突出做過的項目經驗,優先挖掘商業項目經驗,實在沒有學習項目也行。如果沒任何項目經驗,那麼找工作時會吃力很多。本文的重點是講學習方法,準備簡歷的技能只是稍微提到。這塊可以參考的之前寫的博文,。如果有時間的話,或許我會再專門針對畢業生朋友,寫篇文章講在java方面,如何準備簡歷和面試,以及如何找工作。 

10 總結:最多堅持半年,技能就會大變樣

    我記得兩年前,我的Python能力僅限於寫hello world,我運行代碼看文檔,辛苦堅持了半年,自認為就達到了出版書的地步,再過了半年,果真就從出版社接到了一本以股票案例講述Python技術的選題,並自認為寫的內容不會誤人子弟。

    我持續關注了一位大學生網友的公眾號,也就是寫了半年多博客,他技術看上去就更專業多了。能堅持不懈地上進,這種精神值得提倡,雖然我工作很久了,但也得時刻警惕,不能懈怠,這也是我肯推薦該公眾號的原因,不僅推薦其內容,更提倡這種精神。

    不光是這位同學,經我培訓的其它很多大學生,也只要肯上心學,最多半年,最短三個月,就能從小白進階到能實際幹活的水平,而且還真能面試進軟件公司幹活。 

    本文雖然長,但其中也是盡我所能,給出大學生朋友若干有實際操作性的學習建議,其實對於其它初學者,本文給出的建議同樣適用。希望本文能幫到大家,最後感謝大家能讀完此文。

版權說明:

    如果要轉載本文,請先徵得本人同意。

 

 

 

 

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

【其他文章推薦】

※專營大陸空運台灣貨物推薦

台灣空運大陸一條龍服務

Tsx寫一個通用的button組件

一年又要到年底了,vue3.0都已經出來了,我們也不能一直還停留在過去的js中,是時候學習並且在項目中使用一下Ts了。

  如果說jsx是基於js的話,那麼tsx就是基於typescript的

  廢話也不多說,讓我們開始寫一個Tsx形式的button組件,

  ts真的不僅僅只有我們常常熟知的數據類型,還包括接口,類,枚舉,泛型,等等等,這些都是特別重要的

  項目是基於vue-cli 3.0 下開發的,可以自己配置Ts,不會的話那你真的太難了

  

 

     我們再compenonts中新建一個button文件夾,再建一個unit文件夾,button放button組件的代碼,unit,放一些公共使用模塊

  我們再button文件夾下創建 ,index .tsx放的button源碼,index.less放的是樣式,css也是不可缺少的

       

 

   分析一下button需要的一些東西

  第一個當然是props,還有一個是點擊事件,所以我們第一步就定義一下這兩個類型

type ButtonProps = {
  tag: string,
  size: ButtonSize,
  type: ButtonType,
  text: String
}

type ButtonEvents = {
  onClick?(event: Event) :void
}
type ButtonSize = 'large' | 'normal' | 'small' | 'mini'
type ButtonType = 'default' | 'primary' | 'info' | 'warning' | 'danger'

  因為button是很簡單的組件,內部也沒有一些特別的狀態需要改變,所以我們用函數式組件的方式去寫(之後的render會用到這個方法)

function Button (h: CreateElement, props: ButtonProps, slots: DefaultSlots, ctx: RenderContext<ButtonProps>) {
  const { tag, size, type } = props
  let text
  console.log(slots)
  text = slots.default ? slots.default() : props.text
  function onClick (event: Event) {
    emit(ctx, 'click', event)
  }
  let classes = [size,type]
  return (
    <tag
      onClick = {onClick}
      class = {classes}
    >
      {text}
    </tag>
  )
}

  h 是一個預留參數,這裏並沒有用到 ,CreateElement  這個是vue從2.5之後提供的一個類型,也是為了方便在vue項目上使用ts

  props 就是button組件的傳入的屬性,slots插槽,ctx,代表的是當前的組件,可以理解為當前rendercontext執行環境this

  DefaultSlots是我們自定義的一個插槽類型

export type ScopedSlot<Props = any> = (props?: Props) => VNode[] | VNode | undefined;

export type ScopedSlots = {
  [key: string]: ScopedSlot | undefined;
}

  插槽的內容我們都是需要從ctx中讀取的,默認插槽的key就是defalut,具名插槽就是具體的name

  button放發內部還有一個具體的點擊事件,還有一個emit方法,從名字我們也可以看的出,他是粗發自定義事件的,我們這裏當然不能使用this.emit去促發,

  所以我們需要單獨這個emit方法,我們知道組件內所以的自定義事件都是保存在listeners里的,我們從ctx中拿取到所以的listeners



  import { RenderContext, VNodeData } from ‘vue’ // 從vue中引入一些類型


function
emit (context: RenderContext, eventName: string, ...args: any[]) { const listeners = context.listeners[eventName] if (listeners) { if (Array.isArray(listeners)) { listeners.forEach(listener => { listener(...args) }) } else { listeners(...args) } }

  這樣我們組件內部的事件觸發就完成了

  我們的button肯定是有一些默認的屬性,所以,我們給button加上默認的屬性

Button.props = {
  text: String,
  tag: {
    type: String,
    default: 'button'
  },
  type: {
    type: String,
    default: 'default'
  },
  size: {
    type: String,
    default: 'normal'
  }
}

  我們定義一個通用的functioncomponent 類型

type FunctionComponent<Props=DefaultProps, PropsDefs = PropsDefinition<Props>> = {
  (h: CreateElement, Props:Props, slots: ScopedSlots, context: RenderContext<Props>): VNode |undefined,
  props?: PropsDefs
}

  PropsDefinition<T>  這個是vue內部提供的,對 props的約束定義

  不管怎麼樣我們最終返回的肯定是一個對象,我們把這個類型也定義一下

  ComponentOptions<Vue> 這個也是vue內部提供的

 interface DrmsComponentOptions extends ComponentOptions<Vue> {
  functional?: boolean;
  install?: (Vue: VueConstructor) => void;
}

  最終生成一個組件對象

function transformFunctionComponent (fn:FunctionComponent): DrmsComponentOptions {
  return {
    functional: true, // 函數時組件,這個屬性一定要是ture,要不render方法,第二個context永遠為underfine
    props: fn.props,
    model: fn.model,
    render: (h, context): any => fn(h, context.props, unifySlots(context), context)
  }
}

  unifySlots 是讀取插槽的內容

// 處理插槽的內容
export function unifySlots (context: RenderContext) {
  // use data.scopedSlots in lower Vue version
  const scopedSlots = context.scopedSlots || context.data.scopedSlots || {}
  const slots = context.slots()

  Object.keys(slots).forEach(key => {
    if (!scopedSlots[key]) {
      scopedSlots[key] = () => slots[key]
    }
  })

  return scopedSlots
}

  當然身為一個組件,我們肯定是要提供全局注入接口,並且能夠按需導入

  所以我們給組件加上名稱和install方法,install 是 vue.use() 方法使用的,這樣我們能全部註冊組件

export function CreateComponent (name:string) {
  return function <Props = DefaultProps, Events = {}, Slots = {}> (
    sfc:DrmsComponentOptions | FunctionComponent) {
    if (typeof sfc === 'function') {
      sfc = transformFunctionComponent(sfc)
    }
    sfc.functional = true
    sfc.name = 'drms-' + name
    sfc.install = install
    return sfc 
  }
}

  index.tsx 中的最後一步,導出這個組件

export default CreateComponent('button')<ButtonProps, ButtonEvents>(Button)

  還少一個install的具體實現方法,加上install方法,就能全局的按需導入了

function install (this:ComponentOptions<Vue>, Vue:VueConstructor) {
  const { name } = this
  Vue.component(name as string, this)
}

 

   最終實現的效果圖,事件的話也是完全ok的,這個我也是測過的

 

   代碼參考的是vant的源碼:

  該代碼已經傳到git:     dev分支應該是代碼全的,master可能有些並沒有合併

 

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

【其他文章推薦】

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

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

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

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

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

在開發框架中擴展微軟企業庫,支持使用ODP.NET(Oracle.ManagedDataAccess.dll)訪問Oracle數據庫,基於Enterprise Library的Winform開發框架實現支持國產達夢數據庫的擴展操作

在前面隨筆《》中介紹了在代碼生成工具中使用ODP.NET(Oracle.ManagedDataAccess.dll)訪問Oracle數據庫,如果我們在框架應用中需要使用這個如何處理了?由於我們開發框架底層主要使用微軟企業庫(目前用的版本是4.1),如果是使用它官方的Oracle擴展,那麼就是使用EntLibContrib.Data.OdpNet(這個企業庫擴展類庫使用了Oracle.DataAccess.dll),不過這種方式還是受限於32位和64位的問題;假如我們使用ODP.NET(Oracle.ManagedDataAccess.dll)方式,可以使用自己擴展企業庫支持即可,類似於我們支持國產數據庫–達夢數據庫一樣的原理,使用Oracle.ManagedDataAccess類庫可以避免32位和64位衝突問題,實現統一兼容。

1、擴展支持ODP.NET(Oracle.ManagedDataAccess.dll)訪問

為了實現自定義的擴展支持,我們需要對企業庫的擴展類庫進行處理,類似我們之前編寫達夢數據庫的自定義擴展類庫一樣,這方面可以了解下之前的隨筆《》,我們現在增加對ODP.NET(Oracle.ManagedDataAccess.dll)方式的擴展支持。

首先我們創建一個項目,並通過Nugget的方式獲得對應的Oracle.ManagedDataAccess.dll類庫,參考企業庫對於Mysql的擴展或者其他的擴展,稍作調整即可。

 OracleDatabase類似下面代碼

using System;
using System.Data;
using System.Data.Common;

using Microsoft.Practices.EnterpriseLibrary.Common;
using Microsoft.Practices.EnterpriseLibrary.Data;
using Microsoft.Practices.EnterpriseLibrary.Data.Configuration;
using Oracle.ManagedDataAccess.Client;

namespace EntLibContrib.Data.OracleManaged
{
    /// <summary>
    /// <para>Oracle數據庫對象(使用ODP驅動)</para>
    /// </summary>
    /// <remarks>
    /// <para>
    /// Internally uses OracleProvider from Oracle to connect to the database.
    /// </para>
    /// </remarks>
    [DatabaseAssembler(typeof(OracleDatabaseAssembler))]
    public class OracleDatabase : Database
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="OracleDatabase"/> class
        /// with a connection string.
        /// </summary>
        /// <param name="connectionString">The connection string.</param>
        public OracleDatabase(string connectionString) : base(connectionString, OracleClientFactory.Instance)
        {
        }
        
        /// <summary>
        /// <para>
        /// Gets the parameter token used to delimit parameters for the
        /// Oracle database.</para>
        /// </summary>
        /// <value>
        /// <para>The '?' symbol.</para>
        /// </value>
        protected char ParameterToken
        {
            get
            {
                return ':';
            }
        }

        .........

主要就是把對應的類型修改為Oracle的即可,如Oracle的名稱,以及參數的符號為 :等地方,其他的一一調整即可,不在贅述。

完成后,修改程序集名稱,編譯為 EntLibContrib.Data.OracleManaged.dll 即可。

 

2、框架應用的數據庫配置項設置

完成上面的步驟,我們就可以在配置文件中增加配置信息如下所示,它就能正常的解析並處理了。

 

 上面使用了兩種方式,一種是官方擴展的EntLibContrib.Data.OdpNet方式,一種是我們這裏剛剛出爐的 EntLibContrib.Data.OracleManaged方式,完整的數據庫支持文件信息如下所示。

<?xml version="1.0"?>
<configuration>
  <configSections>
    <section name="dataConfiguration" type="Microsoft.Practices.EnterpriseLibrary.Data.Configuration.DatabaseSettings, Microsoft.Practices.EnterpriseLibrary.Data"/>
    <section name="oracleConnectionSettings" type="EntLibContrib.Data.OdpNet.Configuration.OracleConnectionSettings, EntLibContrib.Data.OdpNet" />
  </configSections>
  <connectionStrings>
    <!--SQLServer數據庫的連接字符串-->
    <add name="sqlserver" providerName="System.Data.SqlClient" connectionString="Persist Security Info=False;Data Source=(local);Initial Catalog=WinFramework;Integrated Security=SSPI"/>
    
    <!--Oracle數據庫的連接字符串-->
    <add name="oracle" providerName="System.Data.OracleClient" connectionString="Data Source=orcl;User ID=whc;Password=whc"/>
    
    <!--MySQL數據庫的連接字符串-->
    <add name="mysql" providerName="MySql.Data.MySqlClient" connectionString="Server=localhost;Database=WinFramework;Uid=root;Pwd=123456;"/>
    
    <!--PostgreSQL數據庫的連接字符串-->
    <add name="npgsql" providerName="Npgsql" connectionString="Server=localhost;Port=5432;Database=postgres;User Id=postgres;Password=123456"/>
    
    <!--路徑符號|DataDirectory|代表當前運行目錄-->    
    <!--SQLite數據庫的連接字符串-->
    <add name="sqlite"  providerName="System.Data.SQLite" connectionString="Data Source=|DataDirectory|\WinFramework.db;Version=3;" />
    <!--Microsoft Access數據庫的連接字符串-->
    <add name="access" providerName="System.Data.OleDb" connectionString="Provider=Microsoft.Jet.OLEDB.4.0;Data Source=|DataDirectory|\WinFramework.mdb;User ID=Admin;Jet OLEDB:Database Password=;" />   
    
    <!--IBM DB2數據庫的連接字符串-->
    <add    name="db2" providerName="IBM.Data.DB2"    connectionString="database=whc;uid=whc;pwd=123456"/>
    
    <!--採用OdpNet方式的Oracle數據庫的連接字符串-->
    <add    name="oracle2"    providerName="Oracle.DataAccess.Client"    connectionString="Data Source=orcl;User id=win;Password=win;" />
    <add    name="oracle3"    providerName="OracleManaged"    connectionString="Data Source=(DESCRIPTION=(ADDRESS=(PROTOCOL=TCP)(HOST=localhost)(PORT=1521))(CONNECT_DATA=(SERVER=DEDICATED)(SERVICE_NAME=orcl.mshome.net)));User ID=win;Password=win" />
  </connectionStrings>
  <dataConfiguration defaultDatabase="oracle3">
    <providerMappings>
      <add databaseType="EntLibContrib.Data.MySql.MySqlDatabase, EntLibContrib.Data.MySql" name="MySql.Data.MySqlClient" />
      <add databaseType="EntLibContrib.Data.SQLite.SQLiteDatabase, EntLibContrib.Data.SqLite" name="System.Data.SQLite" />
      <add databaseType="EntLibContrib.Data.PostgreSql.NpgsqlDatabase, EntLibContrib.Data.PostgreSql" name="Npgsql" />      
      <add databaseType="EntLibContrib.Data.DB2.DB2Database, EntLibContrib.Data.DB2" name="IBM.Data.DB2" />
      <add databaseType="EntLibContrib.Data.OdpNet.OracleDatabase, EntLibContrib.Data.OdpNet" name="Oracle.DataAccess.Client" />
      <add databaseType="EntLibContrib.Data.Dm.DmDatabase, EntLibContrib.Data.Dm" name="Dm" />
      <!--增加ODP.NET(Oracle.ManagedDataAccess.dll)方式的擴展支持-->
      <add databaseType="EntLibContrib.Data.OracleManaged.OracleDatabase, EntLibContrib.Data.OracleManaged" name="OracleManaged" />
    </providerMappings>
  </dataConfiguration>
  
  <appSettings>

  </appSettings>
  <startup useLegacyV2RuntimeActivationPolicy="true">
    <supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.0"/>
    <supportedRuntime version="v2.0.50727"/>
  </startup>
</configuration>

這樣我們底層就可以實現多種數據庫的兼容訪問了。

採用不同的數據庫,我們需要為不同數據庫的訪問層進行生成處理,如為SQLServer數據的表生成相關的數據訪問層DALSQL,裏面放置各個表對象的內容,不過由於採用了相關的繼承類處理和基於數據庫的代碼生成,需要調整的代碼很少。

我們來編寫一段簡單的程序代碼來測試支持這種ODP.net方式,測試代碼如下所示。

private void btnGetData_Click(object sender, EventArgs e)
{
    string sql = "select * from T_Customer";// + " Where Name = :name";
    Database db = DatabaseFactory.CreateDatabase();
    DbCommand command = db.GetSqlStringCommand(sql);
    //command.Parameters.Add(new OracleParameter("name", "張三"));

    using (var ds = db.ExecuteDataSet(command))
    {
        this.dataGridView1.DataSource = ds.Tables[0];   
    }
}

測試界面效果如下所示。

以上這些處理,可以適用於Web框架、Bootstrap開發框架、Winform開發框架、混合式開發框架中的應用,也就是CS、BS都可以使用。

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

【其他文章推薦】

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

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

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

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

面向對象和面向過程到底是怎麼回事?

今天下午在一個組的項目回顧會議上,這個同事講了自己用DDD思想對三個模塊的重構。把之前在Service層的一些業務邏輯下沉到了領域層里,由之而引起的討論。

部門經理:“其實你的業務邏輯總體並沒有少,只是把邊界重新劃分了一下。”

一起參与開發的同事:“在第二個模塊中(任務系統,包括了任務拆分,狀態跟蹤等)這種思想比較有優勢,在一三項目中不是很明顯。”

於是引出了我的一個問題:“到底什麼是面向對象,什麼是面向過程,在什麼情況下適合面向對象,什麼場景下適用於面向過程?”

  • 以C語言和Java語言為例: C語言沒有類,但是有結構體,結構體中不能有函數,只能有屬性。這說明了什麼?說明了在面向過程的思考方式中,數據和操作是嚴格分離的
  • C語言中為什麼函數需要定義到調用此函數的前面,也就是說先聲明后調用?如果按照流程化的思路來看這種設計方式,想要調用一個子流程,勢必要在調用之前就定義好
  • 而在java的類中,就沒有函數定義先後的問題,這與面向過程和面向對象的最小定義粒度有關,面向過程的最小定義粒度為流程(方法、操作、函數),而在面向對象中,最小定義粒度為對象,這個對象的行為沒有先後,包含在對象這個大的容器中。
  • 封裝、抽象、繼承、多態其實就是類比的對象進行的建模,比如以人為例,人有些屬性不想示人,有些屬性只能給指定的人了解,這就是封裝。人掌握的知識其實是現象的一種抽象。人繼承來來自父母的一些生活習慣,而又有所不同,這就是多態。
  • 歸總, 子類相對父類來說有不同的模型(對真實世界的建模),這是4種面向對象的終極原因。 
  • 為什麼面向對象的思考方式更有利於擴展維護?拿一個工作崗位為例,一個人在一個工作崗位上,如果有一天這個崗位有了更多的工作要求,如果改動量較小,那麼對該崗位的人進行技能培訓就可以了。如果要求多到一種程度,拆分成兩個人,或者拆分成多個崗位。而如果用面向過程的思路,那麼每次改動,都相當於多了一個流程?(這裏存疑,多流程的問題在哪?難維護的理由是什麼?這裏我沒有想明白
  • 面向過程要求人有更好的流程化思維方式,面向對象要求人有更好的抽象思維方式。那麼如果有一天出現一個“面向文檔編程”呢?要求人有更好的把問題描述清楚的表達能力。換句話說, 面向過程就是面向流程思考,面向對象就是針對模型思考

最後距離,如果我們描述入職流程,一個大牛的入職流程可能和一個應屆生的入職流程完全不一樣,如果把入職這個行為寫到employee的方法中,那麼這就是面向對象的寫法,如果維護一個入職流程的方法,根據不同的人用switch case的方式進行不同行為的跳轉,那麼就是面向過程。

面向過程就是面向流程思考,面向對象就是針對模型思考

 

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

【其他文章推薦】

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

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

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

Java開發者學習技術體系

01基礎技術體系

我認為知識技能體系化是判斷技術是否過關的第一步。知識體系化包含兩層含義:

1、 能夠知道技術知識圖譜(高清版圖譜掃文末二維碼)的內容

比如分佈式系統中常用的RPC技術,其背後就涉及到網絡IO(Netty)、網絡協議、服務發現(Zookeeper配置中心)、RPC服務治理(限流、熔斷、降級)、負載均衡等。

2、 能夠理清各類技術概念之間的區別和聯繫

在分佈式系統領域中,有很多相似的概念,但又分佈在不同的產品或層級中。比如負載均衡這個詞,DNS、LVS、Ngnix、F5等產品都能實現,而且在大型分佈式系統中他們會同時存在,那麼就要搞清楚他們各自的位於什麼層級,解決了什麼問題。

再比如緩存這項技術,有分佈式緩存、本地緩存、數據庫緩存,在往下還有硬件層級的緩存。同樣都是緩存,他們之間的區別又是什麼?

如果你仔細去觀察,大廠的後端開發工程師總是能對整個技術體系了如指掌,從而在系統設計與技術選型階段就能夠做出較為合理的架構。 

02實踐經驗的積累

       能否快速解決實戰中的業務問題是判斷技術是否過關的第二步。
       大家在面試的過程中,都會有一種體會:我的知識體系已經建立了,但在回答面試官問題的時候,總感覺像在背答案,而且也沒有辦法針對性的回答面試官問題。比如在面試官問到這些問題時:

  1. 我們知道消息隊列可應用於耦系統,應對異步消費等場景,那如何在網絡不可靠的場景下保證業務數據處理的正確性?
  2. 我們都知道在分佈式系統會用到緩存,那該如何設置緩存失效機制才能避免系統出現緩存雪崩?
  3. 我們都或多或少的知道系統發布上線的流程,但在大流量場景下採用何種發布機制才能盡可能的做到平滑?

能完善的解決這些問題是區分一個程序員是否有經驗的重要標誌,知識的體系化是可以從書本不斷的凝練來獲得,但經驗的積累需要通過實戰的不斷總結

對很多人來說很為難的一點是,平時寫着的業務代碼,很少有機會接觸到大廠的優秀實踐,那麼這時候更需要從如下兩個角度逼問:

1、當流量規模再提高几個量級,那麼我的系統會出現什麼問題?

2、假如其中一個環節出現了問題,那麼該怎麼保證系統的穩定性?

03技術的原理

上面的提到都是將技術用於業務實踐,以及高效的解決業務中出現的問題。但這是否就意味着自己的技術已經過關了呢?我認為還不能。

判斷技術是否過關的第三步是能否洞察技術背後的設計思想和原理。

如果你參加過一些大廠面試,還會問到一些開放性的問題:

1、 寫一段程序,讓其運行時的表現為觸發了5次Young GC、3次Full GC、然後3次Young GC;

2、 如果一個Java進程突然消失了,你會怎麼去排查這種問題?

3、 給了一段Spring加載Bean的代碼片段,闡述一下具體的執行流程?

       是不是看上去很難,是不是和自己準備的“題庫”中的問題不一樣?不知道從何處下手?如果你有這種感覺,那麼說明你的技術還需要繼續修鍊。

       你要明白的是這種開放性的問題,提問的角度千變萬化,但最終落腳點卻都是基本原理。如果你不了解GC的觸發條件,你就肯定無法答出第一題;同樣,如果你對Spring啟動機制了解的很清楚,那麼無論他給出的是什麼樣的代碼,你都能回答出代碼經歷的過程。如果你能以不變應萬變,那麼恭喜你,你的技術過關了。

       上面提到了很多技術問題,這裏我不做詳細的解釋,都能在下面的技術圖譜中找到答案:

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

【其他文章推薦】

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

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

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

【Leetcode 做題學算法周刊】第四期

首發於微信公眾號《前端成長記》,寫於 2019.11.21

背景

本文記錄刷題過程中的整個思考過程,以供參考。主要內容涵蓋:

  • 題目分析設想
  • 編寫代碼驗證
  • 查閱他人解法
  • 思考總結

目錄

Easy

67.二進制求和

題目描述

給定兩個二進制字符串,返回他們的和(用二進製表示)。

輸入為非空字符串且只包含数字 10

示例:

輸入: a = "11", b = "1"
輸出: "100"

輸入: a = "1010", b = "1011"
輸出: "10101"

題目分析設想

這道題又是一道加法題,所以記住下,直接轉数字進行加法可能會溢出,所以不可取。所以我們需要遍歷每一位來做解答。我這有兩個大方向:補0后遍歷,和不補0遍歷。但是基本的依據都是本位相加,逢2進1即可,類似手寫10進制加法。

  • 補0后遍歷,可以採用先算出的位數推入數組最後反轉,也可以採用先算出的位數填到對應位置后直接輸出
  • 不補0遍歷,根據短數組的長度進行遍歷,長數組剩下的数字與短數組生成的進位進行計算

查閱他人解法

Ⅰ.補0后遍歷,先算先推

代碼:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let times = Math.max(a.length, b.length) // 需要遍歷次數
    // 補 0
    while(a.length < times) {
        a = '0' + a
    }
    while(b.length < times) {
        b = '0' + b
    }
    let res = []
    let carry = 0 // 是否進位
    for(let i = times - 1; i >= 0; i--) {
        const num = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
        carry = num >= 2 ? 1 : 0
        res.push(num % 2)
    }
    if (carry === 1) {
        res.push(1)
    }
    return res.reverse().join('')
};

結果:

  • 294/294 cases passed (68 ms)
  • Your runtime beats 95.13 % of javascript submissions
  • Your memory usage beats 72.58 % of javascript submissions (35.4 MB)
  • 時間複雜度 O(n)

Ⅱ.補0后遍歷,按位運算

代碼:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let times = Math.max(a.length, b.length) // 需要遍歷次數
    // 補 0
    while(a.length < times) {
        a = '0' + a
    }
    while(b.length < times) {
        b = '0' + b
    }
    let res = []
    let carry = 0 // 是否進位
    for(let i = times - 1; i >= 0; i--) {
        res[i] = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
        carry = res[i] >= 2 ? 1 : 0
        res[i] %= 2
    }
    if (carry === 1) {
        res.unshift(1)
    }
    return res.join('')
};

結果:

  • 294/294 cases passed (60 ms)
  • Your runtime beats 99.65 % of javascript submissions
  • Your memory usage beats 65.82 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(n)

Ⅲ.不補0遍歷

當然處理方式還是可以選擇上面兩種,我這就採用先算先推來處理了。

代碼:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let max = Math.max(a.length, b.length) // 最大長度
    let min = Math.min(a.length, b.length) // 最大公共長度

    // 將長字符串拆成兩部分
    let left = a.length > b.length ? a.substr(0, a.length - b.length) : b.substr(0, b.length - a.length)
    let right = a.length > b.length ? a.substr(a.length - b.length) : b.substr(b.length - a.length)

    // 公共長度部分遍歷
    let rightRes = []
    let carry = 0
    for(let i = min - 1; i >= 0; i--) {
        const num = carry + (right.charAt(i) | 0) + (((a.length > b.length ? b : a)).charAt(i) | 0)
        carry = num >= 2 ? 1 : 0
        rightRes.push(num % 2)
    }

    let leftRes = []
    for(let j = max - min - 1; j >= 0; j--) {
        const num = carry + (left.charAt(j) | 0)
        carry = num >= 2 ? 1 : 0
        leftRes.push(num % 2)
    }

    if (carry === 1) {
        leftRes.push(1)
    }
    return leftRes.reverse().join('') + rightRes.reverse().join('')
};

結果:

  • 294/294 cases passed (76 ms)
  • Your runtime beats 80.74 % of javascript submissions
  • Your memory usage beats 24.48 % of javascript submissions (36.2 MB)
  • 時間複雜度 O(n)

查閱他人解法

看到一些細節上的區別,我這使用 '1' | 0 來轉数字,有的使用 ''1' - '0''。另外還有就是初始化結果數組長度為最大長度加1后,最後判斷首位是否為0需要剔除的,我這使用的是判斷最後是否還要進位補1。

這裏還看到用一個提案中的 BigInt 類型來解決的

Ⅰ.BigInt

代碼:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2);
};

結果:

  • 294/294 cases passed (52 ms)
  • Your runtime beats 100 % of javascript submissions
  • Your memory usage beats 97.05 % of javascript submissions (34.1 MB)
  • 時間複雜度 O(1)

思考總結

通過 BigInt 的方案我們能看到,使用原生方法確實性能更優。簡單說一下這個類型,目前還在提案階段,看下面的等式基本就能知道實現原理自己寫對應 Hack 來實現了:

BigInt(10) = '10n'
BigInt(20) = '20n'
BigInt(10) + BigInt(20) = '30n'

雖然這種方式很友好,但是還是希望看到加法題的時候,能考慮到遍歷按位處理。

69.x的平方根

題目描述

實現 int sqrt(int x) 函數。

計算並返回 x 的平方根,其中 x 是非負整數。

由於返回類型是整數,結果只保留整數的部分,小數部分將被捨去。

示例:

輸入: 4
輸出: 2

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
     由於返回類型是整數,小數部分將被捨去。

題目分析設想

同樣,這裏類庫提供的方法 Math.sqrt(x) 就不說了,這也不是本題想考察的意義。所以這裡有幾種方式:

  • 暴力法,這裏不用考慮溢出是因為x沒溢出,所以即使加到平方根加1,也會終止循環
  • 二分法,直接取中位數運算,可以快速排除當前區域一半的區間

編寫代碼驗證

Ⅰ.暴力法

代碼:

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return 0
    let i = 1
    while(i * i < x) {
        i++
    }
    return i * i === x ? i : i - 1
};

結果:

  • 1017/1017 cases passed (120 ms)
  • Your runtime beats 23 % of javascript submissions
  • Your memory usage beats 34.23 % of javascript submissions (35.7 MB)
  • 時間複雜度 O(n)

Ⅱ.二分法

代碼:

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return 0
    let l = 1
    let r = x >>> 1
    while(l < r) {
        // 這裏要用大於判斷,所以取右中位數
        const mid = (l + r + 1) >>> 1

        if (mid * mid > x) {
            r = mid - 1
        } else {
            l = mid
        }
    }
    return l
};

結果:

  • 1017/1017 cases passed (76 ms)
  • Your runtime beats 96.08 % of javascript submissions
  • Your memory usage beats 59.17 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(log2(n))

查閱他人解法

這裏看見了兩個有意思的解法:

  • 2的冪次底層優化
  • 牛頓法

Ⅰ.冪次優化

稍微解釋一下,二分法需要做乘法運算,他這裏改用加減法

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let l = 0
    let r = 1 << 16 // 2的16次方,這裏我猜是因為上限2^32所以取一半
    while (l < r - 1) {
        const mid = (l + r) >>> 1
        if (mid * mid <= x) {
            l = mid
        } else {
            r = mid
        }
    }
    return l
};

結果:

1017/1017 cases passed (72 ms)
Your runtime beats 98.46 % of javascript submissions
Your memory usage beats 70.66 % of javascript submissions (35.4 MB)

  • 時間複雜度 O(log2(n))

Ⅱ.牛頓法

算法說明:

在迭代過程中,以直線代替曲線,用一階泰勒展式(即在當前點的切線)代替原曲線,求直線與 xx 軸的交點,重複這個過程直到收斂。

首先隨便猜一個近似值 x,然後不斷令 x 等於 xa/x 的平均數,迭代個六七次后 x 的值就已經相當精確了。

公式可以寫為 X[n+1]=(X[n]+a/X[n])/2

代碼:

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0 || x === 1) return x

    let a = x >>> 1
    while(true) {
        let cur = a
        a = (a + x / a) / 2
        // 這裡是為了消除浮點運算的誤差,1e-5是我試出來的
        if (Math.abs(a - cur) < 1e-5) {
            return parseInt(cur)
        }
    }
};

結果:

  • 1017/1017 cases passed (68 ms)
  • Your runtime beats 99.23 % of javascript submissions
  • Your memory usage beats 9.05 % of javascript submissions (36.1 MB)
  • 時間複雜度 O(log2(n))

思考總結

這裏就提一下新接觸的牛頓法吧,實際上是牛頓迭代法,主要是迭代操作。由於在單根附近具有平方收斂,所以可以轉換成線性問題去求平方根的近似值。主要應用場景有這兩個方向:

  • 求方程的根
  • 求解最優化問題

70.爬樓梯

題目描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 12 個台階。你有多少種不同的方法可以爬到樓頂呢?

注意:給定 n 是一個正整數。

示例:

輸入: 2
輸出: 2
解釋: 有兩種方法可以爬到樓頂。
1.  1 階 + 1 階
2.  2 階

輸入: 3
輸出: 3
解釋: 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

題目分析設想

這道題很明顯可以用動態規劃和斐波那契數列來求解。然後我們來看看其他正常思路,如果使用暴力法的話,那麼複雜度將會是 2^n,很容易溢出,但是如果能夠優化成 n 的話,其實還可以求解的。所以這道題我就從以下三個方向來作答:

  • 哈希遞歸,也就是暴力運算的改進版,通過存下算過的值降低複雜度
  • 動態規劃
  • 斐波那契數列

編寫代碼驗證

Ⅰ.哈希遞歸

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let hash = {}
    return count(0)
    function count (i) {
        if (i > n) return 0
        if (i === n) return 1

        // 這步節省運算
        if(hash[i] > 0) {
            return hash[i]
        }

        hash[i] = count(i + 1) + count(i + 2)
        return hash[i]
    }
};

結果:

  • 45/45 cases passed (52 ms)
  • Your runtime beats 98.67 % of javascript submissions
  • Your memory usage beats 48.29 % of javascript submissions (33.7 MB)
  • 時間複雜度 O(n)

Ⅱ.動態規劃

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1
    if (n === 2) return 2
    // dp[0] 多一位空間,省的後面做減法
    let dp = new Array(n + 1).fill(0)
    dp[1] = 1
    dp[2] = 2
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

結果:

  • 45/45 cases passed (48 ms)
  • Your runtime beats 99.48 % of javascript submissions
  • Your memory usage beats 21.49 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n)

Ⅲ.斐波那契數列

其實斐波那契數列就可以用動態規劃來實現,所以下面的代碼思路很相似。

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1
    if (n === 2) return 2
    let num1 = 1
    let num2 = 2
    for(let i = 3; i <= n; i++) {
        let count = num1 + num2
        num1 = num2
        num2 = count
    }
    // 相當於fib(n)
    return num2
};

結果:

  • 45/45 cases passed (56 ms)
  • Your runtime beats 95.49 % of javascript submissions
  • Your memory usage beats 46.1 % of javascript submissions (33.7 MB)
  • 時間複雜度 O(n)

查閱他人解法

查看題解發現這麼幾種解法:

  • 斐波那契公式(原來有計算公式可以直接用,尷尬)
  • Binets 方法
  • 排列組合

Ⅰ.斐波那契公式

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5)
    // 由於 F0 = 1,所以相當於需要求 n+1 的值
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2, n + 1)
    return Math.round(fib_n / sqrt_5)
};

結果:

  • 45/45 cases passed (52 ms)
  • Your runtime beats 98.67 % of javascript submissions
  • Your memory usage beats 54.98 % of javascript submissions (33.6 MB)
  • 時間複雜度 O(log(n))

Ⅱ.Binets 方法

算法說明:

使用矩陣乘法來得到第 n 個斐波那契數。注意需要將初始項從 fib(2)=2,fib(1)=1 改成 fib(2)=1,fib(1)=0 ,來達到矩陣等式的左右相等。

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

    function pow(a, n) {
        let ret = [[1,0],[0,1]] // 矩陣
        while(n > 0) {
            if ((n & 1) === 1) {
                ret = multiply(ret, a)
            }
            n >> 1
            a = multiply(a, a)
        }
        return ret;
    }
    function multiply(a, b) {
        let c = [[0,0], [0,0]]
        for (let i = 0; i < 2; i++) {
            for(let j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
            }
        }
        return c
    }

    let q = [[1,1], [1, 0]]
    let res = pow(q, n)
    return res[0][0]
};

結果:

測試用例可以輸出,提交發現超時。

這個筆者還沒完全理解,所以很抱歉,暫時沒有 js 相應代碼分析,後續會補上。也歡迎您補充給我,感謝!

Ⅲ.排列組合

代碼:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    // n 個台階走 i 次1階和 j 次2階走到,推導出 i + 2*j = n
    function combine(m, n) {
        if (m < n) [m, n] = [n, m];
        let count = 1;
        for (let i = m + n, j = 1; i > m; i--) {
            count *= i;
            if (j <= n) count /= j++;
        }
        return count;
    }
    let total = 0;
    // 取出所有滿足條件的解
    for (let i = 0,j = n; j >= 0; j -= 2, i++) {
      total += combine(i, j);
    }
    return total;
};

結果:

  • 45/45 cases passed (60 ms)
  • Your runtime beats 87.94 % of javascript submissions
  • Your memory usage beats 20.72 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n^2)

思考總結

這種疊加的問題,首先就會想到動態規劃的解法,剛好這裏又滿足斐波那契數列,所以我是推薦首選這兩種解法。另外通過查看他人解法學到了斐波那契公式,以及站在排列組合的角度去解,開拓了思路。

83.刪除排序鏈表中的重複元素

題目描述

給定一個排序鏈表,刪除所有重複的元素,使得每個元素只出現一次。

示例:

輸入: 1->1->2
輸出: 1->2

輸入: 1->1->2->3->3
輸出: 1->2->3

題目分析設想

注意一下,給定的是一個排序鏈表,所以只需要依次更改指針就可以直接得出結果。當然,也可以使用雙指針來跳過重複項即可。所以這裡有兩個方向:

  • 直接運算,通過改變指針指向
  • 雙指針,通過跳過重複項

如果是無序鏈表,我會建議先得到所有值然後去重后(比如通過Set)生成新鏈表作答。

編寫代碼驗證

Ⅰ.直接運算

代碼:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 複製一個用做操作,由於對象是傳址,所以改指針指向即可
    let cur = head
    while(cur !== null && cur.next !== null) {
        if (cur.val === cur.next.val) { // 值相等
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return head
};

結果:

  • 165/165 cases passed (76 ms)
  • Your runtime beats 87.47 % of javascript submissions
  • Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(n)

Ⅱ.雙指針法

代碼:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 新建哨兵指針和當前遍歷指針
    if (head === null || head.next === null) return head
    let pre = head
    let cur = head
    while(cur !== null) {
        debugger
        if (cur.val === pre.val) {
            // 當前指針移動
            cur = cur.next
        } else {
            pre.next = cur
            pre = cur
        }
    }
    // 最後一項如果重複需要把head.next指向null
    pre.next = null
    return head
};

結果:

  • 165/165 cases passed (80 ms)
  • Your runtime beats 77.31 % of javascript submissions
  • Your memory usage beats 65.1 % of javascript submissions (35.7 MB)
  • 時間複雜度 O(n)

查閱他人解法

忘記了,這裏確實還可以使用遞歸來作答。

Ⅰ.遞歸法

代碼:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(head === null || head.next === null) return head
    if (head.val === head.next.val) { // 值相等
        return deleteDuplicates(head.next)
    } else {
        head.next = deleteDuplicates(head.next)
    }
    return head
};

結果:

  • 165/165 cases passed (80 ms)
  • Your runtime beats 77.31 % of javascript submissions
  • Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(n)

思考總結

關於鏈表的題目一般都是通過修改指針指向來作答,區分單指針和雙指針法。另外,遍歷也是可以實現的。

88.合併兩個有序數組

題目描述

給定兩個有序整數數組 nums1nums2,將 nums2 合併到 nums1 中,使得 num1 成為一個有序數組。

說明:

  • 初始化 nums1nums2 的元素數量分別為 mn
  • 你可以假設 nums1 有足夠的空間(空間大小大於或等於 m + n)來保存 nums2 中的元素。

示例:

輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

輸出: [1,2,2,3,5,6]

題目分析設想

之前我們做過刪除排序數組中的重複項,其實這裏也類似。可以從這幾個方向作答:

  • 數組合併後排序
  • 遍曆數組並進行插入
  • 雙指針法,輪流比較

但是由於題目有限定空間都在 nums1 ,並且不要寫 return ,直接在 nums1 上修改,所以我這裏主要的思路就是遍歷,通過 splice 來修改數組。區別就在於遍歷的方式方法。

  • 從前往後
  • 從后往前
  • 合併後排序再賦值

編寫代碼驗證

Ⅰ.從前往後

代碼:

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 兩個數組對應指針
    let p1 = 0
    let p2 = 0
    // 這裏需要提前把nums1的元素拷貝出來,要不然比較賦值后就丟失了
    let cpArr = nums1.splice(0, m)

    // 數組指針
    let p = 0
    while(p1 < m && p2 < n) {
        // 先賦值,再進行+1操作
        nums1[p++] = cpArr[p1] < nums2[p2] ? cpArr[p1++] : nums2[p2++]
    }
    // 已經有p個元素了,多餘的元素要刪除,剩餘的要加上
    if (p1 < m) {
        // 剩餘元素,p1 + m + n - p = m + n - (p - p1) = m + n - p2
        nums1.splice(p, m + n - p, ...cpArr.slice(p1, m + n - p2))
    }
    if (p2 < n) {
        // 剩餘元素,p2 + m + n - p = m + n - (p - p2) = m + n - p1
        nums1.splice(p, m + n - p, ...nums2.slice(p2, m + n - p1))
    }
};

結果:

  • 59/59 cases passed (48 ms)
  • Your runtime beats 100 % of javascript submissions
  • Your memory usage beats 64.97 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(m + n)

Ⅱ.從后往前

代碼:

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 避免 nums1 = [0,0,0,0], nums2 = [1,2] 這種 nums1.length > nums2.length 並且 m = 0
    nums1.splice(m, nums1.length - m)
    // 兩個數組對應指針
    let p1 = m - 1
    let p2 = n - 1
    // 數組指針
    let p = m + n - 1
    while(p1 >= 0 && p2 >= 0) {
        // 先賦值,再進行-1操作
        nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] : nums1[p1--]
    }
    // 可能nums2有剩餘,由於指針是下標,所以截取數量需要加1
    nums1.splice(0, p2 + 1, ...nums2.slice(0, p2 + 1))
};

結果:

  • 59/59 cases passed (52 ms)
  • Your runtime beats 99.76 % of javascript submissions
  • Your memory usage beats 78.3 % of javascript submissions (33.6 MB)
  • 時間複雜度 O(m + n)

Ⅲ.合併後排序再賦值

代碼:

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    arr = [].concat(nums1.splice(0, m), nums2.splice(0, n))
    arr.sort((a, b) => a - b)
    for(let i = 0; i < arr.length; i++) {
        nums1[i] = arr[i]
    }
};

結果:

  • 59/59 cases passed (64 ms)
  • Your runtime beats 90.11 % of javascript submissions
  • Your memory usage beats 31.21 % of javascript submissions (34.8 MB)
  • 時間複雜度 O(m + n)

查閱他人解法

這裏看到一個直接用兩次 while ,然後直接用 m/n 來計算下標的,沒有額外空間,但是本質上也是從后往前遍歷。

Ⅰ.兩次while

代碼:

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 避免 nums1 = [0,0,0,0], nums2 = [1,2] 這種 nums1.length > nums2.length 並且 m = 0
    // nums1.splice(m, nums1.length - m)
    // 從后開始賦值
    while(m !== 0 && n !== 0) {
        nums1[m + n - 1] = nums1[m - 1] > nums2[n - 1] ? nums1[--m] : nums2[--n]
    }
    // nums2 有剩餘
    while(n !== 0) {
        nums1[m + n - 1] = nums2[--n]
    }
};

結果:

  • 59/59 cases passed (56 ms)
  • Your runtime beats 99.16 % of javascript submissions
  • Your memory usage beats 64.26 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(m + n)

思考總結

碰到數組操作,會優先考慮雙指針法,具體指針方向可以由題目邏輯來決定。

(完)

本文為原創文章,可能會更新知識點及修正錯誤,因此轉載請保留原出處,方便溯源,避免陳舊錯誤知識的誤導,同時有更好的閱讀體驗
如果能給您帶去些許幫助,歡迎 ⭐️star 或 ️ fork
(轉載請註明出處:https://chenjiahao.xyz)

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

【其他文章推薦】

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

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

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

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

Linux開機過程

相關內容

開機過程

  開機過程指的是從按下電源鍵開始,到進入系統登錄畫面前所經歷的過程。

MBR與磁盤分區

  在目前x86的系統架構中,系統硬盤位於第0號磁道:0到511KB的區塊為MBR(硬盤中的每一個磁道容量為512KB),開機管理程序使用這塊區域來儲存第一階段開機引導程序(stage1)。接着位於1到62號磁道作為第1.5階段的開機引導程序(stage1.5),從第63號磁道開始才是操作系統的分區。

  主引導記錄(MBR,Master Boot Record)是位於磁盤最前邊的一段引導(Loader)代碼。它負責磁盤操作系統(DOS)對磁盤進行讀寫時分區合法性的判別、分區引導信息的定位,它由磁盤操作系統(DOS)在對硬盤進行初始化時產生。

  MBR的內容分為三部分:第一部分是0到445KB,是計算機的基礎導引程序,也稱為第一階段的導引程序;接着446KB到509KB為磁盤分區表,由四個分區表項構成(每個16個字節)。負責說明磁盤上的分區情況。內容包括分區標記、分區的起始位置、分區的容量以及分區的類型。最後一部分為結束標誌只佔2KB,其值為AA55,存儲時低位在前,高位在後。

從百度百科借了張圖:

 

 

MBR中緊跟在主引導程序后的主分區表這64字節(01BE~01FD)中包含了許多磁盤分區描述信息,尤其是01BE~01CD這16字節,包含了分區引導標誌bootid、分區起始源頭beghead、分區起始扇區relsect、分區起始柱面begcy1、操作系統類型systid、分區結尾磁頭endhead、分區結尾扇區begsect、分區結尾柱面begcy1、分區扇區起始位置relsect、分區扇區總數numsect。

其中分區引導標誌bootid表示當前分區是否可以引導,若為0x0,則表示該分區為非活動區;若為0x80,則為可開機啟動區。若有多個開機啟動區,則由用戶開機時的選擇而定(如GRUB的菜單)。

分區扇區起始位置relsect表示分區中第一個扇區相對於磁盤起始點的偏移位置。

開機管理程序

linux上的開機管理程序有LiLO和GRUB,前者是早期的產物,在近年來的Linux操作系統都以GRUB作為默認軟件包。

GNU GRUB(GRand Unified Bootloader簡稱“GRUB”)是一個來自GNU項目的多操作系統啟動程序。GRUB是多啟動規範的實現,它允許用戶可以在計算機內同時擁有多個操作系統,並在計算機啟動時選擇希望運行的操作系統。GRUB可用於選擇操作系統分區上的不同內核,也可用於向這些內核傳遞啟動參數。

運行層級

運行層級(run level)共有7個,分別為0、1、2、3、4、5、6,其中0表示關機、1表示單人模式、6表示重新啟動。中間的2、3、4、5因Linux發行商而異。

過程解析

 從按下電源開始到登錄畫面中所有的過程。

 登錄程序依序分為BIOS、GRUB、內核加載、與init程序四個步驟。

BIOS

當按下電源按鈕后,系統就會運行BIOS檢測,包含檢查系統的硬件配置、執行系統診斷程序、找出系統硬盤,把第0號磁道中的開機導引程序加載到內存中,之後就由GRUB接手後續的開機程序。

GRUB

GRUB是一個較大的程序,本身容量超過MBR的限制(512KB),因此GRUB將開機程序分割為stage1、stage2,並在1與2之中加上選用的程序stage1.5,如e2fs_stage1_5、fat_stage1_5等。

由BIOS接手后的GRUB,會由stage1轉接到stage2(或stage1.5),並找出和載入位於/boot的內核文件。內核文件位於/boot之下。

接着會將內存映像文件(.img)加載到內存中,並使用cpio命令將內容解壓縮到/boot之下。如果硬件的功能都別編入內核中,這個動作是不需要的;但若編譯為模塊且必須在開機時加載,這個步驟就是必要的。

將內核與必要的映像文件加載后,系統開機的過程就交給內核處理了。

內核載入

 內核接手系統開機的程序之後,會進行初始化,包括檢測硬件、設置硬件設備、時鐘設定、加載模塊等,這動作完成後會釋放出曾佔用的內存空間。

 接着啟動文件系統相關的設定,首先會掛接根目錄(“/”),再讀取分區表(/etc/fstab)並掛接所有的分區與啟動SWAP。最後系統啟動/sbin/init程序,並運行硬件與軟件相關的系統常駐程序。

 內核在開機的作用到此告一段落。

init程序

Init是系統的第一個進程,因此PID為0,也是所有進程的父進程,init啟動後會先執行etc/rc.d/rc.sysinit,並讀取配置文件/etc/inittab中的設定

 init的具體內容可參考:

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

【其他文章推薦】

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

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

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

人機對話技術研究進展與思考

嘉賓:袁彩霞 博士 北京郵電大學 副教授

整理:Hoh Xil

來源:阿里小蜜 & DataFun AI Talk

出品:DataFun

注:歡迎轉載,轉載請在留言區內留言。

導讀:本次分享的主題為人機對話技術研究進展與思考。主要梳理了我們團隊近兩年的工作,渴望可以通過這樣的介紹,能給大家一個關於人機對話 ( 包括它的科學問題和應用技術 ) 方面的啟示,幫助我們進行更深入的研究和討論。主要包括:

  1. Spoken dialogue system:a bird view ( 首先我們來看什麼是人機對話,尤其是 Spoken dialogue。其實說 Spoken 的時候,有兩層含義:第一個 spoken 就是 speech,第二個我們處理的語言本身具有 spoken 的特性。但是,稍後會講的 spoken 是指我們已經進行語音識別之後,轉換為文本的一個特殊的自然語言,後面討論的口語對話不過多地討論它的口語特性,主要是講人和機器之間的自然語言對話。)

  2. X-driven dialogue system:緊接着來講解我們近些年的研究主線 X-driven dialogue syatem,X 指構建一個對話系統時,所採用的數據是什麼,從最早的 dialogue -> FAQ -> KB -> KG -> document 以及我們一直在嘗試的圖文多模態數據。

  3. Concluding remarks ( 結束語 )

01

Spoken dialogue system:a bird view

學術界關於對話系統有着不同的劃分,這種劃分目前看來不是非常準確,也不是特別標準的劃分了。但是,接下來的內容,主要是圍繞着這兩個主線:

限定領域,專門指任務型對話 ( 圍繞某一特定用戶對話目標而展開的 )。對於任務型對話,對話系統的優化目標就是如何以一個特別高的回報、特別少的對話輪次、特別高的成功率來達成用戶的對話目標。所以即便是限定領域,我們這裏討論的也是特別限定的、專門有明確的用戶對話目標的一種對話。

開放領域,not purely task-oriented, 已經不再是純粹的對話目標驅動的對話,包括:閑聊、推薦、信息服務等等,後面逐步展開介紹。

我們在研究一個問題或者做論文答辯和開題報告時,經常討論研究對象的意義在哪裡。圖中,前面講的是應用意義,後面是理論意義。我們實驗室在北京郵電大學叫智能科學與技術實驗室,其實她的前身叫人工智能實驗室。所以從名字來看,我們做了非常多的 AI 基礎理論的研究,我們在研究這些理論的時候,也會講 AI 的終極目的是研製一種能夠從事人類思維活動的計算機系統。人類思維活動建立在獲取到的信號的基礎上。人類獲取信號的方式大體有五類,包括視覺、聽覺、觸覺、味覺、嗅覺等,其中視覺和聽覺是兩個比較高級的傳感器通道,尤其是視覺通道,佔據了人類獲得信息的80%以上。所以我們從這兩個角度,設立了兩個研究對象:第一個是語言,第二個是圖像。而我們在研究語言的時候,發現語言有一個重要的屬性,叫交互性,交互性最典型的一個體現就是對話;同時,語言不是一個獨立的模態,語言的處理離不開跟它相關的另一個通道,就是視覺通道。所以我們早期更多是為了把交互和多模態這樣的屬性納入到語言建模的範圍,以其提升其它自然語言處理系統的性能,這就是我們研究的一個動機。

  1. Block diagram

上圖為 CMU 等在1997年提出來的人機對話框架,基於這個框架人們開發出了非常多優秀的應用系統,比如應用天氣領域的 “Jupiter”。這個框架從提出到商業化應用,一直到今天,我們都還沿着這樣的一個系統架構在進行開發,尤其是任務驅動的對話。

這就是具體的對話系統的技術架構。

  1. Specific domain

這個架構發展到現在,在功能模塊上,已經有了一個很清晰的劃分:

首先進行語音識別,然後自然語言理解,緊接着做對話管理,將對話管理的輸出交給自然語言生成模塊,最後形成自然語言應答返回給用戶。這就是一個最典型的 specific domain 的架構。早期 task 限定的 dialogue,基本上都是按照這個架構來做的。這個架構雖然是一個 Pipeline,但是從研究的角度來講,每一個模塊和其它模塊之間都會存在依賴關係。因此,我們試圖從研究的角度把不同的功能模塊進行統一建模。在這個建模過程中,又會產生新的學術性問題,我們旨在在這樣的問題上可以產生驅動性的技術。

  1. Open domain

Open domain,也就是“閑聊”,實現上主要分為途徑:

第一個是基於匹配/規則的閑聊系統;第二個是基於檢索的閑聊系統;第三個是基於編解碼結構的端到端對話系統。當然,實際情境中,這幾個途徑往往結合在一起使用。

02

X-Driven dialogue system

目前無論是任務型對話還是閑聊式對話,都採用數據驅動的方法,因此依據在構建人機對話系統時所用到的數據不同,建模技術和系統特性也就體現出巨大的不同。我們把使用的數據記為 X,於是就有了不同的 X 驅動的對話。

  1. Our roadmap

如果想讓機器學會像人一樣對話,我們可以提供的最自然的數據就是 dialogue。我們從2003年開始做對話驅動的對話;2012年開始做 FAQ 驅動的對話;2015年開始做知識庫 ( KB ) 驅動的對話;2016年開始做知識圖譜 ( KG ) 驅動的對話,相比於 KB,KG 中的知識點產生了關聯,有了這種關聯人們就可以在大規模的圖譜上做知識推理;2017年開始做文檔驅動的對話。這就是我們研究的大致脈絡。

  1. Dialogue-driven dialogue

早期在做 Dialogue driven 的時候,多依賴人工採集數據,但是,從2013年以來,逐步開放了豐富的涵蓋多領域多場景的公開數據集。比如最近的 MultiWOZ,從 task specific 角度講,數據質量足夠好、數據規模足夠大,同時涵蓋的對話情景也非常豐富。但是,目前公開的中文數據集還不是很多。

這個是和任務型對話無關的數據集,也就是採集的人與人對話的數據集。尤其以 Ubuntu 為例,從15年更新至今,已經積累了非常大規模的數據。

以 Dialogue 為輸入,我們開展了任務型和非任務型兩個方向的工作。先來看下任務型對話:

2.1 NLU

當一個用戶輸入過來,第一個要做的就是自然語言理解 ( NLU ),NLU 要做的三件事為:Domain 識別;Intent 識別;信息槽識別或叫槽填充。這三個任務可以分別獨立地或採用管道式方法做,也可以聯合起來進行建模。在聯合建模以外,我們還做了一些特別的研究。比如我們在槽識別的時候,總是有新槽,再比如有些槽值非常奇怪,例如 “XX手機可以一邊打電話一邊視頻嗎?”,對應着槽值 “視頻電話”,採用序列標註的方式,很難識別它,因為這個槽值非常不規範。用戶輸入可能像這樣語義非常鬆散,不連續,也可能存在非常多噪音,在進行聯合建模時,傳統的序列標註或分類為思想,在實際應用中已經不足以解決問題了。

我們針對這個問題做了比較多的探討,右圖為我們2015年的一個工作:在這三個任務聯合建模的同時,在槽填充這個任務上將序列標註和分類進行同時建模,來更好地完成 NLU。

在 NLU 領域還有一個非常重要的問題,隨着開發的業務領域越來越多,我們發現多領域對話產生了諸多非常重要的問題,例如在數據層有些 domain 數據可能很多,有些 domain 數據可能很少,甚至沒有,於是就遇到冷啟動的問題。因此,我們做了非常多的 domain transfer 的工作。上圖為我們2016年的一個工作,我們會把數據比較多的看成源領域,數據比較少的看成目標領域。於是,嘗試了基於多種遷移學習的 NLU,有的是在特徵層進行遷移,有的是在數據層遷移,有的是在模型層進行遷移。圖中是兩個典型的在特徵層進行遷移的例子,不僅關注領域一般特徵,而且關注領域專門特徵,同時採用了對抗網絡來生成一個虛擬的特徵集的模型。

2.2 NLU+DM

緊接着,我們研究了 NLU 和對話管理 ( DM ) 進行聯合建模,因為我們發現人人對話的時候,不見得是聽完對方說完話,理解了對方的意圖,然後才形成對話策略,有可能這兩個過程是同時發生的。甚或 DM 還可以反作用於 NLU。早期我們基於的一個假設是, NLU 可能不需要一個顯式的過程,甚至不需要一個顯式的 NLU 的功能,我們認為 NLU 最終是服務於對話管理 ( DM ),甚至就是對話管理 ( DM ) 的一部分。所以,2013年的時候,我們開始了探索,有兩位特別優秀的畢業生在這兩個方面做了特別多的工作。比如,如何更好地聯合建模語言理解的輸出和對話管理的策略優化。這是我們在 NLU 和 DM 聯合建模的工作,同時提升了 NLU 和 DM 的性能。

在聯合模型中,我們發現,DM 的建模涉及到非常多的 DRL ( 深度強化學習 ) 的工作,訓練起來非常困難,比如如何設計一個好的用戶模擬器,基於規則的,基於統計的,基於語言模型的,基於 RL 的等等我們嘗試了非常多的辦法,也取得了一系列有趣的發現。2018年時我們研究一種不依賴於規則的用戶模擬器,業界管這個問題叫做 “Self”-play,雖然我們和 “Self”-play 在網絡結構上差異挺大的,但是我們還是借鑒了 “Self”-play 訓練的特性,把我們自己的系統叫做 “Self”-play。在這樣的機制引導下,我們研究了不依賴於規則,不依賴於有標記數據的用戶模擬器,使得這個用戶模擬器可以像 Agent 一樣,和我們所構造的對話的 Agent 進行交互,在交互的過程中完成對用戶的模擬。

在訓練過程中還有一個重要的問題,就是 reward 怎麼來,我們知道在 task oriented 時,reward 通常是人類專家根據業務邏輯/規範制定出來的。事實上,當我們在和環境交互的時候不知道 reward 有多大,但是環境會隱式地告訴我們 reward 是多大,所以我們做了非常多的臨接對和 reward reshaping 的工作。

2.3 小結

Dialogue-driven dialogue 這種形式的對話系統,總結來看:

優點:

定義非常好,邏輯清晰,每一個模塊的輸入輸出也非常清晰,同時有特別堅實的數學模型可以對它進行建模。

缺點:

由於非常依賴數據,同時,不論是在 NLU 還是 NLG 時,我們都是採用有監督的模型來做的,所以它依賴於大量的、精細的標註數據。

而 DM 往往採用 DRL 來做。NIPS2018 時的一個 talk,直接指出:任何一個 RL 都存在的問題,就是糟糕的重現性、復用性、魯棒性。

  1. FAQ-driven dialogue

FAQ 是工業界非常常見的一種情景:有大量的標準問,以及這個標準問的答案是什麼。基於這個標準問,一個用戶的問題來了,如何找到和它相似的問題,進而把答案返回給用戶,於是這個 Service 就結束了。

實際中,我們如何建 FAQ?更多的時候,我會把這個問題和我們庫的標準問題做一個相似度的計算或者做一個分類。

我們在做這個工作的時候發現一個特別大的問題,就是 Unbalanced Data 問題。比如,我們有5000個問題,每個問題都有標準答案,有些問題可能對應的用戶問題特別多,比如 “屏幕碎了” 可能會有1000多種不同的問法,還有些問題,可能在幾年的時間里都沒有人問到過。所以,面對數據不均衡的問題,我們從2016年開始做了 Data transfer 的工作。

大致的思路是:我有一個標準問題,但是很糟糕,這個標準問題沒有用戶問題,也就是沒有訓練語料。接下來發現另外一個和這個標準問很相似的其它標準問有很多的訓練語料,於是藉助這個標準問,來生成虛擬樣本,進而削弱了 Unbalance。

具體的方法:我們把目標領域的標準問看成 Query,把和它相似的標準問題及其對應的用戶問題看成 Context,採用了 MRC 機器閱讀理解的架構來生成一個答案,作為目標問題的虛擬的用戶問題,取得了非常好的效果,並且嘗試了三種不同的生成用戶問題的方法。

實際項目中,FAQ 中的 Q 可能有非常多的問題,例如3000多個類,需要做極限分類,這就導致性能低下,且非常耗時,不能快速響應用戶的問題。於是我們做了一個匹配和分類進行交互的 model,取得了不錯的效果。

目前,大部分人都認為 FAQ 驅動的 dialogue 不叫 dialogue,因為我們通常說的 dialogue 輪次是大於兩輪的。而 FAQ 就是一個 QA 系統,沒有交互性。有時候帶來的用戶體驗非常不友好,比如當答案非常長的時候,系統要把長長的答案返回,就會一直講,導致用戶比較差的體驗。於是,我們基於 FAQ 發展出了一個多輪對話的數據,如右圖,這是我們正在開展的一個工作。

  1. KB-driven dialogue

KB 最早人們認為它就是一個結構化的數據庫,通常存儲在關係型數據庫中。比如要訂一個酒店,這個酒店有各種屬性,如位置、名稱、戶型、價格、面積等等。早期 CMU 的對話系統,所有的模塊都要和 Hub 進行交互,最後 Hub 和後端的數據庫進行交互。數據庫的價值非常大,但是早期人們在建模人機對話的時候,都忽視了數據庫。這裏就會存在一個問題:機器和用戶交互了很久,而在檢索數據庫時發現沒有答案,或者答案非常多,造成用戶體驗非常糟糕。

從2012年開始,我們開始把 KB 引入我們的對話系統。圖中的對話系統叫做 “teach-and-learn” bot,這是一個多模態的對話,但是每個涉及到的 object,我們都會把它放到 DB 中。和用戶交互過程中,不光看用戶的對話狀態,還要看數據庫狀態。這個想法把工作往前推進了一些。

直到2016年,MSR 提出的 KB-InfoBot,第一次提出了進行數據庫操作時,要考慮它的可導性,否則,就沒辦法在 RL 網絡中像其它的 Agent action 一樣進行求導。具體的思路:把數據庫的查詢和 Belief State 一起總結起來做同一個 belief,進而在這樣的 belief 基礎上做各種對話策略的優化。

在上述方法的基礎上,我們做了有效的改良,包括 entropy regularities 工作。是每次和用戶進行交互時,數據庫的 entropy 會發生變化。比如當機器問 “你想訂哪裡的酒店?”,用戶答 “阿里中心附近的。”,於是數據庫立刻進行了一次 entropy 計算進行更新,接着繼續問 “你想訂哪一天的?”,用戶答 “訂7月28號的”,於是又進行了一次 entropy 計算進行更新。這樣在和用戶進行交互的時候,不光看用戶的 dialogue 輸入,還看 DB 的 entropy 輸入,以這兩項共同驅動 Agent action 進行優化。

這裏我們做了特別多的工作,信息槽從1個到5個,數據庫的規模從大到小,都做了特別多的嘗試,這樣在和用戶交互的時候,agent 可以自主的查詢檢索,甚至可以填充和修改數據庫。

這是我們2017發布的一個工作,KB driven-dialogue,其優點:

控制萬能高頻回復 ( 提高答應包含的有用信息 )

賦予 agent 對話主動性

  1. KG-driven dialogue

剛剛講的基於 KB 的 dialogue 任務,基本都認為對話任務就是在進行槽填充的任務,如果一個 agent 是主動性的,通過不停的和用戶進行交互來採集槽信息,所以叫槽填充,當槽填完了,就相當於對話任務成功了。但是,當我們在定義槽的時候,我們認為槽是互相獨立的,並且是扁平的。然而,實際中許多任務的槽之間存在相關性,有的是上下位關係,有的是約束關係,有的是遞進關係等等。這樣自然的就引出了知識圖譜,知識圖譜可以較好地描述上述的相關性。於是,產生了兩個新問題:

知識圖譜驅動的對話理解:實體鏈接

知識圖譜驅動的對話管理:圖路徑規劃

這裏主要講下第二個問題。

舉個例子,我們在辦理電信業務,開通一個家庭寬帶,需要提供相關的證件,是自己去辦,還是委託人去辦,是房東還是租戶等等,需要提供各種不同的材料。於是這個情景就產生了條件的約束,某一個 node 和其它 node 是上下位的關係,比如證件可以是身份證,也可以是護照或者戶口簿等等。所以我們可以通過知識圖譜來進行處理。

當一個用戶的對話過來,首先會鏈接到不同的 node,再基於 node 和對話歷史構造一個對話的 state,我們會維持一個全局的 state 和一個活躍的 state,同時活躍的 state 會定義三種不同的操作動作,一個是祖先節點,一個是兄弟節點,還有一個是孩子節點。所以,在這樣的知識圖譜上如何尋優,比如當通過某種計算得到,它應該在某個節點上進行交互的時候,我們就應該輸出一個 action,這個 action 要和用戶確認他是一個租戶,還是自有住房等等。所以,這個 action 是有區別於此前所提到的在特定的、扁平的 slot 槽上和用戶進行信息的確認、修改等還是有很大不同的。解決這樣的問題,一個非常巨大的挑戰就是狀態空間非常大。比如圖中的節點大概有120個,每個節點有3個不同的狀態,知識從節點的狀態來看就有3的120次冪種可能。這也是我們正在開展的待解決的一個問題。

在端到端的對話模型 ( 閑聊 ) 中,也開始逐步地引入知識圖譜。下面介紹兩個比較具有代表性的引入知識圖譜后的人機對話。其中右邊是2018年 IJCAI 的傑出論文,清華大學黃民烈老師團隊的工作,引入了通過 KG 來表示的 Commonsense,同時到底在編碼器端還是在解碼器端引入知識,以及如何排序,排序的時候如何結合對話的 history 做知識的推理等等,都做了特別全面的研究。

另一個比較有代表性的工作是在 ICLR2019 提出的,在架構中引入了 Local Memory 和 Global Memory 相融合的技術,通過這種融合,在編碼器端和解碼器端同時加入了知識的推理。

總結下 KB/KG-driven dialogue:

優點:

已經有大規模公開的數據 ( e.g.,InCar Assistant,MMD,M2M )。

訓練過程可控&穩定,因為這裏多數都是有監督學習。

缺點:

因為採用有監督的方式進行訓練,所以存在如下問題:

① 環境確定性假設
② 缺少對動作的建模
③ 缺少全局的動作規劃
Agent 被動,完全依賴於訓練數據,所以模型是不賦予 Agent 主動性的。

構建 KB 和 KG 成本昂貴!

  1. Document-driven dialogue

Document 驅動的對話,具有如下優點:

① 應用場景真實豐富:

情景對話 ( conversation ),比如針對某個熱門事件在微博會產生很多對話,這就是一個情景式的對話。

電信業務辦理 ( service ),比如10086有非常多的套餐,如何從中選擇一個用戶心儀的套餐?每個套餐都有說明書,我們可以圍繞套餐的說明書和用戶進行交互,如 “您希望流量多、還是語音多”,如果用戶回答 “流量多”,就可以基於文本知道給用戶推薦流量多的套餐,如果有三個候選,機器就可以基於這三個候選和用戶繼續進行交互,縮小候選套餐範圍,直到用戶選出心儀的套餐。

電商產品推薦 ( recommendation ),可以根據商品的描述,進行各種各樣的對話。這裏的輸入不是一個 dialogue,也不是一個 KB,甚至結構化的內容非常少,完全是一個 free document,如何基於這些 document 進行推薦,是一個很好的應用場景。

交互式信息查詢 ( retrieval ),很多時候,一次查詢的結果可能不能用戶的需求,如何基於非結構化的查詢結果和用戶進行交互,來更好地達成用戶的查詢目的。

……

② 數據獲取直接便捷:

相比於 dialogue、FAQ、KB、KQ 等,Document 充斥着互聯網的各種各樣的文本,都可以看成是文本的數據,獲取方便,成本非常低。

③ 領域移植性強:

基於文本,不再基於專家定義的 slot,也不再基於受限的 KB/KG,從技術上講,所構造的 model 本身是和領域無關的,所以它賦予了 model 很強的領域移植性。

這是我們正在進行的工作,情景對話偏向於閑聊,沒有一個用戶目標。這裏需要解決的問題有兩個:

如何引入文檔:編碼端引入文檔、解碼端引入文檔

如何編碼文檔:文檔過長、冗餘信息過多

數據:

我們在 DoG 數據的基礎上模擬了一些數據,形成了如上圖所示的數據集,分 Blind 和 Non-blind 兩種情形構造了不同的數據集。

我們發現,基於文本的端到端的聊天,有些是基於內容的閑聊,有些還需要回答特定的問題。所以,評價的時候,可以直接用 F1 評價回答特定問題,用閑聊通用的評價來評價基於內容的聊天。

剛剛講的是偏閑聊式的對話,接下來講下任務型對話。

這裏的動機分為兩種情況:單文檔和多文檔,我們目前在挑戰多文檔的情況,單文檔則採用簡單的多輪閱讀理解來做。

多文檔要解決的問題:

如何定義對話動作:因為是基於Document進行交互,而不再是基於slot進行交互,所以需要重新定義對話動作。

如何建模文檔差異:以剛剛10086的例子為例,總共有10個業務,通過一輪對話,挑選出3個,這3個業務每個業務可能都有10種屬性,那麼其中一些屬性值相同的屬性,沒必要再和用戶進行交互,只需要交互它們之間不同的點,所以交互的角度需要隨對話進行動態地變化。

數據:

這裏採用的數據是 WikiMovies 和模擬數據,具體見上圖。

  1. A very simple sketch of dialogue

上圖為任務型對話和非任務型對話的幾個重要節點,大家可以了解下。

03

Concluding remarks

任務型對話具有最豐富的落地場景。

純閑聊型對話系統的學術價值尚不清楚。

任務型和非任務型邊界愈加模糊,一個典型的人人對話既包括閑聊,又包括信息獲取、推薦、服務。

引入外部知識十分必要,外部知識形態各異,建模方法也因而千差萬別。

Uncertainty 和 few-shot 問題,是幾乎所有的對話系統最大的 “卡脖子” 問題。

X-driven dialogue 中的 X 還有哪些可能?剛剛提到的 X 都還是基於文本的。事實上,從2005年開始,我們已經開始做 image 和文本數據融合的對話;從2013年開始做 Visual QA/Dialogue,挑戰了 GuessWhat 和 GuessWhich 任務。

X=multi media ( MM Dialogue ),X 還可以很寬泛的就是指多媒體,不光有 image 還可能有 text,2018年已經有了相關的任務,並且開源了非常多的電商業務。這是一個非常有挑戰性的工作,也使人機對話本身更加擬人化。

04

Reference

這是部分的參考文獻,有些是我們自己的工作,有些是特別傑出的別人的工作。

今天的分享就到這裏,感謝大家的聆聽,也感謝我們的團隊。

歡迎關注DataFunTalk同名公眾號,收看第一手原創技術文章。

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

【其他文章推薦】

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

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

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