jrainlau

jrainlau 查看完整檔案

深圳編輯華南師范大學大學城校區  |  光信息科學與技術 編輯騰訊  |  前端 編輯 jrainlau.github.io 編輯
編輯

Hiphop dancer,
Front-end engineer,
Wanna be a designer.

個人動態

jrainlau 發布了文章 · 2月20日

奇怪的知識——位掩碼

108588108-64e3c400-7392-11eb-8275-ed7a7d4a3ebd.png

在春節假期無聊刷手機的時候,偶然間看到了一篇關于“位掩碼”的文章,本身就是奇怪知識的它可以用來解決一些奇怪的問題,實在是非常有趣。

位運算符

在了解“位掩碼”之前,首先要學會位運算符。

我們知道,在計算機中數據其實都是以二進制的形式所儲存的,而位運算符則可以對二進制數據進行操作。舉個簡單的例子,給定兩個二進制數據(其中 0b 是二進制數據的前綴):

const A = 0b1010
const B = 0b1111

image.png

1、按位非運算符 ~

對每一位執行非(NOT)操作,也可以理解為取反碼。
image.png

2、按位與運算符 &

對每一位執行與(AND)操作,只要對應位置均為 1 時,結果才為 1,否則為 0。
image.png

3、按位或運算符 |

對每一位執行或(OR)操作,只要對應位置有一個 1 時,結果就為 1。
image.png

4、按位異或運算符 ^

對每一位執行異或(XOR)操作,當對應位置有且只有一個 1 時,結果就為 1,否則為 0。
image.png

5、左移運算符 <<

將數據向左移動一定的位(<32),右邊用 0 填充。
image.png

6、右移運算符 >>

將數據向右移動一定的位(<32),遺棄被丟出的位。
image.png


在學習完了位運算符以后,肯定有人會說,道理都明白了,那么這些位運算符有什么用呢?應該在什么場合使用呢?平時的業務開發中也沒見過,是不是其實學了也沒什么用?

對于這個問題,答案確實是“是的,這個知識其實沒什么用“。但是呢,秉承著探索的精神,我們也許可以用這個”沒什么用的知識“去解決一些已知的問題。當然,在后續的例子中,你可能會覺得我在小題大做。不過沒關系,學習本來就是枯燥的事情,能夠找到些有趣的方式去學習枯燥的知識,也是很快樂的。

權限系統

假設我們有一個權限系統,它通過 JSON 的方式記錄了某個用戶的權限開通情況(姑且假設權限集是 CURD):

const permission = {
  create: false,
  update: false,
  read: true,
  delete: false,
}

如果我們把 false 寫成 0,true 寫成 1,那么這個 permisson 對象可以簡寫為 0b0010。

const permission = {
  create: false,
  update: false,
  read: true,
  delete: false,
}

// 從左往右,依次為 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

對于 JSON 對象的權限集,如果我們要查看或者修改該用戶的某些權限,只需要通過形如 permission.craete 的普通對象操作即可。那么如果對于二進制形式的權限集,我們又應該如何進行查看或者修改的操作呢?接下來我們就開始使用奇怪的知識——位掩碼來進行了。

位掩碼

首先進行名詞解釋,什么是”位掩碼“。

位掩碼(BitMask),是”位(Bit)“和”掩碼(Mask)“的組合詞?!蔽弧爸复M制數據當中的二進制位,而”掩碼“指的是一串用于與目標數據進行按位操作的二進制數字。組合起來,就是”用一串二進制數字(掩碼)去操作另一串二進制數字“的意思。

明白了位掩碼的作用以后,我們就可以通過它來對權限集二進制數進行操作了。

1、查詢用戶是否擁有某個權限

已知用戶權限集二進制數為 permissionBinary = 0b0010。如果我想知道該用戶是否存在 update 這個權限,可以先給定一個位掩碼 mask = 0b1。

image.png

由于 update 位于右數第三項,所以只需要把位掩碼向左移動兩位,剩余位置補0。最后和權限集二進制數進行按位與運算即可得到結果。
image.png

最后算出來的 result 為 0b0000,使用 Boolean() 函數處理之即可得到 false 的結果,也就是說該用戶的 update 權限為 false。

// 從左往右,依次為 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

// 由于 update 位于右數第三位,因此只需要讓掩碼向左移動2位即可
const mask = 0b1 << 2

const result = permissionBinary & mask

Boolean(result) // false

2、修改用戶的某個權限

當我們明白了如何用位掩碼來查詢權限后,要修改對應的權限也就手到擒來了,無非就是換一種位運算。假設還是 update 權限,如果我想把它修改成 true,我們可以這么干:

image.png

只需要把按位與改為按位異或即可,代碼如下:

// 從左往右,依次為 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

// 由于 update 位于右數第三位,因此只需要讓掩碼向左移動2位即可
const mask = 0b1 << 2

const result = permissionBinary ^ mask

parseInt(result).toString(2) // 0b0110

經過上面的內容,相信你已經基本掌握了位掩碼的知識,同時你肯定還有很多問號,比如說這么復雜又不好閱讀的代碼,真的有意義嗎?

臟數據記錄

前文例子中的權限系統僅有區區4個數據的處理,位掩碼技術顯得復雜又小題大做。那么有沒有什么場景是真的適合使用位掩碼的呢?臟數據記錄就是其中一個。

假設我們存在著一份原始數據,其值如下:

let A = 'a'
let B = 'b'
let C = 'c'
let D = 'd'

給定一個二進制數,從左往右分別對應著 A/B/C/D 的狀態:

let O = 0b0000 // 十進制 0

則數據一旦發生了修改,都可以用對應的比特位來表示

// 當且僅當 A 發生了修改
O = 0b1000 // 十進制 8

// 當且僅當 B 發生了修改
O = 0b0100 // 十進制 4

// 當且僅當 C 發生了修改
O = 0b0010 // 十進制 2

// 當且僅當 D 發生了修改
O = 0b0001 // 十進制 1

同理,當多個數據發生了修改時,則可以同時表示

// 當 A 和 B 發生了修改
O = 0b1100 // 十進制 12

// 當 A/B/C 都發生了修改
O = 0b1110 // 十進制 14

通過這個思路,應用排列組合的思想,可以很快知道只需要僅僅 4 個比特位,就可以表達 16 種數據變化的情況。由于二進制和十進制可以相互轉化,因此只需要區區 16 個十進制數,就可以完整地表達 A/B/C/D 這四個數據的變化情況,也就是臟數據追蹤。舉個例子,給定一個臟數據記錄 14,二進制轉換為 0b1110,因此表示 A/B/C 的數據被修改了。

Svelte 這個框架,就是通過這個思路來實現響應式的:

if ( A 數據變了 ) {
  更新A對應的DOM節點
}
if ( B 數據變了 ) {
  更新B對應的DOM節點
}

/** 轉化成偽代碼 **/

if ( dirty & 8 ) { // 8 === 0b1000
  更新A對應的DOM節點
}
if ( dirty & 4 ) { // 4 === 0b0100
  更新B對應的DOM節點
}
更多具體的介紹可以查看《新興前端框架 Svelte 從入門到原理》。

老鼠喝毒藥

除了用來做臟數據記錄以外,位掩碼也能夠用來處理經典的”老鼠喝毒藥“的問題。

有 1000 瓶水,其中有一瓶有毒,小白鼠只要嘗一點帶毒的水24小時后就會死亡,問至少要多少只小白鼠才能在24小時內鑒別出哪瓶水有毒?

我們簡化一下問題,假設只有 8 瓶水,其編號用二進制表示:

image.png

接著按照圖示的方式對水瓶的水進行混合,得到樣品 A/B/C/D,取4只老鼠編號為 a/b/c/d 分別喝下對應的水,得到如下的表格:

image.png

在 24 小時候,統計老鼠的死亡情況,匯總后可以得到表格和結果:

image.png

答案呼之欲出,由于 8 瓶水可以兌出 4 份樣品,因此只需要 4 只老鼠即可在 24 小時后確定到底哪一瓶水是有毒的?;氐筋}目,如果是 1000 瓶水,只需要知道第 1000 號的二進制數 0b1111101000即可。該二進制數一共有 10 個比特位,意味著 1000 瓶水可以兌出 10 份樣品,也就是說只需要 10 只老鼠,就可以完成測試任務。

尾聲

關于位掩碼技術的探索就到這里。相信在認真讀完這篇文章以后,大家心里已經建立起對位掩碼技術的概念。這是一種非常特別的問題解決思路,也許在未來的某一天你真的會用上它。

查看原文

贊 20 收藏 13 評論 1

jrainlau 發布了文章 · 2020-12-22

探索瀏覽器端的網絡速度測試

image

在最近的工作中,有一項內容是需要知道當前用戶的網絡情況以采取對應的展示策略。這塊內容是我之前沒有研究過的,正好趁此機會了解一下。

那么我們要怎樣做才能獲取到用戶的網絡速度呢?下面是調研到的幾種方法。

一、通過 window.navigator.connection API 獲取網速

在 Chrome 瀏覽器種,我們可以使用 window.navigator.connection API 中的 downlink 屬性來獲取實時網速:
image

image

image

根據 MDN 文檔的說法,該 downlink 屬性是以每秒兆位為單位返回有效帶寬估計值。比如當 downlink 的值是 5.0 的時候,理論下載速度可能是 5Mb/s。

遺憾的是,這個 API 仍然處于實驗階段,部分功能在 iOS 或者 Safari 上都是不可用的,我們需要找到另外一種方式去測試網速。

image

二、部署服務,通過請求接口來獲取網速

這也是一些測速網站常用的做法,比如這個愛測速。

image

它請求了部署在其服務器上的幾個接口

  • /cesu/index/garbage
  • /cesu/index/empty
  • /cesu/index/ip

來分別獲得如下載速度、上傳速度、網絡延遲和網絡抖動等數據。

我們可以通過閱讀它的測速代碼 speedtest_worker.min.js 來一探究竟。簡單地來說,就是通過構造不同的 XHR 對象對接口進行請求,記錄開始和結束的時間,最后換算成具體的數據。

這種部署服務的方式比較主流,但是實現成本較高。另外還有一點需要注意,如果接口掛了,可能就會走到 error 的邏輯,會誤判為用戶的網絡中斷了。

三、獲取靜態圖片資源

這是一種成本較低,也是非常通用的做法。我們可以讓瀏覽器通過 GET 請求去獲取一張既定大小的圖片,分析獲取圖片所需的時間,即可換算成實際的下載速度。這種辦法比第一小節的 window.navigator.connection.downlink 數據更準確,因為那個 API 的只是理論值,實際值還需要通過真正地去下載資源才能獲取。

附上實現的代碼,可以看出這種方案確實最為經濟實惠:

function testDownloadSpeed ({ url, size }) {
  return new Promise((resolve, reject) => {
    const img = new Image()
    img.src = `url?_t=${Math.random()}` // 加個時間戳以避免瀏覽器只發起一次請求
    const startTime = new Date()

    img.onload = function () {
      const fileSize = size // 單位是 kb
      const endTime = new Date()
      const costTime = endTime - startTime
      const speed = fileSize / (endTime - startTime) * 1000 // 單位是 kb/s
      resolve({ speed, costTime })
    }

    img.onerror = reject
  })
}

我們在瀏覽器中拿這張大小為 146kb 的圖片 https://raw.githubusercontent.com/jrainlau/imghost/master/29e9103b4a6801aa42f8f08ef65ad51c%20(1).ytuxq1kbb4f.png 試一下:

image

輸出的耗時和 Network 面板的基本吻合,且計算出來的下載速度也和上一節在 愛測速 得到的數據基本一致,因此可以得出這種方法靠譜的結論。

(完)

查看原文

贊 4 收藏 3 評論 0

jrainlau 贊了文章 · 2020-11-10

編譯原理實戰入門:用 JavaScript 寫一個簡單的四則運算編譯器(修訂版)

編譯器是一個程序,作用是將一門語言翻譯成另一門語言。

例如 babel 就是一個編譯器,它將 es6 版本的 js 翻譯成 es5 版本的 js。從這個角度來看,將英語翻譯成中文的翻譯軟件也屬于編譯器。

一般的程序,CPU 是無法直接執行的,因為 CPU 只能識別機器指令。所以要想執行一個程序,首先要將高級語言編寫的程序翻譯為匯編代碼(Java 還多了一個步驟,將高級語言翻譯成字節碼),再將匯編代碼翻譯為機器指令,這樣 CPU 才能識別并執行。

由于匯編語言和機器語言一一對應,并且匯編語言更具有可讀性。所以計算機原理的教材在講解機器指令時一般會用匯編語言來代替機器語言講解。

本文所要寫的四則運算編譯器需要將 1 + 1 這樣的四則運算表達式翻譯成機器指令并執行。具體過程請看示例:

// CPU 無法識別
10 + 5

// 翻譯成匯編語言
push 10
push 5
add

// 最后翻譯為機器指令,匯編代碼和機器指令一一對應
// 機器指令由 1 和 0 組成,以下指令非真實指令,只做演示用
0011101001010101
1101010011100101
0010100111100001

四則運算編譯器,雖然說功能很簡單,只能編譯四則運算表達式。但是編譯原理的前端部分幾乎都有涉及:詞法分析、語法分析。另外還有編譯原理后端部分的代碼生成。不管是簡單的、復雜的編譯器,編譯步驟是差不多的,只是復雜的編譯器實現上會更困難。

可能有人會問,學會編譯原理有什么好處?

我認為對編譯過程內部原理的掌握將會使你成為更好的高級程序員。另外在這引用一下知乎網友-隨心所往的回答,更加具體:

  1. 可以更加容易的理解在一個語言種哪些寫法是等價的,哪些是有差異的
  2. 可以更加客觀的比較不同語言的差異
  3. 更不容易被某個特定語言的宣揚者忽悠
  4. 學習新的語言是效率也會更高
  5. 其實從語言a轉換到語言b是一個通用的需求,學好編譯原理處理此類需求時會更加游刃有余

好了,下面讓我們看一下如何寫一個四則運算編譯器。

詞法分析

程序其實就是保存在文本文件中的一系列字符,詞法分析的作用是將這一系列字符按照某種規則分解成一個個字元(token,也稱為終結符),忽略空格和注釋。

示例:

// 程序代碼
10 + 5 + 6

// 詞法分析后得到的 token
10
+
5
+
6

終結符

終結符就是語言中用到的基本元素,它不能再被分解。

四則運算中的終結符包括符號和整數常量(暫不支持一元操作符和浮點運算)。

  1. 符號+ - * / ( )
  2. 整數常量:12、1000、111...

詞法分析代碼實現

function lexicalAnalysis(expression) {
    const symbol = ['(', ')', '+', '-', '*', '/']
    const re = /\d/
    const tokens = []
    const chars = expression.trim().split('')
    let token = ''
    chars.forEach(c => {
        if (re.test(c)) {
            token += c
        } else if (c == ' ' && token) {
            tokens.push(token)
            token = ''
        } else if (symbol.includes(c)) {
            if (token) {
                tokens.push(token)
                token = ''
            } 

            tokens.push(c)
        }
    })

    if (token) {
        tokens.push(token)
    }

    return tokens
}

