Easiest way to derive subset array of highest 10 values?

Question

In javascript I have an array as follows:

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4];

And I am interested in finding a way (within one loop, not multiple) to derive a subset array of the highest 10 values, where the previous position of the value is the 'key' (so simulating a Map object):

eg:

var fooTopTen = [[4, 128], [18, 128], [25, 60], [27, 28], [10, 27], [37, 27], [15, 21], [9, 18], [14, 18], [23, 18]];

Answer 1

Here's the de-bugged version of my previous answer using an index table. I did a little benchmarking and for the input given in the question, this solition will be faster than anything else which has been suggested in this thread till now:

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4];

var indexTable = {}, uniqueValues = [];

// --- build reverse index table, find unique values

for(var i = foo.length; i--; ) {
    var value = foo[i];
    if(indexTable.hasOwnProperty(value))
     indexTable[value].push(i);
    else {
     indexTable[value] = [i];
     uniqueValues.push(value);
    }
}

// --- sort unique values in ascending order

uniqueValues.sort(function(i1, i2) {
    return i1 - i2;
});

// --- find ten greatest values

var fooTopTen = [], k = 0;

for(var i = uniqueValues.length; k < 10 && i--; ) {
    var value = uniqueValues[i],
     indices = indexTable[value];

    for(var j = indices.length; k < 10 && j--; )
     fooTopTen[k++] = [indices[j], value];
}

// --- output result

document.writeln('[[' + fooTopTen.join('], [') + ']]');

Answer 2

My previous answer used a reverse index table, but contained some bugs - which are now fixed - and was harder to understand than the following code.

This is actually the slowest of all solutions given in the answers - for maximum performance, check my other answer.

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4];

var fooTopTen = [];

// add index to values
for(var i = 0, len = foo.length; i < len; ++i)
    fooTopTen.push([i, foo[i]]);

// sort first by value (descending order), then by index (ascending order)
fooTopTen.sort(function(t1, t2) {
    return t2[1] - t1[1] || t1[0] - t2[0];
});

// shorten array to correct size
fooTopTen.length = 10;

// output top ten to check result
document.writeln('[[' + fooTopTen.join('], [') + ']]');

The second part of the comparison function (the one comparing the indices) is not needed, as sort() is stable in most implementations (this isn't required by ECMA according to MDC). I'll leave it in as an example to how sorting with multiple requirements can be done...

Answer 3

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4];

var index = 0;
var result = foo.map( function(a){ return [index++, a]; } )
         .sort( function(a,b){ return (a[1] < b[1]); } )
         .splice( 0, 10 );

document.write(result.join( '  ' ));

If foo is very large compared to the size of result required, it may be quicker to iterate over foo insertion-sorting each element into result as we come across it.

Answer 4

// Sorting method
function sortNumber(a, b) {
    return a - b;
}

// Find the offset of an element in array
function findOffset(element, array) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == element) {
            // Make sure we don't find it again
            array[i] = null;
            return i;
        }
    }
}

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4];
// Copies
var bar = foo.slice();
var baz = foo.slice();
var fooTopTen = new Array(10);
// Sort
bar.sort(sortNumber).reverse();
// Create the results
for (var i = 0; i < 10; i++) {
    fooTopTen[i] = new Array(2);
    fooTopTen[i][0] = findOffset(bar[i], baz);
    fooTopTen[i][1] = bar[i];
}

Answer 5

This runs once through the main array it searches, inserting items at the appropriate place in the results array:

function top10(arr) {
  var results = [[0,Number.MAX_VALUE],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]];

  for (var i=0; i<arr.length; i++) {
    // search from back to front
    for (var j=9; j>=0; j--) {
       if (arr[i] <= results[j][1]) {
         if (j==9)
           break;
         results.splice(j+1, 0, [i, arr[i]]);
         results.pop();
         break;
      }
    }
  }
  return results.slice(1);
}

For large arrays this should even be rather fast, since most times the inner loop should only do one iteration.

Answer 6

computer-science-y answer:

problem statement: Given a large array X of length N, and a small number m < N (here m=10), produce an array Y of length m where each element of Y contains the pair {i,X[i]} such that the set of X{i} are the m largest elements of X.

If m is much smaller than N, then loop over elements of X and sort them into Y, discarding pairs to maintain at most m elements. (i.e. as moonshadow mentioned)

Sorting X will cost you O(N log N) elements. Iterating over X and sorting into Y should cost you only O(N log m) elements.