作者
Patrik Nyblom <pan(at)erlang(dot)org> , Fredrik Svahn <Fredrik(dot)Svahn(at)gmail>
狀態
最終/R14A 已在 OTP 版本 R14A 中實作
類型
標準追蹤
建立日期
2009-11-28
Erlang 版本
OTP_R13B03

EEP 31:二進制操作和搜尋模組 #

摘要 #

此 EEP 包含關於 binary 模組的開發建議,該模組最初在 EEP 9 中提出。

EEP 9 提出了幾個模組,並且部分被後來的 EEP(即 EEP 11)取代,但仍包含尚未實作的有價值建議。因此,來自 EEP 9 的剩餘模組將出現在單獨的 EEP 中。此架構是與 EEP 9 的原始作者達成協議後所制定的。

建議 binary 模組包含快速搜尋演算法,以及一些已存在於列表(在 lists 模組中)的常見二進制操作。

動機 #

雖然 re 函式庫中已存在有效的搜尋功能,但如果有效率的實作(例如 Boyer-More 和 Aho-Corassick 演算法),專用的搜尋函數可以進一步加速二進制檔案中的搜尋。單獨的搜尋演算法另一個重要的優點是方便程式設計師使用,因為建議的介面不需要了解正規表示式語法,並且二進制檔案中的特殊字元也不需要跳脫。值得注意的是,正規表示式經常用於簡單的子字串搜尋或取代,而使用此建議的模組可以輕鬆完成。

二進制檔案的分解通常使用位元語法完成。然而,一些常見的操作作為普通函數會很有用,既能提高效能,又能支援更傳統的函數式程式設計風格。

目前在 erlang 模組中有一些用於將列表轉換為二進制檔案和反之的操作。關於二進制檔案的 BIF 現在對二進制檔案中的零基 vs. 一基準定位有不同的看法。例如,binary_to_list/3 使用一基準,而 split_binary/2 使用零基準。由於慣例是使用零基準,因此需要新的函數來將二進制檔案轉換為列表,反之亦然。

二進制檔案實際上是一種共享的資料類型,小型二進制檔案通常以程式設計師無法簡單控制的方式引用大型二進制檔案的部分。位元字串資料類型進一步使程式設計師的事情複雜化,難以輕鬆管理。因此,我也建議使用一些低階函數來檢查二進制表示形式,並複製二進制檔案以確保最小的表示形式。

由於在 guard 表達式中不允許比對,因此我進一步建議將用於提取二進制檔案部分的函數添加到 guard BIF 集合中。這將與允許在 guard 中使用的函數 element/2 一致。

基本原理 #

對於列表資料類型,有一個幫助函式庫,提供用於常見操作的函數,例如搜尋和分割列表。此 EEP 建議應為二進制檔案建立類似的函式庫函數集合。許多提出的函數都是基於 erlang-questions 郵件清單上關於二進制檔案的問題的答案,例如「我如何將數字轉換為二進制檔案?」。因此,此 EEP 建議在 stdlib 中添加一個模組,即 binary 模組,它將以有效的方式實作請求的功能。此模組的大部分需要以原生程式碼(駐留在虛擬機器中)實作,這就是為什麼建議的實作將在即將推出的 Erlang 版本中以「beta」功能交付的原因。

建議的功能如下:

  • 用於在二進制檔案中搜尋、分割和取代的功能。該功能在某些方面會與 Erlang 中已存在的正規表示式函式庫的功能重疊,但效率會更高,並且介面也會更簡單。

  • 二進制檔案的常見操作,它們在 stdlib 模組 lists 中已經有對應的列表。雖然 lists 模組中的並非所有介面都適用於二進制檔案,但許多介面都適用。此模組也為二進制檔案的未來操作提供了一個好位置,這些操作不適用於列表,或者我們仍然不知道其需求。

  • 用於將列表轉換為二進制檔案以及反之的函數。這些函數應對二進制檔案中的零基準索引具有一致的看法。

  • 關於二進制檔案內部表示形式的操作。由於二進制檔案的共享性質,此功能有時是避免大量使用記憶體所必需的。由於在分解二進制檔案時,二進制檔案上的操作不涉及複製,因此程式可能會在不知情(或至少是非故意)的情況下,透過在處理程序中保留看似少量資料的方式,保持對大型二進制檔案的引用。二進制檔案上許多操作的 O(1) 性質使得資料共享是必要的,但其影響有時會令人感到驚訝。另一方面,如果分割二進制檔案時出現 O(n) 的複雜度和立即的記憶體爆炸,則會更加令人感到驚訝,這就是為什麼需要保留目前的行為。建議在此建議的模組中提供用於檢查二進制檔案共享性質和複製二進制檔案副本以避免共享影響的函數。

