深入理解React:懶加載(lazy)實現原理

目錄

  • 代碼分割
  • React的懶加載
    • import() 原理
    • React.lazy 原理
    • Suspense 原理
  • 參考

1.代碼分割

(1)為什麼要進行代碼分割?

現在前端項目基本都採用打包技術,比如 Webpack,JS邏輯代碼打包後會產生一個 bundle.js 文件,而隨着我們引用的第三方庫越來越多或業務邏輯代碼越來越複雜,相應打包好的 bundle.js 文件體積就會越來越大,因為需要先請求加載資源之後,才會渲染頁面,這就會嚴重影響到頁面的首屏加載。

而為了解決這樣的問題,避免大體積的代碼包,我們則可以通過技術手段對代碼包進行分割,能夠創建多個包並在運行時動態地加載。現在像 Webpack、 Browserify等打包器都支持代碼分割技術。

(2)什麼時候應該考慮進行代碼分割?

這裏舉一個平時開發中可能會遇到的場景,比如某個體積相對比較大的第三方庫或插件(比如JS版的PDF預覽庫)只在單頁應用(SPA)的某一個不是首頁的頁面使用了,這種情況就可以考慮代碼分割,增加首屏的加載速度。

2.React的懶加載

示例代碼:

import React, { Suspense } from 'react';

const OtherComponent = React.lazy(() => import('./OtherComponent'));

function MyComponent() {
  return (
    <div>
      <Suspense fallback={<div>Loading...</div>}>
        <OtherComponent />
      </Suspense>
    </div>
  );
}

如上代碼中,通過 import() React.lazySuspense 共同一起實現了 React 的懶加載,也就是我們常說了運行時動態加載,即 OtherComponent 組件文件被拆分打包為一個新的包(bundle)文件,並且只會在 OtherComponent 組件渲染時,才會被下載到本地。

那麼上述中的代碼拆分以及動態加載究竟是如何實現的呢?讓我們來一起探究其原理是怎樣的。

import() 原理

import() 函數是由TS39提出的一種動態加載模塊的規範實現,其返回是一個 promise。在瀏覽器宿主環境中一個import()的參考實現如下:

function import(url) {
  return new Promise((resolve, reject) => {
    const script = document.createElement("script");
    const tempGlobal = "__tempModuleLoadingVariable" + Math.random().toString(32).substring(2);
    script.type = "module";
    script.textContent = `import * as m from "${url}"; window.${tempGlobal} = m;`;

    script.onload = () => {
      resolve(window[tempGlobal]);
      delete window[tempGlobal];
      script.remove();
    };

    script.onerror = () => {
      reject(new Error("Failed to load module script with URL " + url));
      delete window[tempGlobal];
      script.remove();
    };

    document.documentElement.appendChild(script);
  });
}

當 Webpack 解析到該import()語法時,會自動進行代碼分割。

React.lazy 原理

以下 React 源碼基於 16.8.0 版本

React.lazy 的源碼實現如下:

export function lazy<T, R>(ctor: () => Thenable<T, R>): LazyComponent<T> {
  let lazyType = {
    $$typeof: REACT_LAZY_TYPE,
    _ctor: ctor,
    // React uses these fields to store the result.
    _status: -1,
    _result: null,
  };

  return lazyType;
}

可以看到其返回了一個 LazyComponent 對象。

而對於 LazyComponent 對象的解析:

...
case LazyComponent: {
  const elementType = workInProgress.elementType;
  return mountLazyComponent(
    current,
    workInProgress,
    elementType,
    updateExpirationTime,
    renderExpirationTime,
  );
}
...
function mountLazyComponent(
  _current,
  workInProgress,
  elementType,
  updateExpirationTime,
  renderExpirationTime,
) { 
  ...
  let Component = readLazyComponentType(elementType);
  ...
}
// Pending = 0, Resolved = 1, Rejected = 2
export function readLazyComponentType<T>(lazyComponent: LazyComponent<T>): T {
  const status = lazyComponent._status;
  const result = lazyComponent._result;
  switch (status) {
    case Resolved: {
      const Component: T = result;
      return Component;
    }
    case Rejected: {
      const error: mixed = result;
      throw error;
    }
    case Pending: {
      const thenable: Thenable<T, mixed> = result;
      throw thenable;
    }
    default: { // lazyComponent 首次被渲染
      lazyComponent._status = Pending;
      const ctor = lazyComponent._ctor;
      const thenable = ctor();
      thenable.then(
        moduleObject => {
          if (lazyComponent._status === Pending) {
            const defaultExport = moduleObject.default;
            lazyComponent._status = Resolved;
            lazyComponent._result = defaultExport;
          }
        },
        error => {
          if (lazyComponent._status === Pending) {
            lazyComponent._status = Rejected;
            lazyComponent._result = error;
          }
        },
      );
      // Handle synchronous thenables.
      switch (lazyComponent._status) {
        case Resolved:
          return lazyComponent._result;
        case Rejected:
          throw lazyComponent._result;
      }
      lazyComponent._result = thenable;
      throw thenable;
    }
  }
}

注:如果 readLazyComponentType 函數多次處理同一個 lazyComponent,則可能進入Pending、Rejected等 case 中。

從上述代碼中可以看出,對於最初 React.lazy() 所返回的 LazyComponent 對象,其 _status 默認是 -1,所以首次渲染時,會進入 readLazyComponentType 函數中的 default 的邏輯,這裏才會真正異步執行 import(url)操作,由於並未等待,隨後會檢查模塊是否 Resolved,如果已經Resolved了(已經加載完畢)則直接返回moduleObject.default(動態加載的模塊的默認導出),否則將通過 throw 將 thenable 拋出到上層。

為什麼要 throw 它?這就要涉及到 Suspense 的工作原理,我們接着往下分析。

Suspense 原理

由於 React 捕獲異常並處理的代碼邏輯比較多,這裏就不貼源碼,感興趣可以去看 throwException 中的邏輯,其中就包含了如何處理捕獲的異常。簡單描述一下處理過程,React 捕獲到異常之後,會判斷異常是不是一個 thenable,如果是則會找到 SuspenseComponent ,如果 thenable 處於 pending 狀態,則會將其 children 都渲染成 fallback 的值,一旦 thenable 被 resolve 則 SuspenseComponent 的子組件會重新渲染一次。

為了便於理解,我們也可以用 componentDidCatch 實現一個自己的 Suspense 組件,如下:

class Suspense extends React.Component {
  state = {
    promise: null
  }

  componentDidCatch(err) {
    // 判斷 err 是否是 thenable
    if (err !== null && typeof err === 'object' && typeof err.then === 'function') {
      this.setState({ promise: err }, () => {
        err.then(() => {
          this.setState({
            promise: null
          })
        })
      })
    }
  }

  render() {
    const { fallback, children } = this.props
    const { promise } = this.state
    return <>{ promise ? fallback : children }</>
  }
}

小結

至此,我們分析完了 React 的懶加載原理。簡單來說,React利用 React.lazyimport()實現了渲染時的動態加載 ,並利用Suspense來處理異步加載資源時頁面應該如何显示的問題。

3.參考

代碼分割– React

動態import – MDN – Mozilla

proposal-dynamic-import

React Lazy 的實現原理

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

【其他文章推薦】

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

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

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

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

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

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

如何使用 Shell 腳本來查看多個服務器的端口是否打開?

我們在進行服務器配置的時候,經常要查看服務器的某個端口是否已經開放。如果服務器只有一兩台的話,那很好辦,只需要使用 nc 命令一個個查看即可。

但是,如果你的服務器是個集群,有很多台呢?那如果還一個個手動去檢查的話,效率肯定是無比低下的,年底裁員名單里肯定有你。

在這種情況下,我們完全可以使用 Shell 腳本配合 nc 命令來達到我們的目的。而且,不管服務器有幾台,需要檢查的端口有幾個,都可以實現這樣的目標。

在本文里,我們用 Shell 腳本來實現兩個需求:

  • 掃描多台服務器的一個端口是否打開
  • 掃描多台服務器的多個端口是否打開

在開始之前,我們先來了解一下 nc 命令。

nc 命令簡介

nc 是英文單詞 netcat 的縮寫,它是通過使用 TCP 或 UDP 的網絡協議的連接來讀或寫數據,可以直接被第三方程序或腳本直接調用。

同時,它是一款功能非常強大的網絡調試工具,因為它可以創建幾乎所有你所需要的連接方式。

nc 工具主要有三種功能模式:連接模式、監聽模式、通道模式。它的一般使用格式如下:

$ nc [-options] [HostName or IP] [PortNumber]

接下來,我們就用 Shell 腳本結合 nc 命令來實現我們的兩個需求。

1. 掃描多台服務器的一個端口是否打開

在這裏,我們先把需要查詢的所有服務器地址全部放在一個 server-list.txt 文件里,每個地址單獨一行,如下:

# cat server-list.txt
192.168.1.2
192.168.1.3
192.168.1.4
192.168.1.5
192.168.1.6
192.168.1.7

然後,我們再用 for 循環依次掃描 server-list.txt 里對應服務器的端口是否打開。在這裏,我們掃描 22 端口是否打開。

# vi port_scan.sh

#!/bin/sh
for server in `more server-list.txt`
do
#echo $i
nc -zvw3 $server 22
done

最後,我們給這個腳本賦予可執行權限即可。

$ chmod +x port_scan.sh

之後,我們就可以用這個腳本來自動依次檢查多個服務器的 22 端口是否已打開。

# sh port_scan.sh

Connection to 192.168.1.2 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.3 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.4 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.5 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.6 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.7 22 port [tcp/ssh] succeeded!

2. 掃描多台服務器的多個端口是否打開

在這裏,我們同樣把需要查詢的所有服務器地址全部放在一個 server-list.txt 文件里,每個地址單獨一行。這裏就不重複演示了。

與此同時,我們也把需要查詢的服務器端口放在另一個 port-list.txt 文件里,每個端口單獨一行,如下所示:

# cat port-list.txt
22
80

然後,我們再用 for 循環依次掃描 server-list.txt 里對應服務器 port-list.txt 所列的端口是否打開。注意,這裏用到了兩個 for 循環,第一層是服務器列表,第二層是端口列表。

# vi multiple_port_scan.sh

#!/bin/sh
for server in `more server-list.txt`
do
for port in `more port-list.txt`
do
#echo $server
nc -zvw3 $server $port
echo ""
done
done

最後,我們給這個腳本賦予可執行權限即可。

$ chmod +x multiple_port_scan.sh

之後,我們就可以用這個腳本來自動依次檢查多個服務器的多個端口是否已打開。

# sh multiple_port_scan.sh
Connection to 192.168.1.2 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.2 80 port [tcp/http] succeeded!

Connection to 192.168.1.3 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.3 80 port [tcp/http] succeeded!

Connection to 192.168.1.4 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.4 80 port [tcp/http] succeeded!

Connection to 192.168.1.5 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.5 80 port [tcp/http] succeeded!

Connection to 192.168.1.6 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.6 80 port [tcp/http] succeeded!

Connection to 192.168.1.7 22 port [tcp/ssh] succeeded!
Connection to 192.168.1.7 80 port [tcp/http] succeeded!

公眾號:良許Linux

有收穫?希望老鐵們來個三連擊,給更多的人看到這篇文章

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

【其他文章推薦】

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

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

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

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

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

Spark文檔閱讀之二:Programming Guides – Quick Start

Quick Start: https://spark.apache.org/docs/latest/quick-start.html

 

在Spark 2.0之前,Spark的編程接口為RDD (Resilient Distributed Dataset)。而在2.0之後,RDDs被Dataset替代。Dataset很像RDD,但是有更多優化。RDD仍然支持,不過強烈建議切換到Dataset,以獲得更好的性能。 RDD文檔: https://spark.apache.org/docs/latest/rdd-programming-guide.html Dataset文檔: https://spark.apache.org/docs/latest/sql-programming-guide.html  

一、最簡單的Spark Shell交互分析

scala> val textFile = spark.read.textFile("README.md")   # 構建一個Dataset
textFile: org.apache.spark.sql.Dataset[String] = [value: string]

scala> textFile.count()  # Dataset的簡單計算
res0: Long = 104 

scala> val linesWithSpark = textFile.filter(line => line.contain("Spark"))  # 由現有Dataset生成新Dataset
res1: org.apache.spark.sql.Dataset[String] = [value: string]
# 等價於:
# res1 = new Dataset()
# for line in textFile:
#     if line.contain("Spark"):
#         res1.append(line)
# linesWithSpark = res1

scala> linesWithSpark.count()
res2: Long = 19

# 可以將多個操作串行起來
scala> textFile.filter(line => line.contain("Spark")).count()
res3: Long = 19

 

進一步的Dataset分析:

scala> textFile.map(line => line.split(" ").size).reduce((a,b) => if (a > b) a else b)
res12: Int = 16
# 其實map和reduce就是兩個普通的算子,不要被MapReduce中一個map配一個reduce、先map后reduce的思想所束縛
# map算子就是對Dataset的元素X計算fun(X),並且將所有f(X)作為新的Dataset返回
# reduce算子其實就是通過兩兩計算fun(X,Y)=Z,將Dataset中的所有元素歸約為1個值

# 也可以引入庫進行計算
scala> import java.lang.Math
import java.lang.Math

scala> textFile.map(line => line.split(" ").size).reduce((a, b) => Math.max(a, b))
res14: Int = 16

# 還可以使用其他算子
scala> val wordCounts = textFile.flatMap(line => line.split(" ")).groupByKey(identity).count()

# flatMap算子也是對Dataset的每個元素X執行fun(X)=Y,只不過map的res是
#     res.append(Y),如[[Y11, Y12], [Y21, Y22]],結果按元素區分
# 而flatMap是
#     res += Y,如[Y11, Y12, Y21, Y22],各元素結果合在一起

# groupByKey算子將Dataset的元素X作為參數傳入進行計算f(X),並以f(X)作為key進行分組,返回值為KeyValueGroupedDataset類型
# 形式類似於(key: k; value: X1, X2, ...),不過KeyValueGroupedDataset不是一個Dataset,value列表也不是一個array
# 注意:這裏的textFile和textFile.flatMap都是Dataset,不是RDD,groupByKey()中可以傳func;如果以sc.textFile()方法讀文件,得到的是RDD,groupByKey()中間不能傳func

# identity就是函數 x => x,即返回自身的函數

# KeyValueGroupedDataset的count()方法返回(key, len(value))列表,結果是Dataset類型

scala> wordCounts.collect()
res37: Array[(String, Long)] = Array((online,1), (graphs,1), ...
# collect操作:將分佈式存儲在集群上的RDD/Dataset中的所有數據都獲取到driver端

 

數據的cache:

scala> linesWithSpark.cache()  # in-memory cache,讓數據在分佈式內存中緩存
res38: linesWithSpark.type = [value: string]

scala> linesWithSpark.count()
res41: Long = 19

 

二、最簡單的獨立Spark任務(spark-submit提交)

需提前安裝sbt,sbt是scala的編譯工具(Scala Build Tool),類似java的maven。 brew install sbt   1)編寫SimpleApp.scala

import org.apache.spark.sql.SparkSession

object SimpleApp {
    def main(args: Array[String]) {
        val logFile = "/Users/dxm/work-space/spark-2.4.5-bin-hadoop2.7/README.md"
        val spark = SparkSession.builder.appName("Simple Application").getOrCreate()
        val logData = spark.read.textFile(logFile).cache()
        val numAs = logData.filter(line => line.contains("a")).count()  # 包含字母a的行數
        val numBs = logData.filter(line => line.contains("b")).count()  # 包含字母b的行數
        println(s"Lines with a: $numAs, Lines with b: $numBs")
        spark.stop()
    }
}

 

2)編寫sbt依賴文件build.sbt

name := "Simple Application"

version := "1.0"

scalaVersion := "2.12.10"

libraryDependencies += "org.apache.spark" %% "spark-sql" % "2.4.5"

 

其中,”org.apache.spark” %% “spark-sql” % “2.4.5”這類庫名可以在網上查到,例如https://mvnrepository.com/artifact/org.apache.spark/spark-sql_2.10/1.0.0

 

3)使用sbt打包 目錄格式如下,如果SimpleApp.scala和build.sbt放在一個目錄下會編不出來

$ find .
.
./build.sbt
./src
./src/main
./src/main/scala
./src/main/scala/SimpleApp.scala

 

sbt目錄格式要求見官方文檔 https://www.scala-sbt.org/1.x/docs/Directories.html

src/
  main/
    resources/
       <files to include in main jar here>
    scala/
       <main Scala sources>
    scala-2.12/
       <main Scala 2.12 specific sources>
    java/
       <main Java sources>
  test/
    resources
       <files to include in test jar here>
    scala/
       <test Scala sources>
    scala-2.12/
       <test Scala 2.12 specific sources>
    java/
       <test Java sources>

 

使用sbt打包

# 打包
$ sbt package
...
[success] Total time: 97 s (01:37), completed 2020-6-10 10:28:24
# jar包位於 target/scala-2.12/simple-application_2.12-1.0.jar

 

4)提交並執行Spark任務

$ bin/spark-submit --class "SimpleApp" --master spark://xxx:7077 ../scala-tests/SimpleApp/target/scala-2.12/simple-application_2.12-1.0.jar
# 報錯:Caused by: java.lang.ClassNotFoundException: scala.runtime.LambdaDeserialize
# 參考:https://stackoverflow.com/questions/47172122/classnotfoundexception-scala-runtime-lambdadeserialize-when-spark-submit
# 這是spark版本和scala版本不匹配導致的

 

查詢spark所使用的scala的版本

$ bin/spark-shell --master spark://xxx:7077

scala> util.Properties.versionString
res0: String = version 2.11.12

 

修改build.sbt: scalaVersion := “2.11.12” 從下載頁也可驗證,下載的spark 2.4.5使用的是scala 2.11  

 

重新sbt package,產出位置變更為target/scala-2.11/simple-application_2.11-1.0.jar 再次spark-submit,成功

 

$ bin/spark-submit --class "SimpleApp" --master spark://xxx:7077 ../scala-tests/SimpleApp/target/scala-2.11/simple-application_2.11-1.0.jar 
Lines with a: 61, Lines with b: 30

 

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

【其他文章推薦】

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

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

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

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

※回頭車貨運收費標準

隨機抽樣一致性(RANSAC)算法詳解

隨機抽樣一致性(RANSAC)算法能夠有效的剔除特徵匹配中的錯誤匹配點。

實際上,RANSAC能夠有效擬合存在噪聲模型下的擬合函數。實際上,RANSAC算法的核心在於將點劃分為“內點”和“外點”。在一組包含“外點”的數據集中,採用不斷迭代的方法,尋找最優參數模型,不符合最優模型的點,被定義為“外點”。這就是RANSAC的核心思想。

RANSAC原理

OpenCV中濾除誤匹配對採用RANSAC算法尋找一個最佳單應性矩陣H,矩陣大小為3×3。RANSAC目的是找到最優的參數矩陣使得滿足該矩陣的數據點個數最多,通常令h33=1來歸一化矩陣。由於單應性矩陣有8個未知參數,至少需要8個線性方程求解,對應到點位置信息上,一組點對可以列出兩個方程,則至少包含4組匹配點對

 

 

 RANSAC算法從匹配數據集中隨機抽出4個樣本並保證這4個樣本之間不共線,計算出單應性矩陣,然後利用這個模型測試所有數據,並計算滿足這個模型數據點的個數與投影誤差(即代價函數),若此模型為最優模型,則對應的代價函數最小。

