Returning Largest 5 indexs Of Array of double

Simple linear code, though with some overhead.

public Set findLargest(double[] input, int top) {

SortedMap sm = new SortedMap();

for (int i=0;input.length;i++) {

sm.put(new Double(input[i]), new Integer(i));

if (sm.size()>top) {

sm.remove(sm.firstKey());

}

}

return sm.keySet();

}

parza at 2007-7-16 1:54:39 >

This is not a homework assignment. I don't mind if util classes are used, it's just that most of the time they slow things down.

I just need a speedy way of doing this

int[] biggestFiveIndexes = findBiggestFiveIndexes(double[] input);

public int[] findBiggestFiveIndexes(double[] input) {

int[] temp = new int[5];

// I tried finding the initial biggest then storing this, then comparing

// the next biggest with the stored and so on... but no such luck.

// just can't think straight as well as making it efficient

return temp;

}

mm_treoa at 2007-7-16 1:54:39 >

> ... it's just that most of the time they slow things down.

> I just need a speedy way of doing this

Pre-optimization is almost always a really bad idea.

Time consumption is usually really hard to predict because

of things like overhead, algorithm complexity, and 10-90

role. When avoiding using simple algorithms you will most

likely code more bugs, which will take longer to find.

If you are working under any deadline pressure, my advice

is to code the simplest solution you can come up with and

then change it when your time consumption analysis tool

tells you that you must.

However, if you are a student or just coding for fun,

pre-optimization is a really good way to learn.

parza at 2007-7-16 1:54:39 >

> Thank's, but I can't sort the array as I need the

> original index values, as the index values refer to

> something else, so they need to be kept in tact.

Oh yeah, forgot that.

Well here's a way to do it without using a java.util package (I only used it for printing). Be carefull though, if you take a value for 'n' that is near the size of your array of double's, you'll end up with an O(n^2) algortihm.

class Test {

// main-method

public static void main(String[] args) {

double[] array = {1.0, 9.0, 8.0, 5.0, 6.0, 4.0, 2.0, 3.0, 7.0};

int[] biggestFiveIndexes = findBiggestFiveIndexes(array, 5);

System.out.println(java.util.Arrays.toString(array));

System.out.println(java.util.Arrays.toString(biggestFiveIndexes));

}

// Find all 'n' biggest index-numbers of an array of doubles

private static int[] findBiggestFiveIndexes(double[] array, int n) {

double[] copy = copyArray(array);

int[] top = new int[n];

int size = 0;

while(size < n) {

top[size] = getNextBiggest(copy);

size++;

}

return top;

}

// Return the index of the biggest value and reset

// that specific value so it will only be found once.

private static int getNextBiggest(double[] array) {

int biggestIndex = 0;

double biggestValue = array[biggestIndex];

for(int i = 1; i < array.length; i++) {

if(array[i] > biggestValue) {

biggestIndex = i;

biggestValue = array[i];

}

}

array[biggestIndex] = Double.MIN_VALUE;

return biggestIndex;

}

// Return a copy of an array

private static double[] copyArray(double[] array) {

double[] copy = new double[array.length];

for(int i = 0; i < array.length; i++) {

copy[i] = array[i];

}

return copy;

}

}

I'm sure there will be far better (and faster) methods to do it, but this will give you a start.

Good luck.

prometheuzza at 2007-7-16 1:54:39 >

Slightly cleaner version:

public static void getLargest(double[] data, int[] index) {

int k = 0;

for (int i = 0; i < data.length; i++) {

double d = data[i];

if (k < index.length) {

index[k++] = i;

}

else {

double smallest = Double.MAX_VALUE;

int smallestIndex = -1;

for (int j = 0; j < index.length; j++) {

double e = data[index[j]];

if (d > e) {

// is e the smallest?

if (e < smallest) {

smallest = e;

smallestIndex = j;

}

}

}

if (smallestIndex != -1) index[smallestIndex] = i;

}

}

}

rkippena at 2007-7-16 1:54:39 >

I didn't like the formatting.

public int[] findTop(double[] values, int count) {

int[] top = new int[count];

int lowestIndex = 0;

for (int i = 0; i < values.length; i++) {

if (i < count) {

top[i] = i;

if (values[i] < values[lowestIndex]) {

lowestIndex = i;

}

continue;

}

if (values[i] > values[top[lowestIndex]]) {

top[lowestIndex] = i;

for (int n = 0; n < top.length; n++) {

if (values[top[n]] < values[top[lowestIndex]]) {

lowestIndex = n;

}

}

}

}

return top;

}

kablaira at 2007-7-16 1:54:39 >