所有功能都應應用於以位元組為導向的二進制檔案,永遠不要應用於位元長度不是八的倍數的位元字串。提供給這些函數以及由這些函數返回的所有二進制檔案都應通過 is_binary/1 測試,否則會引發錯誤。

建議的模組參考 #

我建議使用以下功能(以 Erlang 手冊頁面的摘錄形式呈現)。有關介面的討論,請參閱下文。

資料類型 #

cp()

不透明資料類型,表示編譯的搜尋模式。保證為 tuple(),以允許程式將其與未預先編譯的搜尋模式區分開來。

part() = {Pos,Length}

Start = int()
Length = int()

二進制檔案中的一部分(或範圍)的表示形式。Start 是二進制檔案中的零基準偏移量,而 Length 是該部分的長度。作為此模組中函數的輸入,允許使用負數 Length 建構反向部分規格,以便二進制檔案的部分從 Start + Length 開始,長度為 -Length。這對於將二進制檔案的最後 N 個位元組引用為 {size(Binary), -N} 很有用。此模組中的函數始終返回具有正數 Length 的 part()。

匯出 #

compile_pattern(Pattern) -> cp() #

類型

Pattern = binary() | [ binary() ]

建構一個內部結構,表示搜尋模式的編譯,以便稍後在 find、split 或 replace 函數中使用。返回的 cp() 保證為 tuple(),以允許程式將其與未預先編譯的搜尋模式區分開來

當給定二進制檔案的列表時,它表示要搜尋的替代二進制檔案的集合。也就是說,如果 [<<"functional">>, <<"programming">>] 作為 Pattern 給定,這表示「<<"functional">> <<"programming">>」。模式是替代方案的集合;當僅給定單個二進制檔案時,該集合只有一個元素。

如果模式不是二進制檔案或二進制檔案的平面適當列表,則會引發 badarg 例外。

match(Subject, Pattern) -> Found | no #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = part()

match(Subject, Pattern, []) 相同。

match(Subject,Pattern,Options) -> Found | no #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = part()
Options = [ Option ]
Option = {scope, part()}

搜尋 SubjectPattern 的第一次出現,並返回位置和長度。

該函數將為 Pattern 中從 Subject 中最低位置開始的二進制檔案返回 {Pos,Length}

範例

1> binary:find(<<"abcde">>, [<<"bcde">>,<<"cd">>],[]).
{1,4}

即使 <<"cd">><<"bcde">> 之前結束,<<"bcde">> 也會先開始,因此是第一個符合項目。如果兩個重疊的符合項目在同一位置開始,則會返回最長的符合項目。

選項摘要

  • {scope, {Start, Length}}
    僅搜尋給定的部分。傳回值仍然具有 Subject 開頭的偏移量。如本手冊的類型部分所述,允許使用負數 Length

    如果未找到 Pattern 中的任何字串,則傳回找到的 part(),否則傳回原子 no

    有關 Pattern 的說明,請參閱 compile_pattern/1

    如果在選項中給定 {scope, {Start,Length}},使得 Start 大於 Subject 的大小,Start + Length 小於零或 Start + Length 大於 Subject 的大小,則會引發 badarg 例外。

matches(Subject, Pattern) -> Found #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = [ part() ] | []

matches(Subject, Pattern, []) 相同。

matches(Subject,Pattern,Options) -> Found #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = [ part() ] | []
Options = [ Option ]
Option = {scope, part()}

其作用類似於 match,但是會搜尋 Subject 直到用盡,並且會返回 Pattern 中存在的所有非重疊部分(依序)的列表。

第一個且最長的符合項目優先於較短的符合項目,這可透過以下範例說明:

1> binary:matches(<<"abcde">>, [<<"bcde">>,<<"bc">>>,<<"de">>],[]).
[{1,4}]

結果顯示,選擇了 <<"bcde">>>,而不是較短的符合項目 <<"bc">>(這會再產生一個符合項目 <<"de">>)。這對應於 posix 正規表示式(以及類似 awk 的程式)的行為,但與 re(和 Perl)中的替代符合項目不一致,後者會在搜尋模式中選擇詞彙順序的字串符合項目。

如果未找到模式中的任何字串,則返回空列表。

關於 Pattern 的說明,請參閱 compile_pattern/1,關於可用選項的說明,請參閱 match/3

如果在選項中給定 {scope, {Start,Length}},使得 Start 大於 Subject 的大小,Start + Length 小於零或 Start + Length 大於 Subject 的大小,則會引發 badarg 例外。

