Встроенная сортировка сравнения в Java

Question

Скажем, я хочу отсортировать элементы с 1 по 10 для случайного выбора после сортировки, с вероятностями выбора, связанными с весом каждого числа (т.е. вес 1 = 10, 2 = 30, 4 = 15, 5 = 35, 6 =)10, а остальные 0);Предположим, я уже вычислил сумму весов до этого.Прямо сейчас мне сначала нужно отсортировать числа по их весам, а затем снова пройти по списку, чтобы разделить каждое на сумму всех (т.е. нормализовать, чтобы вес каждого из них был в [0,1]).Сортировка и затем обход списка медленны, поэтому я попытался поместить весовое значение в метод compareTo(), чтобы оно нормализовалось при сортировке, но Collections.sort () не помещает их в правильном порядке, если я это делаю.Любые предложения (кроме того, чтобы написать свой собственный эффективный алгоритм сортировки с нуля)?Надеюсь, я был достаточно ясен.

Answer 1

Предполагая, ints является List:

Collections.sort(ints, new Comparator<Integer> () {
  private int getWeight(Integer i) {
    int weight = 0;
    switch(i) {
      case 1:
      case 6: weight = 10; break;
      case 2: weight = 30; break;
      case 4: weight = 15; break;
      case 5: weight = 35; break;
    }
    return weight;
  }

  public int compare(Integer i1, Integer i2) {
    int w1 = getWeight(i1);
    int w2 = getWeight(i2);
    return (w1>w2)?1:(w1==w2?0:-1);
  }});

for(int i:ints) {
  System.out.print(i+",");
}

Вы можете использовать enums или hashmap для хранения весов чисел, код был примером того, как проводить сравнение на основе веса.

Answer 2

Что заставляет вас думать, что вам нужно отсортировать по весу, чтобы выбрать случайные числа?

Я бы сделал:

int[] numbers;
int[] weight;

int totalweight;
for (int n : numbers) {
    totalweight += weight[n];
}

int t = new Random().nextInt(totalWeight);
for (int n : numbers) {
    t -= weight[n];
    if (t < 0) return n;
}

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

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

Довольно легко увидеть, что, если у вас нет предварительных знаний о числах или весах, вам нужно будет посмотреть на вескаждого числа (потому что он может затмить все остальные веса), поэтому общий алгоритм должен принимать не менее O (n).

Однако дополнительные ограничения позволяют более эффективные реализации.Если вы знаете достаточно маленькую верхнюю границу веса числа, вы можете сделать A / R-выборку:

int[] numbers;
int[] weight;
int maxWeight;

Random r = new Random();
do {
    c = numbers[r.nextInt(numbers.length)];
} while (r.nextInt(maxWeight) > weight[c]);
return c;

Answer 3

Просто предложение улучшить превосходное предложение Meriton:

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

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