Geschwindigkeitsvergleich der Volltextverarbeitung von Wiktionary mit F # und Python

Ich habe den Prozess des Lesens des vollständigen Textes aus dem Wiktionary-Dump in Python geschrieben, aber ich werde ihn auf F # portieren und die Verarbeitungsgeschwindigkeit vergleichen.

Dies ist eine Reihe von Artikeln.

1. Erkundung effizienter Verarbeitungsmethoden für Wiktionary
2. Vergleich der Wiktionary-Verarbeitungsgeschwindigkeit zwischen F # und Python ← Dieser Artikel

Das Skript für diesen Artikel befindet sich im folgenden Repository.

• https://github.com/7shi/wiktionary-tools/tree/master/fsharp/research

Überblick

Als ich anfing, Wiktionary zu sichern, dachte ich, ich würde F # verwenden, aber .NET Framework konnte bzip2 standardmäßig nicht verarbeiten, also begann ich, es in Python zu implementieren. Nach der Parallelisierung war der Vorgang in etwas mehr als einer Minute abgeschlossen, sodass ich der Meinung war, dass Python in Bezug auf die Geschwindigkeit ausreichend war.

Trotzdem habe ich mich gefragt, wie schnell F # sein würde, also werde ich versuchen, die fehlende Bibliothek auszugleichen.

• Ich habe es kurz geschrieben, aber es hat viel Zeit gekostet, es zu untersuchen.

Die für die Messung verwendete Umgebung ist wie folgt.

• 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)

Anzahl der Zeilen

Für die Arbeit mit bzip2 in .NET Framework ist eine externe Bibliothek erforderlich.

• Untersuchen Sie die bzip2-Bibliothek von .NET Framework

Lesen Sie zunächst alle Zeilen im Speicherauszug und zählen Sie die Anzahl der Zeilen. Listen Sie den entsprechenden Python-Code und die Dauer auf.

F # ist die Geschwindigkeit, die sich dem Befehl nähert.

#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)

Stream aufgeteilt

Lesen Sie die bzip2-Datei für jeden Stream separat.

Maskieren und lesen Sie "FileStream", um den Aufwand beim Durchlaufen der Bytes zu vermeiden. Verwenden Sie den im folgenden Artikel erstellten "SubStream".

• Streams extrahieren und kombinieren → [fsharp / research / StreamUtils.fsx](https://github.com/7shi/wiktionary-tools/blob/ master / fsharp / research / StreamUtils.fsx)

Verwenden Sie die im vorherigen Artikel (https://qiita.com/7shi/items/e8091f6ac72491ad45a6) generierten Daten zur Stream-Länge (streamlen.tsv).

Anscheinend ist der Start des BZip2Stream-Lesevorgangs mit einem nicht zu vernachlässigenden Aufwand verbunden, der recht langsam ist. Ich habe "SubStream" verwendet, um den Overhead ein wenig zu reduzieren, aber ich kann überhaupt nicht aufholen.

#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)

Vermeiden Sie Overhead

Bei der Parallelisierung in Python lese ich alle 10 Streams, um den Overhead der Kommunikation zwischen Prozessen zu verringern, aber ich ergreife die gleiche Aktion. Versuchen Sie auch, alle 100 Streams zum Vergleich zu lesen.

Es ist viel schneller. Da alle 100 Streams schneller sind, wird im nächsten Schritt alle 100 Streams aufgeteilt.

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)

Teilen Sie mit Seq.chunkBySize durch 100 Elemente und summieren Sie mit Array.sum.

String-Konvertierung

In Python war es schneller, in einen String zu konvertieren und "StringIO" zu verwenden. Versuchen Sie den gleichen Vorgang mit F #.

Diese Methode wird abgelehnt, da sie in F # nicht sehr schnell ist.

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)

Textextraktion

Extrahieren Sie den Inhalt des XML-Tags "" und zählen Sie die Anzahl der Zeilen.

allgemeiner Teil

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)

Probieren Sie verschiedene Methoden aus. Ersetzt getPages durch die Methode.

String-Verarbeitung

Analysiert Tags mit Zeichenfolgenverarbeitung Zeile für Zeile.

Die Langsamkeit von "StartsWith" in .NET Framework scheint auf die Verarbeitung wie die Unicode-Normalisierung zurückzuführen zu sein.

• Vergleich der Präfixübereinstimmung von zusammengesetzten Zeichen zwischen .NET Framework und Python

Wenn Sie "Substring" verwenden, um das Äquivalent zu "StartsWith" zu erreichen, ist es endlich ungefähr so schnell wie Python.

StartsWith

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() }}

Erstellen und ersetzen Sie eine Funktion, die "StartsWith" ersetzt.

Scheibe

let inline startsWith (target:string) (value:string) =
    target.Length >= value.Length && target.[.. value.Length - 1] = value

Substring