console.log(lexicalAnalysis('100    +   23   +    34 * 10 / 2')) 
// ["100", "+", "23", "+", "34", "*", "10", "/", "2"]

四則運算的語法規則(語法規則是分層的)

  1. x*, 表示 x 出現零次或多次
  2. x | y, 表示 x 或 y 將出現
  3. ( ) 圓括號,用于語言構詞的分組

以下規則從左往右看,表示左邊的表達式還能繼續往下細分成右邊的表達式,一直細分到不可再分為止。

  • expression: addExpression
  • addExpression: mulExpression (op mulExpression)*
  • mulExpression: term (op term)*
  • term: '(' expression ')' | integerConstant
  • op: + - * /

addExpression 對應 +- 表達式,mulExpression 對應 */ 表達式。

如果你看不太懂以上的規則,那就先放下,繼續往下看??纯丛趺从么a實現語法分析。

語法分析

對輸入的文本按照語法規則進行分析并確定其語法結構的一種過程,稱為語法分析。

一般語法分析的輸出為抽象語法樹(AST)或語法分析樹(parse tree)。但由于四則運算比較簡單,所以這里采取的方案是即時地進行代碼生成和錯誤報告,這樣就不需要在內存中保存整個程序結構。

先來看看怎么分析一個四則運算表達式 1 + 2 * 3。

首先匹配的是 expression,由于目前 expression 往下分只有一種可能,即 addExpression,所以分解為 addExpression。
依次類推,接下來的順序為 mulExpression、term、1(integerConstant)、+(op)、mulExpression、term、2(integerConstant)、*(op)、mulExpression、term、3(integerConstant)。

如下圖所示:

這里可能會有人有疑問,為什么一個表達式搞得這么復雜,expression 下面有 addExpression,addExpression 下面還有 mulExpression。
其實這里是為了考慮運算符優先級而設的,mulExpraddExpr 表達式運算級要高。

1 + 2 * 3
compileExpression
???|?compileAddExpr
???|??|?compileMultExpr
???|??|??|?compileTerm
???|??|??|??|_?matches integerConstant        push 1
  ?|??|??|_
? ?|??|?matches '+'
???|??|?compileMultExpr
???|??|??|?compileTerm
???|??|??|??|_?matches integerConstant        push 2
???|??|??|?matches '*'
???|??|??|?compileTerm
 ??|??|??|??|_?matches integerConstant        push 3
???|??|??|_?compileOp('*')                      *
???|??|_?compileOp('+')                         +
?  |_

有很多算法可用來構建語法分析樹,這里只講兩種算法。

遞歸下降分析法

遞歸下降分析法,也稱為自頂向下分析法。按照語法規則一步步遞歸地分析 token 流,如果遇到非終結符,則繼續往下分析,直到終結符為止。

LL(0)分析法

遞歸下降分析法是簡單高效的算法,LL(0)在此基礎上多了一個步驟,當第一個 token 不足以確定元素類型時,對下一個字元采取“提前查看”,有可能會解決這種不確定性。

以上是對這兩種算法的簡介,具體實現請看下方的代碼實現。

表達式代碼生成

我們通常用的四則運算表達式是中綴表達式,但是對于計算機來說中綴表達式不便于計算。所以在代碼生成階段,要將中綴表達式轉換為后綴表達式。

后綴表達式

后綴表達式,又稱逆波蘭式,指的是不包含括號,運算符放在兩個運算對象的后面,所有的計算按運算符出現的順序,嚴格從左向右進行(不再考慮運算符的優先規則)。

示例:

中綴表達式: 5 + 5 轉換為后綴表達式:5 5 +,然后再根據后綴表達式生成代碼。

// 5 + 5 轉換為 5 5 + 再生成代碼
push 5
push 5
add

代碼實現

編譯原理的理論知識像天書,經常讓人看得云里霧里,但真正動手做起來,你會發現,其實還挺簡單的。

如果上面的理論知識看不太懂,沒關系,先看代碼實現,然后再和理論知識結合起來看。

注意:這里需要引入剛才的詞法分析代碼。

// 匯編代碼生成器
function AssemblyWriter() {
    this.output = ''
}

AssemblyWriter.prototype = {
    writePush(digit) {
        this.output += `push ${digit}\r\n`
    },

    writeOP(op) {
        this.output += op + '\r\n'
    },

    //輸出匯編代碼
    outputStr() {
        return this.output
    }
}

// 語法分析器
function Parser(tokens, writer) {
    this.writer = writer
    this.tokens = tokens
    // tokens 數組索引
    this.i = -1
    this.opMap1 = {
        '+': 'add',
        '-': 'sub',
    }

    this.opMap2 = {
        '/': 'div',
        '*': 'mul'
    }

    this.init()
}

Parser.prototype = {
    init() {
        this.compileExpression()
    },

    compileExpression() {
        this.compileAddExpr()
    },

    compileAddExpr() {
        this.compileMultExpr()
        while (true) {
            this.getNextToken()
            if (this.opMap1[this.token]) {
                let op = this.opMap1[this.token]
                this.compileMultExpr()
                this.writer.writeOP(op)
            } else {
                // 沒有匹配上相應的操作符 這里為沒有匹配上 + - 
                // 將 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileMultExpr() {
        this.compileTerm()
        while (true) {
            this.getNextToken()
            if (this.opMap2[this.token]) {
                let op = this.opMap2[this.token]
                this.compileTerm()
                this.writer.writeOP(op)
            } else {
                // 沒有匹配上相應的操作符 這里為沒有匹配上 * / 
                // 將 token 索引后退一位
                this.i--
                break
            }
        }
    },

    compileTerm() {
        this.getNextToken()
        if (this.token == '(') {
            this.compileExpression()
            this.getNextToken()
            if (this.token != ')') {
                throw '缺少右括號:)'
            }
        } else if (/^\d+$/.test(this.token)) {
            this.writer.writePush(this.token)
        } else {
            throw '錯誤的 token:第 ' + (this.i + 1) + ' 個 token (' + this.token + ')'
        }
    },

    getNextToken() {
        this.token = this.tokens[++this.i]
    },

    getInstructions() {
        return this.writer.outputStr()
    }
}

const tokens = lexicalAnalysis('100+10*10')
const writer = new AssemblyWriter()
const parser = new Parser(tokens, writer)
const instructions = parser.getInstructions()
console.log(instructions) // 輸出生成的匯編代碼
/*
push 100
push 10
push 10
mul
add
*/

模擬執行

現在來模擬一下 CPU 執行機器指令的情況,由于匯編代碼和機器指令一一對應,所以我們可以創建一個直接執行匯編代碼的模擬器。
在創建模擬器前,先來講解一下相關指令的操作。

在內存中,棧的特點是只能在同一端進行插入和刪除的操作,即只有 push 和 pop 兩種操作。

push

push 指令的作用是將一個操作數推入棧中。

pop

pop 指令的作用是將一個操作數彈出棧。

add

add 指令的作用是執行兩次 pop 操作,彈出兩個操作數 a 和 b,然后執行 a + b,再將結果 push 到棧中。

sub

sub 指令的作用是執行兩次 pop 操作,彈出兩個操作數 a 和 b,然后執行 a - b,再將結果 push 到棧中。

mul

mul 指令的作用是執行兩次 pop 操作,彈出兩個操作數 a 和 b,然后執行 a * b,再將結果 push 到棧中。

div

sub 指令的作用是執行兩次 pop 操作,彈出兩個操作數 a 和 b,然后執行 a / b,再將結果 push 到棧中。

四則運算的所有指令已經講解完畢了,是不是覺得很簡單?

代碼實現

注意:需要引入詞法分析和語法分析的代碼

function CpuEmulator(instructions) {
    this.ins = instructions.split('\r\n')
    this.memory = []
    this.re = /^(push)\s\w+/
    this.execute()
}

CpuEmulator.prototype = {
    execute() {
        this.ins.forEach(i => {
            switch (i) {
                case 'add':
                    this.add()
                    break
                case 'sub':
                    this.sub()
                    break
                case 'mul':
                    this.mul()
                    break
                case 'div':
                    this.div()
                    break                
                default:
                    if (this.re.test(i)) {
                        this.push(i.split(' ')[1])
                    }
            }
        })
    },

    add() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a + b)
    },

    sub() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a - b)
    },

    mul() {
        const b = this.pop()
        const a = this.pop()
        this.memory.push(a * b)
    },

    div() {
        const b = this.pop()
        const a = this.pop()
        // 不支持浮點運算,所以在這要取整
        this.memory.push(Math.floor(a / b))
    },

    push(x) {
        this.memory.push(parseInt(x))
    },

    pop() {
        return this.memory.pop()
    },

    getResult() {
        return this.memory[0]
    }
}

const tokens = lexicalAnalysis('(100+  10)*  10-100/  10      +8*  (4+2)')
const writer = new AssemblyWriter()
const parser = new Parser(tokens, writer)
const instructions = parser.getInstructions()
const emulator = new CpuEmulator(instructions)
console.log(emulator.getResult()) // 1138

一個簡單的四則運算編譯器已經實現了。我們再來寫一個測試函數跑一跑,看看運行結果是否和我們期待的一樣:

function assert(expression, result) {
    const tokens = lexicalAnalysis(expression)
    const writer = new AssemblyWriter()
    const parser = new Parser(tokens, writer)
    const instructions = parser.getInstructions()
    const emulator = new CpuEmulator(instructions)
    return emulator.getResult() == result
}

console.log(assert('1 + 2 + 3', 6)) // true
console.log(assert('1 + 2 * 3', 7)) // true
console.log(assert('10 / 2 * 3', 15)) // true
console.log(assert('(10 + 10) / 2', 10)) // true

測試全部正確。另外附上完整的源碼,建議沒看懂的同學再看多兩遍。

更上一層樓

對于工業級編譯器來說,這個四則運算編譯器屬于玩具中的玩具。但是人不可能一口吃成個胖子,所以學習編譯原理最好采取循序漸進的方式去學習。下面來介紹一個高級一點的編譯器,這個編譯器可以編譯一個 Jack 語言(類 Java 語言),它的語法大概是這樣的:

class Generate {
    field String str;
    static String str1;
    constructor Generate new(String s) {
        let str = s;
        return this;
    }

    method String getString() {
        return str;
    }
}

class Main {
    function void main() {
        var Generate str;
        let str = Generate.new("this is a test");
        do Output.printString(str.getString());
        return;
    }
}

上面代碼的輸出結果為:this is a test。

想不想實現這樣的一個編譯器?

這個編譯器出自一本書《計算機系統要素》,它從第 6 章開始,一直到第 11 章講解了匯編編譯器(將匯編語言轉換為機器語言)、VM 編譯器(將類似于字節碼的 VM 語言翻譯成匯編語言)、Jack 語言編譯器(將高級語言 Jack 翻譯成 VM 語言)。每一章都有詳細的知識點講解和實驗,只要你一步一步跟著做實驗,就能最終實現這樣的一個編譯器。

如果編譯器寫完了,最后機器語言在哪執行呢?

這本書已經為你考慮好了,它從第 1 章到第 5 章,一共五章的內容。教你從邏輯門開始,逐步組建出算術邏輯單元 ALU、CPU、內存,最終搭建出一個現代計算機。然后讓你用編譯器編譯出來的程序運行在這臺計算機之上。

另外,這本書的第 12 章會教你寫操作系統的各種庫函數,例如 Math 庫(包含各種數學運算)、Keyboard 庫(按下鍵盤是怎么輸出到屏幕上的)、內存管理等等。

想看一看全書共 12 章的實驗做完之后是怎么樣的嗎?我這里提供幾張這臺模擬計算機運行程序的 DEMO GIF,供大家參考參考。

這幾張圖中的右上角是“計算機”的屏幕,其他部分是“計算機”的堆棧區和指令區。

這本書的所有實驗我都已經做完了(每天花 3 小時,兩個月就能做完),答案放在我的 github 上,有興趣的話可以看看。

參考資料

我的博客即將同步至 OSCHINA 社區,這是我的 OSCHINA ID:譚光志,邀請大家一同入駐:https://www.oschina.net/shari...

查看原文

贊 15 收藏 10 評論 2

jrainlau 發布了文章 · 2020-10-22

Redis + NodeJS 實現一個能處理海量數據的異步任務隊列系統

未命名 002

項目倉庫:https://github.com/jrainlau/n...

前言

在最近的業務中,接到了一個需要處理約十萬條數據的需求。這些數據都以字符串的形式給到,并且處理它們的步驟是異步且耗時的(平均處理一條數據需要 25s 的時間)。如果以串行的方式實現,其耗時是相當長的:

總耗時時間 = 數據量 × 單條數據處理時間

T = N * t (N = 100,000; t = 25s)

總耗時時間 = 2,500,000 秒 ≈ 695 小時 ≈ 29 天

顯然,我們不能簡單地把數據一條一條地處理。那么有沒有辦法能夠減少處理的時間呢?經過調研后發現,使用異步任務隊列是個不錯的辦法。

一、異步任務隊列原理

我們可以把“處理單條數據”理解為一個異步任務,因此對這十萬條數據的處理,就可以轉化成有十萬個異步任務等待進行。我們可以把這十萬條數據塞到一個隊列里面,讓任務處理器自發地從隊列里面去取得并完成。

任務處理器可以有多個,它們同時從隊列里面把任務取走并處理。當任務隊列為空,表示所有任務已經被認領完;當所有任務處理器完成任務,則表示所有任務已經被處理完。

其基本原理如下圖所示:

未命名 001

首先來解決任務隊列的問題。在這個需求中,任務隊列里面的每一個任務,都包含了待處理的數據,數據以字符串的形式存在。為了方便起見,我們可以使用 RedisList 數據格式來存放這些任務。

由于項目是基于 NodeJS 的,我們可以利用 PM2Cluster 模式來啟動多個任務處理器,并行地處理任務。以一個 8 核的 CPU 為例,如果完全開啟了多進程,其理論處理時間將提升 8 倍,從 29 天縮短到 3.6 天。

接下來,我們會從實際編碼的角度來講解上述內容的實現過程。

二、使用 NodeJS 操作 Redis

異步任務隊列使用 Redis 來實現,因此我們需要部署一個單獨的 Redis 服務。在本地開發中為了快速完成 Redis 的安裝,我使用了 Docker 的辦法(默認機器已經安裝了 Docker)。

  1. Docker 拉取 Redis 鏡像
docker pull redis:latest
  1. Docker 啟動 Redis
docker run -itd --name redis-local -p 6379:6379 redis

此時我們已經使用 Docker 啟動了一個 Redis 服務,其對外的 IP 及端口為 127.0.0.1:6379。此外,我們還可以在本地安裝一個名為 Another Redis DeskTop Manager
的 Redis 可視化工具,來實時查看、修改 Redis 的內容。

image

在 NodeJS 中,我們可以使用 node-redis 來操作 Redis。新建一個 mqclient.ts 文件并寫入如下內容:

import * as Redis from 'redis'