損失函數:

 

 

 也就是通過隨機抽樣求解得到一個矩陣,然後驗證其他的點是否符合模型,然後符合的點成為“內點”,不符合的點成為“外點”。下次依然從“新的內點集合”中抽取點構造新的矩陣,重新計算誤差。最後誤差最小,點數最多就是最終的模型。

RANSAC算法步驟:

RANSAC算法步驟: 

          1. 隨機從數據集中隨機抽出4個樣本數據 (此4個樣本之間不能共線),計算出變換矩陣H,記為模型M;

          2. 計算數據集中所有數據與模型M的投影誤差,若誤差小於閾值,加入內點集 I ;

          3. 如果當前內點集 I 元素個數大於最優內點集 I_best , 則更新 I_best = I,同時更新迭代次數k ;

          4. 如果迭代次數大於k,則退出 ; 否則迭代次數加1,並重複上述步驟;

  注:迭代次數k在不大於最大迭代次數的情況下,是在不斷更新而不是固定的;

 

 

 其中,p為置信度,一般取0.995;w為”內點”的比例 ; m為計算模型所需要的最少樣本數=4;
關於RANSAC算法的思想,可以用下圖表示

 

 也就是RANSAC算法的本質是:在存在噪聲的數據中,我們求解一個模型,使得非噪聲數據可以用該模型表示,而噪聲數據被排除在外。

分享三個講解RANSAC算法的網址:

https://www.csdn.net/gather_2d/MtjaMg3sNDAwNS1ibG9n.html

https://www.cnblogs.com/xrwang/archive/2011/03/09/ransac-1.html

https://blog.csdn.net/yanghan742915081/article/details/83005442

 

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

【其他文章推薦】

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

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

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

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

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

※超省錢租車方案

Python機器學習筆記:SVM(4)——sklearn實現,Python機器學習筆記:SVM(1)——SVM概述,Python機器學習筆記:SVM(2)——SVM核函數,Python機器學習筆記:SVM(3)——證明SVM,Python機器學習筆記:SVM(4)——sklearn實現

  上一節我學習了SVM的推導過程,下面學習如何實現SVM,具體的參考鏈接都在第一篇文章中,SVM四篇筆記鏈接為:

Python機器學習筆記:SVM(1)——SVM概述

Python機器學習筆記:SVM(2)——SVM核函數

Python機器學習筆記:SVM(3)——證明SVM

Python機器學習筆記:SVM(4)——sklearn實現

  對SVM的概念理清楚后,下面我們對其使用sklearn進行實現。

1,Sklearn支持向量機庫概述

  我們知道SVM相對感知器而言,它可以解決線性不可分的問題,那麼它是如何解決的呢?其思想很簡單就是對原始數據的維度變換,一般是擴維變換,使得原樣本空間中的樣本點線性不可分,但是在變維之後的空間中樣本點是線性可分的,然後再變換后的高維空間中進行分類。

  上面將SVM再贅述了一下,下面學習sklearn中的SVM方法,sklearn中SVM的算法庫分為兩類,一類是分類的算法庫,主要包含LinearSVC,NuSVC和SVC三個類,另一類是回歸算法庫,包含SVR,NuSVR和LinearSVR三個類,相關模塊都包裹在sklearn.svm模塊中。

  對於SVC,NuSVC和LinearSVC 三個分類的庫,SVC和NuSVC差不多,區別僅僅在於對損失的度量方式不同,而LinearSVC從名字就可以看出,他是線性分類,也就是不支持各種低維到高維的核函數,僅僅支持線性核函數,對線性不可分的數據不能使用。

  同樣的對於SVR,NuSVR和LinearSVR 三個回歸的類,SVR和NuSVR差不多,區別也僅僅在於對損失的度量方式不同。LinearSVR是線性回歸,只能使用線性核函數。

  我們使用這些類的時候,如果有經驗知道數據是線性可以擬合的,那麼使用LinearSVC去分類或者LinearSVR去回歸,他們不需要我們去慢慢的調參選擇各種核函數以及對應的參數,速度也快。如果我們對數據分佈沒有什麼經驗,一般使用SVC去分類或者SVR去回歸,這就需要我們選擇核函數以及對核函數調參了。

2,回顧SVM分類算法和回歸算法

  我們這裏仍然先對SVM算法進行回顧,首先對於SVM分類算法,其原始形式如下:

  其中 n 為樣本個數,我們的樣本為(x1,  y1),(x2,y2),….(xn,  yn),w,b是我們的分離超平面的 wT*xi + b = 0的係數,ξi 為第 i 個樣本的鬆弛係數,C 為懲罰係數,xi (也有時候寫為Φ(xi) 為低維到高維的映射函數)為樣本數。

  通過拉格朗日以及對偶化后的形式為:

  其中和原始形式不同的 α 為拉格朗日係數向量,<xi,  xj> 為我們要使用的核函數。

  對於SVM回歸算法,(我自己沒有總結,借用劉建平老師的博客),其原始形式如下:

  其中 m 為樣本個數,我們的樣本為(x1, y1),(x2,  y2),….,(xm, ym),w,b是我們回歸超平面 wT*xi + b = 0 的係數,ξv, ξ^ 為第 i 個樣本的鬆弛係數, C為懲罰係數,ε 為損失邊界,到超平面距離小於 ε 的訓練集的點沒有損失,Φ(xi) 為低維到高維的映射函數

  通過拉格朗日函數以及對偶后的形式為:

  其中和原始形式不同的 αv, α^ 為拉格朗日係數向量,K(xi, xj) 為我們要使用的核函數。

3,SVM核函數概述

  我在第二篇SVM中學習了核函數,有好幾種,最常用的就是線性核函數,多項式核函數,高斯核函數和Sigmoid核函數,在scikit-learn中,內置的核函數也剛好有這四種。

3.1,線性核函數(Linear Kernel)

  線性核函數表達式為:

  就是普通的內積,LinearSVC和LinearSVR只能使用它。

3.2,多項式核函數(Polynomial Kernel)

  多項式核函數是線性不可分SVM常用的核函數之一,表達式為:

  參數都需要自己調參定義,比較麻煩。

3.3,高斯核函數(Gaussian Kernel)

  高斯核函數,在SVM中也稱為 徑向基核函數(Radial Basisi Function,RBF),它是libsvm默認的核函數,當然也是sklearn默認的核函數,表達式為:

  其中 r 大於0,需要自己調參定義,不過一般情況,我們都使用高斯核函數。

3.4,Sigmoid核函數(Sigmoid Kernel)

  Sigmoid核函數也是線性不可分SVM常用的核函數之一,表示為:

  其中 beta, t 都需要自己調參定義。

  一般情況下,對於非線性數據使用默認的高斯核函數會有比較好的效果,如果你不是SVM調參高手的話,建議使用高斯核來做數據分析。

4,SVM分類算法庫參數小結

  下面我們將具體介紹這三種分類方法都有那些參數值以及不同參數值的含義。

4.1, LinearSVC

  其函數原型如下:

class sklearn.svm.LinearSVC(self, penalty='l2', loss='squared_hinge', dual=True, tol=1e-4,
             C=1.0, multi_class='ovr', fit_intercept=True,
             intercept_scaling=1, class_weight=None, verbose=0,
             random_state=None, max_iter=1000)

  參數說明

  • penalty :正則化參數,L1 和L2兩種參數可選,僅LinearSVC有。默認是L2 正則化,如果我們需要產生稀疏的話,可以選擇L1正則化,這和線性回歸裏面的Lasso回歸類似
  • loss:損失函數,有“hinge” 和“squared_hinge” 兩種可選,前者又稱為L1損失,後者稱為L2損失,默認是“squared_hinge”,其中hinge是SVM的標準損失,squared_hinge是hinge的平方。
  • dual:是否轉化為對偶問題求解,默認是True。這是一個布爾變量,控制是否使用對偶形式來優化算法。
  • tol:殘差收斂條件,默認是0.0001,與LR中的一致。
  • C:懲罰係數,用來控制損失函數的懲罰係數,類似於LR中的正則化係數。默認為1,一般需要通過交叉驗證來選擇一個合適的C,一般來說,噪點比較多的時候,C需要小一些
  • multi_class:負責多分類問題中分類策略制定,有‘ovr’和‘crammer_singer’ 兩種參數值可選,默認值是’ovr’,’ovr’的分類原則是將待分類中的某一類當作正類,其他全部歸為負類,通過這樣求取得到每個類別作為正類時的正確率,取正確率最高的那個類別為正類;‘crammer_singer’ 是直接針對目標函數設置多個參數值,最後進行優化,得到不同類別的參數值大小。
  •  fit_intercept:是否計算截距,與LR模型中的意思一致。
  • class_weight:與其他模型中參數含義一樣,也是用來處理不平衡樣本數據的,可以直接以字典的形式指定不同類別的權重,也可以使用balanced參數值。如果使用“balanced”,則算法會自己計算權重,樣本量少的類別所對應的樣本權重會高,當然,如果你的樣本類別分佈沒有明顯的偏倚,則可以不管這個係數,選擇默認的None
  • verbose:是否冗餘,默認為False
  • random_state:隨機種子的大小
  • max_iter:最大迭代次數,默認為1000.

懲罰係數:

  錯誤項的懲罰係數。C越大,即對分錯樣本的懲罰程度越大,因此在訓練樣本中準確率越高,但是泛化能力降低,也就是對測試數據的分類準確率降低。相反,減少C的話,容許訓練樣本中有一些誤分類錯誤樣本,泛化能力強。對於訓練樣本帶有噪音的情況,一般採用後者,把訓練樣本集中錯誤分類的樣本作為噪音。

4.2,NuSVC

  其函數原型如下:

class sklearn.svm.NuSVC(self, nu=0.5, kernel='rbf', degree=3, gamma='auto_deprecated',
             coef0=0.0, shrinking=True, probability=False, tol=1e-3,
             cache_size=200, class_weight=None, verbose=False, max_iter=-1,
             decision_function_shape='ovr', random_state=None)

   參數說明

  • nu:訓練誤差部分的上限和支持向量部分的下限,取值在(0,1)之間,默認是0.5,它和懲罰係數C類似,都可以控制懲罰的力度。
  • kernel:核函數,核函數是用來將非線性問題轉化為線性問題的一種方法,默認是“rbf”核函數

      常用的核函數有以下幾種:

  • degree:當核函數是多項式核函數(“poly”)的時候,用來控制函數的最高次數。(多項式核函數是將低維的輸入空間映射到高維的特徵空間),這個參數只對多項式核函數有用,是指多項式核函數的階數 n。如果給的核函數參數是其他核函數,則會自動忽略該參數。
  • gamma:核函數係數,默認是“auto”,即特徵維度的倒數。核函數係數,只對rbf  poly  sigmoid 有效。
  • coef0:核函數常數值( y = kx + b 的b值),只有“poly”和“sigmoid” 函數有,默認值是0.
  • max_iter:最大迭代次數,默認值是 -1 ,即沒有限制。
  • probability:是否使用概率估計,默認是False。
  • decision_function_shape:與“multi_class”參數含義類似,可以選擇“ovo” 或者“ovr”(0.18版本默認是“ovo”,0.19版本為“ovr”) OvR(one vs rest)的思想很簡單,無論你是多少元分類,我們都可以看做二元分類,具體的做法是,對於第K類的分類決策,我們把所有第K類的樣本作為正例,除第K類樣本以外的所有樣本作為負類,然後在上面做二元分類,得到第K類的分類模型。 OvO(one vs one)則是每次在所有的T類樣本裏面選擇兩類樣本出來,不妨記為T1類和T2類,把所有的輸出為T1 和 T2的樣本放在一起,把T1作為正例,T2 作為負例,進行二元分類,得到模型參數,我們一共需要T(T-1)/2 次分類。從上面描述可以看出,OvR相對簡單,但是分類效果略差(這裡是指大多數樣本分佈情況,某些樣本分佈下OvR可能更好),而OvO分類相對精確,但是分類速度沒有OvR快,一般建議使用OvO以達到較好的分類效果
  • chache_size:緩衝大小,用來限制計算量大小,默認是200M,如果機器內存大,推薦使用500MB甚至1000MB

4.3,SVC

  其函數原型如下:

class sklearn.svm.SVC(self, C=1.0, kernel='rbf', degree=3, gamma='auto_deprecated',
             coef0=0.0, shrinking=True, probability=False,
             tol=1e-3, cache_size=200, class_weight=None,
             verbose=False, max_iter=-1, decision_function_shape='ovr',
             random_state=None)

  參數說明:

  • C:懲罰係數(前面有詳細學習)

  SVC和NuSVC方法基本一致,唯一區別就是損失函數的度量方式不同(NuSVC中的nu參數和SVC中的C參數)即SVC使用懲罰係數C來控制懲罰力度,而NuSVC使用nu來控制懲罰力度。

5,SVM回歸算法庫參數小結

  下面我們將具體介紹這三種分類方法都有那些參數值以及不同參數值的含義。

5.1, LinearSVR

  其函數原型如下:

class sklearn.svm.LinearSVR(self, epsilon=0.0, tol=1e-4, C=1.0,
             loss='epsilon_insensitive', fit_intercept=True,
             intercept_scaling=1., dual=True, verbose=0,
             random_state=None, max_iter=1000)

  參數說明

  • epsilon:距離誤差epsilon,即回歸模型中的 epsilon,訓練集中的樣本需要滿足:
  • loss:損失函數,有“hinge” 和“squared_hinge” 兩種可選,前者又稱為L1損失,後者稱為L2損失,默認是“squared_hinge”,其中hinge是SVM的標準損失,squared_hinge是hinge的平方。
  • dual:是否轉化為對偶問題求解,默認是True。這是一個布爾變量,控制是否使用對偶形式來優化算法。
  • tol:殘差收斂條件,默認是0.0001,與LR中的一致。
  • C:懲罰係數,用來控制損失函數的懲罰係數,類似於LR中的正則化係數。默認為1,一般需要通過交叉驗證來選擇一個合適的C,一般來說,噪點比較多的時候,C需要小一些
  •  fit_intercept:是否計算截距,與LR模型中的意思一致。
  • verbose:是否冗餘,默認為False
  • random_state:隨機種子的大小
  • max_iter:最大迭代次數,默認為1000.

5.2,NuSVR

  其函數原型如下:

class sklearn.svm.NuSVR(self, nu=0.5, C=1.0, kernel='rbf', degree=3,
             gamma='auto_deprecated', coef0=0.0, shrinking=True,
             tol=1e-3, cache_size=200, verbose=False, max_iter=-1)

   參數說明

  • nu:訓練誤差部分的上限和支持向量部分的下限,取值在(0,1)之間,默認是0.5,它和懲罰係數C類似,都可以控制懲罰的力度。
  • kernel:核函數,核函數是用來將非線性問題轉化為線性問題的一種方法,默認是“rbf”核函數

      常用的核函數有以下幾種:

  • degree:當核函數是多項式核函數(“poly”)的時候,用來控制函數的最高次數。(多項式核函數是將低維的輸入空間映射到高維的特徵空間),這個參數只對多項式核函數有用,是指多項式核函數的階數 n。如果給的核函數參數是其他核函數,則會自動忽略該參數。
  • gamma:核函數係數,默認是“auto”,即特徵維度的倒數。核函數係數,只對rbf  poly  sigmoid 有效。
  • coef0:核函數常數值( y = kx + b 的b值),只有“poly”和“sigmoid” 函數有,默認值是0.
  • chache_size:緩衝大小,用來限制計算量大小,默認是200M,如果機器內存大,推薦使用500MB甚至1000MB

5.3,SVR

  其函數原型如下:

class sklearn.svm.SVC(self, kernel='rbf', degree=3, gamma='auto_deprecated',
             coef0=0.0, tol=1e-3, C=1.0, epsilon=0.1, shrinking=True,
             cache_size=200, verbose=False, max_iter=-1)

  參數說明:

  SVR和NuSVR方法基本一致,唯一區別就是損失函數的度量方式不同(NuSVR中的nu參數和SVR中的C參數)即SVR使用懲罰係數C來控制懲罰力度,而NuSVR使用nu來控制懲罰力度。

6,SVM的方法與對象

6.1 方法

  三種分類的方法基本一致,所以一起來說:

  • decision_function(x):獲取數據集X到分離超平面的距離
  • fit(x , y):在數據集(X,y)上使用SVM模型
  • get_params([deep]):獲取模型的參數
  • predict(X):預測數值型X的標籤
  • score(X,y):返回給定測試集合對應標籤的平均準確率

6.2  對象

  • support_:以數組的形式返回支持向量的索引
  • support_vectors_:返回支持向量
  • n_support_:每個類別支持向量的個數
  • dual_coef:支持向量係數
  • coef_:每個特徵係數(重要性),只有核函數是LinearSVC的是可用,叫權重參數,即w
  • intercept_:截距值(常數值),稱為偏置參數,即b

  加粗的三個屬性是我們常用的,後面會舉例說明 support_vectors_。

 

7,SVM類型算法的模型選擇

7.1 PPT總結

  這裏使用(http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf)的PPT進行整理。

7.2 SVM算法庫其他調參要點

  下面再對其他調參要點做一個小結:

  • 1,一般推薦在做訓練之前對數據進行歸一化,當然測試集的數據也要做歸一化
  • 2,在特徵數非常多的情況下,或者樣本數遠小於特徵數的時候,使用線性核,效果就很好了,並且只需要選擇懲罰係數C即可
  • 3,在選擇核函數的時候,如果線性擬合效果不好,一般推薦使用默認的高斯核(rbf),這時候我們主要對懲罰係數C和核函數參數 gamma 進行調參,經過多輪的交叉驗證選擇合適的懲罰係數C和核函數參數gamma。
  • 4,理論上高斯核不會比線性核差,但是這個理論就建立在要花費更多的時間上調參上,所以實際上能用線性核解決的問題我們盡量使用線性核函數

   在SVM中,其中最重要的就是核函數的選取和參數選擇了,當然這個需要大量的經驗來支撐,這裏幾個例子只是自己網上找的SVM的小例子。

8,SVM調參實例1

  下面學習支持向量機的使用方法以及一些參數的調整,支持向量機的原理就是將低維不可分問題轉換為高維可分問題。這裏不再贅述。

8.1  線性可分支持向量機

  首先做一個簡單的線性可分的例子,這裏直接使用sklearn.datasets.make_blobs 生成數據。生成數據代碼如下:

# 生成數據集
from sklearn.datasets.samples_generator import make_blobs
from matplotlib import pyplot as plt

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=0.6)
# 畫圖形
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
plt.show()

   我們畫圖展示如下:

  我們嘗試繪製分離兩組數據的直線,從而創建分類模型,對於這裏所示的數據,這是我們可以手動完成的任務。但是立馬可以看出有很多分界線可以完美的區分兩個類。

   下面畫出決策邊界。

