Каков самый быстрый способ генерации длинной случайной строки в Go?

Ответ 1

Это примерно 200 Мбит/с на моей коробке. Там есть очевидная возможность для улучшения.

type randomDataMaker struct {
    src rand.Source
}

func (r *randomDataMaker) Read(p []byte) (n int, err error) {
    for i := range p {
        p[i] = byte(r.src.Int63() & 0xff)
    }
    return len(p), nil
}

Вы просто используете io.CopyN для создания нужной строки. Очевидно, вы можете настроить набор символов на том или ином месте.

Хорошая вещь в этой модели заключается в том, что она просто io.Reader, поэтому вы можете использовать ее для чего-либо.

Тест ниже:

func BenchmarkRandomDataMaker(b *testing.B) {
    randomSrc := randomDataMaker{rand.NewSource(1028890720402726901)}
    for i := 0; i < b.N; i++ {
        b.SetBytes(int64(i))
        _, err := io.CopyN(ioutil.Discard, &randomSrc, int64(i))
        if err != nil {
            b.Fatalf("Error copying at %v: %v", i, err)
        }
    }
}

В одном ядре 2,7 ГГц i7:

BenchmarkRandomDataMaker       50000        246512 ns/op     202.83 MB/s

ИЗМЕНИТЬ

Поскольку я написал контрольный показатель, я решил, что сделаю очевидное улучшение (чаще обращайтесь к производителю). С 1/8 звонков на rand, он работает примерно в 4 раза быстрее, хотя он большой уродливый:

Новая версия:

func (r *randomDataMaker) Read(p []byte) (n int, err error) {
    todo := len(p)
    offset := 0
    for {
        val := int64(r.src.Int63())
        for i := 0; i < 8; i++ {
            p[offset] = byte(val & 0xff)
            todo--
            if todo == 0 {
                return len(p), nil
            }
            offset++
            val >>= 8
        }
    }

    panic("unreachable")
}

Новый тест:

BenchmarkRandomDataMaker      200000        251148 ns/op     796.34 MB/s

РЕДАКТИРОВАТЬ 2

Вытащил маскирование в литье в байт, поскольку он был избыточным. Получилось намного быстрее:

BenchmarkRandomDataMaker      200000        231843 ns/op     862.64 MB/s

(это намного проще, чем реальный вздох)

РЕДАКТИРОВАТЬ 3

Сегодня это появилось в irc, поэтому я выпустил библиотеку. Кроме того, мой фактический инструмент сравнения, хотя и полезен для относительной скорости, недостаточно достоверен в своих отчетах.

Я создал randbo, чтобы вы могли повторно использовать произвольные потоки, где бы они вам ни понадобились.

Ответ 2

Вы можете использовать пакет Go uniuri для генерации случайных строк (или просмотреть исходный код, чтобы увидеть, как они это делают), Вы хотите использовать:

func NewLen(length int) string

NewLen возвращает новую случайную строку предоставленной длины, состоящую из стандартных символов.

Или, чтобы указать набор используемых символов:

func NewLenChars(length int, chars []byte) string

Ответ 3

Это на самом деле немного предвзято по отношению к первым 8 символам в наборе (поскольку 255 не кратно len(alphanum)), но это даст вам большую часть пути.

import (
    "crypto/rand"
)

func randString(n int) string {
    const alphanum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    var bytes = make([]byte, n)
    rand.Read(bytes)
    for i, b := range bytes {
        bytes[i] = alphanum[b % byte(len(alphanum))]
    }
    return string(bytes)
}

Ответ 4

Здесь Эван Шоу ответил на повторную работу без смещения в сторону первых 8 символов строки. Обратите внимание, что он использует множество дорогостоящих операций big.Int, поэтому, вероятно, это не так быстро! Ответ крипто сильный, хотя.

Он использует rand.Int для создания целого числа точно соответствующего размера len(alphanum) ** n, а затем делает то, что фактически является базовым преобразованием в базу len(alphanum).

Существует почти наверняка лучший алгоритм для этого, который предполагает сохранение гораздо меньшего остатка и добавление к нему случайных байтов по мере необходимости. Это избавит вас от дорогостоящей длинной целочисленной арифметики.

import (
    "crypto/rand"
    "fmt"
    "math/big"
)

func randString(n int) string {
    const alphanum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    symbols := big.NewInt(int64(len(alphanum)))
    states := big.NewInt(0)
    states.Exp(symbols, big.NewInt(int64(n)), nil)
    r, err := rand.Int(rand.Reader, states)
    if err != nil {
        panic(err)
    }
    var bytes = make([]byte, n)
    r2 := big.NewInt(0)
    symbol := big.NewInt(0)
    for i := range bytes {
        r2.DivMod(r, symbols, symbol)
        r, r2 = r2, r
        bytes[i] = alphanum[symbol.Int64()]
    }
    return string(bytes)
}

Ответ 5

Если вы хотите генерировать криптографически безопасную случайную строку, я рекомендую вам взглянуть на на этой странице. Вот вспомогательная функция, которая считывает n случайные байты из источника случайности вашей ОС, а затем использует эти байты для base64encode. Обратите внимание, что длина строки будет больше, чем n из-за base64.

package main

import(
    "crypto/rand"
    "encoding/base64"
    "fmt"
)

func GenerateRandomBytes(n int) ([]byte, error) {
    b := make([]byte, n)
    _, err := rand.Read(b)
    if err != nil {
        return nil, err
    }

    return b, nil
}

func GenerateRandomString(s int) (string, error) {
    b, err := GenerateRandomBytes(s)
    return base64.URLEncoding.EncodeToString(b), err
}

func main() {
    token, _ := GenerateRandomString(32)
    fmt.Println(token)
}

Ответ 6

Я сделал несколько тестов, и пакет Dustin randbo был самым быстрым, что я видел. Я искал его и делал несколько оптимизаций, поэтому он стал быстрее: GitHub