const client = Redis.createClient({
  host: '127.0.0.1',
  port: 6379
})

export default client

Redis 本質上是一個數據庫,而我們對數據庫的操作無非就是增刪改查。node-redis 支持 Redis 的所有交互操作方式,但是操作結果默認是以回調函數的形式返回。為了能夠使用 async/await,我們可以新建一個 utils.ts 文件,把 node-redis 操作 Redis 的各種操作都封裝成 Promise 的形式,方便我們后續使用。

import client from './mqClient'

// 獲取 Redis 中某個 key 的內容
export const getRedisValue = (key: string): Promise<string | null> => new Promise(resolve => client.get(key, (err, reply) => resolve(reply)))
// 設置 Redis 中某個 key 的內容
export const setRedisValue = (key: string, value: string) => new Promise(resolve => client.set(key, value, resolve))
// 刪除 Redis 中某個 key 及其內容
export const delRedisKey = (key: string) => new Promise(resolve => client.del(key, resolve))

除此之外,還能在 utils.ts 中放置其他常用的工具方法,以實現代碼的復用、保證代碼的整潔。

為了在 Redis 中創建任務隊列,我們可以單獨寫一個 createTasks.ts 的腳本,用于往隊列中塞入自定義的任務。

import { TASK_NAME, TASK_AMOUNT, setRedisValue, delRedisKey } from './utils'
import client from './mqClient'

client.on('ready', async () => {
  await delRedisKey(TASK_NAME)
  for (let i = TASK_AMOUNT; i > 0 ; i--) {
    client.lpush(TASK_NAME, `task-${i}`)
  }
  
  client.lrange(TASK_NAME, 0, TASK_AMOUNT, async (err, reply) => {
    if (err) {
      console.error(err)
      return
    }
    console.log(reply)
    process.exit()
  })
})

在這段腳本中,我們從 utils.ts 中獲取了各個 Redis 操作的方法,以及任務的名稱 TASK_NAME (此處為 local_tasks)和任務的總數 TASK_AMOUNT(此處為 20 個)。通過 LPUSH 方法往 TASK_NAME 的 List 當中塞入內容為 task-1task-20 的任務,如圖所示:

image

image

三、異步任務處理

首先新建一個 index.ts 文件,作為整個異步任務隊列處理系統的入口文件。

import taskHandler from './tasksHandler'
import client from './mqClient'

client.on('connect', () => {
  console.log('Redis is connected!')
})
client.on('ready', async () => {
  console.log('Redis is ready!')
  await taskHandler()
})
client.on('error', (e) => {
  console.log('Redis error! ' + e)
})

在運行該文件時,會自動連接 Redis,并且在 ready 狀態時執行任務處理器 taskHandler()。

在上一節的操作中,我們往任務隊列里面添加了 20 個任務,每個任務都是形如 task-n 的字符串。為了驗證異步任務的實現,我們可以在任務處理器 taskHandler.ts 中寫一段 demo 函數,來模擬真正的異步任務:

  function handleTask(task: string) {
    return new Promise((resolve) => {
      setTimeout(async () => {
        console.log(`Handling task: ${task}...`)
        resolve()
      }, 2000)
    })
  }

上面這個 handleTask() 函數,將會在執行的 2 秒后打印出當前任務的內容,并返回一個 Promise,很好地模擬了異步函數的實現方式。接下來我們將會圍繞這個函數,來處理隊列中的任務。

其實到了這一步為止,整個異步任務隊列處理系統已經基本完成了,只需要在 taskHandler.ts 中補充一點點代碼即可:

import { popTask } from './utils'
import client from './mqClient'

function handleTask(task: string) { /* ... */}

export default async function tasksHandler() {
  // 從隊列中取出一個任務
  const task = await popTask()
  // 處理任務
  await handleTask(task)
  // 遞歸運行
  await tasksHandler()
}

最后,我們使用 PM2 啟動 4 個進程,來試著跑一下整個項目:

pm2 start ./dist/index.js -i 4 && pm2 logs

image

image

可以看到,4 個任務處理器分別處理完了隊列中的所有任務,相互之前互不影響。

事到如今已經大功告成了嗎?未必。為了測試我們的這套系統到底提升了多少的效率,還需要統計完成隊列里面所有任務的總耗時。

四、統計任務完成耗時

要統計任務完成的耗時,只需要實現下列的公式即可:

總耗時 = 最后一個任務的完成時間 - 首個任務被取得的時間

首先來解決“獲取首個任務被取得的時間”這個問題。

由于我們是通過 PM2 的 Cluster 模式來啟動應用的,且從 Redis 隊列中讀取任務是個異步操作,因此在多進程運行的情況下無法直接保證從隊列中讀取任務的先后順序,必須通過一個額外的標記來判斷。其原理如下圖:

未命名 003

如圖所示,綠色的 worker 由于無法保證運行的先后順序,所以編號用問號來表示。當第一個任務被取得時,把黃色的標記值從 false 設置成 true。當且僅當黃色的標記值為 false 時才會設置時間。這樣一來,當其他任務被取得時,由于黃色的標記值已經是 true 了,因此無法設置時間,所以我們便能得到首個任務被取得的時間。

在本文的例子中,黃色的標記值和首個任務被取得的時間也被存放在 Redis 中,分別被命名為 local_tasks_SET_FIRSTlocal_tasks_BEGIN_TIME。

原理已經弄懂,但是在實踐中還有一個地方值得注意。我們知道,從 Redis 中讀寫數據也是一個異步操作。由于我們有多個 worker 但只有一個 Redis,那么在讀取黃色標記值的時候很可能會出現“沖突”的問題。舉個例子,當 worker-1 修改標記值為 true 的同時, worker-2 正好在讀取標記值。由于時間的關系,可能 worker-2 讀到的標記值依然是 false,那么這就沖突了。為了解決這個問題,我們可以使用 node-redlock 這個工具來實現“鎖”的操作。

顧名思義,“鎖”的操作可以理解為當 worker-1 讀取并修改標記值的時候,不允許其他 worker 讀取該值,也就是把標記值給鎖住了。當 worker-1 完成標記值的修改時會釋放鎖,此時才允許其他的 worker 去讀取該標記值。

node-redlock 是 Redis 分布式鎖 Redlock 算法的 JavaScript 實現,關于該算法的講解可參考 https://redis.io/topics/distlock。

值得注意的是,在 node-redlock 在使用的過程中,如果要鎖一個已存在的 key,就必須為該 key 添加一個前綴 locks:,否則會報錯。

回到 utils.ts,編寫一個 setBeginTime() 的工具函數:

export const setBeginTime = async (redlock: Redlock) => {
  // 讀取標記值前先把它鎖住
  const lock = await redlock.lock(`lock:${TASK_NAME}_SET_FIRST`, 1000)
  const setFirst = await getRedisValue(`${TASK_NAME}_SET_FIRST`)
   // 當且僅當標記值不等于 true 時,才設置起始時間
  if (setFirst !== 'true') {
    console.log(`${pm2tips} Get the first task!`)
    await setRedisValue(`${TASK_NAME}_SET_FIRST`, 'true')
    await setRedisValue(`${TASK_NAME}_BEGIN_TIME`, `${new Date().getTime()}`)
  }
  // 完成標記值的讀寫操作后,釋放鎖
  await lock.unlock().catch(e => e)
}

然后把它添加到 taskHandler() 函數里面即可:

export default async function tasksHandler() {
+  // 獲取第一個任務被取得的時間
+  await setBeginTime(redlock)
  // 從隊列中取出一個任務
  const task = await popTask()
  // 處理任務
  await handleTask(task)
  // 遞歸運行
  await tasksHandler()
}

接下來解決“最后一個任務的完成時間”這個問題。

類似上一個問題,由于任務執行的先后順序無法保證,異步操作的完成時間也無法保證,因此我們也需要一個額外的標識來記錄任務的完成情況。在 Redis 中創建一個初始值為 0 的標識 local_tasks_CUR_INDEX,當 worker 完成一個任務就讓標識加。由于任務隊列的初始長度是已知的(為 TASK_AMOUNT 常量,也寫入了 Redis 的 local_tasks_TOTAL 中),因此當標識的值等于隊列初始長度的值時,即可表明所有任務都已經完成。

未命名 004

如圖所示,被完成的任務都會讓黃色的標識加一,任何時候只要判斷到標識的值等于隊列的初始長度值,即可表明任務已經全部完成。

回到 taskHandler() 函數,加入下列內容:

export default async function tasksHandler() {
+  // 獲取標識值和隊列初始長度
+  let curIndex = Number(await getRedisValue(`${TASK_NAME}_CUR_INDEX`))
+  const taskAmount = Number(await getRedisValue(`${TASK_NAME}_TOTAL`))
+  // 等待新任務
+  if (taskAmount === 0) {
+    console.log(`${pm2tips} Wating new tasks...`)
+    await sleep(2000)
+    await tasksHandler()
+    return
+  }
+  // 判斷所有任務已經完成
+  if (curIndex === taskAmount) {
+    const beginTime = await getRedisValue(`${TASK_NAME}_BEGIN_TIME`)
+    // 獲取總耗時
+    const cost = new Date().getTime() - Number(beginTime)
+    console.log(`${pm2tips} All tasks were completed! Time cost: ${cost}ms. ${beginTime}`)
+    // 初始化 Redis 的一些標識值
+    await setRedisValue(`${TASK_NAME}_TOTAL`, '0') 
+    await setRedisValue(`${TASK_NAME}_CUR_INDEX`, '0')
+    await setRedisValue(`${TASK_NAME}_SET_FIRST`, 'false')
+    await delRedisKey(`${TASK_NAME}_BEGIN_TIME`)
+    await sleep(2000)
+    await tasksHandler()
  }
  // 獲取第一個任務被取得的時間
  await setBeginTime(redlock)
  // 從隊列中取出一個任務
  const task = await popTask()
  // 處理任務
  await handleTask(task)
+ // 任務完成后需要為標識位加一
+  try {
+    const lock = await redlock.lock(`lock:${TASK_NAME}_CUR_INDEX`, 1000)
+    curIndex = await getCurIndex()
+    await setCurIndex(curIndex + 1)
+    await lock.unlock().catch((e) => e)
+  } catch (e) {
+    console.log(e)
+  }
+  // recursion
+  await tasksHandler()
+}
  // 遞歸運行
  await tasksHandler()
}

到這一步為止,我們已經解決了獲取“最后一個任務的完成時間”的問題,再結合前面的首個任務被取得的時間,便能得出運行的總耗時。


最后來看一下實際的運行效果。我們循例往隊列里面添加了 task-1task-20 這 20 個任務,然后啟動 4 個進程來跑:

image

image

運行狀況良好。從運行結果來看,4 個進程處理 20 個平均耗時 2 秒的任務,只需要 10 秒的時間,完全符合設想。

五、小結

當面對海量的異步任務需要處理的時候,多進程 + 任務隊列的方式是一個不錯的解決方式。本文通過探索 Redis + NodeJS 結合的方式,構造出了一個異步任務隊列處理系統,能較好地完成最初方案的設想,但依然有很多問題需要改進。比如說當任務出錯了應該怎么辦,系統能否支持不同類型的任務,能否運行多個隊列等等,都是值得思考的問題。如果讀者朋友有更好的想法,歡迎留言和我交流!

(完)

查看原文

贊 21 收藏 13 評論 5

jrainlau 贊了文章 · 2020-09-27

聊聊 ESM、Bundle 、Bundleless 、Vite 、Snowpack

前言

一切要都要從打包構建說起。

當下我們很多項目都是基于 webpack 構建的, 主要用于:

  • 本地開發
  • 打包上線

首先,webpack 是一個偉大的工具。

經過不斷的完善,webpack 以及周邊的各種輪子已經能很好的滿足我們的日常開發需求。

我們都知道,webpack 具備將各類資源打包整合在一起,形成 bundle 的能力。

可是,當資源越來越多時,打包的時間也將越來越長。

一個中大型的項目, 啟動構建的時間能達到數分鐘之久。

拿我的項目為例, 初次構建大概需要三分鐘, 而且這個時間會隨著系統的迭代越來越長。

相信不少同學也都遇到過類似的問題。 打包時間太久,這是一個讓人很難受的事情。

那有沒有什么辦法來解決呢?

當然是有的。

這就是今天的主角 ESM, 以及以它為基礎的各類構建工具, 比如:

  1. Snowpack
  2. Vite
  3. Parcel

等等。

今天,我們就這個話題展開討論, 希望能給大家一些其發和幫助。

文章較長,提供一個傳送門:

  1. 什么是 ESM
  2. ESM 是如何工作的
  3. Bundle & Bundleless
  4. 實現一個乞丐版 Vite
  5. Snowpack & 實踐
  6. bundleless 模式在實際開發中存在的一些問題
  7. 結論

正文

什么是 ESM

ESM 是理論基礎, 我們都需要了解。

「 ESM 」 全稱 ECMAScript modules,基本主流的瀏覽器版本都以已經支持。

image.png

ESM 是如何工作的

image.png

當使用ESM 模式時, 瀏覽器會構建一個依賴關系圖。不同依賴項之間的連接來自你使用的導入語句。

通過這些導入語句, 瀏覽器 或 Node 就能確定加載代碼的方式。

通過指定一個入口文件,然后從這個文件開始,通過其中的import語句,查找其他代碼。

image.png

通過指定的文件路徑, 瀏覽器就找到了目標代碼文件。 但是瀏覽器并不能直接使用這些文件,它需要解析所有這些文件,以將它們轉換為稱為模塊記錄的數據結構。

image.png

然后,需要將 模塊記錄 轉換為 模塊實例 。

image.png

模塊實例, 實際上是 「 代碼 」(指令列表)與「 狀態」(所有變量的值)的組合。

對于整個系統而言, 我們需要的是每個模塊的模塊實例。

模塊加載的過程將從入口文件變為具有完整的模塊實例圖。

對于ES模塊,這分為 三個步驟

  1. 構造—查找,下載所有文件并將其解析為模塊記錄。
  2. 實例化—查找內存中的框以放置所有導出的值(但尚未用值填充它們)。然后使導出和導入都指向內存中的那些框,這稱為鏈接。
  3. 運行—運行代碼以將變量的實際值填充到框中。

image.png

在構建階段時, 發生三件事情:

  1. 找出從何處下載包含模塊的文件
  2. 提取文件(通過從URL下載文件或從文件系統加載文件)
  3. 將文件解析為模塊記錄

1. 查找

首先,需要找到入口點文件。

在HTML中,可以通過腳本標記告訴加載程序在哪里找到它。

image.png

但是,如何找到下一組模塊, 也就是 main.js 直接依賴的模塊呢?

這就是導入語句的來源。

導入語句的一部分稱為模塊說明符, 它告訴加載程序可以在哪里找到每個下一個模塊。

image.png

在解析文件之前,我們不知道模塊需要獲取哪些依賴項,并且在提取文件之前,也無法解析文件。

這意味著我們必須逐層遍歷樹,解析一個文件,然后找出其依賴項,然后查找并加載這些依賴項。

image.png

