Псевдослучайная строка Golang (много дубликатов)

Я пытаюсь создать случайную строку из 5 символов. Каждая реализация, которую я пробовал, генерирует дубликаты после очень небольшого размера выборки (10–40 тысяч). Хотя я понимаю, что программно невозможно генерировать настоящие случайные строки, я был удивлен, увидев, что дубликаты появляются с такой высокой частотой.

Я попробовал несколько реализаций (и их вариантов), но безуспешно. Каждый из них генерирует дубликат максимум через ~ 40 тысяч строк. Учитывая, что в строке из 5 символов, состоящей из [A-Z a-z], содержится 380 204 032 уникальных комбинаций, я ожидал, что смогу сгенерировать значительно больше строк, прежде чем встретим дубликат.

Покопавшись вокруг, я нашел пару хороших источников, которые легли в основу моих реализаций.

Мое внимание особенно привлекла вторая ссылка, поскольку автор упомянул, что использование пакета "crypto/rand" позволяет лучше избегать дубликатов. Однако, похоже, не имело большого значения, сколько строк мне удалось сгенерировать, прежде чем я столкнулся с дубликатом.

Другие варианты, которые я пробовал

  • вызов rand.NewSource после каждого символа (вместо каждой строки)
  • используя несколько rand.NewSource и используя результат 1-го для заполнения 2-го, 3-го и т. д.

Может ли кто-нибудь дать некоторое представление о том, почему эти случайные строки не такие случайные, и какие шаги я мог бы предпринять, чтобы сгенерировать хотя бы 1 миллион строк, прежде чем встретить дубликат?

Я знаю, что могу использовать стороннюю библиотеку, но мне бы хотелось этого избежать.

func Test_RandomString(t *testing.T) {

    tests := map[string]struct {
        Length       int
        UniuqeValues int
    }{
        "5 x 1,000,000": {
            Length:       5,
            UniuqeValues: 1_000_000,
        },
    }

    for name, test := range tests {
        t.Run(name, func(t *testing.T) {
            actual := utils.RandomString(test.Length)
            assert.Equal(t, test.Length, len(actual))

            values := make(map[string]struct{})
            for count := 0; count < test.UniuqeValues; count++ {
                value := utils.RandomString(test.Length)

                _, found := values[value]
                if found {
                    t.Fatalf("duplicate value found after %v: %v", count, value)
                }

                values[value] = struct{}{}
            }

        })
    }
}
func RandomString_CryptoRand(length int) string {

    const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    var randomStr []byte = make([]byte, length)

    for i := 0; i < length; i++ {

        idx, _ := rand.Int(rand.Reader, big.NewInt(int64(len(letters))))
        randomStr[i] = letters[idx.Int64()]
    }
    return string(randomStr)
}
func RandomString_MathRand(length int) string {
    var src = rand.NewSource(time.Now().UnixNano())
    const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    sb := strings.Builder{}
    sb.Grow(length)

    for idx := 0; idx < length; idx++ {
        sb.WriteByte(letterBytes[int64(src.Int63())%int64(len(letterBytes))])
    }

    return sb.String()
}

«Я ожидал, что смогу сгенерировать значительно больше строк, прежде чем столкнусь с дубликатом». Можете ли вы объяснить математические расчеты, лежащие в основе ваших ожиданий? Вы уверены, что ваши ожидания оправданы? Знаете ли вы о «парадоксе дня рождения»?

Volker 03.09.2024 17:46

Помимо того факта, что ваши предположения неверны, вы используете новый ГПСЧ для каждой строки, поэтому ваш результат фактически такой же случайный, как time.Now()

JimB 03.09.2024 18:24

Да, я знаю «парадокс дня рождения». Хотя, похоже, я сделал еще одно фатальное предположение о том, что процент возможных значений останется постоянным... в парадоксе дня рождения необходимо 23 человека для 50% вероятности (23/365 = 6,3%). Поэтому ошибочно предполагалось, что для достижения вероятности 50% при генерации строки из 5 символов потребуются те же 6,3% (23 952 854) всех возможных значений (380 204 032).

SoonGuy 03.09.2024 18:25
Создание API ввода вопросов на разных языках программирования (Python, PHP, Go и Node.js)
Создание API ввода вопросов на разных языках программирования (Python, PHP, Go и Node.js)
API ввода вопросов - это полезный инструмент для интеграции моделей машинного обучения, таких как ChatGPT, в приложения, требующие обработки...
1
3
61
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Без сложной математики, даже без биномиального распределения: допустим, вы выбрали 20 000 из 380 204 032 и у вас еще не было ни одного двойника. В следующем розыгрыше ваши шансы на дубль составляют 20 000/380 204 032 = 0,0001052067.

С этого момента вероятность дубля будет постоянно увеличиваться, но, скажем так, это не так. Для следующих 20 000 розыгрышей мы добавим этот шанс для каждого розыгрыша и получим 20000/380204032 * 20000 = 1,05, что составляет > 1.

Таким образом, даже не принимая во внимание вероятность получения дубля в течение первых 20 000 розыгрышей и не обращая внимания на постоянное увеличение шанса на дубль, мы должны ожидать дубля в течение первых 40 тысяч розыгрышей.

Проблема здесь в ожиданиях, а не в лучшей функции или пакете Go.

Как насчет создания большего количества случайных строк, чем необходимо, а затем удаления двойников? (возможно, посмотрите код здесь: https://github.com/lehnert-b/spd)

Вероятности не могут превышать 1, поэтому ваш аргумент, основанный на умножении (многократном сложении), в корне ошибочен. Вероятность того, что отдельное новое значение уклоняется от всех уже принятых значений, постепенно стремится к нулю по мере добавления новых результатов. Однако вероятности независимых испытаний мультипликативны, поэтому произведение набора значений, уменьшающихся к нулю, начинает довольно быстро сходиться к нулю по мере увеличения количества элементов.

pjs 03.09.2024 19:11

Мой аргумент был ошибочным, если бы я назвал это вероятностью. Я не. Я следил за тем, сколько событий я ожидал. Ожидаемые числа не являются вероятностями.

Bernhard 03.09.2024 22:10

«Шанс» того, что что-то произойдет, выраженный в виде пропорции, представляет собой эмпирически обоснованное определение вероятности.

pjs 03.09.2024 22:30
Ответ принят как подходящий

Это парадокс дня рождения. Вы ошибочно предположили, что вероятность дубликатов линейно пропорциональна размеру пула 525, тогда как на самом деле эта связь пропорциональна квадратному корню. Sqrt(380204032) — это 19498 и изменение, что в значительной степени соответствует тому, что вы наблюдали.

Спасибо. Вы на 100% правы, это было мое ошибочное предположение.

SoonGuy 03.09.2024 18:43

Другие вопросы по теме