囲碁における文字列比較の最適化

あなたの移動プログラムを高速実行したいですか?文字列比較の最適化は、アプリケーションの応答時間を改善し、スケーラビリティを高めることができます.二つの文字列を比較すると、それらが等しいかどうかを比較するのは処理能力がかかりますが、すべての比較は同じではありません.前の記事では、How to compare strings in Goを見て、いくつかのベンチマーキングを行いました.我々はここでそれを展開するつもりです.
それは小さなもののように見えるかもしれません、しかし、すべてのすばらしい最適化者が知っているように、それは少しのものを加えます.掘りましょう.

事例感受性比較の測定

まず、2種類の文字列比較を測定しましょう.

方法1 :比較演算子の使用

if a == b {
  return true
}else {
  return false
}

方法2 :文字列の使用。比較する

if strings.Compare(a, b) == 0 {
  return true
}
return false

それで、我々は最初の方法が少しより簡単であるということを知っています.我々は標準ライブラリから任意のパッケージを持って来る必要はありません、それは少し少ないコードです.公平には、しかし、どちらが速いですか?見つけましょう.
最初に、我々はテストファイルを1つのアプリケーションを設定するつもりです.我々は、ベンチマークユーティリティをGo Testツールから使用するつもりです.

比較する。試み

package main

import (
    "strings"
)

func main() {
}

// operator compare
func compareOperators(a string, b string) bool {
  if a == b {
       return true
    }else {
       return false
    }
}

// strings compare
func compareString(a string, b string) bool {
  if strings.Compare(a, b) == 0 {
       return true
    }
    return false
}

そのためのテストセットを作成します.

コンパックテスト.試み

package main

import (
    "testing"
)

func BenchmarkCompareOperators(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareOperators("This is a string", "This is a strinG")
    }
}

func BenchmarkCompareString(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareString("This is a string", "This is a strinG")
    }
}

文字列のサンプルでは、最後の文字を変更して、文字列全体を解析します.
あなたがこれをしなかったならば、いくつかのメモ

私たちはGo testing packageを使用しています

それを命名することによって、

.試みはここでテストを探すのを知っています.

テストの代わりに、ベンチマークを挿入します.各funcはベンチマークに先行しなければならない

我々はベンチフラグ

で我々のテストを実行します
ベンチマークを実行するには、次のコマンドを使用します.

go test -bench=.

結果はこちら

したがって、標準の比較演算子を使用すると、文字列パッケージからメソッドを使用するよりも高速です.7.39ナノ秒対2.92
テストを複数回実行すると、同様の結果が表示されます.

それで、それは明らかにより速いです.5 msは十分な規模で大きな違いを生むことができます.

Verdict: Basic string comparison is faster than strings package comparison for case sensitive string compares.

大文字小文字を区別しない比較

それを変えましょう.一般的に、文字列比較を行うとき、文字列のテストがどの文字にマッチしてもマッチするかどうかを見たい.これは、我々の操作に若干の複雑さを加えます.

sampleString := "This is a sample string"
compareString := "this is a sample string"

標準の比較では、これらの2つの文字列は、tが資本化されているので、等しくはありません.
しかし、我々は今、テキストを探しており、どのように資本化を気にしないでください.では、以下のように関数を変更しましょう.

// operator compare
func compareOperators(a string, b string) bool {
    if strings.ToLower(a) == strings.ToLower(b) {
        return true
    }
    return false
}

// strings compare
func compareString(a string, b string) bool {
    if strings.Compare(strings.ToLower(a), strings.ToLower(b)) == 0 {
        return true
    }
    return false
}

各比較の前に、両方の文字列を小文字にします.我々は確かにいくつかの余分なサイクルで追加している.ベンチマークしましょう.

彼らは同じように見える.確かに数回実行します.

うん、彼らは同じだ.でもどうして?
つの理由は、我々はすべての実行にStrings.ToLowerアクションを追加しました.これはパフォーマンスヒットです.文字列が単純なルーン文字であることを覚えていて、tolower ()メソッドはruneを通してループし、すべての文字を小文字にして比較を行います.この余分な時間は、アクション間の任意の大きな違いを洗う.

近似

最後の記事では、大文字小文字を区別しない比較を行う別の方法として、私たちは見てみました.我々は、3倍法の最速値である.ベンチマークのこのセットがそれを反映するかどうか見ましょう.
比較するためにこれを加えてください.試み

// EqualFold compare
func compareEF(a string, b string) bool {
    if strings.EqualFold(sampleString, compareString) {
        return true
    }else {
        return false
    }
}

また、CompareRankテストに次のテストを追加します.試み

func BenchmarkEqualFold(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareEF("This is a string", "This is a strinG")
    }
}

では、次の3つの方法でベンチマークを実行できます.

すごい!equalfoldはかなり速いです.私は同じ結果を数回実行します.
なぜそれはより速いですか?また、別の文字を見つけたときには、文字によってrune文字を解析しますが、それは「初期に落ちる」ということです.

