CODEWITHSUNDEEP
javasortingcomparison
John
John

Reputation: 1

Built-in comparison sorting in Java

Say I want to sort items 1 to 10 to randomly choose from after sorting, with probabilities of choosing associated with each number's weight (ie. 1's weight = 10, 2's = 30, 4's = 15, 5's = 35, 6's = 10, and the rest 0); assume I already computed the sum of the weights before this. Right now, I first have to sort the numbers based on their weights, then go through the list again to divide each by the sum of all (ie. normalize in order to make each's weight in [0,1]). Sorting and then traversing the list is slow, so I tried to put the weighting in the compareTo() method so it would normalize while sorting, but Collections.sort() does not put them in the correct order if I do this. Any suggestions (besides having to write my own efficient sorting algorithm from scratch)? I hope I was clear enough.

Upvotes: 0

Views: 1355

Answers (3)

Knubo
Knubo

Reputation: 8443

Just a suggestion to improve on Meriton's excellent suggestion:

If you want to make the first part even faster you can create an index making so that the elements you need to loop is reduced. For every N number when counting weight, take a note of that index in an array/hash and the sum so far.

When you then pick the number t to loop to you can look up in the index and jump passed the elements up to there. Might save you time if you have lots of entries and several lookups.

Upvotes: 0

meriton
meriton

Reputation: 70564

What makes you think you need to sort by weight to choose numbers at random?

I'd do:

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;
}

If you're repeatadly choosing from the same array, you might wish to precompute partial sums and do a binary search on those.

If your array consists of numbers from a range significantly smaller than its length, you might adapt the idea of counting sort, i.e. precompute partial sums for each distinct number and do the binary search on those.

It's quite easy to see that unless you have some prior knowledge about the numbers or weights involved, you will need to look at the weight of each number (because it might dwarf all other weights), so a general algorithm must take at least O(n).

However, additional constraints allow more efficient implementations. If you know a reasonably small upper bound on a number's weight, you could do A/R sampling:

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;

Upvotes: 1

khachik
khachik

Reputation: 28703

Assuming ints is a 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+",");
}

You can use enums, or a hashmap to store weights of the numbers, the code was an example how to do weight-based comparison.

Upvotes: 1

Related Questions