Wiktionary のダンプから全文を読み込む処理を Python で書きましたが、F# に移植して処理速度を比べます。
シリーズの記事です。
- Wiktionaryの効率的な処理方法を探る
- Wiktionaryの処理速度をF#とPythonで比較 ← この記事
- Wiktionaryの言語コードを取得
- Wiktionaryから特定の言語を抽出
- Wiktionaryで英語の不規則動詞を調査
- Wiktionaryのスクリプトをローカルで動かす
この記事のスクリプトは以下のリポジトリに掲載しています。
概要
Wiktionary のダンプに手を出した当初、F# を使おうかとは思ったのですが、.NET Framework はデフォルトで bzip2 が扱えなかったので Python で実装を始めました。並列化すれば 1 分ちょっとで処理が終わるようになったので、速度的には Python でも十分だと感じました。
それでもやはり F# ではどれくらいの速度が出るのだろうかと気になったので、不足しているライブラリを補って試します。
※ さらっと書きましたが、調査にかなり手間が掛かりました。
計測に使用した環境は以下の通りです。
- OS: Windows 10 1909
- CPU: AMD Ryzen 5 2500U with Radeon Vega Mobile Gfx (4 cores)
- .NET Framework 4.8.03752
- Python 3.8.2 (WSL1)
行数
.NET Framework で bzip2 を扱うには外部ライブラリが必要です。
手始めにダンプを全行読み込んで行数を数えます。対応する Python のコードと所要時間を並べます。
| 言語 | コード | 所要時間 |
|---|---|---|
| Python | python/research/countlines.py | 3m34.911s |
| F# | fsharp/research/countlines.fsx | 2m40.270s |
| コマンド | bzcat FILE.xml.bz2 | wc -l |
2m32.203s |
F# はコマンドに迫るスピードです。
#r "AR.Compression.BZip2.dll"
open System
open System.IO
open System.IO.Compression
let target = "enwiktionary-20200501-pages-articles-multistream.xml.bz2"
let mutable lines = 0
do
use fs = new FileStream(target, FileMode.Open)
use bs = new BZip2Stream(fs, CompressionMode.Decompress)
use sr = new StreamReader(bs)
while not (isNull (sr.ReadLine())) do
lines <- lines + 1
Console.WriteLine("lines: {0:#,0}", lines)
ストリーム分割
bzip2 ファイルをストリームごとに分割して読み込みます。
バイト列を経由するオーバーヘッドを回避するため、FileStream をマスクして読み取ります。以下の記事で作成した SubStream を使用します。
前回の記事で生成したストリーム長のデータ（streamlen.tsv）を使用します。
| 言語 | コード | 所要時間 |
|---|---|---|
| Python | python/research/countlines-BytesIO.py | 3m37.827s |
| F# | fsharp/research/countlines-split.fsx | 5m23.122s |
どうやら BZip2Stream の読み取り開始に無視できないオーバーヘッドがあるようで、かなり遅いです。少しでもオーバーヘッドを減らすために SubStream を使用しましたが、全然追い付きません。
#r "AR.Compression.BZip2.dll"
#load "StreamUtils.fsx"
open System
open System.IO
open System.IO.Compression
open StreamUtils
let target, slen =
use sr = new StreamReader("streamlen.tsv")
sr.ReadLine(),
[| while not <| sr.EndOfStream do
yield sr.ReadLine() |> Convert.ToInt32 |]
let mutable lines = 0
do
use fs = new FileStream(target, FileMode.Open)
for length in slen do
use ss = new SubStream(fs, length)
use bs = new BZip2Stream(ss, CompressionMode.Decompress)
use sr = new StreamReader(bs)
while not (isNull (sr.ReadLine())) do
lines <- lines + 1
Console.WriteLine("lines: {0:#,0}", lines)
オーバーヘッド回避
Python で並列化したとき、プロセス間通信のオーバーヘッドを抑えるため 10 ストリームごとに読み取りましたが、同様の措置を取ります。比較のため 100 ストリームごとの読み取りも試します。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| F# | fsharp/research/countlines-split-10.fsx | 2m50.913s | 10 ストリームごと |
| F# | fsharp/research/countlines-split-100.fsx | 2m40.727s | 100 ストリームごと |
かなり高速化しました。100 ストリームごとの方が速いため、この先のステップでは 100 ストリームごとの分割を採用します。
let mutable lines = 0
do
use fs = new FileStream(target, FileMode.Open)
for lengths in Seq.chunkBySize 100 slen do
use ss = new SubStream(fs, Array.sum lengths)
use bs = new BZip2Stream(ss, CompressionMode.Decompress)
use sr = new StreamReader(bs)
while not (isNull (sr.ReadLine())) do
lines <- lines + 1
Console.WriteLine("lines: {0:#,0}", lines)
Seq.chunkBySize で 100 要素ごとに分割して、Array.sum で合計します。
文字列変換
Python では文字列に変換して StringIO を使用した方が高速でした。F# でも同様の処理を試します。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/countlines-StringIO.py | 3m18.568s | 1 ストリームごと |
| F# | fsharp/research/countlines-split-string.fsx | 7m50.915s | 1 ストリームごと |
| F# | fsharp/research/countlines-split-string-10.fsx | 3m55.453s | 10 ストリームごと |
| F# | fsharp/research/countlines-split-string-100.fsx | 3m23.417s | 100 ストリームごと |
F# ではあまり速くないため、この方式は却下します。
let mutable lines = 0
do
use fs = new FileStream(target, FileMode.Open)
for length in slen do
let text =
use ss = new SubStream(fs, length)
use bs = new BZip2Stream(ss, CompressionMode.Decompress)
use ms = new MemoryStream()
bs.CopyTo(ms)
Encoding.UTF8.GetString(ms.ToArray())
use sr = new StringReader(text)
while not (isNull (sr.ReadLine())) do
lines <- lines + 1
Console.WriteLine("lines: {0:#,0}", lines)
テキスト抽出
XML の <text> タグの中身を抽出して、行数を数えます。
let mutable lines = 0
do
use fs = new FileStream(target, FileMode.Open)
fs.Seek(int64 slen.[0], SeekOrigin.Begin) |> ignore
for lengths in Seq.chunkBySize 100 slen.[1 .. slen.Length - 2] do
for _, text in getPages(fs, Array.sum lengths) do
for _ in text do
lines <- lines + 1
Console.WriteLine("lines: {0:#,0}", lines)
各種方式を試します。方式によって getPages を置き換えます。
文字列処理
行ごとに文字列処理でタグをパースします。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/countlines-text.py | 4m06.555s | startswith |
| F# | fsharp/research/countlines-text-split-StartsWith.fsx | 4m42.877s | StartsWith |
| F# | fsharp/research/countlines-text-split-slice.fsx | 4m14.069s | スライス |
| F# | fsharp/research/countlines-text-split.fsx | 4m05.507s | Substring |
.NET Framework の StartsWith が遅いのは、Unicode 正規化などの処理を行っているためのようです。
Substring を使って StartsWith 相当の処理をして、ようやく Python と同じくらいの処理速度になります。
let getPages(stream, length) = seq {
use ss = new SubStream(stream, length)
use bs = new BZip2Stream(ss, CompressionMode.Decompress)
use sr = new StreamReader(bs)
let mutable ns, id = 0, 0
while sr.Peek() <> -1 do
let mutable line = sr.ReadLine().TrimStart()
if line.StartsWith "<ns>" then
ns <- Convert.ToInt32 line.[4 .. line.IndexOf('<', 4) - 1]
id <- 0
elif id = 0 && line.StartsWith "<id>" then
id <- Convert.ToInt32 line.[4 .. line.IndexOf('<', 4) - 1]
elif line.StartsWith "<text " then
let p = line.IndexOf '>'
if line.[p - 1] = '/' then () else
if ns <> 0 then
while not <| line.EndsWith "</text>" do
line <- sr.ReadLine()
else
line <- line.[p + 1 ..]
yield id, seq {
while not <| isNull line do
if line.EndsWith "</text>" then
if line.Length > 7 then yield line.[.. line.Length - 8]
line <- null
else
yield line
line <- sr.ReadLine() }}
StartsWith の代わりの関数を作って置き換えます。
let inline startsWith (target:string) (value:string) =
target.Length >= value.Length && target.[.. value.Length - 1] = value
let inline startsWith (target:string) (value:string) =
target.Length >= value.Length && target.Substring(0, value.Length) = value
XML パーサー
XML パーサーによってツリーを作る方法と、ツリーを作らないでパースだけを行う方法を比較します。
XML のパースにはルート要素が必要です。既に見たように F# では文字列を経由すると遅くなることから、Stream を結合して処理します。以下の記事で作成した ConcatStream を使用します。
ツリーあり
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/countlines-text-xml.py | 5m50.826s | ElementTree.fromstring |
| F# | fsharp/research/countlines-text-split-doc.fsx | 6m21.588s | XmlDocument |
Python に比べて F# は遅いです。
let getPages(stream, length) = seq {
use ss = new SubStream(stream, length)
use cs = new ConcatStream([
new MemoryStream("<pages>"B)
new BZip2Stream(ss, CompressionMode.Decompress)
new MemoryStream("</pages>"B) ])
use xr = XmlReader.Create(cs)
let doc = XmlDocument()
doc.Load(xr)
for page in doc.ChildNodes.[0].ChildNodes do
let ns = Convert.ToInt32(page.SelectSingleNode("ns").InnerText)
if ns = 0 then
let id = Convert.ToInt32(page.SelectSingleNode("id").InnerText)
let text = page.SelectSingleNode("revision/text").InnerText
use sr = new StringReader(text)
yield id, seq {
while sr.Peek() <> -1 do
yield sr.ReadLine() }}
ツリーなし
Python の各種パーサーについては以下の記事を参照してください。
F# ではプル型の XmlReader を使用します。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/countlines-text-xmlparser.py | 6m46.163s | XMLParser |
| Python | python/research/countlines-text-xmlpull.py | 6m04.553s | XMLPullParser |
| Python | python/research/countlines-text-xmliter.py | 6m29.298s | ElementTree.iterparse |
| F# | fsharp/research/countlines-text-split-reader.fsx | 3m17.916s | XmlReader |
| F# | fsharp/research/countlines-text-reader.fsx | 3m16.122s | XmlReader（未分割） |
※ 「未分割」はストリームのことです。結果を見ると、分割によるオーバーヘッドはほとんどないようです。
.NET Framework の XmlDocument は XmlReader を利用して組み立てられます。XmlReader 単体で使った方が圧倒的に速いです。この先のステップでは XmlReader による方式のみを使用します。
Python でも事情は同じはずですが、ツリーの作成が相当に効率化されているようで、ツリーを作った方が高速です。
let getPages(stream, length) = seq {
use ss = new SubStream(stream, length)
use cs = new ConcatStream([
new MemoryStream("<pages>"B)
new BZip2Stream(ss, CompressionMode.Decompress)
new MemoryStream("</pages>"B) ])
use xr = XmlReader.Create(cs)
let mutable ns, id = 0, 0
while xr.Read() do
if xr.NodeType = XmlNodeType.Element then
match xr.Name with
| "ns" ->
if xr.Read() then ns <- Convert.ToInt32 xr.Value
id <- 0
| "id" ->
if id = 0 && xr.Read() then id <- Convert.ToInt32 xr.Value
| "text" ->
if ns = 0 && not xr.IsEmptyElement && xr.Read() then
yield id, seq {
use sr = new StringReader(xr.Value)
while sr.Peek() <> -1 do
yield sr.ReadLine() }
| _ -> () }
言語テーブル
今までのコードから、共通部分を括り出します。
どの項目にどの言語のデータが含まれるかのテーブルを作成します（output1.tsv）。言語名は別テーブルに正規化します（output2.tsv）。
do
use sw = new StreamWriter("output1.tsv")
sw.NewLine <- "\n"
for id, lid in results do
fprintfn sw "%d\t%d" id lid
do
use sw = new StreamWriter("output2.tsv")
sw.NewLine <- "\n"
for kv in langs do
fprintfn sw "%d\t%s" kv.Value kv.Key
1 つの記事は ==言語名== という行で区切られているため、それを検出して id と紐付けます。下位の見出しで ===項目名=== が使用されるため区別します。
既に見たように StartsWith は遅いです。行頭から 1 文字ずつ調べる方法と、正規表現とを比較します。
XML のパースは、Python では文字列処理、F# では XmlReader を使用します。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/checklang.py | 4m35.440s | startswith |
| F# | fsharp/research/checklang-StartsWith.fsx | 3m43.965s | StartsWith |
| Python | python/research/checklang-ch.py | 4m37.771s | 1文字ずつ |
| F# | fsharp/research/checklang.fsx | 3m24.302s | 1文字ずつ |
| Python | python/research/checklang-re.py | 4m31.855s | 正規表現 |
| F# | fsharp/research/checklang-re.fsx | 3m46.270s | 正規表現 |
F# では 1 文字ずつ調べると速いですが、実装が面倒で汎用性もありません。正規表現は StartsWith と速度がほとんど変わりません。汎用性を考えれば正規表現を使うのが無難そうです。
for line in text do
if line.StartsWith "==" && not <| line.StartsWith "===" then
let lang = line.[2..].Trim()
let mutable e = lang.Length - 1
while e > 0 && lang.[e] = '=' do e <- e - 1
let lang = lang.[..e].Trim()
for line in text do
if line.Length >= 3 && line.[0] = '=' && line.[1] = '=' && line.[2] <> '=' then
let r = Regex "^==([^=].*)=="
（略）
for line in text do
let m = r.Match line
if m.Success then
let lang = m.Groups.[1].Value.Trim()
並列化
F# ではマルチスレッド、Python ではマルチプロセスを利用して並列化します。
| 言語 | コード | 所要時間 | 備考 |
|---|---|---|---|
| Python | python/research/checklang-parallel.py | 1m16.566s | startswith |
| F# | fsharp/research/checklang-parallel.fsx | 1m03.941s | 1文字ずつ |
| Python | python/research/checklang-parallel-re.py | 1m07.106s | 正規表現 |
| F# | fsharp/research/checklang-parallel-re.fsx | 1m07.009s | 正規表現 |
ほぼ同じです。並列化による伸び幅は Python の方が大きいです。
let getlangs(pos, length) = async { return [
use fs = new FileStream(target, FileMode.Open, FileAccess.Read)
fs.Seek(pos, SeekOrigin.Begin) |> ignore
for id, text in MediaWikiParse.getPages(fs, length) do
for line in text do
if line.Length >= 3 && line.[0] = '=' && line.[1] = '=' && line.[2] <> '=' then
let lang = line.[2..].Trim()
let mutable e = lang.Length - 1
while e > 0 && lang.[e] = '=' do e <- e - 1
yield id, lang.[..e].Trim() ]}
let getlangs(pos, length) = async { return [
let r = Regex "^==([^=].*)=="
use fs = new FileStream(target, FileMode.Open, FileAccess.Read)
fs.Seek(pos, SeekOrigin.Begin) |> ignore
for id, text in MediaWikiParse.getPages(fs, length) do
for line in text do
let m = r.Match line
if m.Success then
yield id, m.Groups.[1].Value.Trim() ]}
let results =
sposlen.[1 .. sposlen.Length - 2]
|> Seq.chunkBySize 100
|> Seq.map Array.unzip
|> Seq.map (fun (ps, ls) -> Array.min ps, Array.sum ls)
|> Seq.map getlangs
|> Async.Parallel
|> Async.RunSynchronously
|> List.concat
let langs = Dictionary<string, int>()
do
use sw = new StreamWriter("output1.tsv")
sw.NewLine <- "\n"
for id, lang in results do
let lid =
if langs.ContainsKey lang then langs.[lang] else
let lid = langs.Count + 1
langs.[lang] <- lid
lid
fprintfn sw "%d\t%d" id lid
do
use sw = new StreamWriter("output2.tsv")
sw.NewLine <- "\n"
for kv in langs do
fprintfn sw "%d\t%s" kv.Value kv.Key
.NET Core と Mono
WSL1 上の .NET Core と Mono で計測しました。Windows 上の .NET Framework の結果と比較します。
略称との対応は以下の通りです。
- Framework: .NET Framework 4.8.03752 (Windows 10)
- Core: .NET Core 3.1.103 (WSL1)
- Mono: Mono 6.4.0 (WSL1)
| コード | Framework | Core | Mono | 備考 |
|---|---|---|---|---|
| fsharp/research/checklang.fsx | 3m24.302s | 3m25.545s | 4m22.330s | |
| fsharp/research/checklang-re.fsx | 3m46.270s | 3m42.882s | 4m51.236s | 正規表現 |
| fsharp/research/checklang-parallel.fsx | 1m03.941s | 0m59.014s | 2m39.716s | 並列 |
| fsharp/research/checklang-parallel-re.fsx | 1m07.009s | 1m06.136s | 3m28.074s | 並列、正規表現 |
.NET Core は .NET Framework と同じか少し速いようです。
.NET Core はプロジェクトを作るのが基本ですが、実行ファイルが複数あって面倒だったので、以下の方法でコンフィグを書いて対応しました。
感想
最速の方法では F# と Python はほぼ同じという結果になりました。同じ処理内容で移植すると Python の方が速いこともあったのが印象的でした。
以下の記事で試したように、文字単位の処理では圧倒的な差が出ます。