let inline startsWith (target:string) (value:string) =
    target.Length >= value.Length && target.Substring(0, value.Length) = value

XML-Parser

Vergleichen Sie, wie Sie einen Baum mit einem XML-Parser erstellen und wie Sie nur analysieren, ohne einen Baum zu erstellen.

Das Root-Element wird zum Parsen von XML benötigt. Wie wir bereits gesehen haben, ist F # beim Durchlaufen von Strings langsam, daher kombinieren wir Streams für die Verarbeitung. Verwenden Sie den im folgenden Artikel erstellten "ConcatStream".

• Streams extrahieren und kombinieren → [fsharp / research / StreamUtils.fsx](https://github.com/7shi/wiktionary-tools/blob/ master / fsharp / research / StreamUtils.fsx)

Da ist ein Baum

F # ist langsamer als 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 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() }}

Kein Baum

In den folgenden Artikeln finden Sie Informationen zu verschiedenen Python-Parsern.

• Geschwindigkeitsvergleich der Python-XML-Perspektive

F # verwendet einen XmlReader vom Pull-Typ.

• "Ungeteilt" bedeutet einen Stream. Betrachtet man die Ergebnisse, so scheint es, dass aufgrund der Aufteilung fast kein Overhead entsteht.

Das .NET Framework "XmlDocument" wird mit "XmlReader" erstellt. XmlReader ist überwältigend schneller alleine zu benutzen. In den folgenden Schritten verwenden wir nur die XmlReader-Methode.

Die Situation sollte für Python dieselbe sein, aber es scheint, dass das Erstellen eines Baums viel effizienter und das Erstellen eines Baums schneller ist.

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() }
            | _ -> () }

Sprachtabelle

Aus dem bisherigen Code werden wir die gemeinsamen Teile herausdrücken.

• fsharp/research/MediaWikiParse.fsx

Erstellen Sie eine Tabelle, deren Elemente Daten in welcher Sprache enthalten (output1.tsv). Der Sprachname wird auf eine andere Tabelle (output2.tsv) normalisiert.

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

Da ein Artikel durch die Zeile "== Sprachname ==" getrennt ist, wird er erkannt und mit der ID verknüpft. Unterscheiden Sie, weil in den unteren Überschriften === item name === verwendet wird.

Wie wir bereits gesehen haben, ist "StartsWith" langsam. Vergleichen Sie, wie Sie jeweils ein Zeichen vom Anfang einer Zeile mit einem regulären Ausdruck nachschlagen.

Bei der XML-Analyse wird die Zeichenfolgenverarbeitung in Python und "XmlReader" in F # verwendet.

In F # ist es schnell, Zeichen für Zeichen nachzuschlagen, aber die Implementierung ist umständlich und nicht vielseitig. Reguläre Ausdrücke sind fast so schnell wie "StartsWith". In Anbetracht der Vielseitigkeit scheint es sicher, reguläre Ausdrücke zu verwenden.

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()

Zeichen für Zeichen

            for line in text do
                if line.Length >= 3 && line.[0] = '=' && line.[1] = '=' && line.[2] <> '=' then

Reguläre Ausdrücke

            for line in text do
                let m = r.Match line
                if m.Success then
                    let lang = m.Groups.[1].Value.Trim()

Parallelisierung

F # verwendet Multithreading und Python verwendet Multiprozess zur Parallelisierung.

• Beispiel für die parallele Berechnung von Python nach F #

Es ist ein enger Spielraum. Die Wachstumsbreite aufgrund der Parallelisierung ist in Python größer.

Zeichen für Zeichen

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() ]}

Reguläre Ausdrücke

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 und Mono

Gemessen mit .NET Core und Mono auf WSL1. Vergleichen Sie mit .NET Framework-Ergebnissen unter Windows.

Die Entsprechung mit der Abkürzung ist wie folgt.

• Framework: .NET Framework 4.8.03752 (Windows 10)
• Core: .NET Core 3.1.103 (WSL1)
• Mono: Mono 6.4.0 (WSL1)

.NET Core scheint so schnell oder etwas schneller als .NET Framework zu sein.

.NET Core dient im Grunde genommen zum Erstellen eines Projekts, war jedoch problematisch, da mehrere ausführbare Dateien vorhanden waren. Daher habe ich die Konfiguration mit der folgenden Methode geschrieben und damit fertig.

• Verwenden Sie F # mit .NET Core ohne Projekt

Impressionen

Die Verwendung der schnellsten Methode führte zu einem etwas schnelleren F #. Es war beeindruckend, dass Python schneller war, selbst wenn es mit demselben Verarbeitungsinhalt portiert wurde.

Wie ich im folgenden Artikel versucht habe, gibt es einen überwältigenden Unterschied in der zeichenbasierten Verarbeitung.

• Schreiben Sie ein Skript zum Konvertieren eines MySQL-Dumps in TSV