Генерация случайных строк Java и парадокс дня рождения
Мне нужно написать случайный класс генерации строк, который генерирует 7-символьные строки из 31-символьной кодировки чисел и некоторых алфавитов (10+26-5, 5 гласных опущены). простая математика дает набор из 31^7 возможных комбинаций ~ 27,5 млрд. У меня есть вопросы, касающиеся парадокса bday, я провел несколько тестов, и количество дубликатов увеличивается в геометрической прогрессии. Могу ли я сделать что-нибудь, чтобы избежать этого?
At 1 million, duplicates encountered till now = 19
At 2 million, duplicates encountered till now = 69
At 3 million, duplicates encountered till now = 157
At 4 million, duplicates encountered till now = 280
At 5 million, duplicates encountered till now = 470
At 6 million, duplicates encountered till now = 662
At 7 million, duplicates encountered till now = 896
At 8 million, duplicates encountered till now = 1185
At 9 million, duplicates encountered till now = 1500
At 10 million, duplicates encountered till now = 1823
At 11 million, duplicates encountered till now = 2204
At 12 million, duplicates encountered till now = 2584
At 13 million, duplicates encountered till now = 3020
At 14 million, duplicates encountered till now = 3527
At 15 million, duplicates encountered till now = 4110
At 16 million, duplicates encountered till now = 4683
At 17 million, duplicates encountered till now = 5284
At 18 million, duplicates encountered till now = 5919
At 19 million, duplicates encountered till now = 6611
At 20 million, duplicates encountered till now = 7343
At 21 million, duplicates encountered till now = 8095
At 22 million, duplicates encountered till now = 8858
At 23 million, duplicates encountered till now = 9707
At 24 million, duplicates encountered till now = 10547
At 25 million, duplicates encountered till now = 11452
At 26 million, duplicates encountered till now = 12399
At 27 million, duplicates encountered till now = 13356
At 28 million, duplicates encountered till now = 14393
At 29 million, duplicates encountered till now = 15369
At 30 million, duplicates encountered till now = 16436
Ниже приведен тестовый класс:
import java.util.Set;
import org.apache.commons.lang3.RandomStringUtils;
import com.google.common.collect.Sets;
public class RandomUnivmylocaL {
public static void main(String[] argv) {
final int million = 1_000_000;
final int iterations = 30;
// 31 chars
final char[] charArr = new char[] { '1', '2', '3', '4', '5', '6', '7',
'8', '9', '0', 'B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L',
'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z' };
// System.out.println(charArr.length);
final Set<String> set = Sets.newHashSetWithExpectedSize(
iterations * million);
for (int i = 0; i < iterations; i++) {
for (int j = 0; j < million; j++) {
final String univCode = RandomStringUtils.random(7, charArr);
set.add(univCode);
}
System.out.println("At " + (i + 1) + " million, " +
"duplicates encountered till now = " +
(((i + 1) * million) - set.size()));
}
System.out.println("done");
}
}
1 ответ
Это парадокс дня рождения.
sqrt (27.5bn) = 165831, формула парадокса дня рождения для большого M равна 1.177*sqrt(M), поэтому, когда вы сгенерируете около 200 000, вероятность возникновения проблемы составит 50/50, а к миллиону вы получите будет около 18 проблем и т.д..
Проблема дня рождения - сколько, пока есть вероятность, что вы получите столкновение - около 200 000. http://www.wolframalpha.com/input/?i=n%3D200000,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)
Установите n = 23,0 и m = 365, чтобы увидеть 23 человека в эквивалентном номере. http://www.wolframalpha.com/input/?i=n%3D23.0,+m%3D365,+n+-+m(1+-+((m-1)%2Fm)%5En)
Вы можете видеть, насколько близко было ваше моделирование к ожидаемому ответу для больших чисел.
http://www.wolframalpha.com/input/?i=n%3D30e6,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)
Статья Quora хороша. http://www.quora.com/How-can-I-calculate-the-expected-number-of-cache-hits.
Поэтому вам нужно увеличить количество разрешенных символов или использовать более длинную строку. ИЛИ - чтобы использовать 7 цифр, просто увеличьте счетчик. ИЛИ используйте случайные и проверьте, использовали ли вы это раньше, и перезагрузите, когда вам надоест искать новые номера.
Существуют также псевдослучайные генераторы, которые могут покрывать пространство без повторных попаданий. 7 символов просто не сделают ваше решение безопасным.