如果主線程要等待這些文件中的每個文件下載,則許多其他任務將堆積在其隊列中。

那是因為當瀏覽器中工作時,下載部分會花費很長時間。

image.png

這樣阻塞主線程會使使用模塊的應用程序使用起來太慢。

這是ES模塊規范將算法分為多個階段的原因之一。

將構造分為自己的階段,使瀏覽器可以在開始實例化的同步工作之前獲取文件并建立對模塊圖的理解。

這種方法(算法分為多個階段)是 ESMCommonJS模塊 之間的主要區別之一。

CommonJS可以做不同的事情,因為從文件系統加載文件比通過Internet下載花費的時間少得多。

這意味著Node可以在加載文件時阻止主線程。

并且由于文件已經加載,因此僅實例化和求值(在CommonJS中不是單獨的階段)是有意義的。

這也意味著在返回模塊實例之前,需要遍歷整棵樹,加載,實例化和評估任何依賴項。

該圖顯示了一個Node模塊評估一個require語句,然后Node將同步加載和評估該模塊及其任何依賴項

在具有CommonJS模塊的Node中,可以在模塊說明符中使用變量。

require在尋找下一個模塊之前,正在執行該模塊中的所有代碼。這意味著當進行模塊解析時,變量將具有一個值。

但是,使用ES模塊時,需要在進行任何評估之前預先建立整個模塊圖。

這意味著不能在模塊說明符中包含變量,因為這些變量還沒有值。

使用變量的require語句很好。 使用變量的導入語句不是。

但是,有時將變量用于模塊路徑確實很有用。

例如,你可能要根據代碼在做什么,或者在不同環境中運行來記載不同的模塊。

為了使ES模塊成為可能,有一個建議叫做動態導入。有了它,您可以使用類似的導入語句:

import(`${path}/foo.js`)。

這種工作方式是將使用加載的任何文件import()作為單獨圖的入口點進行處理。

動態導入的模塊將啟動一個新圖,該圖將被單獨處理。

兩個模塊圖之間具有依賴性,并用動態導入語句標記

但是要注意一件事–這兩個圖中的任何模塊都將共享一個模塊實例。

這是因為加載程序會緩存模塊實例。對于特定全局范圍內的每個模塊,將只有一個模塊實例。

這意味著發動機的工作量更少。

例如,這意味著即使多個模塊依賴該模塊文件,它也只會被提取一次。(這是緩存模塊的一個原因。我們將在評估部分中看到另一個原因。)

加載程序使用稱為模塊映射的內容來管理此緩存。每個全局變量在單獨的模塊圖中跟蹤其模塊。

當加載程序獲取一個URL時,它將把該URL放入模塊映射中,并記下它當前正在獲取文件。然后它將發出請求并繼續以開始獲取下一個文件。

加載程序圖填充在“模塊映射表”中,主模塊的URL在左側,而“獲取”一詞在右側

如果另一個模塊依賴于同一文件會怎樣?加載程序將在模塊映射中查找每個URL。如果在其中看到fetching,它將繼續前進到下一個URL。

但是模塊圖不僅跟蹤正在獲取的文件。模塊映射還充當模塊的緩存,如下所示。

2. 解析

現在我們已經獲取了該文件,我們需要將其解析為模塊記錄。這有助于瀏覽器了解模塊的不同部分。

該圖顯示了被解析成模塊記錄的main.js文件

創建模塊記錄后,它將被放置在模塊圖中。這意味著無論何時從此處請求,加載程序都可以將其從該映射中拉出。

模塊映射圖中的“獲取”占位符被模塊記錄填充

解析中有一個細節看似微不足道,但實際上有很大的含義。

解析所有模塊,就像它們"use strict"位于頂部一樣。還存在其他細微差異。

例如,關鍵字await是在模塊的頂級代碼保留,的值this就是undefined。

這種不同的解析方式稱為“解析目標”。如果解析相同的文件但使用不同的目標,那么最終將得到不同的結果。
因此,需要在開始解析之前就知道要解析的文件類型是否是模塊。

在瀏覽器中,這非常簡單。只需放入type="module"的script標簽。
這告訴瀏覽器應將此文件解析為模塊。并且由于只能導入模塊,因此瀏覽器知道任何導入也是模塊。

加載程序確定main.js是一個模塊,因為script標簽上的type屬性表明是這樣,而counter.js必須是一個模塊,因為它已導入

但是在Node中,您不使用HTML標記,因此無法選擇使用type屬性。社區嘗試解決此問題的一種方法是使用 .mjs擴展。使用該擴展名告訴Node,“此文件是一個模塊”。您會看到人們在談論這是解析目標的信號。目前討論仍在進行中,因此尚不清楚Node社區最終決定使用什么信號。

無論哪種方式,加載程序都將確定是否將文件解析為模塊。如果它是一個模塊并且有導入,則它將重新開始該過程,直到提取并解析了所有文件。

我們完成了!在加載過程結束時,您已經從只有入口點文件變為擁有大量模塊記錄。

建設階段的結果,左側為JS文件,右側為3個已解析的模塊記錄

下一步是實例化此模塊并將所有實例鏈接在一起。

3. 實例化

就像我之前提到的,實例將代碼與狀態結合在一起。

該狀態存在于內存中,因此實例化步驟就是將所有事物連接到內存。

首先,JS引擎創建一個模塊環境記錄。這將管理模塊記錄的變量。然后,它將在內存中找到所有導出的框。模塊環境記錄將跟蹤與每個導出關聯的內存中的哪個框。

內存中的這些框尚無法獲取其值。只有在評估之后,它們的實際值才會被填寫。該規則有一個警告:在此階段中初始化所有導出的函數聲明。這使評估工作變得更加容易。

為了實例化模塊圖,引擎將進行深度優先的后順序遍歷。這意味著它將下降到圖表的底部-底部的不依賴其他任何內容的依賴項-并設置其導出。

中間的一列空內存。 計數和顯示模塊的模塊環境記錄已連接到內存中的框。

引擎完成了模塊下面所有出口的接線-模塊所依賴的所有出口。然后,它返回一個級別,以連接來自該模塊的導入。

請注意,導出和導入均指向內存中的同一位置。首先連接出口,可以確保所有進口都可以連接到匹配的出口。

與上圖相同,但具有main.js的模塊環境記錄,現在其導入鏈接到其他兩個模塊的導出。

這不同于CommonJS模塊。在CommonJS中,整個導出對象在導出時被復制。這意味著導出的任何值(例如數字)都是副本。

這意味著,如果導出模塊以后更改了該值,則導入模塊將看不到該更改。

中間的內存中,有一個導出的通用JS模塊指向一個內存位置,然后將值復制到另一個內存位置,而導入的JS模塊則指向新位置

相反,ES模塊使用稱為實時綁定的東西。兩個模塊都指向內存中的相同位置。這意味著,當導出模塊更改值時,該更改將顯示在導入模塊中。

導出值的模塊可以隨時更改這些值,但是導入模塊不能更改其導入的值。話雖如此,如果模塊導入了一個對象,則它可以更改該對象上的屬性值。

導出模塊更改內存中的值。 導入模塊也嘗試但失敗。

之所以擁有這樣的實時綁定,是因為您可以在不運行任何代碼的情況下連接所有模塊。當您具有循環依賴性時,這將有助于評估,如下所述。

因此,在此步驟結束時,我們已連接了所有實例以及導出/導入變量的存儲位置。

現在我們可以開始評估代碼,并用它們的值填充這些內存位置。

4. 執行

最后一步是將這些框填充到內存中。JS引擎通過執行頂級代碼(函數外部的代碼)來實現此目的。

除了僅在內存中填充這些框外,評估代碼還可能觸發副作用。例如,模塊可能會調用服務器。

模塊將在功能之外進行編碼,標記為頂級代碼

由于存在潛在的副作用,您只需要評估模塊一次。與實例化中發生的鏈接可以完全相同的結果執行多次相反,評估可以根據您執行多少次而得出不同的結果。

這是擁有模塊映射的原因之一。模塊映射通過規范的URL緩存模塊,因此每個模塊只有一個模塊記錄。這樣可以確保每個模塊僅執行一次。與實例化一樣,這是深度優先的后遍歷。

那我們之前談到的那些周期呢?

在循環依賴關系中,您最終在圖中有一個循環。通常,這是一個漫長的循環。但是為了解釋這個問題,我將使用一個簡短的循環的人為例子。

左側為4個模塊循環的復雜模塊圖。 右側有一個簡單的2個模塊循環。

讓我們看一下如何將其與CommonJS模塊一起使用。首先,主模塊將執行直到require語句。然后它將去加載計數器模塊。

一個commonJS模塊,其變量是在require語句之后從main.js導出到counter.js的,具體取決于該導入

然后,計數器模塊將嘗試message從導出對象進行訪問。但是由于尚未在主模塊中對此進行評估,因此它將返回undefined。JS引擎將在內存中為局部變量分配空間,并將其值設置為undefined。

中間的內存,main.js和內存之間沒有連接,但是從counter.js到未定義的內存位置的導入鏈接

評估一直持續到計數器模塊頂級代碼的末尾。我們想看看我們是否最終將獲得正確的消息值(在評估main.js之后),因此我們設置了超時時間。然后評估在上恢復main.js。

counter.js將控制權返回給main.js,從而完成評估

消息變量將被初始化并添加到內存中。但是由于兩者之間沒有連接,因此在所需模塊中它將保持未定義狀態。

main.js獲取到內存的導出連接并填寫正確的值,但是counter.js仍指向其中未定義的其他內存位置

如果使用實時綁定處理導出,則計數器模塊最終將看到正確的值。到超時運行時,main.js的評估將完成并填寫值。

支持這些循環是ES模塊設計背后的重要理由。正是這種設計使它們成為可能。


(以上是關于 ESM 的理論介紹, 原文鏈接在文末)。

Bundle & Bundleless

談及 Bundleless 的優勢,首先是啟動快。

因為不需要過多的打包,只需要處理修改后的單個文件,所以響應速度是 O(1) 級別,刷新即可即時生效,速度很快。

image.png

所以, 在開發模式下,相比于Bundle,Bundleless 有著巨大的優勢。

基于 Webpack 的 bundle 開發模式

image.png
上面的圖具體的模塊加載機制可以簡化為下圖:
image.png
在項目啟動和有文件變化時重新進行打包,這使得項目的啟動和二次構建都需要做較多的事情,相應的耗時也會增長。

基于 ESModule 的 Bundleless 模式

image.png
從上圖可以看到,已經不再有一個構建好的 bundle、chunk 之類的文件,而是直接加載本地對應的文件。
image.png
從上圖可以看到,在 Bundleless 的機制下,項目的啟動只需要啟動一個服務器承接瀏覽器的請求即可,同時在文件變更時,也只需要額外處理變更的文件即可,其他文件可直接在緩存中讀取。

對比總結

image.png

Bundleless 模式可以充分利用瀏覽器自主加載的特性,跳過打包的過程,使得我們能在項目啟動時獲取到極快的啟動速度,在本地更新時只需要重新編譯單個文件。

實現一個乞丐版 Vite

Vite 也是基于 ESM 的, 文件處理速度 O(1)級別, 非???。

作為探索, 我就簡單實現了一個乞丐版Vite:

GitHub 地址: Vite-mini,

image.png

簡要分析一下。

<body>
  <div id="app"></div>
  <script type="module" data-original="/src/main.js"></script>
</body>

html 文件中直接使用了瀏覽器原生的 ESM(type="module") 能力。

所有的 js 文件經過 vite 處理后,其 import 的模塊路徑都會被修改,在前面加上 /@modules/。當瀏覽器請求 import 模塊的時候,vite 會在 node_modules 中找到對應的文件進行返回。

image.png

其中最關鍵的步驟就是模塊的記載和解析, 這里我簡單用koa簡單實現了一下, 整體結構:

const fs = require('fs');
const path = require('path');
const Koa = require('koa');
const compilerSfc = require('@vue/compiler-sfc');
const compileDom = require('@vue/compiler-dom');
const app = new Koa();

// 處理引入路徑
function rewriteImport(content) {
  // ...
}