# 生成數據集
from sklearn.datasets.samples_generator import make_blobs
from matplotlib import pyplot as plt
import numpy as np

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=0.6)

# 畫圖形
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
# 線性等分詳細
xfit = np.linspace(-1, 3.5)
plt.plot([0.6], [2.1], 'x', color='red', markeredgewidth=2, markersize=10)

for m, b in [(1, 0.65), (0.5, 1.6), (-0.2, 2.9)]:
    plt.plot(xfit, m * xfit + b, '-k')

plt.show()

   圖如下:

  (注意:這三條直線是我隨便畫的,其實你可以使用Logistic回歸,線性回歸等分類,畫出線,我這裡是為了方便)

   這裡是三條不同的分割直線,並且這些分割直線能夠完全區分這些樣例。但是根據支持向量機的思想,哪一條直線是最優的分割線呢?支持向量機並不是簡單的繪製一條直線,而是畫出邊距為一定寬度的直線,直到最近的點。

  下面我們對直線進行加粗,代碼如下:

# 生成數據集
from sklearn.datasets.samples_generator import make_blobs
from matplotlib import pyplot as plt
import numpy as np

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=0.6)

# 畫圖形
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
# 線性等分詳細
xfit = np.linspace(-1, 3.5)
plt.plot([0.6], [2.1], 'x', color='red', markeredgewidth=2, markersize=10)

for m, b, d in [(1, 0.65, 0.33), (0.5, 1.6, 0.55), (-0.2, 2.9, 0.2)]:
    yfit = m * xfit + b
    plt.plot(xfit, yfit, '-k')
    plt.fill_between(xfit, yfit - d, yfit + d, edgecolor='none',
                     color='#AAAAAA', alpha=0.4)  # alpha為透明度
plt.show()

   如圖所示:

   在支持向量機中,邊距最大化的直線是我們將選擇的最優模型。支持向量機是這種最大邊距估計器的一個例子。

  接下來,我們訓練一個基本的SVM,我們使用sklearn的支持向量機,對這些數據訓練SVM模型。目前我們將使用一個線性核並將C參數設置為一個默認的數值。如下:

from sklearn.svm import SVC  # Support Vector Classifier

model = SVC(kernel='linear') # 線性核函數
model.fit(X, y)

   我們順便看看SVC的所有參數情況:

SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape='ovr', degree=3, gamma='auto_deprecated',
    kernel='linear', max_iter=-1, probability=False, random_state=None,
    shrinking=True, tol=0.001, verbose=False)

   為了更好展現這裏發生的事情,下面我們創建一個輔助函數,為我們繪製SVM的決策邊界。

def plot_SVC_decision_function(model, ax=None, plot_support=True):
    '''Plot the decision function for a 2D SVC'''
    if ax is None:
        ax = plt.gca()  #get子圖
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # create grid to evaluate model
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    # 生成網格點和坐標矩陣
    Y, X = np.meshgrid(y, x)
    # 堆疊數組
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)

    # plot decision boundary and margins
    ax.contour(X, Y, P, colors='k', levels=[-1, 0, 1],
               alpha=0.5, linestyles=['--', '-', '--'])  # 生成等高線 --

    # plot support vectors
    if plot_support:
        ax.scatter(model.support_vectors_[:, 0],
                   model.support_vectors_[:, 1],
                   s=300, linewidth=1, facecolors='none')

    ax.set_xlim(xlim)
    ax.set_ylim(ylim)

   下面繪製決策邊界:

def train_SVM():
    # n_samples=50 表示取50個點,centers=2表示將數據分為兩類
    X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=0.6)

    # 線性核函數
    model = SVC(kernel='linear')
    model.fit(X, y)
    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(model)
    plt.show()
    return X, y

   結果如圖所示:

   這是最大化兩組點之間的間距的分界線,那中間這條線就是我們最終的決策邊界了。請注意:一些訓練點碰到了邊緣,如圖所示,在兩個邊界上包含兩個紅點和一個黃點,所以這三個點又稱為支持向量,是 alpha 值不為零的,這些點是這種擬合的關鍵要素,被稱為支持向量。在sklearn中,這些點存儲在分類器的 support_vectors_ 屬性中。

  我們通過下面代碼可以得出支持向量的結果。

    print(model.support_vectors_)
    '''
    [[0.44359863 3.11530945]
     [2.33812285 3.43116792]
     [2.06156753 1.96918596]]
    '''

  在支持向量機只有位於支持向量上面的點才會對決策邊界有影響,也就是說不管有多少的點是非支持向量,那對最終的決策邊界都不會產生任何影響。我們可以看到這一點,例如,如果我們繪製該數據集的前 60個點和前120個點獲得的模型:

def plot_svm(N=10, ax=None):
    X, y = make_blobs(n_samples=200, centers=2, random_state=0, cluster_std=0.6)
    X, y = X[:N], y[:N]
    model = SVC(kernel='linear')
    model.fit(X, y)

    ax = ax or plt.gca()
    ax.scatter(X[:, 0], X[:, 1], c=y, cmap='autumn')
    ax.set_xlim(-1, 4)
    ax.set_ylim(-1, 6)
    plot_SVC_decision_function(model, ax)

if __name__ == '__main__':
    # train_SVM()
    fig, ax = plt.subplots(1, 2, figsize=(16, 6))
    fig.subplots_adjust(left=0.0625, right=0.95, wspace=0.1)
    for axi, N in zip(ax, [60, 120]):
        plot_svm(N, axi)
        axi.set_title('N = {0}'.format(N))

   結果如圖所示:

  上面就是我們繪製的該數據集前60個點和前120個點獲得的模型,可以發現無論使用60,還是使用120個數據點,決策邊界都沒有發生變換,所有隻要支持向量沒變,其他的數據怎麼加都無所謂。

   這個分類器成功的關鍵在於:為了擬合,只有支持向量的位置是最重要的;任何遠離邊距的點都不會影響擬合的結果,邊界之外的點無論有多少都不會對其造成影響,也就是說不管有多少點是非支持向量,對最終的決策邊界都不會產生任何影響。

8.2 線性不可分支持向量機

  下面引入核函數,來看看核函數的威力,首先我們導入一個線性不可分的數據集。

def train_svm_plus():
    # 二維圓形數據 factor 內外圓比例(0, 1)
    X, y = make_circles(100, factor=0.1, noise=0.1)
    
    clf = SVC(kernel='linear')
    clf.fit(X, y)
    
    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(clf, plot_support=False)

   數據集如圖所示:

   很明顯,用線性分類器無論怎麼畫線也不能分好,那咋辦呢?下面試試高斯核變換吧。在進行核變換之前,先看看數據在高維空間下的映射:

def plot_3D(X, y, elev=30, azim=30):
    # 我們加入了新的維度 r
    r = np.exp(-(X ** 2).sum(1))
    ax = plt.subplot(projection='3d')
    ax.scatter3D(X[:, 0], X[:, 1], r, c=y, s=50, cmap='autumn')
    ax.view_init(elev=elev, azim=azim)
    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_zlabel('z')


if __name__ == '__main__':
    X, y = train_svm_plus()
    plot_3D(elev=30, azim=30, X=X, y=y)

   畫出三維圖形,如圖所示:

   見證核變換威力的時候到了,引入徑向基函數(也叫高斯核函數),進行核變換:

def train_svm_plus():
    # 二維圓形數據 factor 內外圓比例(0, 1)
    X, y = make_circles(100, factor=0.1, noise=0.1)
    # 加入徑向基函數
    clf = SVC(kernel='rbf')
    clf.fit(X, y)

    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(clf, plot_support=False)
    return X, y

   得到的SVM模型為:

SVC(C=1000000.0, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape='ovr', degree=3, gamma='auto_deprecated',
    kernel='rbf', max_iter=-1, probability=False, random_state=None,
    shrinking=True, tol=0.001, verbose=False)

   再次進行分類任務,代碼如下:

def train_svm_plus():
    # 二維圓形數據 factor 內外圓比例(0, 1)
    X, y = make_circles(100, factor=0.1, noise=0.1)
    # 加入徑向基函數
    clf = SVC(kernel='rbf')
    clf.fit(X, y)

    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(clf, plot_support=False)
    plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
                s=300, lw=1, facecolors='none')
    return X, y

   分類結果如圖所示:

   可以清楚的看到效果很好,我們將線性不可分的兩對數據分割開來。使用這種核支持向量機,我們學習一個合適的非線性決策邊界。這種核變換策略在機器學習中經常被使用。

8.3 線性近似可分支持向量機——軟間隔問題

  SVM模型有兩個非常重要的參數C與gamma,其中C是懲罰係數,即對誤差的寬容忍,C越高,說明越不能容忍出現誤差,容易過擬合。C越小,容易欠擬合。C過大或過小,泛化能力變差。

  gamma 是選擇 RBF 函數作為kernel后,該函數自帶的一個參數。隱含的決定了數據映射到新的特徵空間后的分佈,gamma越大,支持向量越小,gamma值越小,支持向量越多。

  下面我們分別調劑一下C和gamma來看一下對結果的影響。

  首先我們調節C,先做一個有噪音的數據分佈

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=100, centers=2, random_state=0, cluster_std=0.8)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')

   結果如圖所示:

   上面的分佈看起來要劃分似乎有點困難,所以我們可以進行軟件各調整看看。

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=100, centers=2, random_state=0, cluster_std=0.8)

fig, ax = plt.subplots(1, 2, figsize=(16, 6))
fig.subplots_adjust(left=0.0625, right=0.95, wspace=0.1)

for axi, C in zip(ax, [10.0, 0.1]):
    model = SVC(kernel='linear', C=C)
    model.fit(X, y)
    axi.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(model, axi)
    axi.scatter(model.support_vectors_[:, 0],
                model.support_vectors_[:, 1],
                s=300, lw=1, facecolors='none')
    axi.set_title('C={0:.1f}'.format(C), size=14)

   結果如圖所示:

   可以看到左邊這幅圖C值比較大,要求比較嚴格,不能分錯東西,隔離帶中沒有進入任何一個點,但是隔離帶的距離比較小,泛化能力比較差。右邊這幅圖C值比較小,要求相對來說比較松一點,隔離帶較大,但是隔離帶中進入了很多的黃點和紅點。那麼C大一些好還是小一些好呢?這需要考慮實際問題,可以進行K折交叉驗證來得到最合適的C值。

   下面再看看另一個參數gamma值,這個參數值只是在高斯核函數裏面才有,這個參數控制着模型的複雜程度,這個值越大,模型越複雜,值越小,模型就越精簡。

  代碼如下:

# n_samples=50 表示取50個點,centers=2表示將數據分為兩類
X, y = make_blobs(n_samples=100, centers=2, random_state=0, cluster_std=0.8)

fig, ax = plt.subplots(1, 3, figsize=(16, 6))
fig.subplots_adjust(left=0.0625, right=0.95, wspace=0.1)

for axi, gamma in zip(ax, [10.0, 1.0, 0.1]):
    model = SVC(kernel='rbf', gamma=gamma)
    model.fit(X, y)
    axi.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_SVC_decision_function(model, axi)
    axi.scatter(model.support_vectors_[:, 0],
                model.support_vectors_[:, 1],
                s=300, lw=1, facecolors='none')
    axi.set_title('gamma={0:.1f}'.format(gamma), size=14)

   結果如下:

   可以看出,當這個參數較大時,可以看出模型分類效果很好,但是泛化能力不太好。當這個參數較小時,可以看出模型裏面有些分類是錯誤的,但是這個泛化能力更好,一般也應有的更多。

  通過這個簡單的例子,我們對支持向量機在SVM中的基本使用,以及軟間隔參數的調整,還有核函數變換和gamma值等一些參數的比較。

  完整代碼請參考我的GitHub(地址:https://github.com/LeBron-Jian/MachineLearningNote)。

9,SVM調參實例2

  下面我們用一個實例學習SVM RBF分類調參(此例子是劉建平老師的博客內容,鏈接在文後)。

  首先,我們生成一些隨機數據,為了讓數據難一點,我們加入了一些噪音,代碼如下:

# _*_coding:utf-8_*_
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.datasets import make_moons, make_circles
from sklearn.preprocessing import StandardScaler
from matplotlib.colors import ListedColormap

X, y = make_circles(noise=0.2, factor=0.5, random_state=1)
# 對數據進行標準化
X = StandardScaler().fit_transform(X)

# 下面看看數據長什麼樣子
cm = plt.cm.RdBu
cm_birght = ListedColormap(['#FF0000', '#0000FF'])
ax = plt.subplot()

ax.set_title('Input data')
# plot the training points
ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cm_birght)
ax.set_xticks([])
ax.set_yticks([])
plt.tight_layout()
plt.show()

  上面代碼對數據做了標準化,注意做標準化和不做標準化的差異(不一定所有的數據標準化后的效果更好,但是絕大多數確實更好)。比如下圖:

  我們看,當不做數據標準化,我們x1的取值範圍由0~90不等,當做了數據標準化之後,其取值範圍就在-2~2之間了。說明標準化的作用還是很明顯的,不多贅述,下面繼續。

   生成的數據如下(可能下一次運行,就變了哈):

   知道數據長什麼樣了,下面我們要對這個數據集進行SVM RBF分類了,分類時我們採用了網格搜索,在C=(0.1, 1, 10)和 gamma=(1, 0.1, 0.01)形成的9種情況中選擇最好的超參數,我們用了4折交叉驗證。這裏只是一個例子,實際運用中,可能需要更多的參數組合來進行調參。

  代碼及其結果如下:

# 網格搜索尋找最佳參數
grid = GridSearchCV(SVC(), param_grid={'C': [0.1, 1, 10], 'gamma': [1, 0.1, 0.01]}, cv=4)
grid.fit(X, y)
print("The best parameters are %s with a score of %0.2f"
      % (grid.best_params_, grid.best_score_))
# The best parameters are {'C': 10, 'gamma': 0.1} with a score of 0.91

   就是說,我們通過網格搜索,在我們給定的9組超參數組合中,C=10, gamma=0.1 分數最高,這就是我們最終的參數候選。

  下面我們看看SVM分類后的可視化,這裏我們把上面九種組合各個訓練后,通過對網格里的點預測來標色,觀察分類的效果圖,代碼如下:

# SVM 分類後進行可視化
x_min, x_max = X[:, 0].min(), X[:, 0].max() + 1
y_min, y_max = X[:, 1].min(), X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                     np.arange(y_min, y_max, 0.02))

for i, C in enumerate((0.1, 1, 10)):
    for j, gamma in enumerate((1, 0.1, 0.01)):
        # plt.subplot()
        clf = SVC(C=C, gamma=gamma)
        clf.fit(X, y)
        Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

        # put the result into a color plot
        Z = Z.reshape(xx.shape)
        plt.contourf(xx, yy, Z, cmap=plt.cm.coolwarm)

        # Plot also the training points
        plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.coolwarm)

        plt.xlim(xx.min(), xx.max())
        plt.ylim(yy.min(), yy.max())
        plt.xticks(())
        plt.yticks(())
        plt.xlabel(" gamma=" + str(gamma) + " C=" + str(C))
        plt.show()

   結果如下:

   從我測試的結果來看,劉老師的代碼還是有一點點問題,显示不出九個,所以這裏我打算重新學習一個例子。

   完整代碼請參考我的GitHub(地址:https://github.com/LeBron-Jian/MachineLearningNote)。

10,SVM調參實例3(非線性支持向量機)

  非線性的話,我們一方面可以利用核函數構造出非線性,一方面我們可以自己構造非線性。下面首先學習自己構造非線性。

10.1 自己構造非線性數據

  我們構造非線性數據的代碼如下:

# _*_coding:utf-8_*_
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.datasets import make_moons, make_circles
from sklearn.preprocessing import StandardScaler

X1D = np.linspace(-4, 4, 9).reshape(-1, 1)
# np.c_是按行連接兩個矩陣,就是把兩矩陣左右相加,要求行數相等。
X2D = np.c_[X1D, X1D ** 2]
y = np.array([0, 0, 1, 1, 1, 1, 1, 0, 0])

plt.figure(figsize=(11, 4))

plt.subplot(121)
plt.grid(True, which='both')
plt.axhline(y=0, color='k')
plt.plot(X1D[:, 0][y == 0], np.zeros(4), 'bs')
plt.plot(X1D[:, 0][y == 1], np.zeros(5), 'g*')
plt.gca().get_yaxis().set_ticks([])
plt.xlabel(r'$x_1$', fontsize=20)
plt.axis([-4.5, 4.5, -0.2, 0.2])

plt.subplot(122)
plt.grid(True, which='both')
plt.axhline(y=0, color='k')
plt.axvline(x=0, color='k')
plt.plot(X2D[:, 0][y == 0], X2D[:, 1][y == 0], 'bs')
plt.plot(X2D[:, 0][y == 1], X2D[:, 1][y == 1], 'g*')
plt.xlabel(r'$x_1$', fontsize=20)
plt.ylabel(r'$x_2$', fontsize=20, rotation=0)
plt.gca().get_yaxis().set_ticks([0, 4, 8, 12, 16])
plt.plot([-4.5, 4.5], [6.5, 6.5], 'r--', linewidth=3)
plt.axis([-4.5, 4.5, -1, 17])

plt.subplots_adjust(right=1)
plt.show()

   圖如下:

  從這個圖可以看到,我們利用對數據的變換,可以對數據的維度增加起來,變成非線性。

   假設我們不使用核函數的思想,先對數據做變換,看能不能達到一個比較好的結果,首先我們做一個測試的數據,代碼如下:

# _*_coding:utf-8_*_
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=100, noise=0.15, random_state=42)


def plot_dataset(X, y, axes):
    plt.plot(X[:, 0][y == 0], X[:, 1][y == 0], 'bs')
    plt.plot(X[:, 0][y == 1], X[:, 1][y == 1], 'g*')
    plt.axis(axes)
    plt.grid(True, which='both')
    plt.xlabel(r'$x_1$', fontsize=20)
    plt.ylabel(r'$x_2$', fontsize=20, rotation=0)

plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])
plt.show()

   生成的圖如下:

   下面代碼將兩類數據分出來了:

Polynomial_svm_clf = Pipeline((('poly_features', PolynomialFeatures(degree=3)),
                               ('scaler', StandardScaler()),
                               ('svm_clf', LinearSVC(C=10))
                               ))
Polynomial_svm_clf.fit(X, y)

def plot_predictions(clf, axes):
    x0s = np.linspace(axes[0], axes[1], 100)
    x1s = np.linspace(axes[2], axes[3], 100)
    x0, x1 = np.meshgrid(x0s, x1s)
    X = np.c_[x0.ravel(), x1.ravel()]
    y_pred = clf.predict(X).reshape(x0.shape)
    # 下面填充一個等高線, alpha表示透明度
    plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2)

plot_predictions(Polynomial_svm_clf, [-1.5, 2.5, -1, 1.5])
plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])
plt.show()

   結果如下:

   從結果來看,我們使用線性支持向量機將兩類數據區分開是沒有問題的。而最重要的是我們如何使用核函數呢?下面繼續學習

