CODEWITHSUNDEEP
javaarrayssorting
Eypros
Eypros

Reputation: 5723

Getting the largest k elements of a double array

The problem I am facing is this one:

I have an array of doubles from which I want to keep the top k greater values.

  1. I have seen some implementations involving Arrays.sort. For example in this example with relative issue it is suggested to use this approach.
  2. Since I am only interested in the first k elements I have also experimented with MinMaxPriorityQueue. I have created a MinMaxPriorityQueue with a maximumSize:

Of course there is again autoboxing.

Builder<Comparable> builder = MinMaxPriorityQueue.maximumSize(maximumSize);
MinMaxPriorityQueue<Double> top2 = builder.create();

The problem is that the order is the ascending one that it's the opposite of the one I want. So I cannot use it this way.

To state the problem's real parameters my arrays is about 50 elements long and I am interested in up to the top k = 5 elements.

So is there any way to bypass this problem using the second approach? Should I stay with the first one even though I don't really need all elements sorted? Do you know if there is any significant difference in speed performance (I will have to use this in a lot of situations so that's where the speed is needed)? Is there any other solution I could use?

As for the performance, I know I can theoretically check it myself but I am a bit out of time and if someone have any solution I am happy to hear it (or read it anyway).

Upvotes: 1

Views: 181

Answers (2)

AlexR
AlexR

Reputation: 2408

You can use System.arraycopy on a sorted array:

double[] getMaxElements(double[] input, int k) {
    double[] temp = Arrays.copyOf(input, input.length);
    Arrays.sort(temp); // Sort a copy to keep input as it is since Arrays.sort works in-place.
    return Arrays.copyOfRange(temp, temp.length - k, temp.length); // Fetch largest elements
}

For 50 elements, it is much faster to sort an array than to mess with generics and comparables.
I will write up an additional "fast" algorithm...

double[] getMaxElements2(double[] input, int k) {
    double[] res = new double[k];
    for (int i = 0; i < k; i++) res[i] = Double.NEGATIVE_INFINITY; // Make them as small as possible.
    for (int j = 0; j < input.length; j++) // Look at every element
        if (res[0] < input[j]) { // Keep the current element
            res[0] = input[j];
            Arrays.sort(res); // Keep the lowest kept element at res[0]
        }
    return res;
}

This is O(N*k*log(k)) while the first one is O(N*log(N)).

Upvotes: 0

icza
icza

Reputation: 418585

If you only have like 50 elements, as noted in my comment, just sort it and take the last k elements. It's 2 lines only:

public static double[] largests(double[] arr, int k) {
    Arrays.sort(arr);
    return Arrays.copyOfRange(arr, arr.length - k, arr.length);
}

This modifies (sorts) the original array. If you want your original array unmodified, you only need +1 line:

public static double[] largests2(double[] arr, int k) {
    arr = Arrays.copyOf(arr, arr.length);
    Arrays.sort(arr);
    return Arrays.copyOfRange(arr, arr.length - k, arr.length);
}

Upvotes: 3

Related Questions