Jak wygenerować losowy ciąg o ustalonej długości w Go?

Rozwiązanie Pawła zapewnia proste, ogólne rozwiązanie.

Pytanie zadaje "najszybszy i najprostszy sposób" . Zajmijmy się tym. Dotrzemy do naszego ostatecznego, najszybszego kodu w sposób iteracyjny. Benchmarking każdą iterację można znaleźć na końcu odpowiedzi.

Wszystkie rozwiązania i Kod benchmarkingu można znaleźć na Go Playground . Kod na placu zabaw jest plikiem testowym, a nie wykonywalnym. Musisz zapisać go do pliku o nazwie XX_test.go i uruchom go z go test -bench ..

I. Ulepszenia

1. Genesis (Runy)

Dla przypomnienia, oryginalne, ogólne rozwiązanie, które ulepszamy, jest następujące:]}

func init() {
    rand.Seed(time.Now().UnixNano())
}

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

2. Bajty

Jeśli znaki do wyboru i złożenia losowego ciągu zawiera tylko wielkie i małe litery alfabetu angielskiego, możemy pracować z bajtami tylko dlatego, że litery alfabetu angielskiego mapują bajty 1-do-1 w kodowaniu UTF-8 (co jest jak Go przechowuje struny).

Więc zamiast:

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

Możemy użyć:

var letters = []bytes("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

Albo nawet lepiej:

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

Teraz jest to już duża poprawa: moglibyśmy to osiągnąć jako const (istnieją string stałe, ale nie ma stałych slice ). Jako dodatkowy zysk, wyrażenie len(letters) będzie również const! (Wyrażenie {[16] } jest stałe, jeśli {[17] } jest stałą łańcuchową.)

I jakim kosztem? Zupełnie nic. stringS mogą być indeksowane, które indeksują swoje bajty, idealne, dokładnie to, czego chcemy.

Nasz następny cel wygląda tak:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func RandStringBytes(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Intn(len(letterBytes))]
    }
    return string(b)
}

3. Reszta

Poprzednie rozwiązania otrzymują losową liczbę, aby wyznaczyć losową literę, wywołując rand.Intn() które delegaci do Rand.Intn() które delegaci do Rand.Int31n().

Jest to znacznie wolniejsze w porównaniu do rand.Int63() co daje liczbę losową z 63 losowymi bitami.

Więc możemy po prostu zadzwonić rand.Int63() i użyć reszty po podzieleniu przez len(letterBytes):

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

To działa i jest znacznie szybsze, wadą jest to, że prawdopodobieństwo wszystkich liter nie będzie dokładnie takie samo (zakładając, że rand.Int63() produkuje wszystkie 63-bitowe liczby z równym prawdopodobieństwem). Chociaż zniekształcenie jest bardzo małe, ponieważ liczba liter 52 jest znacznie-znacznie mniejsza niż 1<<63 - 1, więc w praktyce jest to całkowicie w porządku.

^{aby to zrozumieć łatwiej: powiedzmy, że chcesz losową liczbę w zakresie 0..5. Używając 3 losowych bitów, uzyskamy liczby 0..1 Z Podwójnym prawdopodobieństwem niż z zakresu 2..5. Używając 5 losowych bitów, liczby z zakresu 0..1 występują z prawdopodobieństwem 6/32, A liczby z zakresu 2..5 z prawdopodobieństwem 5/32, które jest teraz bliższe pożądanemu. Zwiększenie liczby bitów sprawia, że jest to mniej znaczące, przy osiągnięciu 63 bitów jest znikome.}

4. Maskowanie

Bazując na poprzednim rozwiązaniu, możemy utrzymać równe rozkład liter za pomocą tylko tyle najniższych bitów liczby losowej, ile jest wymagane do reprezentowania liczby liter. Na przykład, jeśli mamy 52 litery, potrzeba 6 bitów, aby ją reprezentować: 52 = 110100b. Będziemy więc używać tylko najniższych 6 bitów liczby zwracanej przez rand.Int63(). Aby zachować równomierny rozkład liter, "akceptujemy" liczbę tylko wtedy, gdy mieści się ona w przedziale 0..len(letterBytes)-1. Jeśli najniższe bity są większe, odrzucamy je i pytamy o nową liczbę losową.

Uwaga że szansa, że najniższe bity będą większe lub równe len(letterBytes) jest mniejsza niż 0.5 w ogólności (średnio0.25), co oznacza, że nawet gdyby tak było, powtarzanie tego "rzadkiego" przypadku zmniejsza szansę Nie znalezienia dobrej liczby. Po powtórzeniu n szansa, że sill nie będzie miał dobrego indeksu jest znacznie mniejsza niż pow(0.5, n), a to jest tylko górne oszacowanie. W przypadku 52 liter szansa, że 6 najniższych bitów nie jest dobre jest tylko (64-52)/64 = 0.19; co oznacza na przykład szansa, że po 10 powtórzeniach nie będzie dobrej liczby jest 1e-8.

Oto rozwiązanie:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
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. Poprawiono Maskowanie

Poprzednie rozwiązanie używa tylko najniższych 6 bitów z 63 losowych bitów zwracanych przez rand.Int63(). Jest to strata, ponieważ pobieranie losowych bitów jest najwolniejszą częścią naszego algorytmu.

Jeśli mamy 52 litery, oznacza to, że 6 bitów koduje indeks liter. Tak więc 63 losowe bity mogą wyznaczać 63/6 = 10 różne indeksy literowe. Wykorzystajmy te wszystkie 10:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

func RandStringBytesMaskImpr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdxMax letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 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. Źródło

Ulepszone maskowanie jest całkiem dobre, niewiele możemy na nim poprawić. Moglibyśmy, ale nie warte złożoności.

Teraz znajdźmy coś innego do poprawy. Źródło liczb losowych.

