Создание уникального случайного числа при каждом вызове

В интервью мне было предложено обратиться к методу, который будет генерировать уникальное 5-значное случайное число каждый раз, когда он будет вызван. Например: если я вызываю метод и получаю 22222, то в следующем вызове я не должен получать 22222.

Я написал код, как показано ниже:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class RandomNumberGen {
 private static ArrayList arr=new ArrayList();
 private static int k=-1;
 public RandomNumberGen(){
 for (int i=10000;i<99999;i++){
 arr.add(i);
 }
 Collections.shuffle(arr);
 }
 public static void main(String[] args) {
 for(int m=0;m<10;m++){
 try {
 System.out.println(new RandomNumberGen().randomNumbermethod());
 } catch (Exception e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 }
 }
 }
 public Integer randomNumbermethod() throws Exception{
 k++;
 if(k>=arr.size()){
 throw new Exception("No more number available");
 }else return (Integer) arr.get(k);
 }
}

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

5 ответов

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

import java.util.Collection;
import java.util.HashSet;
import java.util.Random;
public class UniqueRandom {
 static Random rnd=new Random();
 public static void main(String args[]){
 Collection<integer> alreadyChosen = new HashSet<integer>();
 for(int i=0;i<10;i++){
 System.out.println(getNextUniqueRandom (alreadyChosen));
 }
 }
 public static int getNextUniqueRandom(Collection<integer> alreadyChosen){
 if (alreadyChosen.size()==90000){ //hardcoded 5 figure numbers, consider making a variable
 throw new RuntimeException("All 5 figure IDs used");
 }
 boolean unique=false;
 int value=0;
 while(unique==false){
 value=rnd.nextInt(90000)+10000;
 unique=!alreadyChosen.contains(value);
 }
 alreadyChosen.add(value);
 return value;
 }
}
</integer></integer></integer>

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

Примечания для рассмотрения

  • Как уже было сказано, это будет очень медленным, так как больше значений выбранный, должен быть понятен конечному пользователю или даже лучше; изменить алгоритм после стольких вызовов


Последствия:

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

Сгенерированные числа можно отследить в коллекции (Установить). Это означает, что накладные расходы составляют 32 бит на номер (при отслеживании доступных или сгенерированных номеров) плюс накладные расходы на сбор. Другая возможность - использовать булев-массив и отметить, какие слоты были использованы. Опять же, это накладные расходы, поскольку булевы обычно сохраняются как 32-битное значение. Но там более дешевый способ хранения булевых: как упакованные биты в целое число. То, что делает java.util.BitSet, поэтому каждое булево будет занимать один бит.

Решение с BitSet и отслеживание количества доступных номеров:

public class RandomNumbers {
 private final Random random = new Random();
 private final BitSet used = new BitSet();
 private final int min = 10000;
 private final int max = 99999;
 private final int numbersAvailable = max - min + 1;
 public static void main (String[] args) {
 RandomNumbers randomNumbers = new RandomNumbers();
 for (int i = 0; i < 100; i++) {
 System.out.println(randomNumbers.nextRandom());
 }
 }
 public int nextRandom () throws NoSuchElementException {
 while (numbersAvailable > 0) {
 int rnd = min + random.nextInt(max - min + 1);
 if (!used.get(rnd)) {
 used.set(rnd);
 numbersAvailable--;
 return rnd;
 }
 }
 throw new NoSuchElementException();
 }
}


private static int number = 10000;
public int getNextUniqueRandomNumber() {
 return number++;
}


Просто

(int)(Math.random()*89999)+10000

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

Из моего комментария: после того, как вы получили около 50% номеров, я бы создал коллекцию оставшихся номеров, которые вы выбрали, то же самое, что и у вас, но вы должны документировать в классе, чтобы он мог замерзнуть на мгновение после 50% использования результатов и дать способность устанавливать этот фактор для клиента.

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


Кажется довольно простым. Более простое решение с меньшим объемом использования памяти - это просто создать набор, который будет содержать все номера, которые вы хотите:

Random random = new Random();
Set<integer> randomNumbers = new HashSet<integer>(10);
while(randomNumbers.size() < 10)
 randomNumbers.add( new Integer(random.nextInt(89999) + 10000) );
</integer></integer>

И просмотреть их все:

for(Integer randomNumber : randomNumbers){
 System.out.println(randomNumber);
}

Это гарантирует уникальность свойств набора и значительно улучшит использование вашей памяти.

licensed under cc by-sa 3.0 with attribution.