10.2 如何對非線性數據進行核函數的變換

   我們首先看svm的官方文檔:

   核函數默認是 rbf,也就是徑向基核函數。下面分別演示核函數。

  我們依舊拿上面的數據,首先取核函數為 多項式核 看看效果(這裏對比的是多項式核的degree,也就是多項式核的維度):

# _*_coding:utf-8_*_
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC, SVC

X, y = make_moons(n_samples=100, noise=0.15, random_state=42)

def plot_dataset(X, y, axes):
    plt.plot(X[:, 0][y == 0], X[:, 1][y == 0], 'bs')
    plt.plot(X[:, 0][y == 1], X[:, 1][y == 1], 'g*')
    plt.axis(axes)
    plt.grid(True, which='both')
    plt.xlabel(r'$x_1$', fontsize=20)
    plt.ylabel(r'$x_2$', fontsize=20, rotation=0)

# 展示圖像
def plot_predictions(clf, axes):
    x0s = np.linspace(axes[0], axes[1], 100)
    x1s = np.linspace(axes[2], axes[3], 100)
    x0, x1 = np.meshgrid(x0s, x1s)
    X = np.c_[x0.ravel(), x1.ravel()]
    y_pred = clf.predict(X).reshape(x0.shape)
    # 下面填充一個等高線, alpha表示透明度
    plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2)


Poly_kernel_svm_clf = Pipeline((('scaler', StandardScaler()),
                                ('svm_clf', SVC(kernel='poly', degree=3, coef0=1, C=5))
                                ))
Poly_kernel_svm_clf.fit(X, y)
# 下面做一個對比試驗,看看degree的值的變換
Poly_kernel_svm_clf_plus = Pipeline((('scaler', StandardScaler()),
                                     ('svm_clf', SVC(kernel='poly', degree=10, coef0=1, C=5))
                                     ))
Poly_kernel_svm_clf_plus.fit(X, y)

plt.subplot(121)
plot_predictions(Poly_kernel_svm_clf, [-1.5, 2.5, -1, 1.5])
plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])
plt.title(r'$d=3, r=1, C=5$', fontsize=18)

plt.subplot(122)
plot_predictions(Poly_kernel_svm_clf, [-1.5, 2.5, -1, 1.5])
plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])
plt.title(r'$d=10, r=100, C=5$', fontsize=18)
plt.show()

   結果如下:

   我們是把數據映射到高維空間,然後再拿回來看效果,實際上並沒有去高維空間做運算。。這就是我們想要展示的多項式核函數,下面學習高斯核函數。

  高斯核函數:利用相似度來變換特徵

  我們選擇一份一維數據,並在 x1=-2,  x1=1 處為其添加兩個高斯函數,接下來讓我門將相似度函數定義為 gamma=0.3 的徑向基核函數(RBF):

  例如: x1 = -1:它位於距第一個地標距離為1的地方,距離第二個地標距離為2。因此其新特徵為 x2 = exp(-0.3*1^2)=0.74 ,並且  x3 = exp(-0.3 * 2^2)=0.3。

  圖如下:

   這裏說一下,就是假設 X2和 X3為兩個高斯函數,我們看 x這個點距離兩個地標的距離。離高斯分佈的中心越近,就越發生什麼。。經過計算出來距離兩個地標的距離,我們就可以依此類推,來計算所有一維坐標相對應的二維坐標。(二維坐標就是距離兩個高斯函數的距離)。

  我們這裏用相似度特徵來替換原本的特徵。

  下面我們做一個實驗,我們只看 gamma的變換,高斯函數的開口變化:

X1D = np.linspace(-4, 4, 9).reshape(-1, 1)
X2D = np.c_[X1D, X1D ** 2]

X, y = make_moons(n_samples=100, noise=0.15, random_state=42)


def gaussian_rbf(x, landmark, gamma):
    return np.exp(-gamma * np.linalg.norm(x - landmark, axis=1) ** 2)


gamma = 0.3

# 下面進行訓練,得到一個支持向量機的模型(這裏我們沒有訓練,直接畫出來了)
# 因為測試的數據是我們自己寫的,為了方便,我們自己畫出來,當然你也可以自己做
xls = np.linspace(-4.5, 4.5, 200).reshape(-1, 1)
x2s = gaussian_rbf(xls, -2, gamma)
x3s = gaussian_rbf(xls, 1, gamma)

XK = np.c_[gaussian_rbf(X1D, -2, gamma), gaussian_rbf(X2D, 1, gamma)]
yk = np.array([0, 0, 1, 1, 1, 1, 1, 0, 0])

plt.figure(figsize=(11, 4))

# plt.subplot(121)
plt.grid(True, which='both')
plt.axhline(y=0, color='k')
plt.scatter(x=[-2, 1], y=[0, 0], s=150, alpha=0.5, c='red')
plt.plot(X1D[:, 0][yk == 0], np.zeros(4), 'bs')
plt.plot(X1D[:, 0][yk == 1], np.zeros(5), 'g*')
plt.plot(xls, x2s, 'g--')
plt.plot(xls, x3s, 'b:')
plt.gca().get_yaxis().set_ticks([0, 0.25, 0.5, 0.75, 1])
plt.xlabel(r'$x_1$', fontsize=20)
plt.ylabel(r'Similarity', fontsize=14)

plt.annotate(r'$\mathbf{x}$',
             xy=(X1D[3, 0], 0),
             xytest=(-0.5, 0.20),
             ha='center',
             arrowprops=dict(facecolor='black', shrink=0.1),
             fontsize=18,
             )
plt.text(-2, 0.9, "$x_2$", ha='center', fontsize=20)
plt.text(1, 0.9, "$x_3$", ha='center', fontsize=20)
plt.axis([-4.5, 4.5, -0.1, 1.1])

   結果如下(下面我們分別調試gamma,分為0.3   0.8):

   理論情況下,我們會得到怎麼維特徵呢?可以對每一個實例(樣本數據點)創建一個地標,此時會將mn 的訓練集轉換成 mm 的訓練集(m表示樣本個數,n表示特徵維度個數)。

  SVM中利用核函數的計算技巧,大大降低了計算複雜度

  • 增加gamma 使高斯曲線變窄,因此每個實例的影響範圍都較小,決策邊界最終變得不規則,在個別實例周圍擺動
  • 減少gamma 使高斯曲線變寬,因此實例具有更大的影響範圍,並且決策邊界更加平滑

   下面做一個對比試驗(gamma值(0.1  0.5), C值(0.001, 1000)):

rbf_kernel_svm_clf = Pipeline((('scaler', StandardScaler()),
                               ('svm_clf', SVC(kernel='rbf', gamma=5, C=0.001))
                               ))

gamma1, gamma2 = 0.1, 5
C1, C2 = 0.001, 1000
hyperparams = (gamma1, C1), (gamma1, C2), (gamma2, C1), (gamma2, C2)

svm_clfs = []
for gamma, C in hyperparams:
    rbf_kernel_svm_clf.fit(X, y)
    svm_clfs.append(rbf_kernel_svm_clf)

plt.figure(figsize=(11, 7))

for i, svm_clfs in enumerate(svm_clfs):
    plt.subplot(221 + i)
    plot_predictions(svm_clfs, [-1.5, 2.5, -1, 1.5])
    plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])
    gamma, C = hyperparams[i]
    plt.title(r'$\gamma={}, C={}$'.format(gamma, C), fontsize=16)
plt.show()

   結果如下:

   我們看第一幅圖,邊界比較平穩,沒有過擬合的風險,我們看當 gamma比較大的時候,過擬合的風險卻比較大了。所以說最終我們看的還是高斯函數的開口大還是小,大一點,也就是gamma小,過擬合風險小,反之同理。

  完整代碼請參考我的GitHub(地址:https://github.com/LeBron-Jian/MachineLearningNote)。

完整代碼及其數據,請移步小編的GitHub

  傳送門:請點擊我

  如果點擊有誤:https://github.com/LeBron-Jian/MachineLearningNote

 

 

參考文獻:https://blog.csdn.net/BIT_666/article/details/79979580

https://www.cnblogs.com/tonglin0325/p/6107114.html

https://cloud.tencent.com/developer/article/1146077

https://www.cnblogs.com/xiaoyh/p/11604168.html

https://www.cnblogs.com/pinard/p/6126077.html

https://www.cnblogs.com/pinard/p/6117515.html

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

【其他文章推薦】

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

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

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

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

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

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

C++值元編程

——永遠不要在OJ上使用值元編程,過於簡單的沒有優勢,能有優勢的編譯錯誤。

背景

2019年10月,我在學習算法。有一道作業題,輸入規模很小,可以用打表法解決。具體方案有以下三種:

  1. 運行時預處理,生成所需的表格,根據輸入直接找到對應項,稍加處理后輸出;

  2. 一個程序生成表格,作為提交程序的一部分,後續與方法1相同,這樣就省去了運行時計算的步驟;

  3. 以上兩種方法結合,編譯期計算表格,運行時直接查詢,即元編程(metaprogramming)。

做題當然是用方法1或2,但是元編程已經埋下了種子。時隔大半年,我來補上這個坑。

題目

北京大學OpenJudge 百練4119 複雜的整數劃分問題

描述

將正整數 \(n\) 表示成一系列正整數之和,\(n = n_1 + n_2 + … + n_k\),其中 \(n_1 \geq n_2 \geq … \geq n_k \geq 1\)\(k \geq 1\)。正整數 \(n\) 的這種表示稱為正整數 \(n\) 的劃分。

輸入

標準的輸入包含若干組測試數據。每組測試數據是一行輸入數據,包括兩個整數 \(N\)\(K\)。( \(0 \le N \leq 50\)\(0 \le K \leq N\)

輸出

對於每組測試數據,輸出以下三行數據:

第一行: \(N\) 劃分成 \(K\) 個正整數之和的劃分數目

第二行: \(N\) 劃分成若干個不同正整數之和的劃分數目

第三行: \(N\) 劃分成若干個奇正整數之和的劃分數目

樣例輸入

5 2

樣例輸出

2
3
3

提示

第一行: 4+1,3+2

第二行: 5,4+1,3+2

第三行: 5,1+1+3,1+1+1+1+1+1

解答

標準的動態規劃題。用dp[c][i][j]表示把i分成c個正整數之和的方法數,其中每個數都不超過j

第一行。初始化:由 \(i \leq j\) 是否成立決定dp[1][i][j]的值,當 \(i \leq j\) 時為1,劃分為 \(i = i\),否則無法劃分,值為0

遞推:為了求dp[c][i][j],對 \(i = i_1 + i_2 + … + i_c\)\(i_1 \geq i_2 \geq … \geq i_c\) 中的最大數 \(i_1\) 分類討論,最小為 \(1\),最大不超過 \(i – 1\),因為 \(c \geq 2\),同時不超過 \(j\),因為定義。最大數為 \(n\) 時,對於把 \(i – n\) 分成 \(c – 1\) 個數,每個數不超過 \(n\) 的劃分,追加上 \(n\) 可得 \(i\) 的一個劃分。\(n\) 只有這些取值,沒有漏;對於不同的 \(n\),由於最大數不一樣,兩個劃分也不一樣,沒有多。故遞推式為:

\[dp[c][i][j] = \sum_{n=1}^{min\{i-1,j\}}dp[c-1][i-n][n] \]

dp[K][N][N]即為所求ans1[K][N]

第二行。可以把遞推式中的dp[c - 1][i - n][n]修改為dp[c - 1][i - n][n - 1]后重新計算。由於只需一個與c無關的結果,可以省去c這一維度,相應地改變遞推順序,每輪累加。

另一種方法是利用已經計算好的ans1數組。設 \(i = i_1 + i_2 + … + + i_{c-1} + i_c\),其中 \(i_1 \ge i_2 \ge … \ge i_{c+1} \ge i_c \ge 0\),則 \(i_1 – \left( c-1 \right) \geq i_2 – \left( c-2 \right) \geq … \geq i_{c-1} – 1 \geq i_c \ge 0\),且 \(\left( i_1 – \left( c-1 \right) \right) + \left( i_2 – \left( c-2 \right) \right) + … + \left( i_{c-1} – 1 \right) + \left( i_c \right) = i – \frac {c \left( c-1 \right)} {2}\),故把i劃分成c個不同正整數之和的劃分數目等於ans[c][i - c * (c - 1) / 2],遍歷c累加即得結果。

第三行。想法與第二行相似,也是找一個對應,此處從略。另外,數學上可以證明,第二行和第三行的結果一定是一樣的。

#include <iostream>
#include <algorithm>

constexpr int max = 50;
int dp[max + 1][max + 1][max + 1] = { 0 };
int ans1[max + 1][max + 1] = { 0 };
int ans2[max + 1] = { 0 };
int ans3[max + 1] = { 0 };

int main()
{
    int num, k;
    for (int i = 1; i <= max; ++i)
        for (int j = 1; j <= max; ++j)
            dp[1][i][j] = i <= j;
    for (int cnt = 2; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            for (int j = 1; j <= max; ++j)
            {
                auto min = std::min(i - 1, j);
                for (int n = 1; n <= min; ++n)
                    dp[cnt][i][j] += dp[cnt - 1][i - n][n];
            }
    for (int cnt = 1; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            ans1[cnt][i] = dp[cnt][i][i];
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i - cnt * (cnt - 1) / 2;
            if (j <= 0)
                break;
            ans2[i] += ans1[cnt][j];
        }
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i + cnt;
            if (j % 2)
                continue;
            j /= 2;
            ans3[i] += ans1[cnt][j];
        }
    
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans3[num] << std::endl;
    }
}

值元編程基礎

元編程是指計算機程序能把其他程序作為它們的數據的編程技術。在目前的C++中,元編程體現為用代碼生成代碼,包括宏與模板。當我們使用了std::vector<int>中的任何一個名字時,std::vector類模板就用模板參數int, std::allocator<int>實例化為std::vector<int, std::allocator<int>>模板類,這是一種元編程,不過我們通常不這麼講。

狹義的C++模板元編程(template metaprogramming,TMP)包括值元編程、類型元編程,以及兩者的相交。本文討論的是值元編程,即為編譯期值編程。

在C++中有兩套工具可用於值元編程:模板和constexpr。C++模板是圖靈完全的,這是模板被引入C++以後才被發現的,並不是C++模板的初衷,因此用模板做計算在C++中算不上一等用法,導致其語法比較冗長複雜。constexpr的初衷是提供純正的編譯期常量,後來才取消對計算的限制,但不能保證計算一定在編譯期完成。總之,這兩套工具都不完美,所以本文都會涉及。

嚴格來說,constexpr不符合上述對元編程的定義,但它確實可以提供運行時程序需要的數據,所以也歸入元編程的類別。

constexpr式值元編程

constexpr開始講,是因為它與我們在C++中慣用的編程範式——過程式範式是一致的。

constexpr關鍵字在C++11中被引入。當時,constexpr函數中只能包含一條求值語句,就是return語句,返回值可以用於初始化constexpr變量,作模板參數等用途。如果需要分支語句,用三目運算符?:;如果需要循環語句,用函數遞歸實現。比如,計算階乘:

constexpr int factorial(int n)
{
    return n <= 1 ? 1 : (n * factorial(n - 1));
}

對於編譯期常量ifactorial(i)產生編譯期常量;對於運行時值jfactorial(j)產生運行時值,也就是說,constexpr可以視為對既有函數的附加修飾。

然而,多數函數不止有一句return語句,constexpr對函數體的限制使它很難用於中等複雜的計算任務,為此C++14放寬了限制,允許定義局部變量,允許if-elseswitch-casewhilefor等控制流。factorial函數可以改寫為:

constexpr int factorial(int n)
{
    int result = 1;
    for (; n > 1; --n)
        result *= n;
    return result;
}

也許你會覺得factorial函數的遞歸版本比循環版本易懂,那是因為你學習遞歸時接觸的第一個例子就是它。對於C++開發者來說,大多數情況下首選的還是循環。

計算單個constexpr值用C++14就足夠了,但是傳遞數組需要C++17,因為std::arrayoperator[]從C++17開始才是constexpr的。

整數劃分問題的constexpr元編程實現需要C++17標準:

#include <iostream>
#include <utility>
#include <array>

constexpr int MAX = 50;

constexpr auto calculate_ans1()
{
    std::array<std::array<std::array<int, MAX + 1>, MAX + 1>, MAX + 1> dp{};
    std::array<std::array<int, MAX + 1>, MAX + 1> ans1{};
    constexpr int max = MAX;
    for (int i = 1; i <= max; ++i)
        for (int j = 1; j <= max; ++j)
            dp[1][i][j] = i <= j;
    for (int cnt = 2; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            for (int j = 1; j <= max; ++j)
            {
                auto min = std::min(i - 1, j);
                for (int n = 1; n <= min; ++n)
                    dp[cnt][i][j] += dp[cnt - 1][i - n][n];
            }
    for (int cnt = 1; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            ans1[cnt][i] = dp[cnt][i][i];
    return ans1;
}

constexpr auto calculate_ans2()
{
    constexpr auto ans1 = calculate_ans1();
    std::array<int, MAX + 1> ans2{};
    constexpr int max = MAX;
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i - cnt * (cnt - 1) / 2;
            if (j <= 0)
                break;
            ans2[i] += ans1[cnt][j];
        }
    return ans2;
}

int main()
{
    constexpr auto ans1 = calculate_ans1();
    constexpr auto ans2 = calculate_ans2();

    for (int cnt = 1; cnt <= 10; ++cnt)
    {
        for (int i = 1; i <= 10; ++i)
            std::cout << ans1[cnt][i] << ' ';+
        std::cout << std::endl;
    }
    std::cout << std::endl;
    for (int i = 1; i <= 50; ++i)
        std::cout << ans2[i] << ' ';
    std::cout << std::endl;

    int num, k;
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans2[num] << std::endl;
    }
}

模板式值元編程

模板式與C++11中的constexpr式類似,必須把循環化為遞歸。事實上C++模板是一門函數式編程語言,對值元編程和類型元編程都是如此。

程序控制流有三種基本結構:順序、分支與循環。

順序

在函數式編程中,數據都是不可變的,函數總是接受若干參數,返回若干結果,參數和結果是不同的變量;修改原來的變量是不允許的。對於C++模板這門語言,函數是類模板,也稱“元函數”(metafunction);參數是模板參數;運算結果是模板類中定義的靜態編譯期常量(在C++11以前,常用enum來定義;C++11開始用constexpr)。

比如,對於參數 \(x\),計算 \(x + 1\)\(x ^ 2\) 的元函數:

template<int X>
struct PlusOne
{
    static constexpr int value = X + 1;
};

template<int X>
struct Square
{
    static constexpr int value = X * X;
};

這裏假定運算數的類型為int。從C++17開始,可以用auto聲明非類型模板參數。

順序結構,是對數據依次進行多個操作,可以用函數嵌套來實現:

std::cout << PlusOne<1>::value << std::endl;
std::cout << Square<2>::value << std::endl;
std::cout << Square<PlusOne<3>::value>::value << std::endl;
std::cout << PlusOne<Square<4>::value>::value << std::endl;

或者藉助constexpr函數,回歸熟悉的過程式範式:

template<int X>
struct SquareAndIncrease
{
    static constexpr int calculate()
    {
        int x = X;
        x = x * x;
        x = x + 1;
        return x;
    }
    static constexpr int value = calculate();
};

void f()
{
    std::cout << SquareAndIncrease<5>::value << std::endl;
}

過程式方法同樣可以用於分支和循環結構,以下省略;函數式方法可以相似地用於值元編程與類型元編程,所以我更青睞(主要還是逼格更高)。

分支

C++模板元編程實現分支的方式是模板特化與模板參數匹配,用一個額外的帶默認值的bool類型模板參數作匹配規則,特化falsetrue的情形,另一種情形留給主模板。

比如,計算 \(x\) 的絕對值:

template<int X, bool Pos = (X > 0)>
struct AbsoluteHelper
{
    static constexpr int value = X;
};

template<int X>
struct AbsoluteHelper<X, false>
{
    static constexpr int value = -X;
};

如果你怕用戶瞎寫模板參數,可以再包裝一層:

template<int X>
struct Absolute : AbsoluteHelper<X> { };

void g()
{
    std::cout << Absolute<6>::value << std::endl;
    std::cout << Absolute<-7>::value << std::endl;
}

標準庫提供了std::conditional及其輔助類型std::conditional_t用於模板分支:

template<bool B, class T, class F>
struct conditional;

定義了成員類型type,當B == true時為T,否則為F

模板匹配實際上是在處理switch-case的分支,bool只是其中一種簡單情況。對於對應關係不太規則的分支語句,可以用一個constexpr函數把參數映射到一個整數或枚舉上:

enum class Port_t
{
    PortB, PortC, PortD, PortError,
};

constexpr Port_t portMap(int pin)
{
    Port_t result = Port_t::PortError;
    if (pin < 0)
        ;
    else if (pin < 8)
        result = Port_t::PortD;
    else if (pin < 14)
        result = Port_t::PortB;
    else if (pin < 20)
        result = Port_t::PortC;
    return result;
}

template<int Pin, Port_t Port = portMap(Pin)>
struct PinOperation;

template<int Pin>
struct PinOperation<Pin, Port_t::PortB> { /* ... */ };

template<int Pin>
struct PinOperation<Pin, Port_t::PortC> { /* ... */ };

template<int Pin>
struct PinOperation<Pin, Port_t::PortD> { /* ... */ };

如果同一個模板有兩個參數分別處理兩種分支(這已經從分支上升到模式匹配了),或同時處理分支和循環的特化,總之有兩個或以上維度的特化,需要注意兩個維度的特化是否會同時滿足,如果有這樣的情形但沒有提供兩參數都特化的模板特化,編譯會出錯。見problem2::Accumulator,它不需要提供兩個參數同時特化的版本。

循環

如前所述,循環要化為遞歸,循環的開始與結束是遞歸的起始與終點或兩者對調,遞歸終點的模板需要特化。比如,還是計算階乘:

template<int N>
struct Factorial
{
    static constexpr int value = N * Factorial<N - 1>::value;
};

template<>
struct Factorial<0>
{
    static constexpr int value = 1;
};

或許階乘的遞歸定義很大程度上來源於數學,那就再看一個平方和的例子:

template<int N>
struct SquareSum
{
    static constexpr int value = SquareSum<N - 1>::value + N * N;
};

template<>
struct SquareSum<0>
{
    static constexpr int value = 0;
};

\(1^2 + 2^2 + \cdots + n^2 = \frac {n \left( n + 1 \right) \left( 2n + 1\right)} {6}\)

好吧,還是挺數學的,去下面看實例感覺一下吧,那裡還有break——哦不,被我放到思考題中去了。

加群是交換群,求和順序不影響結果,上面這樣的順序寫起來方便。有些運算符不滿足交換律,需要逆轉順序。還以平方和為例:

template<int N, int Cur = 0>
struct SquareSumR
{
    static constexpr int value = Cur * Cur + SquareSumR<N, Cur + 1>::value;
};

template<int N>
struct SquareSumR<N, N>
{
    static constexpr int value = N * N;
};

遞歸

遞歸在過程式中是一種高級的結構,它可以直接轉化為函數式的遞歸,後面會提到兩者的異同。

比如,計算平方根,這個例子來源於C++ Templates: The Complete Guide 2e:

// primary template for main recursive step
template<int N, int LO = 1, int HI = N>
struct Sqrt {
    // compute the midpoint, rounded up
    static constexpr auto mid = (LO + HI + 1) / 2;
    // search a not too large value in a halved interval
    using SubT = std::conditional_t<(N < mid * mid),
                                   Sqrt<N, LO, mid - 1>,
                                   Sqrt<N, mid, HI>>;
    static constexpr auto value = SubT::value;
};
// partial specialization for end of recursion criterion
template<int N, int S>
struct Sqrt<N, S, S> {
    static constexpr auto value = S;
};

這個遞歸很容易化為循環,有助於你對循環化遞歸的理解。

存儲

實際應用中我們可能不需要把所有計算出來的值存儲起來,但在打表的題目中需要。存儲一系列數據需要用循環,循環的實現方式依然是遞歸。比如,存儲階乘(Factorial類模板見上):

template<int N>
inline void storeFactorial(int* dst)
{
    storeFactorial<N - 1>(dst);
    dst[N] = Factorial<N>::value;
}

template<>
inline void storeFactorial<-1>(int* dst)
{
    ;
}

void h()
{
    constexpr int MAX = 10;
    int factorial[MAX + 1];
    storeFactorial<MAX>(factorial);
    for (int i = 0; i <= MAX; ++i)
        std::cout << factorial[i] << ' ';
    std::cout << std::endl;
}

多維數組同理,例子見下方。注意,函數模板不能偏特化,但有靜態方法的類模板可以,這個靜態方法就充當原來的模板函數。

雖然我們是對數組中的元素挨個賦值的,但編譯器的生成代碼不會這麼做,即使不能優化成所有數據一起用memcpy,至少能做到一段一段拷貝。

類內定義的函數隱式成為inline,手動寫上inline沒有語法上的意義,但是對於一些編譯器,寫上以後函數被內聯的可能性更高,所以寫inline是一個好習慣。

解答

#include <iostream>
#include <algorithm>

constexpr int MAX = 50;

namespace problem1
{

template<int Count, int Num, int Max>
struct Partition;

template<int Count, int Num, int Loop>
struct Accumulator
{
    static constexpr int value = Accumulator<Count, Num, Loop - 1>::value + Partition<Count, Num - Loop, Loop>::value;
};

template<int Count, int Num>
struct Accumulator<Count, Num, 0>
{
    static constexpr int value = 0;
};

template<int Count, int Num, int Max = Num>
struct Partition
{
    static constexpr int value = Accumulator<Count - 1, Num, std::min(Num - 1, Max)>::value;
};

template<int Num, int Max>
struct Partition<1, Num, Max>
{
    static constexpr int value = Num <= Max;
};

template<int Count, int Num>
struct Store
{
    static inline void store(int* dst)
    {
        Store<Count, Num - 1>::store(dst);
        dst[Num] = Partition<Count, Num>::value;
    }
};

template<int Count>
struct Store<Count, 0>
{
    static inline void store(int* dst)
    {
        ;
    }
};

template<int Count>
inline void store(int (*dst)[MAX + 1])
{
    store<Count - 1>(dst);
    Store<Count, MAX>::store(dst[Count]);
}

template<>
inline void store<0>(int (*dst)[MAX + 1])
{
    ;
}

inline void store(int(*dst)[MAX + 1])
{
    store<MAX>(dst);
}

}

namespace problem2
{

template<int Num, int Count = Num, int Helper = Num - Count * (Count - 1) / 2, bool Valid = (Helper > 0)>
struct Accumulator
{
    static constexpr int value = Accumulator<Num, Count - 1>::value + problem1::Partition<Count, Helper>::value;
};

template<int Num, int Count, int Helper>
struct Accumulator<Num, Count, Helper, false>
{
    static constexpr int value = Accumulator<Num, Count - 1>::value;
};

template<int Num, int Helper, bool Valid>
struct Accumulator<Num, 0, Helper, Valid>
{
    static constexpr int value = 0;
};

template<int Num>
inline void store(int* dst)
{
    store<Num - 1>(dst);
    dst[Num] = Accumulator<Num>::value;
}

template<>
inline void store<0>(int* dst)
{
    ;
}

inline void store(int* dst)
{
    store<MAX>(dst);
}

}

int ans1[MAX + 1][MAX + 1];
int ans2[MAX + 1];

int main()
{
    problem1::store(ans1);
    problem2::store(ans2);
    int num, k;
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans2[num] << std::endl;
    }
}