split(Subject,Pattern) -> Parts #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Parts = [ binary() ]

split(Subject, Pattern, []) 相同。

split(Subject,Pattern,Options) -> Parts #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Parts = [ binary() ]
Options = [ Option ]
Option = {scope, part()} | trim | global

根據 Pattern 將二進制資料分割成二進制資料列表。如果沒有給定 global 選項,則只會根據 Subject 中首次出現的 Pattern 進行分割。

Subject 中實際找到的 Pattern 部分不包含在結果中。

範例

1> binary:split(<<1,255,4,0,0,0,2,3>>, [<<0,0,0>>,<<2>>],[]).
[<<1,255,4>>, <<2,3>>]
2> binary:split(<<0,1,0,0,4,255,255,9>>, [<<0,0>>, <<255,255>>],[global]).
[<<0,1>>,<<4>>,<<9>>]

選項摘要

  • {scope, part()}
    作用與 binary:match/3binary:matches/3 相同。請注意,這只定義了搜尋匹配字串的範圍,並不會在分割前切斷二進制資料。範圍之前和之後的位元組將保留在結果中。請參閱下面的範例。

  • trim 移除結果中尾部的空部分(如同 re:split/3 中的 trim 一樣)

  • global
    重複分割直到 Subject 被耗盡。概念上,global 選項使 splitbinary:matches/3 返回的位置上操作,而通常它在 binary:match/3 返回的位置上操作。

scope 和在分割之前將二進制資料拆開的差異範例

1> binary:split(<<"banana">>,[<<"a">>],[{scope,{2,3}}]).
[<<"ban">>,<<"na">>]
2> binary:split(binary:part(<<"banana">>,{2,3}),[<<"a">>],[]).
[<<"n">>,<<"n">>]

返回類型始終是一個二進制資料列表,它們都參照 Subject。這表示 Subject 中的資料實際上沒有複製到新的二進制資料中,並且在不再參照分割結果之前,Subject 無法進行垃圾回收。

有關 Pattern 的說明,請參閱 compile_pattern/1

replace(Subject,Pattern,Replacement) -> Result #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Replacement = binary()
Result = binary()

replace(Subject,Pattern,Replacement,[]) 相同。

replace(Subject,Pattern,Replacement,Options) -> Result #

類型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Replacement = binary()
Result = binary()
Options = [ Option ]
Option = global | {scope, part()} | {insert_replaced, InsPos}
InsPos = OnePos | [ OnePos ]
OnePos = int() =< byte_size(Replacement)

通過將 Subject 中與 Pattern 匹配的部分替換為 Replacement 的內容來建構新的二進制資料。

如果要將 Subject 中產生替換的匹配子部分插入到結果中,則選項 {insert_replaced, InsPos} 將在實際將 Replacement 插入到 Subject 之前,將匹配部分插入到 Replacement 中的給定位置(或多個位置)。範例

1> binary:replace(<<"abcde">>,<<"b">>,<<"[]">>,[{insert_replaced,1}]).
<<"a[b]cde">>
2> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[]">>,
                 [global,{insert_replaced,1}]).
<<"a[b]c[d]e">>
3> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[]">>,
                 [global,{insert_replaced,[1,1]}]).
<<"a[bb]c[dd]e">>
4> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[-]">>,
                 [global,{insert_replaced,[1,2]}]).
<<"a[b-b]c[d-d]e">>

如果 InsPos 中給定的任何位置大於替換二進制資料的大小,則會引發 badarg 例外。

選項 global{scope, part()} 的作用與 binary:split/3 相同。返回類型始終是一個二進制資料。

有關 Pattern 的說明,請參閱 compile_pattern/1

longest_common_prefix(Binaries) -> int() #

類型

Binaries = [ binary() ]

返回列表 Binaries 中二進制資料的最長共同前綴的長度。範例

1> binary:longest_common_prefix([<<"erlang">>,<<"ergonomy">>]).
2
2> binary:longest_common_prefix([<<"erlang">>,<<"perl">>]).
0

如果 Binaries 不是二進制資料的扁平列表,則會引發 badarg 例外。

longest_common_suffix(Binaries) -> int() #

類型

Binaries = [ binary() ]

返回列表 Binaries 中二進制資料的最長共同後綴的長度。範例

1> binary:longest_common_suffix([<<"erlang">>,<<"fang">>]).
3
2> binary:longest_common_suffix([<<"erlang">>,<<"perl">>]).
0

如果 Binaries 不是二進制資料的扁平列表,則會引發 badarg 例外。