Istnieje crypto/rand pakiet, który zapewnia Read(b []byte) funkcji, więc możemy tego użyć, aby uzyskać tyle bajtów za pomocą jednego wywołania, ile potrzebujemy. Nie pomogłoby to pod względem wydajności, ponieważ crypto/rand implementuje kryptograficznie Bezpieczny generator liczb pseudorandomowych, więc jest znacznie wolniejszy.

Więc trzymajmy się math/rand pakietu. rand.Rand używa rand.Source jako źródło losowych bitów. {[52] } jest interfejsem, który określa metodę Int63() int64: dokładnie i jedyną rzeczą, której potrzebowaliśmy i wykorzystaliśmy w naszym najnowszym rozwiązaniu.

Więc tak naprawdę nie potrzebujemy rand.Rand (zarówno jawnego, jak i globalnego, wspólnego pakietu rand), a rand.Source jest w zupełności wystarczające dla us:

var src = rand.NewSource(time.Now().UnixNano())

func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

Zauważ również, że to ostatnie rozwiązanie nie wymaga inicjalizacji (zalążka) globalnego Rand pakietu math/rand, ponieważ nie jest ono używane (a nasza rand.Source jest odpowiednio zainicjalizowana / zaszeregowana).

Jeszcze jedno: pakiet doc math/rand stwierdza:

Domyślne źródło jest bezpieczne dla jednoczesnego użycia wielu goroutines.

Więc domyślne źródło jest wolniejsze niż Source, które można uzyskać przez rand.NewSource(), ponieważ domyślne źródło musi zapewniać bezpieczeństwo przy równoczesnym dostępie / użyciu, podczas gdy rand.NewSource() nie oferuje tego (a zatem Source zwracane przez niego jest bardziej prawdopodobne, że będzie szybsze).

(7. Using rand.Read())

Go 1.7 dodano a rand.Read() funkcja i a Rand.Read() metoda. Powinniśmy pokusić się o ich użycie, aby w jednym kroku odczytać tyle bajtów, ile potrzebujemy, aby osiągnąć lepszą wydajność.

Jest jeden mały "problem" z tym: ile bajtów potrzebujemy? My można powiedzieć: tyle ile liczba liter wyjściowych. Uważamy, że jest to wyższa wartość, ponieważ indeks literowy używa mniej niż 8 bitów (1 bajt). Ale w tym momencie mamy już gorzej (ponieważ uzyskanie losowych bitów jest "trudną częścią") i otrzymujemy więcej niż potrzeba.

Zauważ również, że aby utrzymać równy rozkład wszystkich indeksów literowych, mogą istnieć pewne" śmieci " losowe DANE, których nie będziemy w stanie użyć, więc skończymy na pominięciu niektórych danych, a tym samym skończą się krótkie, gdy przejrzyj cały kawałek bajtu. Będziemy musieli uzyskać więcej losowych bajtów, "rekurencyjnie". A teraz tracimy nawet przewagę "pojedynczego połączenia do rand pakietu"...

Moglibyśmy" nieco " zoptymalizować wykorzystanie losowych danych, które pozyskujemy z math.Rand(). Możemy oszacować, ile bajtów (bitów) będziemy potrzebować. 1 litera wymaga letterIdxBits bitów i potrzebujemy n liter, więc potrzebujemy n * letterIdxBits / 8.0 bajtów zaokrąglonych w górę. Możemy obliczyć prawdopodobieństwo, że indeks losowy nie będzie użyteczny (patrz wyżej), więc może zażądać więcej, że" bardziej prawdopodobne " wystarczy (jeśli okaże się, że nie jest, powtarzamy proces). Możemy na przykład przetworzyć kawałek bajtu jako "strumień bitowy", dla którego mamy ładny lib 3rd party: github.com/icza/bitio (ujawnienie: jestem autorem).

Odpowiedź na ostatnie pytanie brzmi, ponieważ rand.Read() używa pętli i ciągle wywołuje Source.Int63() dopóki nie wypełni przekazanego plasterka. Dokładnie jakie rozwiązanie RandStringBytesMaskImprSrc() czy, bez bufora pośredniego i bez dodatkowej złożoności. Dlatego pozostaje na tronie. Tak, RandStringBytesMaskImprSrc() używa niesynchronizowanego rand.Source W przeciwieństwie do rand.Read(). Ale rozumowanie nadal ma zastosowanie; i co jest udowodnione, jeśli używamy Rand.Read() zamiast rand.Read() (pierwsze jest również niesynchronizowane).

II. Benchmark

BenchmarkRunes                   1000000              1703 ns/op
BenchmarkBytes                   1000000              1328 ns/op
BenchmarkBytesRmndr              1000000              1012 ns/op
BenchmarkBytesMask               1000000              1214 ns/op
BenchmarkBytesMaskImpr           5000000               395 ns/op
BenchmarkBytesMaskImprSrc        5000000               303 ns/op

Po prostu przełączając się z Run na bajty, natychmiast mamy 22% wzrost wydajności.

Pozbycie się rand.Intn() i użycie rand.Int63() zamiast tego daje kolejny 24% boost.

Maskowanie (i powtarzanie w przypadku dużych indeksów) trochę spowalnia (z powodu powtarzania wywołań): -20%...

Ale kiedy wykorzystamy wszystkie (lub większość) z 63 losowych bitów (10 indeksów z jednego wywołania rand.Int63()): to przyspiesza 3,4 razy .

I wreszcie, jeśli rozliczymy się z (nie domyślnym, nowym) rand.Source zamiast rand.Rand, ponownie zyskujemy 23%.

Porównanie końcowego z początkowym rozwiązaniem: RandStringBytesMaskImprSrc() jest5,6 razy szybsze niż RandStringRunes().