請對照運行時版本自行理解。

討論

constexpr

constexpr不保證計算在編譯期完成,大部分編譯器在Debug模式下把所有可以推遲的constexpr計算都推遲到運行時完成。但constexpr可以作為一個強有力的優化提示,原本在最高優化等級都不會編譯期計算的代碼,在有了constexpr后編譯器會儘力幫你計算。如果編譯器實在做不到,根據你是否強制編譯期求值,編譯器會給出錯誤或推遲到運行時計算。在不同的編譯器中,這類行為的表現是不同的——眾所周知MSVC對constexpr的支持不好。

目前(C++17)沒有任何方法可以檢查一個表達式是否是編譯期求值的,但是有方法可以讓編譯器對於非編譯期求值表達式給出一個錯誤,把期望constexpr的表達式放入模板參數或static_assert表達式都是可行的:如果編譯期求值,則編譯通過;否則編譯錯誤。

(C++20:constevalis_constant_evaluated

模板

如果我們把Sqrt中的遞歸替換為如下語句:

static constexpr auto value = (N < mid * mid) ? Sqrt<N, LO, mid - 1>::value
                                              : Sqrt<N, mid, HI>::value;

顯然計算結果是相同的,看上去還更簡潔。但是問題在於,編譯器會把Sqrt<N, LO, mid - 1>Sqrt<N, mid, HI>兩個類都實例化出來,儘管只有一個模板類的value會被使用到。這些類模板實例繼續導致其他實例產生,最終將產生 \(O \left( n \log n \right)\) 個實例。相比之下,把兩個類型名字傳給std::conditional並不會導致類模板被實例化,std::conditional只是定義一個類型別名,對該類型求::value才會實例化它,一共產生 \(O \left( \log n \right)\) 個實例。

還有一個很常見的工具是變參模板,我沒有介紹是因為暫時沒有用到,而且我怕寫出非多項式複雜度的元程序。如果我還有機會寫一篇類型元編程的話,肯定會包含在其中的。

函數式

循環的一次迭代往往需要上一次迭代的結果,對應地在遞歸中就是函數對一個參數的結果依賴於對其他 \(n\) 個參數的結果。有些問題用遞歸解決比較直觀,但是如果 \(n \geq 2\),計算過程就會指數爆炸,比如:

int fibonacci(int n)
{
    if (n <= 2)
        return 1;
    else
        return fibonacci(n - 2) + fibonacci(n - 1);
}

計算fibonacci(30)已經需要一點點時間了,而計算fibonacci(46)(4字節帶符號整型能容納的最大斐波那契數)就很慢了。把這種遞歸轉化為循環,就是設計一個動態規劃算法的過程。然而函數式中的遞歸與過程式中的循環可能有相同的漸近複雜度:

template<int N>
struct Fibonacci
{
    static constexpr int value = Fibonacci<N - 2>::value + Fibonacci<N - 1>::value;
};

template<>
struct Fibonacci<1>
{
    static constexpr int value = 1;
};

template<>
struct Fibonacci<2>
{
    static constexpr int value = 1;
};

因為只有Fibonacci<1>Fibonacci<46>這46個類模板被實例化,是 \(O \left( n \right)\) 複雜度的。

在題目中,由於表中的所有數據都有可能用到,並且運行時不能執行計算,所以要把所有數據都計算出來。實際問題中可能只需要其中一個值,比如我現在就想知道不同整數的劃分問題對 \(50\) 的答案是多少,就寫:

std::cout << problem2::Accumulator<50>::value << std::endl;

那麼problem1::PartitionCount參數就不會超過10,不信的話你可以加一句static_assert。實例化的模板數量一共只有2000多個,而在完整的問題中這個數量要翻100倍不止。這種性質稱為惰性求值,即用到了才求值。惰性求值是必需的,總不能窮盡模板參數的所有可能組合一一實例化出來吧?

函數式編程語言可以在運行時實現這些特性。

性能

我愧對這個小標題,因為C++值元編程根本沒有性能,時間和空間都是。類型元編程也許是必需,至於值元編程,emm,做點簡單的計算就可以了,這整篇文章都是反面教材。

思考題2用GCC編譯,大概需要10分鐘;用MSVC編譯,出現我聞所未聞的錯誤:

因為編譯器是32位的,4GB內存用完了就爆了。

停機問題

一個很有趣的問題是編譯器對於死循環的行為。根據圖靈停機問題,編譯器無法判斷它要編譯的元程序是否包含死循環,那麼它在遇到死循環時會怎樣表現呢?當然不能跟着元程序一起死循環,constexpr的循環次數與模板的嵌套深度都是有限制的。在GCC中,可以用-fconstexpr-depth-fconstexpr-loop-limit-ftemplate-depth等命令行參數來控制。

思考題

  1. problem2::AccumulatorCount == 0Count == Num都要實例化,但其實只需實例化到 \(O \left( \sqrt{n} \right)\) 就可以了,試改寫之。

  2. 洛谷 NOIp2016提高組D2T1 組合數問題,用元編程實現。

    • 只需完成 \(n \leq 100, m \leq 100\) 的任務點;

    • 使用64位編譯器(指編譯器本身而非目標代碼),給編譯器億點點時間;

    • 不要去網站上提交,我已經試過了,編譯錯誤。

    • 測試數據下載。

題目描述

組合數 \(\binom {n} {m}\) 表示的是從 \(n\) 個物品中選出 \(m\) 個物品的方法數。舉個例子,從 \(\left( 1, 2, 3 \right)\) 三個物品中選擇兩個物品可以有 \(\left( 1, 2 \right), \left( 1, 3 \right), \left( 2, 3 \right)\) 這三種選擇方法。根據組合數的定義,我們可以給出計算組合數 \(\binom {n} {m}\) 的一般公式

\[\binom {n} {m} = \frac {n!} {m! \left( n-m \right) !} \,, \]

其中 \(n! = 1 \times 2 \times \cdots \times n\);特別地,定義 \(0! = 1\)

小蔥想知道如果給定 \(n\)\(m\)\(k\),對於所有的 \(0 \leq i \leq n, 0 \leq j \leq \min \left( i, m \right)\) 有多少對 \(\left( i, j \right)\) 滿足 \(k \mid \binom {i} {j}\)

輸入格式

第一行有個兩個整數 \(t, k\),其中 \(t\) 代表該測試點總共有多少組測試數據,\(k\) 的意義見問題描述。

接下來 \(t\) 行每行兩個整數 \(n, m\),其中 \(n, m\) 的意義見問題描述。

輸出格式

\(t\) 行,每行一個整數代表所有的 \(0 \leq i \leq n, 0 \leq j \leq \min \left( i, m \right)\) 有多少對 \(\left( i, j \right)\) 滿足 \(k \mid \binom {i} {j}\)

輸入輸出樣例

【輸入#1】

1 2
3 3

【輸出#1】

1

【輸入#2】

2 5
4 5
6 7

【輸出#2】

0 7

說明/提示

【樣例1說明】

在所有可能的情況中,只有 \(\binom {2} {1} = 2\) 一種情況是 \(2\) 的倍數。

【子任務】

測試點 \(n\) \(m\) \(k\) \(t\)
1 \(\leq 3\) $ \leq 3$ \(= 2\) $ = 1$
2 \(= 3\) \(\leq 10^4\)
3 \(\leq 7\) $ \leq 7$ \(= 4\) $ = 1$
4 \(= 5\) \(\leq 10^4\)
5 \(\leq 10\) $ \leq 10$ \(= 6\) $ = 1$
6 \(= 7\) \(\leq 10^4\)
7 \(\leq 20\) $ \leq 100$ \(= 8\) $ = 1$
8 \(= 9\) \(\leq 10^4\)
9 \(\leq 25\) $ \leq 2000$ \(=10\) $ = 1$
10 \(=11\) \(\leq 10^4\)
11 \(\leq 60\) $ \leq 20$ \(=12\) $ = 1$
12 \(=13\) \(\leq 10^4\)
13 \(\leq 100\) $ \leq 25$ \(=14\) $ = 1$
14 \(=15\) \(\leq 10^4\)
15 $ \leq 60$ \(=16\) $ = 1$
16 \(=17\) \(\leq 10^4\)
17 \(\leq 2000\) $ \leq 100$ \(=18\) $ = 1$
18 \(=19\) \(\leq 10^4\)
19 $ \leq 2000$ \(=20\) $ = 1$
20 \(=21\) \(\leq 10^4\)
  • 對於全部的測試點,保證 \(0 \leq n, m \leq 2 \times 10^3, 1 \leq t \leq 10^4\)

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

【其他文章推薦】

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

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

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

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

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

Spring AOP學習筆記03:AOP的核心實現之獲取增強器

  上文講了spring是如何開啟AOP的,簡單點說就是將AnnotationAwareAspectJAutoProxyCreator這個類註冊到容器中,因為這個類最終實現了BeanPostProcessor接口,並且在其postProcessAfterInitialization()方法中完成了AOP代理對象的創建,創建時機則是在bean的init方法被執行之後即bean初始化完成之後。postProcessAfterInitialization()方法是重點,本文及下一篇文章都是圍繞着這個方法來的。

  該方法是實現在其父類中的AbstractAutoProxyCreator,我們先來看一下其實現:

public Object postProcessAfterInitialization(Object bean, String beanName) throws BeansException {
    if (bean != null) {
            // 根據給定的bean的class和name構件key,格式:beanClassName_beanName
        Object cacheKey = getCacheKey(bean.getClass(), beanName);
        if (!this.earlyProxyReferences.containsKey(cacheKey)) {
                    // 如果它適合被代理,則在這裏面生成代理類
            return wrapIfNecessary(bean, beanName, cacheKey);
        }
    }
    return bean;
}

protected Object wrapIfNecessary(Object bean, String beanName, Object cacheKey) {
    // 如果已經處理過則不再處理
    if (beanName != null && this.targetSourcedBeans.containsKey(beanName)) {
        return bean;
    }
    // 無需增強則直接返回
    if (Boolean.FALSE.equals(this.advisedBeans.get(cacheKey))) {
        return bean;
    }
    // 指定的bean類是否代表一個基礎設施類,基礎設施類不應被代理,或者配置了指定bean也不需要自動代理
    if (isInfrastructureClass(bean.getClass()) || shouldSkip(bean.getClass(), beanName)) {
        this.advisedBeans.put(cacheKey, Boolean.FALSE);
        return bean;
    }

    // 如果存在Advice則創建代理
    Object[] specificInterceptors = getAdvicesAndAdvisorsForBean(bean.getClass(), beanName, null);
    // 如果獲取到了增強則需要針對增強創建代理
    if (specificInterceptors != DO_NOT_PROXY) {
        this.advisedBeans.put(cacheKey, Boolean.TRUE);
            // 創建代理
        Object proxy = createProxy(bean.getClass(), beanName, specificInterceptors, new SingletonTargetSource(bean));
        this.proxyTypes.put(cacheKey, proxy.getClass());
        return proxy;
    }

    this.advisedBeans.put(cacheKey, Boolean.FALSE);
    return bean;
}

  在上面的函數中我們已經可以看到代理創建的雛形,當然,在真正開始之前還需要經過一系列判斷,比如是否已經處理過或者是否是需要跳過的bean,而真正創建代理是從getAdvicesAndAdvisorsForBean開始的。
  創建代理主要包含了兩個步驟:

  • 獲取增強方法或者增強器;
  • 根據獲取的增強進行代理創建;

  這裏雖然看起來只有簡單的兩步,但是每一步中都有着大量複雜的邏輯。本文先來看看獲取增強方法的實現邏輯。

protected Object[] getAdvicesAndAdvisorsForBean(Class beanClass, String beanName, TargetSource targetSource) {
    List advisors = findEligibleAdvisors(beanClass, beanName);
    if (advisors.isEmpty()) {
        return DO_NOT_PROXY;
    }
    return advisors.toArray();
}

protected List<Advisor> findEligibleAdvisors(Class beanClass, String beanName) {
    List<Advisor> candidateAdvisors = findCandidateAdvisors();
    List<Advisor> eligibleAdvisors = findAdvisorsThatCanApply(candidateAdvisors, beanClass, beanName);
    extendAdvisors(eligibleAdvisors);
    if (!eligibleAdvisors.isEmpty()) {
        eligibleAdvisors = sortAdvisors(eligibleAdvisors);
    }
    return eligibleAdvisors;
}

  對於某個bean的增強方法的獲取也是包含兩個步驟的,獲取所有的增強以及尋找所有增強中適用於bean的增強並應用,而findCandidateAdvisors()與findAdvisorsThatCanApply()便是做了這兩件事情。這裏如果無法找到對應的增強器則直接返回DO_NOT_PROXY,也就是null。

1. 獲取增強器

  這裏我們分析的是註解方式的AOP,對於findCandidateAdvisors的實現其實是由AnnotationAwareAspectJAutoProxyCreator類來完成的,繼續跟蹤:

protected List<Advisor> findCandidateAdvisors() {
    // 使用註解方式配置AOP的時候並不會丟棄對XML配置的支持,在這裡會調用父類方法去加載配置文件中的AOP聲明
    List<Advisor> advisors = super.findCandidateAdvisors();
    // Build Advisors for all AspectJ aspects in the bean factory.
    advisors.addAll(this.aspectJAdvisorsBuilder.buildAspectJAdvisors());
    return advisors;
}

  AnnotationAwareAspectJAutoProxyCreator間接繼承了AbstractAdvisorAutoProxyCreator,在實現獲取增強的方法中除了保留父類的獲取配置文件中定義的增強外,同時增加了獲取Bean的註解增強的功能,這部分實現是由this.aspectJAdvisorsBuilder.buildAspectJAdvisors()來完成的。

  這裏其實可以自己先嘗試想象一下解析思路,看看自己的實現與Spring是否有差別?我們可以先在自己頭腦中嘗試實現一下獲取增強這個功能點,看看是否有思路。實際上,Spring在實現的時候主要分成了四步:

  • 獲取所有beanName,這一步驟中所有在beanFactory中註冊的Bean都會被提取出來;
  • 遍歷所有beanName,並找出聲明AspectJ註解的類,進行進一步的處理;
  • 對標記為AspectJ註解的類進行增強器的提取;
  • 將提取結果加入緩存;

  我們來看看Spring如何實現對所有的類進行分析並提取Advisor:

public List<Advisor> buildAspectJAdvisors() {
    List<String> aspectNames = null;

    synchronized (this) {
        aspectNames = this.aspectBeanNames;
        if (aspectNames == null) {
            List<Advisor> advisors = new LinkedList<Advisor>();
            aspectNames = new LinkedList<String>();
            // 獲取所有的beanName
            String[] beanNames =
                    BeanFactoryUtils.beanNamesForTypeIncludingAncestors(this.beanFactory, Object.class, true, false);
            // 遍歷所有的beanName找出對應的增強方法
            for (String beanName : beanNames) {
                // 不合法的bean則略過,由子類定義規則,默認返回true
                if (!isEligibleBean(beanName)) {
                    continue;
                }
                // 獲取對應的bean的類型
                Class beanType = this.beanFactory.getType(beanName);
                if (beanType == null) {
                    continue;
                }
                // 如果該bean上存在Aspect註解
                if (this.advisorFactory.isAspect(beanType)) {
                    aspectNames.add(beanName);
                    AspectMetadata amd = new AspectMetadata(beanType, beanName);
                    if (amd.getAjType().getPerClause().getKind() == PerClauseKind.SINGLETON) {
                        MetadataAwareAspectInstanceFactory factory =
                                new BeanFactoryAspectInstanceFactory(this.beanFactory, beanName);
                        // 解析增強方法
                        List<Advisor> classAdvisors = this.advisorFactory.getAdvisors(factory);
                        if (this.beanFactory.isSingleton(beanName)) {
                            this.advisorsCache.put(beanName, classAdvisors);
                        }
                        else {
                            this.aspectFactoryCache.put(beanName, factory);
                        }
                        advisors.addAll(classAdvisors);
                    }
                    else {
                        // Per target or per this.
                        if (this.beanFactory.isSingleton(beanName)) {
                            throw new IllegalArgumentException("Bean with name '" + beanName +
                                    "' is a singleton, but aspect instantiation model is not singleton");
                        }
                        MetadataAwareAspectInstanceFactory factory =
                                new PrototypeAspectInstanceFactory(this.beanFactory, beanName);
                        this.aspectFactoryCache.put(beanName, factory);
                        advisors.addAll(this.advisorFactory.getAdvisors(factory));
                    }
                }
            }
            this.aspectBeanNames = aspectNames;
            return advisors;
        }
    }

    if (aspectNames.isEmpty()) {
        return Collections.EMPTY_LIST;
    }
    // 記錄緩存
    List<Advisor> advisors = new LinkedList<Advisor>();
    for (String aspectName : aspectNames) {
        List<Advisor> cachedAdvisors = this.advisorsCache.get(aspectName);
        if (cachedAdvisors != null) {
            advisors.addAll(cachedAdvisors);
        }
        else {
            MetadataAwareAspectInstanceFactory factory = this.aspectFactoryCache.get(aspectName);
            advisors.addAll(this.advisorFactory.getAdvisors(factory));
        }
    }
    return advisors;
}

  到這裏已經完成了Advisor的提取,在上面步驟中最為重要也最為複雜的就是增強器的獲取,這一功能是委託給getAdvisors方法來實現(this.advisorFactory.getAdvisors(factory))。 

public List<Advisor> getAdvisors(MetadataAwareAspectInstanceFactory maaif) {
    // 獲取標記為AspectJ的類及其名字,並驗證
    final Class<?> aspectClass = maaif.getAspectMetadata().getAspectClass();
    final String aspectName = maaif.getAspectMetadata().getAspectName();
    validate(aspectClass);

    // We need to wrap the MetadataAwareAspectInstanceFactory with a decorator
    // so that it will only instantiate once.
    final MetadataAwareAspectInstanceFactory lazySingletonAspectInstanceFactory =
            new LazySingletonAspectInstanceFactoryDecorator(maaif);

    final List<Advisor> advisors = new LinkedList<Advisor>();
    for (Method method : getAdvisorMethods(aspectClass)) {
        // 獲取增強器
        Advisor advisor = getAdvisor(method, lazySingletonAspectInstanceFactory, advisors.size(), aspectName);
        if (advisor != null) {
            advisors.add(advisor);
        }
    }

    // If it's a per target aspect, emit the dummy instantiating aspect.
    if (!advisors.isEmpty() && lazySingletonAspectInstanceFactory.getAspectMetadata().isLazilyInstantiated()) {
        Advisor instantiationAdvisor = new SyntheticInstantiationAdvisor(lazySingletonAspectInstanceFactory);
        advisors.add(0, instantiationAdvisor);
    }

    // Find introduction fields.
    for (Field field : aspectClass.getDeclaredFields()) {
        Advisor advisor = getDeclareParentsAdvisor(field);
        if (advisor != null) {
            advisors.add(advisor);
        }
    }

    return advisors;
}

  上面函數中首先完成了對增強器的獲取,包括獲取註解以及根據註解生成增強的步驟,然後考慮到在配置中可能會將增強配置成延遲初始化,那麼需要在首位加入同步實例化增強器以保證增強使用之前的實例化,最後是對DeclareParents註解的獲取,這裏着重分析對增強器的獲取。
  對普通增強器的獲取邏輯是實現在getAdvisor方法中的,實現步驟包括對切點的註解的獲取以及根據註解信息生成增強。

public Advisor getAdvisor(Method candidateAdviceMethod, MetadataAwareAspectInstanceFactory aif,
        int declarationOrderInAspect, String aspectName) {

    validate(aif.getAspectMetadata().getAspectClass());
    // 切點信息的獲取
    AspectJExpressionPointcut ajexp =
            getPointcut(candidateAdviceMethod, aif.getAspectMetadata().getAspectClass());
    if (ajexp == null) {
        return null;
    }
    // 根據切點信息生成增強器
    return new InstantiationModelAwarePointcutAdvisorImpl(
            this, ajexp, aif, candidateAdviceMethod, declarationOrderInAspect, aspectName);
}

1.1 切點信息的獲取

  所謂獲取切點信息就是指定註解的表達式信息的獲取,如@Before(“test()”)。

private AspectJExpressionPointcut getPointcut(Method candidateAdviceMethod, Class<?> candidateAspectClass) {
    // 獲取方法上的註解
    AspectJAnnotation<?> aspectJAnnotation =
            AbstractAspectJAdvisorFactory.findAspectJAnnotationOnMethod(candidateAdviceMethod);
    if (aspectJAnnotation == null) {
        return null;
    }
    // 使用AspectJExpressionPointcut實例封裝獲取的信息
    AspectJExpressionPointcut ajexp =
            new AspectJExpressionPointcut(candidateAspectClass, new String[0], new Class[0]);
    // 提取得到的註解中的表達式,如:
    // @Pointcut("execution(* *.*test*(..))")中的execution(* *.*test*(..))")
    ajexp.setExpression(aspectJAnnotation.getPointcutExpression());
    return ajexp;
}

protected static AspectJAnnotation findAspectJAnnotationOnMethod(Method method) {
    // 設置敏感的註解類
    Class<? extends Annotation>[] classesToLookFor = new Class[] {
            Before.class, Around.class, After.class, AfterReturning.class, AfterThrowing.class, Pointcut.class};
    for (Class<? extends Annotation> c : classesToLookFor) {
        AspectJAnnotation foundAnnotation = findAnnotation(method, c);
        if (foundAnnotation != null) {
            return foundAnnotation;
        }
    }
    return null;
}

// 獲取指定方法上的註解並使用AspectJAnnotation封裝
private static <A extends Annotation> AspectJAnnotation<A> findAnnotation(Method method, Class<A> toLookFor) {
    A result = AnnotationUtils.findAnnotation(method, toLookFor);
    if (result != null) {
        return new AspectJAnnotation<A>(result);
    }
    else {
        return null;
    }
}

1.2 根據切點信息生成增強

  所有的增強都是由Advisor的實現類InstantiationModelAwarePointcutAdvisorImpl統一封裝的。

public InstantiationModelAwarePointcutAdvisorImpl(AspectJAdvisorFactory af, AspectJExpressionPointcut ajexp,
        MetadataAwareAspectInstanceFactory aif, Method method, int declarationOrderInAspect, String aspectName) {

    this.declaredPointcut = ajexp;
    this.method = method;
    this.atAspectJAdvisorFactory = af;
    this.aspectInstanceFactory = aif;
    this.declarationOrder = declarationOrderInAspect;
    this.aspectName = aspectName;

    if (aif.getAspectMetadata().isLazilyInstantiated()) {
        // Static part of the pointcut is a lazy type.
        Pointcut preInstantiationPointcut =
                Pointcuts.union(aif.getAspectMetadata().getPerClausePointcut(), this.declaredPointcut);

        // Make it dynamic: must mutate from pre-instantiation to post-instantiation state.
        // If it's not a dynamic pointcut, it may be optimized out
        // by the Spring AOP infrastructure after the first evaluation.
        this.pointcut = new PerTargetInstantiationModelPointcut(this.declaredPointcut, preInstantiationPointcut, aif);
        this.lazy = true;
    }
    else {
        // A singleton aspect.
        this.instantiatedAdvice = instantiateAdvice(this.declaredPointcut);
        this.pointcut = declaredPointcut;
        this.lazy = false;
    }
}

  在封裝過程中只是簡單地將信息封裝在類的實例中,所有的信息單純地賦值,在實例初始化的過程中還完成了對於增強器的初始化。因為不同的增強所體現的邏輯是不同的,比如@Before(“test()”)與@After(“test()”)標籤的區別就是增強器增強的位置不同,所以就需要不同的增強器來完成不同的邏輯,而根據註解中的信息初始化對應的增強器就是在instantiateAdvice函數中實現的。

private Advice instantiateAdvice(AspectJExpressionPointcut pcut) {
    return this.atAspectJAdvisorFactory.getAdvice(
            this.method, pcut, this.aspectInstanceFactory, this.declarationOrder, this.aspectName);
}

    public Advice getAdvice(Method candidateAdviceMethod, AspectJExpressionPointcut ajexp,
        MetadataAwareAspectInstanceFactory aif, int declarationOrderInAspect, String aspectName) {

    Class<?> candidateAspectClass = aif.getAspectMetadata().getAspectClass();
    validate(candidateAspectClass);

    AspectJAnnotation<?> aspectJAnnotation =
            AbstractAspectJAdvisorFactory.findAspectJAnnotationOnMethod(candidateAdviceMethod);
    if (aspectJAnnotation == null) {
        return null;
    }

    // If we get here, we know we have an AspectJ method.
    // Check that it's an AspectJ-annotated class
    if (!isAspect(candidateAspectClass)) {
        throw new AopConfigException("Advice must be declared inside an aspect type: " +
                "Offending method '" + candidateAdviceMethod + "' in class [" +
                candidateAspectClass.getName() + "]");
    }

    if (logger.isDebugEnabled()) {
        logger.debug("Found AspectJ method: " + candidateAdviceMethod);
    }

    AbstractAspectJAdvice springAdvice;
    // 根據不同的註解類型封裝不同的增強器
    switch (aspectJAnnotation.getAnnotationType()) {
        case AtBefore:
            springAdvice = new AspectJMethodBeforeAdvice(candidateAdviceMethod, ajexp, aif);
            break;
        case AtAfter:
            springAdvice = new AspectJAfterAdvice(candidateAdviceMethod, ajexp, aif);
            break;
        case AtAfterReturning:
            springAdvice = new AspectJAfterReturningAdvice(candidateAdviceMethod, ajexp, aif);
            AfterReturning afterReturningAnnotation = (AfterReturning) aspectJAnnotation.getAnnotation();
            if (StringUtils.hasText(afterReturningAnnotation.returning())) {
                springAdvice.setReturningName(afterReturningAnnotation.returning());
            }
            break;
        case AtAfterThrowing:
            springAdvice = new AspectJAfterThrowingAdvice(candidateAdviceMethod, ajexp, aif);
            AfterThrowing afterThrowingAnnotation = (AfterThrowing) aspectJAnnotation.getAnnotation();
            if (StringUtils.hasText(afterThrowingAnnotation.throwing())) {
                springAdvice.setThrowingName(afterThrowingAnnotation.throwing());
            }
            break;
        case AtAround:
            springAdvice = new AspectJAroundAdvice(candidateAdviceMethod, ajexp, aif);
            break;
        case AtPointcut:
            if (logger.isDebugEnabled()) {
                logger.debug("Processing pointcut '" + candidateAdviceMethod.getName() + "'");
            }
            return null;
        default:
            throw new UnsupportedOperationException(
                    "Unsupported advice type on method " + candidateAdviceMethod);
    }

    // Now to configure the advice...
    springAdvice.setAspectName(aspectName);
    springAdvice.setDeclarationOrder(declarationOrderInAspect);
    String[] argNames = this.parameterNameDiscoverer.getParameterNames(candidateAdviceMethod);
    if (argNames != null) {
        springAdvice.setArgumentNamesFromStringArray(argNames);
    }
    springAdvice.calculateArgumentBindings();
    return springAdvice;
}

  從上面可以看到,Spring會根據不同的註解生成不同的增強器,例如AtBefore會對應AspectJMethodBeforeAdvice,在AspectJMethodBeforeAdvice中完成了增強方法的邏輯。本文嘗試分析幾個常用的增強器實現。

AspectJMethodBeforeAdvice

  這是前置增強器,在Spring中,它會封裝到MethodBeforeAdviceInterceptor類的內部,這個是一個攔截器,會被放在攔截器鏈中,在創建代理bean時會用到:

public class MethodBeforeAdviceInterceptor implements MethodInterceptor, Serializable {

    private MethodBeforeAdvice advice;

    /**
     * Create a new MethodBeforeAdviceInterceptor for the given advice.
     * @param advice the MethodBeforeAdvice to wrap
     */
    public MethodBeforeAdviceInterceptor(MethodBeforeAdvice advice) {
        Assert.notNull(advice, "Advice must not be null");
        this.advice = advice;
    }

    public Object invoke(MethodInvocation mi) throws Throwable {
        this.advice.before(mi.getMethod(), mi.getArguments(), mi.getThis() );
        return mi.proceed();
    }
}

  其中的屬性MethodBeforeAdvicce就代表着前置增強的AspectJMethodBeforeAdvice,跟蹤其before()方法:

public void before(Method method, Object[] args, Object target) throws Throwable {
    invokeAdviceMethod(getJoinPointMatch(), null, null);
}

protected Object invokeAdviceMethod(JoinPointMatch jpMatch, Object returnValue, Throwable ex) throws Throwable {
    return invokeAdviceMethodWithGivenArgs(argBinding(getJoinPoint(), jpMatch, returnValue, ex));
}

protected Object invokeAdviceMethodWithGivenArgs(Object[] args) throws Throwable {
    Object[] actualArgs = args;
    if (this.aspectJAdviceMethod.getParameterTypes().length == 0) {
        actualArgs = null;
    }
    try {
        ReflectionUtils.makeAccessible(this.aspectJAdviceMethod);
        // 激活增強方法
        return this.aspectJAdviceMethod.invoke(this.aspectInstanceFactory.getAspectInstance(), actualArgs);
    }
    catch (IllegalArgumentException ex) {
        throw new AopInvocationException("Mismatch on arguments to advice method [" +
                this.aspectJAdviceMethod + "]; pointcut expression [" +
                this.pointcut.getPointcutExpression() + "]", ex);
    }
    catch (InvocationTargetException ex) {
        throw ex.getTargetException();
    }
}

   invokeAdviceMethodWithGivenArgs方法中的aspectJAdviceMethod正是對應於前置增強的方法,在這裏實現了調用。

AspectJAfterAdvice

  後置增強與前置增強有稍許不一致的地方。回顧上面講過的前置增強,大致的結構是在攔截器鏈中放置MethodBeforeAdviceInterceptor,並在MethodBeforeAdviceInterceptor中又放置了AspectJMethodBeforeAdvice,在調用inovke時首先串聯調用。但是在後置增強的時候卻是不一樣的,沒有提供如MethodBeforeAdviceInterceptor的中間類,而是直接實現MethodInterceptor接口,並在攔截器鏈中使用了中間的AspectAfterAdvice。

public class AspectJAfterAdvice extends AbstractAspectJAdvice implements MethodInterceptor, AfterAdvice {

    public AspectJAfterAdvice(Method aspectJBeforeAdviceMethod, AspectJExpressionPointcut pointcut, AspectInstanceFactory aif) {
        super(aspectJBeforeAdviceMethod, pointcut, aif);
    }

    public Object invoke(MethodInvocation mi) throws Throwable {
        try {
            return mi.proceed();
        }
        finally {
            // 激活增強方法
            invokeAdviceMethod(getJoinPointMatch(), null, null);
        }
    }
}

2. 尋找匹配的增強器

  前面已經把所有增強器的獲取分析完了,但是對於所有增強來說,並不一定都適用於當前的Bean,還要挑選出適合的增強器,也就是滿足我們配置的通配符的增強器。這部分的具體實現在findAdvisorsThatCanApply中。

protected List<Advisor> findAdvisorsThatCanApply(
        List<Advisor> candidateAdvisors, Class beanClass, String beanName) {

    ProxyCreationContext.setCurrentProxiedBeanName(beanName);
    try {
        // 過濾已經得到的advisors
        return AopUtils.findAdvisorsThatCanApply(candidateAdvisors, beanClass);
    }
    finally {
        ProxyCreationContext.setCurrentProxiedBeanName(null);
    }
}

public static List<Advisor> findAdvisorsThatCanApply(List<Advisor> candidateAdvisors, Class<?> clazz) {
    if (candidateAdvisors.isEmpty()) {
        return candidateAdvisors;
    }
    List<Advisor> eligibleAdvisors = new LinkedList<Advisor>();
    for (Advisor candidate : candidateAdvisors) {
        if (candidate instanceof IntroductionAdvisor && canApply(candidate, clazz)) {
            eligibleAdvisors.add(candidate);
        }
    }
    boolean hasIntroductions = !eligibleAdvisors.isEmpty();
    for (Advisor candidate : candidateAdvisors) {
        if (candidate instanceof IntroductionAdvisor) {
            // already processed
            continue;
        }
        if (canApply(candidate, clazz, hasIntroductions)) {
            eligibleAdvisors.add(candidate);
        }
    }
    return eligibleAdvisors;
}

  findAdvisorsThatCanApply函數的主要功能是尋找所有增強器中適用於當前class的增強器,而對於真正的匹配其實是在canApply中實現的。

public static boolean canApply(Advisor advisor, Class<?> targetClass, boolean hasIntroductions) {
    if (advisor instanceof IntroductionAdvisor) {
        return ((IntroductionAdvisor) advisor).getClassFilter().matches(targetClass);
    }
    else if (advisor instanceof PointcutAdvisor) {
        PointcutAdvisor pca = (PointcutAdvisor) advisor;
        return canApply(pca.getPointcut(), targetClass, hasIntroductions);
    }
    else {
        // It doesn't have a pointcut so we assume it applies.
        return true;
    }
}

public static boolean canApply(Pointcut pc, Class<?> targetClass, boolean hasIntroductions) {
    Assert.notNull(pc, "Pointcut must not be null");
    if (!pc.getClassFilter().matches(targetClass)) {
        return false;
    }

    MethodMatcher methodMatcher = pc.getMethodMatcher();
    IntroductionAwareMethodMatcher introductionAwareMethodMatcher = null;
    if (methodMatcher instanceof IntroductionAwareMethodMatcher) {
        introductionAwareMethodMatcher = (IntroductionAwareMethodMatcher) methodMatcher;
    }

    Set<Class> classes = new LinkedHashSet<Class>(ClassUtils.getAllInterfacesForClassAsSet(targetClass));
    classes.add(targetClass);
    for (Class<?> clazz : classes) {
        Method[] methods = clazz.getMethods();
        for (Method method : methods) {
            if ((introductionAwareMethodMatcher != null &&
                    introductionAwareMethodMatcher.matches(method, targetClass, hasIntroductions)) ||
                    methodMatcher.matches(method, targetClass)) {
                return true;
            }
        }
    }

    return false;
}

  這裏的邏輯也不是很複雜,無非就是根據advisor中封裝的classFilter來判斷是否match對應的類。

 3. 總結

  本文主要學習了Spring AOP核心實現原理中的對增強方法的獲取,主要包含兩個步驟:

  • 獲取所有增強;
  • 尋找所有增強中適用於bean的增強;

  下文會聚焦在AOP核心實現原理的另一部分–代理的創建。

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

【其他文章推薦】

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

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

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

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

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

C++ Primer Plus(一)

完整閱讀C++ Primer Plus 

  系統重新學習C++語言部分,記錄重要但易被忽略的,關鍵但易被遺忘的。

 

預備

  1、C++相對於C增加了最關鍵的兩項,面向對象和范型編程。

 

處理數據

  2、對於變量明,C++沒有長度限制;同時,以兩個下劃線或一個下劃線和大寫字母開頭的名稱被保留給實現(編譯器及其使用的資源)使用;以一個下劃線開頭的名稱被保留給實現,用作全局標識符。

  3、C++11提供一種大括號初始化器,可以用它初始化任何類型。

1 int ham = {24};
2 int ems{7};
3 int roc = {}; // 為0
4 int rhs{};

  4、對於整型字面值,如果第一位為1~9則為十進制;如果第一位為0,第二位為1~7,則是八進制;如果前兩位為0x或0X,則為十六進制。如果希望使用cout輸出八進制或十六進制格式的整數,可以使用cout的控制符(這三個控制符都被包含在std命名空間)。

1 cout << dec << a; // 10進制,默認的
2 cout << oct << b; // 8進制
3 cout << hex << c; // 16進制

  5、cout.put()、cin.get()的用法,可參照C語言中get()與put()的用法。

  6、C++有一種表示特殊字符的機制,他獨立於鍵盤,被稱作通用字符名。通用字符名以\u或\U開頭,前者後面是8個十六進制位,後者後面則是16個十六進制位。這些位表示的是ISO10646碼點。

  7、對於寬字符類型wcha_t,cin和cout無法很好的處理,此時應該使用wcinwcout

  8、C++11新增了char16_t和char32_t類型,C++11使用前綴u表示前者,U表示後者;並與形式為\u00F6和\U0000222B的通用字符名匹配。

1 u'C' u“be good”   U'R' U”dirty rat”

  

複合類型

  9、cin使用空白(空格、製表符、換行符)來確定字符串結束的位置,而cin.getline()可以依據換行符來讀取整行,並且可以制定最多讀取字符的數量。

  10、可以使用沒有名稱的結構類型,方法是省略名稱,同時定義一個結構類型和一個這種類型的變量,不常用,可用作臨時變量。

  11、C++允許對一個整數強制類型轉換為一個枚舉值,並參与賦值操作;同時可以有多個值相同的枚舉值,目前枚舉值也可以使用long,long long類型的值。對於較小的值編譯器會使用一個字節甚至更少的的字節,對於包含long類型的枚舉,會使用4個字節。

  12、在C中允許給指針直接賦字面值,但C++不允許,必須進行類型轉換。

 

循環和關係表達式

  13、前綴遞增,前綴遞減,解除引用運算符的優先級相同,以從右往左的方式進行結合;後綴遞增,後綴遞減的優先級相同,但比前綴運算符的優先級高,以從左往右的方式結合。

  14、 cin.get(ch)和cin.get()的區別。

屬性 cin.get(ch) cin.get()
傳遞輸入字符的方式 賦值給參數ch 將函數返回值賦給ch
用於字符輸入時函數的返回值  istream對象(執行bool轉換後為true)  int類型的字符編碼
到達EOF時函數的返回值   istream對象(執行bool轉換後為false) EOF 

 

函數——C++編程模塊

  15、如果數據類型本身並不是指針,則可以將const數據或者非const數據的地址賦給指向const的指針,但只能將非const數據的地址賦給非const指針

 

函數探幽

  16、函數重載后,在調用函數時,如果沒有完全相同的參數類型,編譯器會做強制類型轉換進行匹配,但如果有多個可轉換的類型(也就是說有多個重載過的函數),C++將拒絕這種函數調用。

  17、函數重載的關鍵是函數的參數列表,也成為特徵標,以下兩個聲明互斥:

1 long gronk(int n, float m);
2 double gronk(int n, float m);

  C++不允許這種方式的重載,返回類型可以不同,但特徵標必須也不同。

  18、對於重載了引用參數的函數,C++將選擇調用最匹配的版本,這使得能夠根據參數是左值引用,const類型的左值引用還是右值引用來定製函數的行為。

  19、 函數模板並非函數定義,在使用模板時,編譯器會針對特定的類型生成函數實例,這種實例化方式被稱為隱式實例化

  20、C++允許顯式實例化,也就是說可以針對特定類型使用模板生成特定的實例。

1 template void Swap<int>(int, int); // 用<>指定類型,在聲明前加template

  它的語義為“使用Swap()模板生成int類型的函數定義”。

  與顯式實例化不同的是,顯式具體化使用下面兩個等價的聲明之一:

1 template<> void Swap<int>(int, int);
2 template<> void Swap(int, int);

  它們的語義是,“不要使用Swap模板來生產函數定義,而應使用專門為int類型显示地定義的函數定義”。

  21、還可以在程序中創建顯式實例化:

1 template <class T>
2 T Add(T a, T b){ return a + b; }
3 int m = 6;
4 double n = 9.8;
5 cout << Add<double>(m, n) << endl;

  由於這裏显示實例化中的特定類型為double,所以變量m會被強制類型轉換成double類型。

  22、對於函數重載函數模板函數模板重載,C++將選擇哪個版本?

  請看這裏———>   C++ 函數重載,函數模板和函數模板重載,選擇哪一個?

  23、C++11,在函數模板中,當無法得知一個變量的值時,可以使用decltype關鍵字來決定返回值類型:

1 template<class T1, class T2>
2 void ft(T1 x, T2 y)
3 {
4     decltype(x+y) xpy = x + y; // 此時xpy的類型就是x+y后的類型
5 }

  24、decltype關鍵字本質上更複雜一些,編譯器必須遍歷一個核對錶去確定類型,現在有如下聲明:

1 decltype(expression) var;

  第一,expression是一個沒有用括號括起來的標識符,則var的類型與該標識符相同,包括const等限定符。

  第二,如果expression是一個函數調用,則於與函數的返回值相同,這裏並不執行函數,只是查看返回值類型。

  第三,如果expression是一個左值,並且expression是被括號括起的,var會是引用類型,否則第一步就會處理。

  第四,到了這裏,var的類型只能與expression相同。

  25、C++11,在函數模板中,當無法得知返回值類型時,一般不可以直接使用關鍵字decltype來得到返回值類型,因為此時往往decltype後面表達式中的變量還不在作用域內,此時,需要使用後置返回類型

1 template<class T1, class T2>
2 auto gt(T1 x, T2 y) -> decltype(x+y) // 此時x,y已在作用域內
3 {
4     return x + y;
5 }

  auto表示是一個佔位符,表示後置返回類型提供的類型。

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

【其他文章推薦】

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

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

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

※超省錢租車方案

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

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

一篇文章搞懂filebeat(ELK)

本文使用的filebeat是7.7.0的版本
本文從如下幾個方面說明:

  • filebeat是什麼,可以用來幹嘛
  • filebeat的原理是怎樣的,怎麼構成的
  • filebeat應該怎麼玩

一、filebeat是什麼

1.1、filebeat和beats的關係

  首先filebeat是Beats中的一員。
  Beats在是一個輕量級日誌採集器,其實Beats家族有6個成員,早期的ELK架構中使用Logstash收集、解析日誌,但是Logstash對內存、cpu、io等資源消耗比較高。相比Logstash,Beats所佔系統的CPU和內存幾乎可以忽略不計。
目前Beats包含六種工具:

  • Packetbeat:網絡數據(收集網絡流量數據)
  • Metricbeat:指標(收集系統、進程和文件系統級別的CPU和內存使用情況等數據)
  • Filebeat:日誌文件(收集文件數據)
  • Winlogbeat:windows事件日誌(收集Windows事件日誌數據)
  • Auditbeat:審計數據(收集審計日誌)
  • Heartbeat:運行時間監控(收集系統運行時的數據)

1.2、filebeat是什麼

  Filebeat是用於轉發和集中日誌數據的輕量級傳送工具。Filebeat監視您指定的日誌文件或位置,收集日誌事件,並將它們轉發到Elasticsearch或 Logstash進行索引。

  Filebeat的工作方式如下:啟動Filebeat時,它將啟動一個或多個輸入,這些輸入將在為日誌數據指定的位置中查找。對於Filebeat所找到的每個日誌,Filebeat都會啟動收集器。每個收集器都讀取單個日誌以獲取新內容,並將新日誌數據發送到libbeat,libbeat將聚集事件,並將聚集的數據發送到為Filebeat配置的輸出。

       工作的流程圖如下:

 

1.3、filebeat和logstash的關係

  因為logstash是jvm跑的,資源消耗比較大,所以後來作者又用golang寫了一個功能較少但是資源消耗也小的輕量級的logstash-forwarder。不過作者只是一個人,加入http://elastic.co公司以後,因為es公司本身還收購了另一個開源項目packetbeat,而這個項目專門就是用golang的,有整個團隊,所以es公司乾脆把logstash-forwarder的開發工作也合併到同一個golang團隊來搞,於是新的項目就叫filebeat了。

 

二、filebeat原理是什麼

2.1、filebeat的構成

  filebeat結構:由兩個組件構成,分別是inputs(輸入)和harvesters(收集器),這些組件一起工作來跟蹤文件並將事件數據發送到您指定的輸出,harvester負責讀取單個文件的內容。harvester逐行讀取每個文件,並將內容發送到輸出。為每個文件啟動一個harvester。harvester負責打開和關閉文件,這意味着文件描述符在harvester運行時保持打開狀態。如果在收集文件時刪除或重命名文件,Filebeat將繼續讀取該文件。這樣做的副作用是,磁盤上的空間一直保留到harvester關閉。默認情況下,Filebeat保持文件打開,直到達到close_inactive

關閉harvester可以會產生的結果:

  • 文件處理程序關閉,如果harvester仍在讀取文件時被刪除,則釋放底層資源。
  • 只有在scan_frequency結束之後,才會再次啟動文件的收集。
  • 如果該文件在harvester關閉時被移動或刪除,該文件的收集將不會繼續

  一個input負責管理harvesters和尋找所有來源讀取。如果input類型是log,則input將查找驅動器上與定義的路徑匹配的所有文件,併為每個文件啟動一個harvester。每個input在它自己的Go進程中運行,Filebeat當前支持多種輸入類型。每個輸入類型可以定義多次。日誌輸入檢查每個文件,以查看是否需要啟動harvester、是否已經在運行harvester或是否可以忽略該文件

2.2、filebeat如何保存文件的狀態

  Filebeat保留每個文件的狀態,並經常將狀態刷新到磁盤中的註冊表文件中。該狀態用於記住harvester讀取的最後一個偏移量,並確保發送所有日誌行。如果無法訪問輸出(如Elasticsearch或Logstash),Filebeat將跟蹤最後發送的行,並在輸出再次可用時繼續讀取文件。當Filebeat運行時,每個輸入的狀態信息也保存在內存中。當Filebeat重新啟動時,來自註冊表文件的數據用於重建狀態,Filebeat在最後一個已知位置繼續每個harvester。對於每個輸入,Filebeat都會保留它找到的每個文件的狀態。由於文件可以重命名或移動,文件名和路徑不足以標識文件。對於每個文件,Filebeat存儲唯一的標識符,以檢測文件是否以前被捕獲。

2.3、filebeat何如保證至少一次數據消費

  Filebeat保證事件將至少傳遞到配置的輸出一次,並且不會丟失數據。是因為它將每個事件的傳遞狀態存儲在註冊表文件中。在已定義的輸出被阻止且未確認所有事件的情況下,Filebeat將繼續嘗試發送事件,直到輸出確認已接收到事件為止。如果Filebeat在發送事件的過程中關閉,它不會等待輸出確認所有事件后再關閉。當Filebeat重新啟動時,將再次將Filebeat關閉前未確認的所有事件發送到輸出。這樣可以確保每個事件至少發送一次,但最終可能會有重複的事件發送到輸出。通過設置shutdown_timeout選項,可以將Filebeat配置為在關機前等待特定時間

三、filebeat怎麼玩

3.1、壓縮包方式安裝

本文採用壓縮包的方式安裝,linux版本,filebeat-7.7.0-linux-x86_64.tar.gz

curl-L-Ohttps://artifacts.elastic.co/downloads/beats/filebeat/filebeat-7.7.0-linux-x86_64.tar.gz
tar -xzvf filebeat-7.7.0-linux-x86_64.tar.gz

配置示例文件:filebeat.reference.yml(包含所有未過時的配置項)
配置文件:filebeat.yml

3.2、基本命令

詳情見官網:https://www.elastic.co/guide/en/beats/filebeat/current/command-line-options.html

export   #導出
run      #執行(默認執行)
test     #測試配置
keystore #秘鑰存儲
modules  #模塊配置管理
setup    #設置初始環境

例如:./filebeat test config  #用來測試配置文件是否正確

3.3、輸入輸出

支持的輸入組件:

Multilinemessages,Azureeventhub,CloudFoundry,Container,Docker,GooglePub/Sub,HTTPJSON,Kafka,Log,MQTT,NetFlow,Office365ManagementActivityAPI,Redis,s3,Stdin,Syslog,TCP,UDP(最常用的額就是log)

支持的輸出組件:

Elasticsearch,Logstash,Kafka,Redis,File,Console,ElasticCloud,Changetheoutputcodec(最常用的就是Elasticsearch,Logstash)

3.4、keystore的使用

keystore主要是防止敏感信息被泄露,比如密碼等,像ES的密碼,這裏可以生成一個key為ES_PWD,值為es的password的一個對應關係,在使用es的密碼的時候就可以使用${ES_PWD}使用

創建一個存儲密碼的keystore:filebeat keystore create
然後往其中添加鍵值對,例如:filebeatk eystore add ES_PWD
使用覆蓋原來鍵的值:filebeat key store add ES_PWD–force
刪除鍵值對:filebeat key store remove ES_PWD
查看已有的鍵值對:filebeat key store list

例如:後期就可以通過${ES_PWD}使用其值,例如:

output.elasticsearch.password:”${ES_PWD}”

3.5、filebeat.yml配置(log輸入類型為例)

詳情見官網:https://www.elastic.co/guide/en/beats/filebeat/current/filebeat-input-log.html

type: log #input類型為log
enable: true #表示是該log類型配置生效
paths:     #指定要監控的日誌,目前按照Go語言的glob函數處理。沒有對配置目錄做遞歸處理,比如配置的如果是:
- /var/log/* /*.log  #則只會去/var/log目錄的所有子目錄中尋找以".log"結尾的文件,而不會尋找/var/log目錄下以".log"結尾的文件。
recursive_glob.enabled: #啟用全局遞歸模式,例如/foo/**包括/foo, /foo/*, /foo/*/* encoding:#指定被監控的文件的編碼類型,使用plain和utf-8都是可以處理中文日誌的
exclude_lines: ['^DBG'] #不包含匹配正則的行
include_lines: ['^ERR', '^WARN']  #包含匹配正則的行
harvester_buffer_size: 16384 #每個harvester在獲取文件時使用的緩衝區的字節大小
max_bytes: 10485760 #單個日誌消息可以擁有的最大字節數。max_bytes之後的所有字節都被丟棄而不發送。默認值為10MB (10485760)
exclude_files: ['\.gz$']  #用於匹配希望Filebeat忽略的文件的正則表達式列表
ingore_older: 0 #默認為0,表示禁用,可以配置2h,2m等,注意ignore_older必須大於close_inactive的值.表示忽略超過設置值未更新的
文件或者文件從來沒有被harvester收集
close_* #close_ *配置選項用於在特定標準或時間之後關閉harvester。 關閉harvester意味着關閉文件處理程序。 如果在harvester關閉
後文件被更新,則在scan_frequency過後,文件將被重新拾取。 但是,如果在harvester關閉時移動或刪除文件,Filebeat將無法再次接收文件
,並且harvester未讀取的任何數據都將丟失。
close_inactive  #啟動選項時,如果在制定時間沒有被讀取,將關閉文件句柄
讀取的最後一條日誌定義為下一次讀取的起始點,而不是基於文件的修改時間
如果關閉的文件發生變化,一個新的harverster將在scan_frequency運行后被啟動
建議至少設置一個大於讀取日誌頻率的值,配置多個prospector來實現針對不同更新速度的日誌文件
使用內部時間戳機制,來反映記錄日誌的讀取,每次讀取到最後一行日誌時開始倒計時使用2h 5m 來表示
close_rename #當選項啟動,如果文件被重命名和移動,filebeat關閉文件的處理讀取
close_removed #當選項啟動,文件被刪除時,filebeat關閉文件的處理讀取這個選項啟動后,必須啟動clean_removed
close_eof #適合只寫一次日誌的文件,然後filebeat關閉文件的處理讀取
close_timeout #當選項啟動時,filebeat會給每個harvester設置預定義時間,不管這個文件是否被讀取,達到設定時間后,將被關閉
close_timeout 不能等於ignore_older,會導致文件更新時,不會被讀取如果output一直沒有輸出日誌事件,這個timeout是不會被啟動的,
至少要要有一個事件發送,然後haverter將被關閉
設置0 表示不啟動
clean_inactived #從註冊表文件中刪除先前收穫的文件的狀態
設置必須大於ignore_older+scan_frequency,以確保在文件仍在收集時沒有刪除任何狀態
配置選項有助於減小註冊表文件的大小,特別是如果每天都生成大量的新文件
此配置選項也可用於防止在Linux上重用inode的Filebeat問題
clean_removed #啟動選項后,如果文件在磁盤上找不到,將從註冊表中清除filebeat
如果關閉close removed 必須關閉clean removed
scan_frequency #prospector檢查指定用於收穫的路徑中的新文件的頻率,默認10s
tail_files:#如果設置為true,Filebeat從文件尾開始監控文件新增內容,把新增的每一行文件作為一個事件依次發送,
而不是從文件開始處重新發送所有內容。
symlinks:#符號鏈接選項允許Filebeat除常規文件外,可以收集符號鏈接。收集符號鏈接時,即使報告了符號鏈接的路徑,
Filebeat也會打開並讀取原始文件。
backoff: #backoff選項指定Filebeat如何积極地抓取新文件進行更新。默認1s,backoff選項定義Filebeat在達到EOF之後
再次檢查文件之間等待的時間。
max_backoff: #在達到EOF之後再次檢查文件之前Filebeat等待的最長時間
backoff_factor: #指定backoff嘗試等待時間幾次,默認是2
harvester_limit:#harvester_limit選項限制一個prospector并行啟動的harvester數量,直接影響文件打開數

tags #列表中添加標籤,用過過濾,例如:tags: ["json"]
fields #可選字段,選擇額外的字段進行輸出可以是標量值,元組,字典等嵌套類型
默認在sub-dictionary位置
filebeat.inputs:
fields:
app_id: query_engine_12
fields_under_root #如果值為ture,那麼fields存儲在輸出文檔的頂級位置

multiline.pattern #必須匹配的regexp模式
multiline.negate #定義上面的模式匹配條件的動作是 否定的,默認是false
假如模式匹配條件'^b',默認是false模式,表示講按照模式匹配進行匹配 將不是以b開頭的日誌行進行合併
如果是true,表示將不以b開頭的日誌行進行合併
multiline.match # 指定Filebeat如何將匹配行組合成事件,在之前或者之後,取決於上面所指定的negate
multiline.max_lines #可以組合成一個事件的最大行數,超過將丟棄,默認500
multiline.timeout #定義超時時間,如果開始一個新的事件在超時時間內沒有發現匹配,也將發送日誌,默認是5s
max_procs #設置可以同時執行的最大CPU數。默認值為系統中可用的邏輯CPU的數量。
name #為該filebeat指定名字,默認為主機的hostname
 

3.6、實例一:logstash作為輸出

filebeat.yml配置

#=========================== Filebeat inputs =============================

filebeat.inputs:

# Each - is an input. Most options can be set at the input level, so
# you can use different inputs for various configurations.
# Below are the input specific configurations.

- type: log

  # Change to true to enable this input configuration.
  enabled: true

  # Paths that should be crawled and fetched. Glob based paths.
  paths:  #配置多個日誌路徑
    - /var/logs/es_aaa_index_search_slowlog.log
    - /var/logs/es_bbb_index_search_slowlog.log
    - /var/logs/es_ccc_index_search_slowlog.log
    - /var/logs/es_ddd_index_search_slowlog.log
    #- c:\programdata\elasticsearch\logs\*

  # Exclude lines. A list of regular expressions to match. It drops the lines that are
  # matching any regular expression from the list.
  #exclude_lines: ['^DBG']

  # Include lines. A list of regular expressions to match. It exports the lines that are
  # matching any regular expression from the list.
  #include_lines: ['^ERR', '^WARN']

  # Exclude files. A list of regular expressions to match. Filebeat drops the files that
  # are matching any regular expression from the list. By default, no files are dropped.
  #exclude_files: ['.gz$']

  # Optional additional fields. These fields can be freely picked
  # to add additional information to the crawled log files for filtering
  #fields:
  #  level: debug
  #  review: 1

  ### Multiline options

  # Multiline can be used for log messages spanning multiple lines. This is common
  # for Java Stack Traces or C-Line Continuation

  # The regexp Pattern that has to be matched. The example pattern matches all lines starting with [
  #multiline.pattern: ^\[

  # Defines if the pattern set under pattern should be negated or not. Default is false.
  #multiline.negate: false

  # Match can be set to "after" or "before". It is used to define if lines should be append to a pattern
  # that was (not) matched before or after or as long as a pattern is not matched based on negate.
  # Note: After is the equivalent to previous and before is the equivalent to to next in Logstash
  #multiline.match: after


#================================ Outputs =====================================

#----------------------------- Logstash output --------------------------------
output.logstash:
  # The Logstash hosts #配多個logstash使用負載均衡機制
  hosts: ["192.168.110.130:5044","192.168.110.131:5044","192.168.110.132:5044","192.168.110.133:5044"]  
  loadbalance: true  #使用了負載均衡

  # Optional SSL. By default is off.
  # List of root certificates for HTTPS server verifications
  #ssl.certificate_authorities: ["/etc/pki/root/ca.pem"]

  # Certificate for SSL client authentication
  #ssl.certificate: "/etc/pki/client/cert.pem"

  # Client Certificate Key
  #ssl.key: "/etc/pki/client/cert.key"

./filebeat -e   #啟動filebeat

logstash的配置

input {
  beats {
    port => 5044   
  }
}

output {
  elasticsearch {
    hosts => ["http://192.168.110.130:9200"] #這裏可以配置多個
    index => "query-%{yyyyMMdd}" 
  }
}

 

3.7、實例二:elasticsearch作為輸出

filebeat.yml的配置:

###################### Filebeat Configuration Example #########################

# This file is an example configuration file highlighting only the most common
# options. The filebeat.reference.yml file from the same directory contains all the
# supported options with more comments. You can use it as a reference.
#
# You can find the full configuration reference here:
# https://www.elastic.co/guide/en/beats/filebeat/index.html

# For more available modules and options, please see the filebeat.reference.yml sample
# configuration file.

#=========================== Filebeat inputs =============================

filebeat.inputs:

# Each - is an input. Most options can be set at the input level, so
# you can use different inputs for various configurations.
# Below are the input specific configurations.

- type: log

  # Change to true to enable this input configuration.
  enabled: true

  # Paths that should be crawled and fetched. Glob based paths.
  paths:
    - /var/logs/es_aaa_index_search_slowlog.log
    - /var/logs/es_bbb_index_search_slowlog.log
    - /var/logs/es_ccc_index_search_slowlog.log
    - /var/logs/es_dddd_index_search_slowlog.log
    #- c:\programdata\elasticsearch\logs\*

  # Exclude lines. A list of regular expressions to match. It drops the lines that are
  # matching any regular expression from the list.
  #exclude_lines: ['^DBG']

  # Include lines. A list of regular expressions to match. It exports the lines that are
  # matching any regular expression from the list.
  #include_lines: ['^ERR', '^WARN']

  # Exclude files. A list of regular expressions to match. Filebeat drops the files that
  # are matching any regular expression from the list. By default, no files are dropped.
  #exclude_files: ['.gz$']

  # Optional additional fields. These fields can be freely picked
  # to add additional information to the crawled log files for filtering
  #fields:
  #  level: debug
  #  review: 1

  ### Multiline options

  # Multiline can be used for log messages spanning multiple lines. This is common
  # for Java Stack Traces or C-Line Continuation

  # The regexp Pattern that has to be matched. The example pattern matches all lines starting with [
  #multiline.pattern: ^\[

  # Defines if the pattern set under pattern should be negated or not. Default is false.
  #multiline.negate: false

  # Match can be set to "after" or "before". It is used to define if lines should be append to a pattern
  # that was (not) matched before or after or as long as a pattern is not matched based on negate.
  # Note: After is the equivalent to previous and before is the equivalent to to next in Logstash
  #multiline.match: after


#============================= Filebeat modules ===============================

filebeat.config.modules:
  # Glob pattern for configuration loading
  path: ${path.config}/modules.d/*.yml

  # Set to true to enable config reloading
  reload.enabled: false

  # Period on which files under path should be checked for changes
  #reload.period: 10s

#==================== Elasticsearch template setting ==========================


#================================ General =====================================

# The name of the shipper that publishes the network data. It can be used to group
# all the transactions sent by a single shipper in the web interface.
name: filebeat222

# The tags of the shipper are included in their own field with each
# transaction published.
#tags: ["service-X", "web-tier"]

# Optional fields that you can specify to add additional information to the
# output.
#fields:
#  env: staging

#cloud.auth:

#================================ Outputs =====================================


#-------------------------- Elasticsearch output ------------------------------
output.elasticsearch:
  # Array of hosts to connect to.
  hosts: ["192.168.110.130:9200","92.168.110.131:9200"]

  # Protocol - either `http` (default) or `https`.
  #protocol: "https"

  # Authentication credentials - either API key or username/password.
  #api_key: "id:api_key"
  username: "elastic"
  password: "${ES_PWD}"   #通過keystore設置密碼

./filebeat -e   #啟動filebeat

查看elasticsearch集群,有一個默認的索引名字filebeat-%{[beat.version]}-%{+yyyy.MM.dd}

 

 

 

3.8、filebeat模塊

官網:https://www.elastic.co/guide/en/beats/filebeat/current/filebeat-modules.html

這裏我使用elasticsearch模式來解析es的慢日誌查詢,操作步驟如下,其他的模塊操作也一樣:

前提: 安裝好Elasticsearch和kibana兩個軟件,然後使用filebeat

具體的操作官網有:https://www.elastic.co/guide/en/beats/filebeat/current/filebeat-modules-quickstart.html

第一步,配置filebeat.yml文件

#============================== Kibana =====================================

# Starting with Beats version 6.0.0, the dashboards are loaded via the Kibana API.
# This requires a Kibana endpoint configuration.
setup.kibana:

  # Kibana Host
  # Scheme and port can be left out and will be set to the default (http and 5601)
  # In case you specify and additional path, the scheme is required: http://localhost:5601/path
  # IPv6 addresses should always be defined as: https://[2001:db8::1]:5601
  host: "192.168.110.130:5601"  #指定kibana
  username: "elastic"   #用戶
  password: "${ES_PWD}"  #密碼,這裏使用了keystore,防止明文密碼

  # Kibana Space ID
  # ID of the Kibana Space into which the dashboards should be loaded. By default,
  # the Default Space will be used.
  #space.id:

#================================ Outputs =====================================

# Configure what output to use when sending the data collected by the beat.

#-------------------------- Elasticsearch output ------------------------------
output.elasticsearch:
  # Array of hosts to connect to.
  hosts: ["192.168.110.130:9200","192.168.110.131:9200"]

  # Protocol - either `http` (default) or `https`.
  #protocol: "https"

  # Authentication credentials - either API key or username/password.
  #api_key: "id:api_key"
  username: "elastic"  #es的用戶
  password: "${ES_PWD}" # es的密碼
  #這裏不能指定index,因為我沒有配置模板,會自動生成一個名為filebeat-%{[beat.version]}-%{+yyyy.MM.dd}的索引

第二步:配置elasticsearch的慢日誌路徑

cd filebeat-7.7.0-linux-x86_64/modules.d

vim  elasticsearch.yml

 

 

 

第三步:生效es模塊

./filebeat modules elasticsearch

查看生效的模塊

./filebeat modules list

 

 

 

第四步:初始化環境

./filebeat setup -e

 

 

 

 

 第五步:啟動filebeat

./filebeat -e

查看elasticsearch集群,如下圖所示,把慢日誌查詢的日誌都自動解析出來了:

 

 到這裏,elasticsearch這個module就實驗成功了

 

參考

官網:https://www.elastic.co/guide/en/beats/filebeat/current/index.html

 

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

【其他文章推薦】

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

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

※超省錢租車方案

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

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

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

MySQL 性能優化之慢查詢

性能優化的思路

  1. 首先需要使用慢查詢功能,去獲取所有查詢時間比較長的SQL語句
  2. 其次使用explain命令去查詢由問題的SQL的執行計劃(腦補鏈接:點我直達1,點我直達2)
  3. 最後可以使用show profile[s] 查看由問題的SQL的性能使用情況
  4. 優化SQL語句

介紹

  數據庫查詢快慢是影響項目性能的一大因素,對於數據庫,我們除了要優化SQL,更重要的是得先找到需要優化的SQL語句

  MySQL數據庫有一個“慢查詢日誌”功能,用來記錄查詢時間超過某個設定值的SQL,這將極大程度幫助我們快速定位到問題所在,以便對症下藥

至於查詢時間的多少才算慢,每個項目、業務都有不同的要求。
    比如傳統企業的軟件允許查詢時間高於某個值,但是把這個標準方在互聯網項目或者訪問量大的網站上,估計就是一個Bug,甚至可能升級為一個功能缺陷。

  MySQL的慢查詢日誌功能,默認是關閉的,需要手動開啟

開啟慢查詢功能

查看是否開啟慢查詢功能

 

 

參數說明:

  • slow_query_log:是否開啟慢查詢,on為開啟,off為關閉;
  • log-slow-queries:舊版(5.6以下版本)MySQL數據庫慢查詢存儲路徑,可以不設置該參數,系統則會給一個缺省的文件:host_name-slow.log
  • long_query_time:慢查詢閥值,當查詢時間多於設置的閥值時,記錄日誌,單位為秒。

臨時開啟滿查詢功能

  在MySQL執行SQL語句設置,但是如果重啟MySQL的話會失效。

set global slow_query_log=on;
set global long_query_time=1;

永久性開啟慢查詢

  修改:/etc/my.cnf,添加以下內容,然後重啟MySQL服務

[mysqld]
lower_case_table_names=1
slow_query_log=ON
slow_query_log_file=/usr/local/mysql/data/chenyanbindeMacBook-Pro-slow.log
long_query_time=1

 

查看滿查詢啟動狀態

演示慢查詢

  為了演示方便,我們讓sql睡眠3秒!

格式說明:

  • 第一行,SQL查詢執行的具體時間
  • 第二行,執行SQL查詢的連接信息,用戶和連接IP
  • 第三行,記錄了一些我們比較有用的信息,
    • Query_timme,這條SQL執行的時間,越長則越慢
    • Lock_time,在MySQL服務器階段(不是在存儲引擎階段)等待表鎖時間
    • Rows_sent,查詢返回的行數
    • Rows_examined,查詢檢查的行數,越長就越浪費時間
  • 第四行,設置時間戳,沒有實際意義,只是和第一行對應執行時間。
  • 第五行,執行的SQL語句記錄信息

分析滿查詢日誌

MySQL自帶的mysqldumpslow

 

 

 

參數說明:

  • -s, 是表示按照何種方式排序,c、t、l、r分別是按照記錄次數、時間、查詢時間、返回的記錄數來排序,ac、at、al、ar,表示相應的倒敘;
  • -t, 是top n的意思,即為返回前面多少條的數據;
  • -g, 後邊可以寫一個正則匹配模式,大小寫不敏感的;

MySQL性能fenix語句show profile(重要

介紹

  • Query Profiler是MySQL自帶的一種query診斷分析工具,通過它可以分析出一條SQL語句性能瓶頸在什麼地方。
  • 通常使用explain,以及slow query log都無法做到精確分析,但是Query profiler卻可以定位出一條SQL執行的各種資源消耗情況,比如CPU、IO等,以及該SQL執行所耗費的時間等。不過該工具只有在MySQL5.0.37以上版本中才有實現
  • 默認的情況下,MySQL的該功能沒有打開,需要自己手動打開

語句使用

  • show profileshow profiles語句可以展示當前會話(退出session后,profiling重置為0)中執行語句的資源使用情況。
  • show profiles:以列表形式显示最近發送到服務器上執行的語句的資源使用情況,显示的記錄數由變量:profiling_history_size控制,默認15條
  • show profile:只是最近一條語句執行的消息資源佔用信息,默認實現Status和Duration兩列

開啟Profile功能

  • Profile功能由MySQL會話變量:profiling控制,默認是OFF關閉狀態。
  • 查看是否開啟了Profile功能
select @@profiling;

show variables like '%profil%';

 

打開profiling功能

set profiling=1;

 

show profile用法

SHOW PROFILE [type [, type] …… ] [FOR QUERY n] [LIMIT row_count [OFFSET offset]]

type: { ALL | BLOCK IO | CONTEXT SWITCHES | CPU | IPC | MEMORY | PAGE FAULTS | SOURCE | SWAPS }

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

【其他文章推薦】

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

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

※回頭車貨運收費標準

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

※超省錢租車方案

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