first(Subject) -> int() #

類型

Subject = binary()

以整數形式返回二進制資料的第一個位元組。如果二進制資料的長度為零,則會引發 badarg 例外。

last(Subject) -> int() #

類型

Subject = binary()

以整數形式返回二進制資料的最後一個位元組。如果二進制資料的長度為零,則會引發 badarg 例外。

at(Subject, Pos) -> int() #

類型

Subject = binary()
Pos = int() >= 0

以整數形式返回二進制資料 Subject 中位置 Pos(從零開始)的位元組。如果 Pos >= byte_size(Subject),則會引發 badarg 例外。

part(Subject, PosLen) -> binary() #

類型

Subject = binary()
PosLen = part()

提取 PosLen 所描述的二進制資料部分。

可以使用負長度來提取二進制資料末尾的位元組

1> Bin = <<1,2,3,4,5,6,7,8,9,10>>.
2> binary:part(Bin,{byte_size(Bin), -5)).
<<6,7,8,9,10>>

如果 PosLen 以任何方式參照到二進制資料外部,則會引發 badarg 例外。

part(Subject, Pos, Len) -> binary() #

類型

Subject = binary()
Pos = int()
Len = int()

part(Subject, {Pos, Len}) 相同。

bin_to_list(Subject) -> list() #

類型

Subject = binary()

bin_to_list(Subject,{0,byte_size(Subject)}) 相同。

bin_to_list(Subject, PosLen) -> list() #

Subject = binary()
PosLen = part()

Subject 轉換為 int() 列表,每個 int 代表一個位元組的值。part() 表示要轉換的 binary() 的哪個部分。範例

1> binary:bin_to_list(<<"erlang">>,{1,3}).
"rla"
%% or [114,108,97] in list notation.

如果 PosLen 以任何方式參照到二進制資料外部,則會引發 badarg 例外。

bin_to_list(Subject, Pos, Len) -> list() #

類型

Subject = binary()
Pos = int()
Len = int()

bin_to_list(Subject,{Pos,Len}) 相同。

list_to_bin(ByteList) -> binary() #

類型

ByteList = iodata() (see module erlang)

erlang:list_to_binary/1 的功能完全相同,為完整性而添加。

copy(Subject) -> binary() #

類型

Subject = binary()

copy(Subject, 1) 相同。

copy(Subject,N) -> binary() #

類型

Subject = binary()
N = int() >= 0

建立一個二進制資料,其中包含 Subject 的內容重複 N 次。

此函數將始終建立新的二進制資料,即使 N = 1。通過在參照較大二進制資料的二進制資料上使用 copy/1,可以釋放較大的二進制資料以進行垃圾回收。

注意!通過刻意複製單個二進制資料以避免參照較大的二進制資料,可能會產生比需要的更多的二進制資料,而不是釋放較大的二進制資料以供稍後垃圾回收。共享二進制資料通常是好的。只有在特殊情況下,當小部分參照較大的二進制資料且較大的二進制資料不再在任何進程中使用時,刻意複製才是好主意。

如果 N < 0,則會引發 badarg 例外。

referenced_byte_size(binary()) -> int() #

如果二進制資料參照較大的二進制資料(通常描述為子二進制資料),則取得實際參照的二進制資料的大小可能會很有用。此函數可用於程式中以觸發 copy/1 的使用。通過複製二進制資料,可以取消對原始(可能很大)二進制資料的參照,而較小的二進制資料是對該原始二進制資料的參照。

範例

store(Binary, GBSet) ->
  NewBin =
      case binary:referenced_byte_size(Binary) of
          Large when Large > 2 * byte_size(Binary) ->
               binary:copy(Binary);
          _ ->
         Binary
      end,
  gb_sets:insert(NewBin,GBSet).

在此範例中,如果二進制資料參照的二進制資料大小超過我們將要保留的資料大小的兩倍,我們選擇先複製二進制資料內容,然後再將其插入 gb_set()。當然,不同的程式將會應用不同的複製規則。

每當二進制資料被拆分時,都會發生二進制資料共享,這是二進制資料速度快的基本原因,分解始終可以以 O(1) 的複雜度完成。但是,在極少數情況下,這種資料共享是不希望發生的,因此,當優化記憶體使用時,此函數與 copy/1 結合使用可能會很有用。

二進制資料共享範例

1> A = binary:copy(<<1>>,100).
<<1,1,1,1,1 ...
2> byte_size(A).
100
3> binary:referenced_byte_size(A)
100
4> <<_:10/binary,B:10/binary,_/binary>> = A.
<<1,1,1,1,1 ...
5> byte_size(B).
10
6> binary:referenced_byte_size(B)
100

