Какой самый быстрый способ получить значение nth nextInt? - PullRequest
Новая
       15

Какой самый быстрый способ получить значение nth nextInt?

0 голосов
/ 25 мая 2019

Я должен найти n-й nextInt каждого элемента массива.Приведенный ниже код очень медленный, так как элементы массива имеют размер более 40 Кбайт, а каждый элемент массива превышает миллион.если да, пожалуйста, как?

Ответы [ 2 ]

0 голосов
/ 25 мая 2019

Вам действительно нужно семя, чтобы случайная последовательность всегда была одинаковой? Затем вы можете отсортировать массив чисел по возрастанию. Тогда для второго элемента вам не нужно сбрасывать генератор случайных чисел, а просто продолжить с того места, где вы оставили. Таким образом, вам придется вызывать nextInt только так часто, как самый высокий номер в вашем массиве, вместо 40 миллиардов

0 голосов
/ 25 мая 2019

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

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

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

Далее, если вам требуется подобная повторяемость, вы можете их предварительно вычислить, и ваш код будет включать эту таблицу результатов.Затем вы можете просматривать результаты в постоянное время.

Если вам нужна повторяемая последовательность, которая выглядит случайной, но не обязательно должна быть этой конкретной последовательностью, вы можете использовать другой псевдослучайный генератор.Например, вы можете зашифровать «индекс» (1 миллион в вашем примере) блочным шифром и использовать несколько байтов из результата.Это также алгоритм с постоянным временем, независимо от индекса.

Вот реализация последней идеи: 

public class PredictableSequenceGenerator {

  private final int[] numbers;

  public PredictableSequenceGenerator(int[] numbers) {
    this.numbers = Objects.requireNonNull(numbers);
  }

  public int[] generate(long seed) {
    ByteBuffer src = ByteBuffer.wrap(new byte[16]);
    ByteBuffer dst = ByteBuffer.wrap(new byte[16]);
    src.putLong(seed).putLong(seed);
    SecretKey key = new SecretKeySpec(src.array(), "AES");
    Cipher cipher;
    try {
      cipher = Cipher.getInstance("AES/ECB/NoPadding");
      cipher.init(Cipher.ENCRYPT_MODE, key);
    } catch (GeneralSecurityException ex) {
      throw new IllegalStateException("Failed to initialize generator.", ex);
    }
    int[] results = new int[numbers.length];
    for (int idx = 0; idx < numbers.length; ++idx) {
      src.clear();
      src.putInt(0, idx);
      dst.clear();
      try {
        cipher.doFinal(src, dst);
      } catch (GeneralSecurityException ex) {
        throw new IllegalStateException("Failed to transform index.", ex);
      }
      results[idx] = dst.flip().getInt();
    }
    return results;
  }

  public static void main(String... argv) {
    int[] numbers = { 1000000, 1004300, 2204000, 1306000, /* 40k+ */ };
    PredictableSequenceGenerator gen = new PredictableSequenceGenerator(numbers);
    int[] random = gen.generate(1234);
    for (int r : random)
      System.out.println(r);
  }

}
...