Verdict: EqualFold (Strings Package) comparison is faster for case sensitive string compares.

テストの準備をしましょう

ので、これらのベンチマークは、メソッド間の重要な違いを示す知っている.もっと複雑にしましょう.
最後の記事では、この200,000 line word listで比較を行うために追加しました.このファイルを開くためにメソッドを変更し、マッチを見つけるまで文字列比較を実行します.

このファイルでは、私たちがファイルの最後に探している名前を追加しましたので、一致する前にテストをループする必要があります.
メソッドを次のように変更します.

比較する。試み

// operator compare
func compareOperators(a string) bool {
    file, err := os.Open("names.txt")
    result := false;

    if err != nil {
        log.Fatalf("failed opening file: %s", err)
    }

    scanner := bufio.NewScanner(file)
    scanner.Split(bufio.ScanLines)

    for scanner.Scan() {
        if strings.ToLower(a) == strings.ToLower(scanner.Text()) {
            result = true
        }else {
            result = false
        }
    }
    file.Close()
    return result
}

// strings compare
func compareString(a string) bool {
    file, err := os.Open("names.txt")
    result := false;

    if err != nil {
        log.Fatalf("failed opening file: %s", err)
    }

    scanner := bufio.NewScanner(file)
    scanner.Split(bufio.ScanLines)

    for scanner.Scan() {
        if strings.Compare(strings.ToLower(a), strings.ToLower(scanner.Text())) == 0  {
            result = true
        }else {
            result = false
        }
    }
    file.Close()
    return result
}

// EqualFold compare
func compareEF(a string) bool {
    file, err := os.Open("names.txt")
    result := false;

    if err != nil {
        log.Fatalf("failed opening file: %s", err)
    }

    scanner := bufio.NewScanner(file)
    scanner.Split(bufio.ScanLines)

    for scanner.Scan() {
        if strings.EqualFold(a, scanner.Text()) {
            result = true
        }else {
            result = false
        }
    }
    file.Close()
    return result
}

はい、これらの各々は現在行きます

テキストファイル

を開きます

はライン

で線を解析します

検索フレーズ

を探してください
今テストを変えましょう.

コンパックテスト.試み

func BenchmarkCompareOperators(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareOperators("Immanuel1234")
    }
}

func BenchmarkCompareString(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareString("Immanuel1234")
    }
}

func BenchmarkEqualFold(b *testing.B) {
    for n := 0; n < b.N; n++ {
        compareEF("Immanuel1234")
    }
}

だから今、私たちはテストが長くかかることを期待できるので、ベンチマークツールからの反復が少なくなります.走りましょう

そして、equalfoldはまだ上に、かなり少し出てくる.
このテストの複雑さに加えて良いと悪いです.
良い:テキストの読み取りとシーケンシャルテストを行うこと
良い:異なる文字列でより多様なテストを強制することができます
悪い:私たちの結果を歪める可能性のあるいくつかの要因(ファイルの読み込みなど)を紹介します.

Verdict: EqualFold (Strings Package) comparison is STILL faster for case sensitive string compares.

しかし、待って、もっと！

我々がこれをさらに速くすることができるどんな方法もありますか?もちろん.私は文字列の文字を数えることを試みることにした.文字の数が異なる場合は、同じ文字列ではないので、我々は“初期”を比較することができますを比較してください.
しかし、文字列が同じ長さが異なる文字の場合には、equalfoldを含める必要があります.カウントの追加チェックは、操作がより高価になりますので、それが速くなるだろうか?見つけましょう.

比較する。試み

func compareByCount(a string) bool {
    file, err := os.Open("names.txt")
    result := false;

    if err != nil {
        log.Fatalf("failed opening file: %s", err)
    }

    scanner := bufio.NewScanner(file)
    scanner.Split(bufio.ScanLines)

    for scanner.Scan() {
        if len(a) == len(scanner.Text()) &&  strings.EqualFold(a, scanner.Text()){
            result = true
        }else {
            result = false
        }
    }
    file.Close()
    return result
}

コンパックテスト.試み

func BenchmarkCompareByCount(b *testing.B){
    for n := 0; n < b.N; n++ {
        compareByCount("Immanuel1234")
    }
}

そして、それは本当に速いです!あらゆる小さいビットは数えます.

Verdict: Do a character count with your EqualFold comparison for even more speed

概要

この記事では、いくつかの異なる文字列比較メソッドを見ました.ボトムライン:大文字小文字を区別しない比較のための基本的な比較を使用してください、そして、大文字小文字を区別しない比較のために文字カウント+ equalfold.
私はこれのようなテストをするのが好きです、そして、あなたが最適化をしているとき、小さい変化がかなり素晴らしくなるとわかるでしょう.私たちがこのような最適化を見るより多くの記事のために、とどまってください.
あなたはどう思いますか.Let me know!