// 處理文件類型等, 比如支持ts, less 等類似webpack的loader的功能
app.use(async (ctx) => {
  // ...
}

app.listen(3001, () => {
  console.log('3001');
});

我們先看路徑相關的處理:

function rewriteImport(content) {
    return content.replace(/from ['"]([^'"]+)['"]/g, function (s0, s1) {
        // import a from './c.js' 這種格式的不需要改寫
        // 只改寫需要去node_module找的
        if (s1[0] !== '.' && s1[0] !== '/') {
          return `from '/@modules/${s1}'`;
        }
        return s0;
    });
}

處理文件內容: 源碼地址

image.png

后續的都是類似的:

image.png

這個代碼只是解釋實現原理, 不同的文件類型處理邏輯其實可以抽離出去, 以中間件的形式去處理。

代碼實現的比較簡單, 就不額解釋了。

Snowpack

image.png

和 webpack 的對比:

image.png

我使用 Snowpack 做了個 demo , 支持打包, 輸出 bundle。

github: Snowpack-React-Demo

image.png

能夠清晰的看到, 控制臺產生了大量的文件請求(也叫瀑布網絡請求),

不過因為都是加載的本地文件, 所以速度很快。

配合HMR, 實現編輯完成立刻生效, 幾乎不用等待:

image.png

但是如果是在生產中,這些請求對于生產中的頁面加載時間而言, 就不太好了。

尤其是HTTP1.1,瀏覽器都會有并行下載的上限,大部分是5個左右,所以如果你有60個依賴性要下載,就需要等好長一點。

雖然說HTTP2多少可以改善這問題,但若是東西太多,依然沒辦法。

關于這個項目的打包, 直接執行build:

image.png

打包完成后的文件目錄,和傳統的 webpack 基本一致:

image.png

在 build 目錄下啟動一個靜態文件服務:

image.png

build 模式下,還是借助了 webpack 的打包能力:

image.png

做了資源合并:

image.png

就這點而言, 我認為未來一段時間內, 生產環境還是不可避免的要走bundle模式。

bundleless 模式在實際開發中的一些問題

開門見山吧, 開發體驗不是很友好,幾點比較突出的問題:

  • 部分模塊沒有提供 ESModule 的包。(這一點尤為致命)
  • 生態不夠健全,工具鏈不夠完善;

當然還有其他方方面面的問題, 就不一一列舉。

我簡單改造了一個頁面, 就遇到很多奇奇怪怪的問題, 開發起來十分難受, 盡管代碼的修改能立刻生效。

結論

bundleless 能在開發模式下帶了很大的便利。 但就目前來說,要運用到生產的話, 還是有一段路要走的。

就目當下而言, 如果真的要用的話,可能還是 bundleless(dev) + bundle(production) 的組合。

至于未來能不能全面鋪開 bundleless,我認為還是有可能的, 交給時間吧。

結尾

本文主要介紹了 esm 的原理, 以及介紹了以此為基礎的Vite, Snowpack 等工具, 提供了兩個可運行的 demo:

  1. Vite-mini,
  2. Snowpack-React-Demo

并探索了 bundleless 在生產中的可行性。

Bundleless, 本質上是將原先 Webpack 中模塊依賴解析的工作交給瀏覽器去執行,使得在開發過程中代碼的轉換變少,極大地提升了開發過程中的構建速度,同時也可以更好地利用瀏覽器的相關開發工具。

最后,也非常感謝 ESModule、Vite、Snowpack 等標準和工具的出現,為前端開發提效。

才疏學淺, 文中若有錯誤,還能各位大佬指正, 謝謝。

參考資料

  1. https://hacks.mozilla.org/201...
  2. https://developer.aliyun.com/...

如果你覺得這篇內容對你挺有啟發,可以:

  1. 點個「在看」,讓更多的人也能看到這篇內容。
  2. 關注公眾號「前端e進階」,掌握前端面試重難點,公眾號后臺回復「加群」和小伙伴們暢聊技術。

圖片

查看原文

贊 53 收藏 24 評論 7

jrainlau 發布了文章 · 2020-09-23

使用 babel 全家桶模塊化古老的面條代碼

image

在最近的工作中,接手了一個古老的項目,其中的 JS 代碼是一整坨的面條代碼,約 3000 行的代碼全寫在一個文件里,維護起來著實讓人頭疼。

image

想不通為啥之前維護項目的同學能夠忍受這么難以維護的代碼……既然現在這個鍋被我拿下了,怎么著也不能容忍如此丑陋的代碼繼續存在著,必須把它優化一下。

橫豎看了半天,由于邏輯都揉在了一個文件里,看都看得眼花繚亂,當務之急便是把它進行模塊化拆分,把這一大坨面條狀代碼拆分成一個個模塊并抽離成文件,這樣才方便后續的持續優化。

一、結構分析

說干就干,既然要拆分成模塊,首先就要分析源碼的結構。雖然源碼內容很長很復雜,但萬幸的是它還是有一個清晰的結構,簡化一下,就是下面這種形式:

code

很容易看出,這是一種 ES5 時代的經典代碼組織方式,在一個 IIFE 里面放一個構造函數,在構造函數的 protorype 上掛載不同的方法,以實現不同的功能。既然代碼結構是清晰的,那么我們要做模塊化的思路也很清晰,就是想辦法把所有綁定在構造函數的 prototype 上的方法抽離出來,以模塊文件的形式放置,而源碼則使用 ES6 的 import 語句把模塊引入進來,完成代碼的模塊化:

code

為了完成這個效果,我們可以借助 @babel 全家桶來構造我們的轉化腳本。

二、借助 AST 分析代碼

關于 AST 的相關資料一搜一大堆,在這里就不贅述了。在本文中,我們會借助 AST 去分析源碼,挑選源碼中需要被抽離、改造的部分,因此 AST 可以說是本文的核心。在 https://astexplorer.net/ 這個網站,我們可以貼入示例代碼,在線查看它的 AST 長什么樣:

image

從右側的 AST 樹中可以很清晰地看到,Demo.prototype.func = function () {} 屬于 AssignmentExpression 節點,即為“賦值語句”,擁有左右兩個不同的節點(left,right)。

由于一段 JS 代碼里可能存在多種賦值語句,而我們只想處理形如 Demo.prototype.func = function () {} 的情況,所以我們需要繼續對其左右兩側的節點進行深入分析。

首先看左側的節點,它屬于一個“MemberExpression”,其特征如下圖箭頭所示:

image

對于左側的節點,只要它的 object.property.name 的值為 prototype 即可,那么對應的函數名就是該節點的 property.name。

接著看右側的節點,它屬于一個“FunctionExpression”:
image

我們要做的,就是把它提取出來作為一個獨立的文件。

分析完了 AST 以后,我們已經知道需要被處理的代碼都有一些什么樣的特征,接下來就是針對這些特征進行操作了,這時候就需要我們的 @babel 全家桶出場了!

三、處理代碼

首先我們需要安裝四個工具,它們分別是:

  • @babel/parser:用于把 JS 源碼轉化成 AST;
  • @babel/traverse:用于遍歷 AST 樹,獲取當中的節點內容;
  • @babel/generator:把 AST 節點轉化成對應的 JS 代碼;
  • @babel/types:新建 AST 節點。

接下來新建一個 index.js 文件,引入上面四個工具,并設法加載我們的源碼(源碼為 demo/es5code.js):

const fs = require('fs')
const { resolve } = require('path')

const parser = require('@babel/parser')
const traverse = require('@babel/traverse').default
const generator = require('@babel/generator').default
const t = require('@babel/types')

const INPUT_CODE = resolve(__dirname, '../demo/es5code.js')

const code = fs.readFileSync(`${INPUT_CODE}`, 'utf-8')

接著使用 @babel/parser 獲取源碼的 AST:

const ast = parser.parse(code)

拿到 AST 以后,就可以使用 @babel/traverse 來遍歷它的節點。從上一節的 AST 分析可以知道,我們只需要關注“AssignmentExpression”節點即可:

traverse(ast, {
  AssignmentExpression ({ node }) {
    /* ... */
  }
})

當前節點即為參數 node,我們需要分析它左右兩側的節點。只有當左側節點的類型為“MemberExpression”且右側節點的類型為“FunctionExpression”才需要進入下一步分析(因為形如 a = 1 之類的節點也屬于 AssignmentExpression 類型,不在我們的處理范圍內)。

由于 JS 中可能存在不同的 MemberExpression 節點,如 a.b.c = function () {},但我們現在只需要處理 a.prototype.func 的情況,意味著要盯著關鍵字 prototype。通過分析 AST 節點,我們知道這個關鍵字位于左側節點的 object.property.name 屬性中:

image

同時對應的函數名則藏在左側節點的 property.name 屬性中:

image

因此便可以很方便地提取出方法名

traverse(ast, {
  AssignmentExpression ({ node }) {
    const { left, right } = node
    if (left.type === 'MemberExpression' && right.type === 'FunctionExpression') {
      const { object, property } = left
      if (object.property.name === 'prototype') {
        const funcName = property.name // 提取出方法名
        console.log(funcName)
      }
    }
  }
})

可以很方便地把方法名打印出來檢查:

image

現在我們已經分析完左側節點的代碼,提取出了方法名。接下來則是處理右側節點。由于右側代碼直接就是一個 FunctionExpression 節點,因此我們要做的就是通過 @babel/generator 把該節點轉化成 JS 代碼,并寫入文件。

此外,我們也要把原來的代碼從 Demo.prototype.func = function () {} 轉化成 Demo.prototype.func = func 的形式,因此右側的節點需要從“FuncitionExpression”類型轉化成“Identifier”類型,我們可以借助 @babel/types 來處理。

還有一個事情別忘了,就是我們已經把右側節點的代碼抽離成了 JS 文件,那么我們也應該在最終改造完的源文件里把它們給引入進來,形如 import func1 from './func1' 這種形式,因此可以繼續使用 @babel/typesimportDeclaration() 函數來生成對應的代碼。這個函數參數比較復雜,可以封裝成一個函數:

function createImportDeclaration (funcName) {
  return t.importDeclaration([t.importDefaultSpecifier(t.identifier(funcName))], t.stringLiteral(`./${funcName}`))
}

只需要傳入一個 funcName,就可以生成一段 import funcName from './funcName' 代碼。

最終整體代碼如下:

const fs = require('fs')
const { resolve } = require('path')

const parser = require('@babel/parser')
const traverse = require('@babel/traverse').default
const generator = require('@babel/generator').default
const t = require('@babel/types')

const INPUT_CODE = resolve(__dirname, '../demo/es5code.js')
const OUTPUT_FOLDER = resolve(__dirname, '../output')

const code = fs.readFileSync(`${INPUT_CODE}`, 'utf-8')
const ast = parser.parse(code)

function createFile (filename, code) {
  fs.writeFileSync(`${OUTPUT_FOLDER}/${filename}.js`, code, 'utf-8')
}

function createImportDeclaration (funcName) {
  return t.importDeclaration([t.importDefaultSpecifier(t.identifier(funcName))], t.stringLiteral(`./${funcName}`))
}

traverse(ast, {
  AssignmentExpression ({ node }) {
    const { left, right } = node
    if (left.type === 'MemberExpression' && right.type === 'FunctionExpression') {
      const { object, property } = left
      if (object.property.name === 'prototype') {    
        // 獲取左側節點的方法名
        const funcName = property.name
        // 獲取右側節點對應的 JS 代碼
        const { code: funcCode } = generator(right)
        // 右側節點改為 Identifier
        const replacedNode = t.identifier(funcName)
        node.right = replacedNode
       
        // 借助 `fs.writeFileSync()` 把右側節點的 JS 代碼寫入外部文件
        createFile(funcName, 'export default ' + funcCode)

        // 在文件頭部引入抽離的文件
        ast.program.body.unshift(createImportDeclaration(funcName))
      }
    }
  }
})

// 輸出新的文件
createFile('es6code', generate(ast).code)

四、運行腳本

在我們的項目目錄中,其結構如下:

.
├── demo
│   └── es5code.js
├── output
├── package.json
└── src
    └── index.js

運行腳本,demo/es5code.js 的代碼將會被處理,然后輸出到 output 目錄:

.
├── demo
│   └── es5code.js
├── output
│   ├── es6code.js
│   ├── func1.js
│   ├── func2.js
│   └── func3.js
├── package.json
└── src
    └── index.js

看看我們的代碼:
image

image

大功告成!把腳本運用到我們的項目中,甚至可以發現原來的約 3000 行代碼,已經被整理成了 300 多行:

image

放到真實環境去跑一遍這段代碼,原有功能不受影響!

小結

剛剛接手這個項目,我的內心是一萬頭神獸奔騰而過,內心是非常崩潰的。但是既然接手了,就值得好好對待它。借助 AST 和 @babel 全家桶,我們就有了充分改造源碼的手段?;ò雮€小時個腳本,把丑陋的面條代碼整理成清晰的模塊化代碼,內心的陰霾一掃而空,對這個古老的項目更是充滿了期待——會不會有更多的地方可以被改造被優化呢?值得拭目以待!

查看原文

贊 13 收藏 7 評論 4

jrainlau 發布了文章 · 2020-07-29

【譯】如何用 JavaScript 來解析 URL

原文鏈接:https://dmitripavlutin.com/pa...

統一資源定位符,縮寫為URL,是對網絡資源(網頁、圖像、文件)的引用。URL指定資源位置和檢索資源的機制(http、ftp、mailto)。

舉個例子,這里是這篇文章的 URL 地址:

https://dmitripavlutin.com/parse-url-javascript

很多時候你需要獲取到一段 URL 的某個組成部分。它們可能是 hostname(例如 dmitripavlutin.com),或者 pathname(例如 /parse-url-javascript)。

一個方便的用于獲取 URL 組成部分的辦法是通過 URL() 構造函數。

在這篇文章中,我將給大家展示一段 URL 的結構,以及它的主要組成部分。

接著,我會告訴你如何使用 URL() 構造函數來輕松獲取 URL 的組成部分,比如 hostname,pathname,query 或者 hash。

1. URL 結構

一圖勝千言。不需要過多的文字描述,通過下面的圖片你就可以理解一段 URL 的各個組成部分:

image

2. URL() 構造函數

URL() 構造函數允許我們用它來解析一段 URL:

const url = new URL(relativeOrAbsolute [, absoluteBase]);

參數 relativeOrAbsolute 既可以是絕對路徑,也可以是相對路徑。如果第一個參數是相對路徑的話,那么第二個參數 absoluteBase 則必傳,且必須為第一個參數的絕對路徑。

舉個例子,讓我們用一個絕對路徑的 URL 來初始化 URL() 函數:

const url = new URL('http://example.com/path/index.html');

url.href; // => 'http://example.com/path/index.html'

或者我們可以使用相對路徑和絕對路徑:

const url = new URL('/path/index.html', 'http://example.com');

url.href; // => 'http://example.com/path/index.html'

URL() 實例中的 href 屬性返回了完整的 URL 字符串。

在新建了 URL() 的實例以后,你可以用它來訪問前文圖片中的任意 URL 組成部分。作為參考,下面是 URL() 實例的接口列表:

interface URL {
  href:     USVString;
  protocol: USVString;
  username: USVString;
  password: USVString;
  host:     USVString;
  hostname: USVString;
  port:     USVString;
  pathname: USVString;
  search:   USVString;
  hash:     USVString;

  readonly origin: USVString;
  readonly searchParams: URLSearchParams;

  toJSON(): USVString;
}

上述的 USVString 參數在 JavaScript 中會映射成字符串。

3. Query 字符串

url.search 可以獲取到 URL 當中 ? 后面的 query 字符串:

const url = new URL(
  'http://example.com/path/index.html?message=hello&who=world'
);

url.search; // => '?message=hello&who=world'

如果 query 參數不存在,url.search 默認會返回一個空字符串 ''

const url1 = new URL('http://example.com/path/index.html');
const url2 = new URL('http://example.com/path/index.html?');

url1.search; // => ''
url2.search; // => ''

3.1 解析 query 字符串

相比于獲得原生的 query 字符串,更實用的場景是獲取到具體的 query 參數。

獲取具體 query 參數的一個簡單的方法是利用 url.searchParams 屬性。這個屬性是 URLSearchParams 的實例。

URLSearchParams 對象提供了許多用于獲取 query 參數的方法,如get(param),has(param)等。

下面來看個例子:

const url = new URL(
  'http://example.com/path/index.html?message=hello&who=world'
);

url.searchParams.get('message'); // => 'hello'
url.searchParams.get('missing'); // => null

url.searchParams.get('message') 返回了 message 這個 query 參數的值——hello。

如果使用 url.searchParams.get('missing') 來獲取一個不存在的參數,則得到一個 null。

4. hostname

url.hostname 屬性返回一段 URL 的 hostname 部分:

const url = new URL('http://example.com/path/index.html');

url.hostname; // => 'example.com'

5. pathname

url. pathname 屬性返回一段 URL 的 pathname 部分:

const url = new URL('http://example.com/path/index.html?param=value');

url.pathname; // => '/path/index.html'

如果這段 URL 不含 path,則該屬性返回一個斜杠 /

const url = new URL('http://example.com/');

url.pathname; // => '/'

6. hash

最后,我們可以通過 url.hash 屬性來獲取 URL 中的 hash 值:

const url = new URL('http://example.com/path/index.html#bottom');

url.hash; // => '#bottom'

當 URL 中的 hash 不存在時,url.hash 屬性會返回一個空字符串 ''

const url = new URL('http://example.com/path/index.html');

url.hash; // => ''

7. URL 校驗

當使用 new URL() 構造函數來新建實例的時候,作為一種副作用,它同時也會對 URL 進行校驗。如果 URL 不合法,則會拋出一個 TypeError。

舉個例子,http ://example.com 是一段非法 URL,因為它在 http 后面多寫了一個空格。

讓我們用這個非法 URL 來初始化 URL() 構造函數:

try {
  const url = new URL('http ://example.com');
} catch (error) {
  error; // => TypeError, "Failed to construct URL: Invalid URL"
}

因為 http ://example.com 是一段非法 URL,跟我們想的一樣,new URL() 拋出了一個 TypeError。

8. 修改 URL

除了獲取 URL 的組成部分以外,像 search,hostname,pathnamehash 這些屬性都是可寫的——這也意味著你可以修改 URL。

舉個例子,讓我們把一段 URL 從 red.com 修改成 blue.io

const url = new URL('http://red.com/path/index.html');

url.href; // => 'http://red.com/path/index.html'

url.hostname = 'blue.io';

url.href; // => 'http://blue.io/path/index.html'

注意,在 URL() 實例中只有 originsearchParams 屬性是只讀的,其他所有的屬性都是可寫的,并且會修改原來的 URL。

9. 總結

URL() 構造函數是 JavaScript 中的一個能夠很方便地用于解析(或者校驗)URL 的工具。

new URL(relativeOrAbsolute [, absoluteBase]) 中的第一個參數接收 URL 的絕對路徑或者相對路徑。當第一個參數是相對路徑時,第二個參數必傳且必須為第一個參數的基路徑。

在新建 URL() 的實例以后,你就能很輕易地獲得 URL 當中的大部分組成部分了,比如:

  • url.search 獲取原生的 query 字符串
  • url.searchParams 通過 URLSearchParams 的實例去獲取具體的 query 參數
  • url.hostname獲取 hostname
  • url.pathname 獲取 pathname
  • url.hash 獲取 hash 值

那么你最愛用的解析 URL 的 JavaScript 工具又是什么呢?

查看原文

贊 7 收藏 6 評論 2

jrainlau 發布了文章 · 2020-01-14

【譯】用Node.js編寫內存效率高的應用程序

一座被設計為能避開氣流的建筑 (https://pixelz.cc)

軟件應用程序在計算機的主存儲器中運行,我們稱之為隨機存取存儲器(RAM)。JavaScript,尤其是 NodeJS (服務端 JS)允許我們為終端用戶編寫從小型到大型的軟件項目。處理程序的內存總是一個棘手的問題,因為糟糕的實現可能會阻塞在給定服務器或系統上運行的所有其他應用程序。C 和 C++ 程序員確實關心內存管理,因為隱藏在代碼的每個角落都有可能出現可怕的內存泄漏。但是對于 JS 開發者來說,你真的有關心過這個問題嗎?

由于 JS 開發人員通常在專用的高容量服務器上進行 web 服務器編程,他們可能不會察覺多任務處理的延遲。比方說在開發 web 服務器的情況下,我們也會運行多個應用程序,如數據庫服務器( MySQL )、緩存服務器( Redis )和其他需要的應用。我們需要知道它們也會消耗可用的主內存。如果我們隨意地編寫應用程序,很可能會降低其他進程的性能,甚至讓內存完全拒絕對它們的分配。在本文中,我們通過解決一個問題來了解 NodeJS 的流、緩沖區和管道等結構,并了解它們分別如何支持編寫內存有效的應用程序。

我們使用 NodeJS v8.12.0 來運行這些程序,所有代碼示例都放在這里:

narenaryan/node-backpressure-internals

原文鏈接:Writing memory efficient software applications in Node.js

問題:大文件復制

如果有人被要求用 NodeJS 寫一段文件復制的程序,那么他會迅速寫出下面這段代碼:

const fs = require('fs');

let fileName = process.argv[2];
let destPath = process.argv[3];

fs.readFile(fileName, (err, data) => {
    if (err) throw err;

    fs.writeFile(destPath || 'output', data, (err) => {
        if (err) throw err;
    });
    
    console.log('New file has been created!');
});

這段代碼簡單地根據輸入的文件名和路徑,在嘗試對文件讀取后把它寫入目標路徑,這對于小文件來說是不成問題的。

現在假設我們有一個大文件(大于4 GB)需要用這段程序來進行備份。就以我的一個達 7.4G 的超高清4K 電影為例子好了,我用上述的程序代碼把它從當前目錄復制到別的目錄。

$ node basic_copy.js cartoonMovie.mkv ~/Documents/bigMovie.mkv

然后在 Ubuntu(Linux )系統下我得到了這段報錯:

/home/shobarani/Workspace/basic_copy.js:7
    if (err) throw err;
             ^
RangeError: File size is greater than possible Buffer: 0x7fffffff bytes
    at FSReqWrap.readFileAfterStat [as oncomplete] (fs.js:453:11)

正如你看到的那樣,由于 NodeJS 最大只允許寫入 2GB 的數據到它的緩沖區,導致了錯誤發生在讀取文件的過程中。為了解決這個問題,當你在進行 I/O 密集操作的時候(復制、處理、壓縮等),最好考慮一下內存的情況。

NodeJS 中的 Streams 和 Buffers

為了解決上述問題,我們需要一個辦法把大文件切成許多文件塊,同時需要一個數據結構去存放這些文件塊。一個 buffer 就是用來存儲二進制數據的結構。接下來,我們需要一個讀寫文件塊的方法,而 Streams 則提供了這部分能力。

Buffers(緩沖區)

我們能夠利用 Buffer 對象輕松地創建一個 buffer。

let buffer = new Buffer(10); # 10 為 buffer 的體積
console.log(buffer); # prints <Buffer 00 00 00 00 00 00 00 00 00 00>

在新版本的 NodeJS (>8)中,你也可以這樣寫。

let buffer = new Buffer.alloc(10);
console.log(buffer); # prints <Buffer 00 00 00 00 00 00 00 00 00 00>

如果我們已經有了一些數據,比如數組或者別的數據集,我們可以為它們創建一個 buffer。

let name = 'Node JS DEV';
let buffer = Buffer.from(name);
console.log(buffer) # prints <Buffer 4e 6f 64 65 20 4a 53 20 44 45 5>

Buffers 有一些如 buffer.toString()buffer.toJSON() 之類的重要方法,能夠深入到其所存儲的數據當中去。

我們不會為了優化代碼而去直接創建原始 buffer。NodeJS 和 V8 引擎在處理 streams 和網絡 socket 的時候就已經在創建內部緩沖區(隊列)中實現了這一點。

Streams(流)

簡單來說,流就像 NodeJS 對象上的任意門。在計算機網絡中,入口是一個輸入動作,出口是一個輸出動作。我們接下來將繼續使用這些術語。

流的類型總共有四種:

  • 可讀流(用于讀取數據)
  • 可寫流(用于寫入數據)
  • 雙工流(同時可用于讀寫)
  • 轉換流(一種用于處理數據的自定義雙工流,如壓縮,檢查數據等)

下面這句話可以清晰地闡述為什么我們應該使用流。

Stream API (尤其是 stream.pipe() 方法)的一個重要目標是將數據緩沖限制在可接受的水平,這樣不同速度的源和目標就不會阻塞可用內存。

我們需要一些辦法去完成任務而不至于壓垮系統。這也是我們在文章開頭就已經提到過的。

image

上面的示意圖中我們有兩個類型的流,分別是可讀流和可寫流。.pipe() 方法是一個非?;镜姆椒?,用于連接可讀流和可寫流。如果你不明白上面的示意圖,也沒關系,在看完我們的例子以后,你可以回到示意圖這里來,那個時候一切都會顯得理所當然。管道是一種引人注目的機制,下面我們用兩個例子來說明它。

解法1(簡單地使用流來復制文件)

讓我們設計一種解法來解決前文中大文件復制的問題。首先我們要創建兩個流,然后執行接下來的幾個步驟。

  1. 監聽來自可讀流的數據塊
  2. 把數據塊寫進可寫流
  3. 跟蹤文件復制的進度

我們把這段代碼命名為 streams_copy_basic.js

/*
    A file copy with streams and events - Author: Naren Arya
*/

const stream = require('stream');
const fs = require('fs');

let fileName = process.argv[2];
let destPath = process.argv[3];

const readabale = fs.createReadStream(fileName);
const writeable = fs.createWriteStream(destPath || "output");

fs.stat(fileName, (err, stats) => {
    this.fileSize = stats.size;
    this.counter = 1;
    this.fileArray = fileName.split('.');
    
    try {
        this.duplicate = destPath + "/" + this.fileArray[0] + '_Copy.' + this.fileArray[1];
    } catch(e) {
        console.exception('File name is invalid! please pass the proper one');
    }
    
    process.stdout.write(`File: ${this.duplicate} is being created:`);
    
    readabale.on('data', (chunk)=> {
        let percentageCopied = ((chunk.length * this.counter) / this.fileSize) * 100;
        process.stdout.clearLine();  // clear current text
        process.stdout.cursorTo(0);
        process.stdout.write(`${Math.round(percentageCopied)}%`);
        writeable.write(chunk);
        this.counter += 1;
    });
    
    readabale.on('end', (e) => {
        process.stdout.clearLine();  // clear current text
        process.stdout.cursorTo(0);
        process.stdout.write("Successfully finished the operation");
        return;
    });
    
    readabale.on('error', (e) => {
        console.log("Some error occured: ", e);
    });
    
    writeable.on('finish', () => {
        console.log("Successfully created the file copy!");
    });
    
});

在這段程序中,我們接收用戶傳入的兩個文件路徑(源文件和目標文件),然后創建了兩個流,用于把數據塊從可讀流運到可寫流。然后我們定義了一些變量去追蹤文件復制的進度,然后輸出到控制臺(此處為 console)。與此同時我們還訂閱了一些事件:

data:當一個數據塊被讀取時觸發

end:當一個數據塊被可讀流所讀取完的時候觸發

error:當讀取數據塊的時候出錯時觸發

運行這段程序,我們可以成功地完成一個大文件(此處為7.4 G)的復制任務。

$ time node streams_copy_basic.js cartoonMovie.mkv ~/Documents/4kdemo.mkv

然而,當我們通過任務管理器觀察程序在運行過程中的內存狀況時,依舊有一個問題。

image

4.6GB?我們的程序在運行時所消耗的內存,在這里是講不通的,以及它很有可能會卡死其他的應用程序。

發生了什么?

如果你有仔細觀察上圖中的讀寫率,你會發現一些端倪。

Disk Read: 53.4 MiB/s

Disk Write: 14.8 MiB/s

這意味著生產者正在以更快的速度生產,而消費者無法跟上這個速度。計算機為了保存讀取的數據塊,將多余的數據存儲到機器的RAM中。這就是RAM出現峰值的原因。

上述代碼在我的機器上運行了3分16秒……

17.16s user 25.06s system 21% cpu 3:16.61 total

解法2(基于流和自動背壓的文件復制)

為了克服上述問題,我們可以修改程序來自動調整磁盤的讀寫速度。這個機制就是背壓。我們不需要做太多,只需將可讀流導入可寫流即可,NodeJS 會負責背壓的工作。

讓我們將這個程序命名為 streams_copy_efficient.js

/*
    A file copy with streams and piping - Author: Naren Arya
*/

const stream = require('stream');
const fs = require('fs');

let fileName = process.argv[2];
let destPath = process.argv[3];

const readabale = fs.createReadStream(fileName);
const writeable = fs.createWriteStream(destPath || "output");

fs.stat(fileName, (err, stats) => {
    this.fileSize = stats.size;
    this.counter = 1;
    this.fileArray = fileName.split('.');
    
    try {
        this.duplicate = destPath + "/" + this.fileArray[0] + '_Copy.' + this.fileArray[1];
    } catch(e) {
        console.exception('File name is invalid! please pass the proper one');
    }
    
    process.stdout.write(`File: ${this.duplicate} is being created:`);
    
    readabale.on('data', (chunk) => {
        let percentageCopied = ((chunk.length * this.counter) / this.fileSize) * 100;
        process.stdout.clearLine();  // clear current text
        process.stdout.cursorTo(0);
        process.stdout.write(`${Math.round(percentageCopied)}%`);
        this.counter += 1;
    });
    
    readabale.pipe(writeable); // Auto pilot ON!
    
    // In case if we have an interruption while copying
    writeable.on('unpipe', (e) => {
        process.stdout.write("Copy has failed!");
    });
    
});

在這個例子中,我們用一句代碼替換了之前的數據塊寫入操作。

readabale.pipe(writeable); // Auto pilot ON!

這里的 pipe 就是所有魔法發生的原因。它控制了磁盤讀寫的速度以至于不會阻塞內存(RAM)。

運行一下。

$ time node streams_copy_efficient.js cartoonMovie.mkv ~/Documents/4kdemo.mkv

我們復制了同一個大文件(7.4 GB),讓我們來看看內存利用率。

image

震驚!現在 Node 程序僅僅占用了61.9 MiB 的內存。如果你觀察到讀寫速率的話:

Disk Read: 35.5 MiB/s

Disk Write: 35.5 MiB/s

在任意給定的時間內,因為背壓的存在,讀寫速率得以保持一致。更讓人驚喜的是,這段優化后的程序代碼整整比之前的快了13秒。

12.13s user 28.50s system 22% cpu 3:03.35 total
由于 NodeJS 流和管道,內存負載減少了98.68%,執行時間也減少了。這就是為什么管道是一個強大的存在。

61.9 MiB 是由可讀流創建的緩沖區大小。我們還可以使用可讀流上的 read 方法為緩沖塊分配自定義大小。

const readabale = fs.createReadStream(fileName);
readable.read(no_of_bytes_size);

除了本地文件的復制以外,這個技術還可以用于優化許多 I/O 操作的問題:

  • 處理從卡夫卡到數據庫的數據流
  • 處理來自文件系統的數據流,動態壓縮并寫入磁盤
  • 更多……

源碼(Git)

你可以在我的倉庫底下找到所有的例子并在自己的機器上測試。
narenaryan/node-backpressure-internals

結論

我寫這篇文章的動機,主要是為了說明即使 NodeJS 提供了很好的 API,我們也可能會一不留神就寫出性能很差的代碼。如果我們能更多地關注其內置的工具,我們便可以更好地優化程序的運行方式。

你在此可以找到更多關于“背壓”的資料:
backpressuring-in-streams

完。

查看原文

贊 30 收藏 19 評論 5

jrainlau 贊了文章 · 2019-12-09

有趣的6種圖片灰度轉換算法

本文轉載自blog

轉載請注明出處

圖片描述

前言

黑白照片的時代雖然已經過去,但現在看到以前的照片,是不是有一種回到過去的感覺,很cool有木有~
看完這篇文章,就可以把彩色照片變成各種各樣的黑白的照片啦。

本文完整的在線例子圖片灰度算法例子,例子的圖片有點多,可能有些慢。

例子的源碼位于blog/demo

三原色與灰度

原色是指不能透過其他顏色的混合調配而得出的“基本色”。一般來說疊加型的三原色是紅色、綠色、藍色,以不同比例將原色混合,可以產生出其他的新顏色。這套原色系統常被稱為“RGB色彩空間”,亦即由紅(R)綠(G)藍(B)所組合出的色彩系統。

當這三種原色以等比例疊加在一起時,會變成灰色;若將此三原色的強度均調至最大并且等量重疊時,則會呈現白色?;叶染褪菦]有色彩,RGB色彩分量全部相等。

獲取圖片的像素數據

算法不區分語言,這里以前端舉例??梢允褂?code>canvas取得圖片某個區域的像素數據

//偽代碼
var img = new Image();
img.src = 'xxx.jpg';
var myCanvas = document.querySelector(canvasId);
var canvasCtx = myCanvas.getContext("2d");
canvasCtx.drawImage(img, 0, 0, img.width, img.height);
//圖片的像素數據
var data = canvasCtx.getImageData(0, 0, img.width, img.height);

使用getImageData()返回一個ImageData對象,此對象有個data屬性就是我們要的數據了,數據是以Uint8ClampedArray 描述的一個一維數組,包含以 RGBA 順序的數據,數據使用 0 至 255(包含)的整數表示。 所以,一個像素會有4個數據(RGBA),RGB是紅綠藍,A指的是透明度。

舉個例子:本文720480的水果圖片,一共有720 480 = 259200像素,每個像素又有4個數據,所以數據數組的總長度為259200 * 4 = 1036800。

可以看到圖片的數據很長,如果一次性處理很多圖片的時候,計算量相當可觀,所以例子中會使用worker,把繁重的計算任務交給后臺線程。

算法的基本步驟

  1. 取得每一個像素的red,green,blue值。

  2. 使用灰度算法,算出一個灰度值。

  3. 用這個灰度值代替像素原始的red,green,blue值。

比如我們的灰度算法是:

Gray = (Red + Green + Blue) / 3

計算過程:

//偽代碼
for(var Pixel in Image){
  var Red = Image[Pixel].Red
  var Green = Image[Pixel].Green
  var Blue = Image[Pixel].Blue

  var Gray = (Red + Green + Blue) / 3

  Image[Pixel].Red = Gray
  Image[Pixel].Green = Gray
  Image[Pixel].Blue = Gray
}

很簡單對吧。

很多好吃的鮮艷水果,但是它們馬上要變灰了??!

fruits

算法1 - 平均法

使用算法1:

算法1

這是最常見的灰度算法,簡單暴力,把它放到第一位。公式是:

 Gray = (Red + Green + Blue) / 3

這個算法可以生成不錯灰度值,因為公式簡單,所以易于維護和優化。然而它也不是沒有缺點,因為簡單快速,從人眼的感知角度看,圖片的灰度陰影和亮度方面做的還不夠好。所以,我們需要更復雜的運算。

算法2 - 基于人眼感知

使用算法2:

算法2

算法1與算法2生成的圖片似乎沒太大差別,所以增加一個例子,將圖片上半部分用算法1,下半部分用算法2。

上半部分是算法1,下半部分是算法2:

算法1+算法2

仔細看的話,中間有一根黑線。上半部分(算法1)比下半部分(算法2)更蒼白一些。如果還是看不出來,注意最右邊的檸檬,算法1的檸檬反光更強烈,算法2的檸檬更柔和。

第二種算法考慮到了人眼對不同光感知程度不同。人的眼睛內有幾種辨別顏色的錐形感光細胞,分別對黃綠色、綠色和藍紫色的光最敏感。雖然眼球中的椎狀細胞并非對紅、綠、藍三色的感受度最強,但是由肉眼的椎狀細胞所能感受的光的帶寬很大,紅、綠、藍也能夠獨立刺激這三種顏色的受光體。

人類對紅綠藍三色的感知程度依次是: 綠>紅>藍,所以平均算法從這個角度看是不科學的。應該按照人類對光的感知程度為每個顏色設定一個權重,它們的之間的地位不應該是平等的。

一個圖像處理通用的公式是:

Gray = (Red * 0.3 + Green * 0.59 + Blue * 0.11)

可以看到,每個顏色的系數相差很大。

現在對圖像灰度處理的最佳公式還存在爭議,有一些類似的公式:

Gray = (Red * 0.2126 + Green * 0.7152 + Blue * 0.0722)

or

Gray = (Red * 0.299 + Green * 0.587 + Blue * 0.114)

它們只是在系數上存在一些偏差,大體的比值差不多。

算法3 - 去飽和

使用算法3:

算法3

在說這個算法之前,先說說RGB,大多數程序員都使用RGB模型,每一種顏色都可以由紅綠藍組成,RGB對計算機來說可以很好的描述顏色,但對于人類而言就很難理解了。如果升國旗的時候說,“五星紅旗多么RGB(255, 0, 42)”,可能會被暴打一頓。但我說鮮紅的五星紅旗,老師可能會點頭稱贊。

所以為了更通俗易懂,有時我們選擇HLS模型描述顏色,這三個字母分別表示Hue(色調)、Saturation(飽和度)、Lightness(亮度)。色調,取值為:0 - 360,0(或360)表示紅色,120表示綠色,240表示藍色,也可取其他數值來指定顏色。飽和度,取值為:0.0% - 100.0%,它通常指顏色的鮮艷程度。亮度,取值為:0.0% - 100.0%,黑色的亮度為0。

去飽和的過程就是把RGB轉換為HLS,然后將飽和度設為0。因此,我們需要取一種顏色,轉換它為最不飽和的值。這個數學公式比本文介紹的更復雜,這里提供一個簡單的公式,一個像素可以被去飽和通過計算RGB中的最大值和最小值的中間值:

Gray = ( Math.max(Red, Green, Blue) + Math.min(Red, Green, Blue) ) / 2

去飽和后,圖片立體感減弱,但是更柔和。對比算法2,可以很明顯的看出差異,從效果上看,可能大多數人都喜歡算法2,算法3是目前為止,處理的圖片立體感最弱,最黑暗的。

算法4 - 分解

取最大值

算法4max

取最小值

算法4min

分解算法可以認為是去飽和更簡單一種的方式。分解是基于每一個像素的,只取RGB的最大值或者最小值。

最大值分解:

Gray = Math.max(Red, Green, Blue)

最小值分解:

Gray = Math.min(Red, Green, Blue)

正如上面展現的,最大值分解提供了更明亮的圖,而最小值分解提供了更黑暗的圖。

算法5 - 單一通道

取紅色通道

算法5red

取綠色通道

算法5green

取藍色通道

算法5blue

圖片變灰更快捷的方法,這個方法不用做任何計算,取一個通道的值直接作為灰度值。

Gray = Red

or

Gray = Green

or

Gray = Blue

不管相不相信,大多數數碼相機都用這個算法生成灰度圖片。很難預測這種轉換的結果,所以這種算法多用于藝術效果。

算法6 - 自定義灰度陰影

NumberOfShades = 4

算法6a

這是到目前為止最有趣的算法,允許用戶提供一個灰色陰影值,值的范圍在2-256。2的結果是一張全白的圖片,256的結果和算法1一樣。

NumberOfShades = 16

算法6b

該算法通過選擇陰影值來工作,它的公式有點復雜

ConversionFactor = 255 / (NumberOfShades - 1)
AverageValue = (Red + Green + Blue) / 3
Gray = Math.round((AverageValue / ConversionFactor) + 0.5) * ConversionFactor
  • NumberOfShades 的范圍在2-256。

  • 從技術上說,任何灰度算法都可以計算AverageValue,它僅僅提供一個初始灰度的估計值。

  • “+ 0.5” 是一個可選參數,用于模擬四舍五入。

小節

這是一篇很有趣的文章,不僅僅是介紹灰度算法,對了解圖片的處理過程也很有幫助。

References

查看原文

贊 7 收藏 17 評論 0

jrainlau 發布了文章 · 2019-12-09

利用 JS 實現多種圖片相似度算法

image

在搜索領域,早已出現了“查找相似圖片/相似商品”的相關功能,如 Google 搜圖,百度搜圖,淘寶的拍照搜商品等。要實現類似的計算圖片相似度的功能,除了使用聽起來高大上的“人工智能”以外,其實通過 js 和幾種簡單的算法,也能八九不離十地實現類似的效果。

在閱讀本文之前,強烈建議先閱讀完阮一峰于多年所撰寫的《相似圖片搜索的原理》相關文章,本文所涉及的算法也來源于其中。

體驗地址:https://img-compare.netlify.com/

特征提取算法

為了便于理解,每種算法都會經過“特征提取”和“特征比對”兩個步驟進行。接下來將著重對每種算法的“特征提取”步驟進行詳細解讀,而“特征比對”則單獨進行闡述。

平均哈希算法

參考阮大的文章,“平均哈希算法”主要由以下幾步組成:

第一步,縮小尺寸為8×8,以去除圖片的細節,只保留結構、明暗等基本信息,摒棄不同尺寸、比例帶來的圖片差異。

第二步,簡化色彩。將縮小后的圖片轉為灰度圖像。

第三步,計算平均值。計算所有像素的灰度平均值。

第四步,比較像素的灰度。將64個像素的灰度,與平均值進行比較。大于或等于平均值,記為1;小于平均值,記為0。

第五步,計算哈希值。將上一步的比較結果,組合在一起,就構成了一個64位的整數,這就是這張圖片的指紋。

第六步,計算哈希值的差異,得出相似度(漢明距離或者余弦值)。

明白了“平均哈希算法”的原理及步驟以后,就可以開始編碼工作了。為了讓代碼可讀性更高,本文的所有例子我都將使用 typescript 來實現。

圖片壓縮:

我們采用 canvas 的 drawImage() 方法實現圖片壓縮,后使用 getImageData() 方法獲取 ImageData 對象。

export function compressImg (imgSrc: string, imgWidth: number = 8): Promise<ImageData> {
  return new Promise((resolve, reject) => {
    if (!imgSrc) {
      reject('imgSrc can not be empty!')
    }
    const canvas = document.createElement('canvas')
    const ctx = canvas.getContext('2d')
    const img = new Image()
    img.crossOrigin = 'Anonymous'
    img.onload = function () {
      canvas.width = imgWidth
      canvas.height = imgWidth
      ctx?.drawImage(img, 0, 0, imgWidth, imgWidth)
      const data = ctx?.getImageData(0, 0, imgWidth, imgWidth) as ImageData
      resolve(data)
    }
    img.src = imgSrc
  })
}

可能有讀者會問,為什么使用 canvas 可以實現圖片壓縮呢?簡單來說,為了把“大圖片”繪制到“小畫布”上,一些相鄰且顏色相近的像素往往會被刪減掉,從而有效減少了圖片的信息量,因此能夠實現壓縮的效果:
image

在上面的 compressImg() 函數中,我們利用 new Image() 加載圖片,然后設定一個預設的圖片寬高值讓圖片壓縮到指定的大小,最后獲取到壓縮后的圖片的 ImageData 數據——這也意味著我們能獲取到圖片的每一個像素的信息。

關于 ImageData,可以參考 MDN 的文檔介紹。

圖片灰度化

為了把彩色的圖片轉化成灰度圖,我們首先要明白“灰度圖”的概念。在維基百科里是這么描述灰度圖像的:

在計算機領域中,灰度(Gray scale)數字圖像是每個像素只有一個采樣顏色的圖像。

大部分情況下,任何的顏色都可以通過三種顏色通道(R, G, B)的亮度以及一個色彩空間(A)來組成,而一個像素只顯示一種顏色,因此可以得到“像素 => RGBA”的對應關系。而“每個像素只有一個采樣顏色”,則意味著組成這個像素的三原色通道亮度相等,因此只需要算出 RGB 的平均值即可:

// 根據 RGBA 數組生成 ImageData
export function createImgData (dataDetail: number[]) {
  const canvas = document.createElement('canvas')
  const ctx = canvas.getContext('2d')
  const imgWidth = Math.sqrt(dataDetail.length / 4)
  const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData
  for (let i = 0; i < dataDetail.length; i += 4) {
    let R = dataDetail[i]
    let G = dataDetail[i + 1]
    let B = dataDetail[i + 2]
    let Alpha = dataDetail[i + 3]

    newImageData.data[i] = R
    newImageData.data[i + 1] = G
    newImageData.data[i + 2] = B
    newImageData.data[i + 3] = Alpha
  }
  return newImageData
}

export function createGrayscale (imgData: ImageData) {
  const newData: number[] = Array(imgData.data.length)
  newData.fill(0)
  imgData.data.forEach((_data, index) => {
    if ((index + 1) % 4 === 0) {
      const R = imgData.data[index - 3]
      const G = imgData.data[index - 2]
      const B = imgData.data[index - 1]

      const gray = ~~((R + G + B) / 3)
      newData[index - 3] = gray
      newData[index - 2] = gray
      newData[index - 1] = gray
      newData[index] = 255 // Alpha 值固定為255
    }
  })
  return createImgData(newData)
}

ImageData.data 是一個 Uint8ClampedArray 數組,可以理解為“RGBA數組”,數組中的每個數字取值為0~255,每4個數字為一組,表示一個像素的 RGBA 值。由于ImageData 為只讀對象,所以要另外寫一個 creaetImageData() 方法,利用 context.createImageData() 來創建新的 ImageData 對象。

拿到灰度圖像以后,就可以進行指紋提取的操作了。

指紋提取

在“平均哈希算法”中,若灰度圖的某個像素的灰度值大于平均值,則視為1,否則為0。把這部分信息組合起來就是圖片的指紋。由于我們已經拿到了灰度圖的 ImageData 對象,要提取指紋也就變得很容易了:

export function getHashFingerprint (imgData: ImageData) {
  const grayList = imgData.data.reduce((pre: number[], cur, index) => {
    if ((index + 1) % 4 === 0) {
      pre.push(imgData.data[index - 1])
    }
    return pre
  }, [])
  const length = grayList.length
  const grayAverage = grayList.reduce((pre, next) => (pre + next), 0) / length
  return grayList.map(gray => (gray >= grayAverage ? 1 : 0)).join('')
}

image


通過上述一連串的步驟,我們便可以通過“平均哈希算法”獲取到一張圖片的指紋信息(示例是大小為8×8的灰度圖):
image

感知哈希算法

關于“感知哈希算法”的詳細介紹,可以參考這篇文章:《基于感知哈希算法的視覺目標跟蹤》。

image

簡單來說,該算法經過離散余弦變換以后,把圖像從像素域轉化到了頻率域,而攜帶了有效信息的低頻成分會集中在 DCT 矩陣的左上角,因此我們可以利用這個特性提取圖片的特征。

該算法的步驟如下:

  • 縮小尺寸:pHash以小圖片開始,但圖片大于88,3232是最好的。這樣做的目的是簡化了DCT的計算,而不是減小頻率。
  • 簡化色彩:將圖片轉化成灰度圖像,進一步簡化計算量。
  • 計算DCT:計算圖片的DCT變換,得到32*32的DCT系數矩陣。
  • 縮小DCT:雖然DCT的結果是3232大小的矩陣,但我們只要保留左上角的88的矩陣,這部分呈現了圖片中的最低頻率。
  • 計算平均值:如同均值哈希一樣,計算DCT的均值。
  • 計算hash值:這是最主要的一步,根據8*8的DCT矩陣,設置0或1的64位的hash值,大于等于DCT均值的設為”1”,小于DCT均值的設為“0”。組合在一起,就構成了一個64位的整數,這就是這張圖片的指紋。

回到代碼中,首先添加一個 DCT 方法:

function memoizeCosines (N: number, cosMap: any) {
  cosMap = cosMap || {}
  cosMap[N] = new Array(N * N)

  let PI_N = Math.PI / N

  for (let k = 0; k < N; k++) {
    for (let n = 0; n < N; n++) {
      cosMap[N][n + (k * N)] = Math.cos(PI_N * (n + 0.5) * k)
    }
  }
  return cosMap
}

function dct (signal: number[], scale: number = 2) {
  let L = signal.length
  let cosMap: any = null

  if (!cosMap || !cosMap[L]) {
    cosMap = memoizeCosines(L, cosMap)
  }

  let coefficients = signal.map(function () { return 0 })

  return coefficients.map(function (_, ix) {
    return scale * signal.reduce(function (prev, cur, index) {
      return prev + (cur * cosMap[L][index + (ix * L)])
    }, 0)
  })
}

然后添加兩個矩陣處理方法,分別是把經過 DCT 方法生成的一維數組升維成二維數組(矩陣),以及從矩陣中獲取其“左上角”內容。

// 一維數組升維
function createMatrix (arr: number[]) {
  const length = arr.length
  const matrixWidth = Math.sqrt(length)
  const matrix = []
  for (let i = 0; i < matrixWidth; i++) {
    const _temp = arr.slice(i * matrixWidth, i * matrixWidth + matrixWidth)
    matrix.push(_temp)
  }
  return matrix
}

// 從矩陣中獲取其“左上角”大小為 range × range 的內容
function getMatrixRange (matrix: number[][], range: number = 1) {
  const rangeMatrix = []
  for (let i = 0; i < range; i++) {
    for (let j = 0; j < range; j++) {
      rangeMatrix.push(matrix[i][j])
    }
  }
  return rangeMatrix
}

復用之前在“平均哈希算法”中所寫的灰度圖轉化函數createGrayscale(),我們可以獲取“感知哈希算法”的特征值:

export function getPHashFingerprint (imgData: ImageData) {
  const dctData = dct(imgData.data as any)
  const dctMatrix = createMatrix(dctData)
  const rangeMatrix = getMatrixRange(dctMatrix, dctMatrix.length / 8)
  const rangeAve = rangeMatrix.reduce((pre, cur) => pre + cur, 0) / rangeMatrix.length
  return rangeMatrix.map(val => (val >= rangeAve ? 1 : 0)).join('')
}

image

顏色分布法

首先摘抄一段阮大關于“顏色分布法“的描述:
image

阮大把256種顏色取值簡化成了4種?;谶@個原理,我們在進行顏色分布法的算法設計時,可以把這個區間的劃分設置為可修改的,唯一的要求就是區間的數量必須能夠被256整除。算法如下:

// 劃分顏色區間,默認區間數目為4個
// 把256種顏色取值簡化為4種
export function simplifyColorData (imgData: ImageData, zoneAmount: number = 4) {
  const colorZoneDataList: number[] = []
  const zoneStep = 256 / zoneAmount
  const zoneBorder = [0] // 區間邊界
  for (let i = 1; i <= zoneAmount; i++) {
    zoneBorder.push(zoneStep * i - 1)
  }
  imgData.data.forEach((data, index) => {
    if ((index + 1) % 4 !== 0) {
      for (let i = 0; i < zoneBorder.length; i++) {
        if (data > zoneBorder[i] && data <= zoneBorder[i + 1]) {
          data = i
        }
      }
    }
    colorZoneDataList.push(data)
  })
  return colorZoneDataList
}

image

把顏色取值進行簡化以后,就可以把它們歸類到不同的分組里面去:

export function seperateListToColorZone (simplifiedDataList: number[]) {
  const zonedList: string[] = []
  let tempZone: number[] = []
  simplifiedDataList.forEach((data, index) => {
    if ((index + 1) % 4 !== 0) {
      tempZone.push(data)
    } else {
      zonedList.push(JSON.stringify(tempZone))
      tempZone = []
    }
  })
  return zonedList
}

image

最后只需要統計每個相同的分組的總數即可:

export function getFingerprint (zonedList: string[], zoneAmount: number = 16) {
  const colorSeperateMap: {
    [key: string]: number
  } = {}
  for (let i = 0; i < zoneAmount; i++) {
    for (let j = 0; j < zoneAmount; j++) {
      for (let k = 0; k < zoneAmount; k++) {
        colorSeperateMap[JSON.stringify([i, j, k])] = 0
      }
    }
  }
  zonedList.forEach(zone => {
    colorSeperateMap[zone]++
  })
  return Object.values(colorSeperateMap)
}

image

內容特征法

”內容特征法“是指把圖片轉化為灰度圖后再轉化為”二值圖“,然后根據像素的取值(黑或白)形成指紋后進行比對的方法。這種算法的核心是找到一個“閾值”去生成二值圖。
image

對于生成灰度圖,有別于在“平均哈希算法”中提到的取 RGB 均值的辦法,在這里我們使用加權的方式去實現。為什么要這么做呢?這里涉及到顏色學的一些概念。

具體可以參考這篇《Grayscale to RGB Conversion》,下面簡單梳理一下。

采用 RGB 均值的灰度圖是最簡單的一種辦法,但是它忽略了紅、綠、藍三種顏色的波長以及對整體圖像的影響。以下面圖為示例,如果直接取得 RGB 的均值作為灰度,那么處理后的灰度圖整體來說會偏暗,對后續生成二值圖會產生較大的干擾。

image

那么怎么改善這種情況呢?答案就是為 RGB 三種顏色添加不同的權重。鑒于紅光有著更長的波長,而綠光波長更短且對視覺的刺激相對更小,所以我們要有意地減小紅光的權重而提升綠光的權重。經過統計,比較好的權重配比是 R:G:B = 0.299:0.587:0.114。

image

于是我們可以得到灰度處理函數:

enum GrayscaleWeight {
  R = .299,
  G = .587,
  B = .114
}

function toGray (imgData: ImageData) {
  const grayData = []
  const data = imgData.data

  for (let i = 0; i < data.length; i += 4) {
    const gray = ~~(data[i] * GrayscaleWeight.R + data[i + 1] * GrayscaleWeight.G + data[i + 2] * GrayscaleWeight.B)
    data[i] = data[i + 1] = data[i + 2] = gray
    grayData.push(gray)
  }

  return grayData
}

上述函數返回一個 grayData 數組,里面每個元素代表一個像素的灰度值(因為 RBG 取值相同,所以只需要一個值即可)。接下來則使用“大津法”(Otsu's method)去計算二值圖的閾值。關于“大津法”,阮大的文章已經說得很詳細,在這里就不展開了。我在這個地方找到了“大津法”的 Java 實現,后來稍作修改,把它改為了 js 版本:

/ OTSU algorithm
// rewrite from http://www.labbookpages.co.uk/software/imgProc/otsuThreshold.html
export function OTSUAlgorithm (imgData: ImageData) {
  const grayData = toGray(imgData)
  let ptr = 0
  let histData = Array(256).fill(0)
  let total = grayData.length

  while (ptr < total) {
    let h = 0xFF & grayData[ptr++]
    histData[h]++
  }

  let sum = 0
  for (let i = 0; i < 256; i++) {
    sum += i * histData[i]
  }

  let wB = 0
  let wF = 0
  let sumB = 0
  let varMax = 0
  let threshold = 0

  for (let t = 0; t < 256; t++) {
    wB += histData[t]
    if (wB === 0) continue
    wF = total - wB
    if (wF === 0) break

    sumB += t * histData[t]

    let mB = sumB / wB
    let mF = (sum - sumB) / wF

    let varBetween = wB * wF * (mB - mF) ** 2

    if (varBetween > varMax) {
      varMax = varBetween
      threshold = t
    }
  }

  return threshold
}

OTSUAlgorithm() 函數接收一個 ImageData 對象,經過上一步的 toGray() 方法獲取到灰度值列表以后,根據“大津法”算出最佳閾值然后返回。接下來使用這個閾值對原圖進行處理,即可獲取二值圖。

export function binaryzation (imgData: ImageData, threshold: number) {
  const canvas = document.createElement('canvas')
  const ctx = canvas.getContext('2d')
  const imgWidth = Math.sqrt(imgData.data.length / 4)
  const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData
  for (let i = 0; i < imgData.data.length; i += 4) {
    let R = imgData.data[i]
    let G = imgData.data[i + 1]
    let B = imgData.data[i + 2]
    let Alpha = imgData.data[i + 3]
    let sum = (R + G + B) / 3

    newImageData.data[i] = sum > threshold ? 255 : 0
    newImageData.data[i + 1] = sum > threshold ? 255 : 0
    newImageData.data[i + 2] = sum > threshold ? 255 : 0
    newImageData.data[i + 3] = Alpha
  }
  return newImageData
}

image

若圖片大小為 N×N,根據二值圖“非黑即白”的特性,我們便可以得到一個 N×N 的 0-1 矩陣,也就是指紋:

image

特征比對算法

經過不同的方式取得不同類型的圖片指紋(特征)以后,應該怎么去比對呢?這里將介紹三種比對算法,然后分析這幾種算法都適用于哪些情況。

漢明距離

摘一段維基百科關于“漢明距離”的描述:

在信息論中,兩個等長字符串之間的漢明距離(英語:Hamming distance)是兩個字符串對應位置的不同字符的個數。換句話說,它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

例如:

  • 1011101與1001001之間的漢明距離是2。
  • 2143896與2233796之間的漢明距離是3。
  • "toned"與"roses"之間的漢明距離是3。

明白了含義以后,我們可以寫出計算漢明距離的方法:

export function hammingDistance (str1: string, str2: string) {
  let distance = 0
  const str1Arr = str1.split('')
  const str2Arr = str2.split('')
  str1Arr.forEach((letter, index) => {
    if (letter !== str2Arr[index]) {
      distance++
    }
  })
  return distance
}

使用這個 hammingDistance() 方法,來驗證下維基百科上的例子:
image

驗證結果符合預期。

知道了漢明距離,也就可以知道兩個等長字符串之間的相似度了(漢明距離越小,相似度越大):

相似度 = (字符串長度 - 漢明距離) / 字符串長度

余弦相似度

從維基百科中我們可以了解到關于余弦相似度的定義:

余弦相似性通過測量兩個向量的夾角的余弦值來度量它們之間的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。兩個向量有相同的指向時,余弦相似度的值為1;兩個向量夾角為90°時,余弦相似度的值為0;兩個向量指向完全相反的方向時,余弦相似度的值為-1。這結果是與向量的長度無關的,僅僅與向量的指向方向相關。余弦相似度通常用于正空間,因此給出的值為0到1之間。

注意這上下界對任何維度的向量空間中都適用,而且余弦相似性最常用于高維正空間。

image

余弦相似度可以計算出兩個向量之間的夾角,從而很直觀地表示兩個向量在方向上是否相似,這對于計算兩個 N×N 的 0-1 矩陣的相似度來說非常有用。根據余弦相似度的公式,我們可以把它的 js 實現寫出來:

export function cosineSimilarity (sampleFingerprint: number[], targetFingerprint: number[]) {
  // cosθ = ∑n, i=1(Ai × Bi) / (√∑n, i=1(Ai)^2) × (√∑n, i=1(Bi)^2) = A · B / |A| × |B|
  const length = sampleFingerprint.length
  let innerProduct = 0
  for (let i = 0; i < length; i++) {
    innerProduct += sampleFingerprint[i] * targetFingerprint[i]
  }
  let vecA = 0
  let vecB = 0
  for (let i = 0; i < length; i++) {
    vecA += sampleFingerprint[i] ** 2
    vecB += targetFingerprint[i] ** 2
  }
  const outerProduct = Math.sqrt(vecA) * Math.sqrt(vecB)
  return innerProduct / outerProduct
}

兩種比對算法的適用場景

明白了“漢明距離”和“余弦相似度”這兩種特征比對算法以后,我們就要去看看它們分別適用于哪些特征提取算法的場景。

首先來看“顏色分布法”。在“顏色分布法”里面,我們把一張圖的顏色進行區間劃分,通過統計不同顏色區間的數量來獲取特征,那么這里的特征值就和“數量”有關,也就是非 0-1 矩陣。

image

顯然,要比較兩個“顏色分布法”特征的相似度,“漢明距離”是不適用的,只能通過“余弦相似度”來進行計算。

接下來看“平均哈希算法”和“內容特征法”。從結果來說,這兩種特征提取算法都能獲得一個 N×N 的 0-1 矩陣,且矩陣內元素的值和“數量”無關,只有 0-1 之分。所以它們同時適用于通過“漢明距離”和“余弦相似度”來計算相似度。

image

計算精度

明白了如何提取圖片的特征以及如何進行比對以后,最重要的就是要了解它們對于相似度的計算精度。

本文所講的相似度僅僅是通過客觀的算法來實現,而判斷兩張圖片“像不像”卻是一個很主觀的問題。于是我寫了一個簡單的服務,可以自行把兩張圖按照不同的算法和精度去計算相似度:

https://img-compare.netlify.com/

經過對不同素材的多方比對,我得出了下列幾個非常主觀的結論。

  • 對于兩張顏色較為豐富,細節較多的圖片來說,“顏色分布法”的計算結果是最符合直覺的。
    image
  • 對于兩張內容相近但顏色差異較大的圖片來說,“內容特征法”和“平均/感知哈希算法”都能得到符合直覺的結果。
    image
  • 針對“顏色分布法“,區間的劃分數量對計算結果影響較大,選擇合適的區間很重要。
    image

總結一下,三種特征提取算法和兩種特征比對算法各有優劣,在實際應用中應該針對不同的情況靈活選用。

總結

本文是在拜讀阮一峰的兩篇《相似圖片搜索的原理》之后,經過自己的實踐總結以后而成。由于對色彩、數學等領域的了解只停留在淺顯的層面,文章難免有謬誤之處,如果有發現表述得不正確的地方,歡迎留言指出,我會及時予以更正。

查看原文

贊 102 收藏 65 評論 5

認證與成就

  • SegmentFault 講師
  • 獲得 2476 次點贊
  • 獲得 33 枚徽章 獲得 0 枚金徽章, 獲得 9 枚銀徽章, 獲得 24 枚銅徽章

擅長技能
編輯

開源項目 & 著作
編輯

  • Markcook--簡潔、高效的markdown編輯器

    使用了vue.js+webpack進行開發和構建。 非常的簡單,高效,沒有多余的東西。 她的優點有很多: 實時預覽,所見即所得,無需擔心排版問題。 提供了齊全的快捷按鈕,無需查閱markdown語法即可進行排版。 完全離線的單頁應用,可以把gh-pages分支的文件clone下來,作為本地客戶端使用。 提供本地緩存功能,防止重要內容丟失。 拖拽導入文件,編輯本地文件方便快捷。 支持文件導出,編寫完畢可直接保存。

注冊于 2015-09-02
個人主頁被 16k 人瀏覽

一本到在线是免费观看_亚洲2020天天堂在线观看_国产欧美亚洲精品第一页_最好看的2018中文字幕 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>