注意!二進制資料在進程之間共享。如果另一個進程仍然參照較大的二進制資料,則複製此進程使用的部分只會消耗更多記憶體,而不會釋放較大的二進制資料以進行垃圾回收。請極度謹慎地使用這種侵入性函數,並且僅在檢測到真實問題時才使用。

encode_unsigned(Unsigned) -> binary() #

類型

Unsigned = int() >= 0

encode_unsigned(Unsigned,big) 相同。

encode_unsigned(Unsigned,Endianess) -> binary() #

類型

Unsigned = int() >= 0
Endianess = big | little

將正整數轉換為二進制數字表示形式中可能最小的表示形式,可以是 big endian 或 little endian。

範例

1> binary:encode_unsigned(11111111,big).
<<169,138,199>>

decode_unsigned(Subject) -> Unsigned #

類型

Subject = binary()
Unsigned = int() >= 0

encode_unsigned(Subject,big) 相同。

decode_unsigned(Subject, Endianess) -> Unsigned #

類型

Subject = binary()
Endianess = big | little
Unsigned = int() >= 0

Subject 中正整數的二進制數字表示形式(以 big endian 或 little endian 格式)轉換為 Erlang int()。

範例

1> binary:decode_unsigned(<<169,138,199>>,big).
11111111

Guard BIF #

我建議將函數 binary:part/2binary:part/3 添加到 guard 測試中允許的 BIF 集合。由於 guard BIF 傳統上放在 erlang 模組中,因此建議為 guard BIF 使用以下名稱

erlang:binary_part/2
erlang:binary_part/3

它們的功能應該與二進制模組中的對應項完全相同。

介面設計討論 #

與所有模組一樣,關於實際介面有很多爭論,有時甚至比關於功能本身的爭論還要多。在這種情況下,必須考慮許多參數。

  • 效率 - 介面的建構應該允許快速實現,並且可以讓使用介面的程式碼以有效的方式編寫。不產生不必要的垃圾是一個參數,允許編寫通用程式碼是另一個參數。

  • 參數順序 - 我選擇在所有適用的呼叫中將二進制主體作為第一個參數。將主體放在首位與 re 介面一致。但是,lists 模組通常將主體作為最後一個參數。我們可以改為使用該參數,但不幸的是,與 part 函數對應的 lists:sublist/{2,3} 介面將主體放在首位,因此,遵循 lists 的慣例不僅會破壞與 re 的一致性,還會給我們帶來一般的非嚴格介面。不符合 lists 介面的影響是,使用該模組中的函數名稱會導致混淆,因此應避免使用。

  • 函數命名 - 在這裡命名函數時,我們需要考慮兩個相關的模組。模組 re 與搜尋函數(matchreplace 等)有關,而 lists 模組與分解函數(firstlast 等)有關。

    當我發現功能(無論是在概念上還是介面上)都足夠相似時,我基本上保留了 re 中的名稱。由於規則運算式是小型可執行程式,這對二進制集合而言太大了,因為此模組中的模式是規則運算式,因此禁止使用函數名稱 run 來實際執行搜尋。我們使用 matchmatches 而不是 run

    由於此模組比 re 更通用,因此像 compile 這樣的函數名稱並不是很好。re:compile 的意思是「編譯規則運算式」,但是 binary:compile 的意思是什麼?因此,預處理函數改名為 compile_pattern

    當涉及到 lists 模組時,參數順序使我無法重複使用任何函數名稱,除了 last 之外,它在 lists 中只接受一個參數,並且沒有真正的替代方法。

  • 選項或多個函數 - 我認為一個好的經驗法則是不要使用會更改函數返回類型的選項,如果我們對 match/3 使用 global 選項而不是單獨的 matches/3 函數,就會發生這種情況。

    搜尋和分解函數的一組可能的返回類型是可以管理的,這讓我們可以遵循該經驗法則。

    (不幸的是,該規則在 re 中不容易遵循,因為豐富的選項會產生不可管理數量的函數名稱)。

效能 #

儘管分解函數並不像使用位元語法進行分解那樣快,但它們產生的垃圾比位元語法少一些。由於它們的速度不比位元語法慢,因此它們在允許不同的編程風格方面也很有用。

應將 match/replace/split 功能與 re 模組中的類似功能進行比較。必須選擇實現方法,以使此模組的搜尋函數比 re 更快,甚至可能顯著更快。

參考實作 #

在最終包含在 R14A 中之前,GitHub 開發分支上提供了參考實作。

版權 #

本文檔根據 Creative Commons 授權 授權。