Я пытаюсь создать случайную строку из 5 символов. Каждая реализация, которую я пробовал, генерирует дубликаты после очень небольшого размера выборки (10–40 тысяч). Хотя я понимаю, что программно невозможно генерировать настоящие случайные строки, я был удивлен, увидев, что дубликаты появляются с такой высокой частотой.
Я попробовал несколько реализаций (и их вариантов), но безуспешно. Каждый из них генерирует дубликат максимум через ~ 40 тысяч строк. Учитывая, что в строке из 5 символов, состоящей из [A-Z a-z], содержится 380 204 032 уникальных комбинаций, я ожидал, что смогу сгенерировать значительно больше строк, прежде чем встретим дубликат.
Покопавшись вокруг, я нашел пару хороших источников, которые легли в основу моих реализаций.
Как сгенерировать случайную строку фиксированной длины в Go?
https://www.datagenx.net/2022/10/random-number-genearion-with-cryptorand.html
Мое внимание особенно привлекла вторая ссылка, поскольку автор упомянул, что использование пакета "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()
}
Помимо того факта, что ваши предположения неверны, вы используете новый ГПСЧ для каждой строки, поэтому ваш результат фактически такой же случайный, как time.Now()
Да, я знаю «парадокс дня рождения». Хотя, похоже, я сделал еще одно фатальное предположение о том, что процент возможных значений останется постоянным... в парадоксе дня рождения необходимо 23 человека для 50% вероятности (23/365 = 6,3%). Поэтому ошибочно предполагалось, что для достижения вероятности 50% при генерации строки из 5 символов потребуются те же 6,3% (23 952 854) всех возможных значений (380 204 032).
Без сложной математики, даже без биномиального распределения: допустим, вы выбрали 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, поэтому ваш аргумент, основанный на умножении (многократном сложении), в корне ошибочен. Вероятность того, что отдельное новое значение уклоняется от всех уже принятых значений, постепенно стремится к нулю по мере добавления новых результатов. Однако вероятности независимых испытаний мультипликативны, поэтому произведение набора значений, уменьшающихся к нулю, начинает довольно быстро сходиться к нулю по мере увеличения количества элементов.
Мой аргумент был ошибочным, если бы я назвал это вероятностью. Я не. Я следил за тем, сколько событий я ожидал. Ожидаемые числа не являются вероятностями.
«Шанс» того, что что-то произойдет, выраженный в виде пропорции, представляет собой эмпирически обоснованное определение вероятности.
Это парадокс дня рождения. Вы ошибочно предположили, что вероятность дубликатов линейно пропорциональна размеру пула 525, тогда как на самом деле эта связь пропорциональна квадратному корню. Sqrt(380204032) — это 19498 и изменение, что в значительной степени соответствует тому, что вы наблюдали.
Спасибо. Вы на 100% правы, это было мое ошибочное предположение.
«Я ожидал, что смогу сгенерировать значительно больше строк, прежде чем столкнусь с дубликатом». Можете ли вы объяснить математические расчеты, лежащие в основе ваших ожиданий? Вы уверены, что ваши ожидания оправданы? Знаете ли вы о «парадоксе дня рождения»?