Bagaimanakah Saya Menjana Rentetan Pantas, Rawak bagi Set Panjang dalam Go?

Bagaimana untuk menjana rentetan rawak dengan panjang tetap dalam Go?

Masalah

Saya mahukan rentetan aksara rawak sahaja (huruf besar atau huruf kecil ), tiada nombor, dalam Go. Apakah cara terpantas dan paling mudah untuk melakukan ini?

Jawapan

Soalan mencari pendekatan "terpantas dan paling mudah". Jawapan Paul menawarkan teknik yang mudah. Walau bagaimanapun, mari kita pertimbangkan juga aspek "terpantas". Kami akan memperhalusi kod kami secara berulang, sampai pada penyelesaian yang dioptimumkan.

I. Penambahbaikan

1. Genesis (Runes)

Penyelesaian awal yang akan kami optimumkan ialah:

<code class="go">import (
    "math/rand"
    "time"
)

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}</code>

2. Bait

Jika aksara yang digunakan untuk rentetan rawak dihadkan kepada abjad Inggeris huruf besar dan kecil, kami boleh bekerja dengan bait kerana huruf abjad Inggeris memetakan 1-ke-1 kepada bait dalam pengekodan UTF-8 ( yang Go gunakan untuk menyimpan rentetan).

Jadi kita boleh menggantikan:

<code class="go">var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")</code>

dengan:

<code class="go">var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")</code>

Atau lebih baik lagi:

<code class="go">const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"</code>

Ini adalah peningkatan yang ketara kerana kini kita boleh menggunakan const (Go menyokong pemalar rentetan tetapi bukan pemalar hirisan). Selain itu, ungkapan len(huruf) juga akan tetap.

3. Baki

Penyelesaian sebelumnya menentukan nombor rawak untuk surat dengan memanggil rand.Intn() (yang mewakilkan kepada Rand.Intn() dan seterusnya ke Rand.Int31n()).

Ini lebih perlahan daripada menggunakan rand.Int63() yang menghasilkan nombor rawak dengan 63 bit rawak.

Jadi kita boleh panggil rand.Int63() dan gunakan bakinya selepas bahagikan dengan len(huruf):

<code class="go">func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letters[rand.Int63() % int64(len(letters))]
    }
    return string(b)
}</code>

Ini lebih pantas sambil mengekalkan taburan kebarangkalian yang sama bagi semua huruf (walaupun herotan boleh diabaikan, bilangan huruf 52 jauh lebih kecil daripada 1<<63 - 1).

4. Masking

Kita boleh mengekalkan pengagihan huruf yang sama dengan menggunakan hanya bit terendah nombor rawak, cukup untuk mewakili bilangan huruf. Untuk 52 huruf, 6 bit diperlukan: 52 = 110100b. Jadi kami hanya akan menggunakan 6 bit terendah nombor yang dikembalikan oleh rand.Int63().

Kami juga hanya "menerima" nombor itu jika ia berada dalam julat 0..len(letterBytes)-1 . Jika bit terendah lebih besar, kami membuang dan meminta nombor baharu.

<code class="go">const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
)

func RandStringBytesMask(n int) string {
    b := make([]byte, n)
    for i := 0; i < n; {
        if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i++
        }
    }
    return string(b)
}

5. Masking Improved

Penyelesaian sebelumnya hanya menggunakan 6 bit terendah daripada 63 bit rawak daripada rand.Int63(). Ini tidak cekap kerana mendapatkan bit rawak adalah bahagian paling perlahan dalam algoritma kami.

Memandangkan kami mempunyai 52 huruf, 6 bit mengekod indeks huruf. 63 bit rawak boleh menetapkan 63/6 = 10 indeks huruf yang berbeza. Jom gunakan kesemua 10:

const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return string(b)
}

6. Sumber
Masking Improved agak cekap. Mari kita pertimbangkan aspek lain: sumber nombor rawak.
Pakej crypto/rand menyediakan fungsi Baca(b []bait). Walau bagaimanapun, ini tidak akan membantu prestasi kerana crypto/rand melaksanakan penjana nombor pseudorandom yang selamat secara kriptografi, yang lebih perlahan.
Jadi kami akan berpegang pada pakej matematik/rand. rand.Rand menggunakan rand.Sumber sebagai sumber bit rawak. Jadi kita boleh menggunakan rand.Sumber terus:
<code class="go">import (
    "math/rand"
    "time"
)

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}</code>
Salin selepas log masuk
7. Menggunakan rentetan.Pembina
Penyelesaian sebelumnya mengembalikan rentetan yang dibina dahulu dalam kepingan ([]rune dalam Genesis dan []bait seterusnya) dan kemudian ditukar kepada rentetan. Penukaran akhir ini memerlukan penyalinan kandungan hirisan kerana nilai rentetan tidak boleh diubah.
Go 1.10 rentetan diperkenalkan.Builder. Jenis baharu ini boleh digunakan untuk membina kandungan rentetan sama seperti bait. Penampan. Ia menggunakan []bait secara dalaman dan tidak perlu menyalin kandungan untuk menghasilkan rentetan.
<code class="go">var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")</code>
Salin selepas log masuk
Salin selepas log masuk
8. "Meniru" rentetan.Builder dengan pakej tidak selamat
rentetan.Builder membina rentetan dalam []bait dalaman, seperti yang kita lakukan pada diri kita sendiri. Jadi menggunakan strings.Builder memperkenalkan beberapa overhed, yang kami hanya tukar untuk mengelakkan penyalinan akhir.
Walau bagaimanapun, kami juga boleh mengelakkan penyalinan ini dengan menggunakan pakej yang tidak selamat:
<code class="go">var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")</code>
Salin selepas log masuk
Salin selepas log masuk
Atas ialah kandungan terperinci Bagaimanakah Saya Menjana Rentetan Pantas, Rawak bagi Set Panjang dalam Go?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!