Sort dictionary containing array as value and rank

Question

I am looking for the best possible, minimum operation to solve this.

var sourceDictionary = {
    "200" : [
        [ "a", 5 ],
        [ "al", 6 ],
        [ "xl", 8 ]
    ],
    "201" : [
        [ "b", 2 ],
        [ "al", 16 ],
        [ "al", 26 ],
        [ "al", 9 ],
        [ "al", 3 ]
    ],
    "202" : [
        [ "lm", 7 ]
    ]
}

I want to sort the dictionary based on the integer values contained within each key and then rank each value,as shown in the outputputDictionary.

var targetDictionary = {
    "200" : [
        [ "a", 5, "rank-7" ],
        [ "al", 6, "rank-6" ],
        [ "xl", 8, "rank-4" ]
    ],
    "201" : [
        [ "b", 2, "rank-9" ],
        [ "al", 16, , "rank-2" ],
        [ "al", 26, "rank-1" ],
        [ "al", 9, "rank-3" ],
        [ "al", 3, "rank-8" ]
    ],
    "202" : [
        [ "lm", 7, "rank-5" ]
    ]
}

For example [ "al", 26, "rank-1" ] .This is rank-1 as 26 is maximum among all the other values.

Javascript is the most preferable language.Looking for the best optimal solution

my approach was normal...loop through the dictionary,collect all the arrays in one variable(and keep the references) and then sort them,assign the rank and convert it back to the willing target structure...its a lot of operation and if i consider there are half a million keys in the dictionary,my approach really sucks..therefore looking for anyone who has a better approach — deepg, Feb 24 '17 at 16:14
You probably have a mistake, there is no `rank-7`. Is it intentional or is it a mistake? — ibrahim mahrir, Feb 24 '17 at 16:17
What if two entries have value 10 and one has 5, do we get two rank 1 and one rank 3? — fafl, Feb 24 '17 at 16:18
So, have you taken a look at http://stackoverflow.com/questions/979256/sorting-an-array-of-javascript-objects?rq=1 — Heretic Monkey, Feb 24 '17 at 16:19
@gully I don't think you'll get around sorting all the keys together if you want to rank them all. Or is there any existing structure on your data that could be exploited? Btw, if you already have a working version and only are looking for a more efficient one, please post the code you have. — Bergi, Feb 24 '17 at 16:20
@fafl there can be joint ranks..so two values of 10 would rank-1 and 5 would rank-2 — deepg, Feb 24 '17 at 16:22
@Bergi I know the approach of the way I want to solve it..i have mentioned the approach in the above comments..bt as I said my goal is to find the optimal approach and I believe there might be a better approach than mine — deepg, Feb 24 '17 at 16:23
If you have a working approach, and are seeking a better one, your question probably belongs on code review — Dexygen, Feb 24 '17 at 16:30
@gully No. Sorting always requires `O(n log n)`. There's no way to get around that. — Bergi, Feb 24 '17 at 16:35

ibrahim mahrir · Accepted Answer · 2017-02-24T16:40:12.950

Since arrays are passed by reference, you can make use of that like this:

function rankify(obj) {
  // PHASE 1: get a reference of all the sub-arrays
  var references = [];
  for(var key in obj) {               // for each key in the object obj
    obj[key].forEach(function(e) {    // for each element e (sub-array) of the array obj[key]
      references.push(e);             // push a reference of that array into reference array
    });
  }
  
  // PHASE 2: sort the references
  references.sort(function(a, b) {    // sort the items
    return b[1] - a[1];               // to reverse the sort order (a[1] - b[1])
  });
  
  // PHASE 3: assign the ranks
  references.forEach(function(e, i) { // for each array in the reference array
    e.push("rank-" + (i + 1));        // push another item ("rank-position") where the position is defined by the sort above
  });
}


var sourceDictionary = {"200" : [[ "a", 5 ],[ "al", 6 ],[ "xl", 8 ]],"201" : [[ "b", 2 ],[ "al", 16 ],[ "al", 26 ],[ "al", 9 ],[ "al", 3 ]],"202" : [[ "lm", 7 ]]};

rankify(sourceDictionary);
console.log(sourceDictionary);

If you are allowed to use arrow functions:

function rankify(obj) {
  Object.keys(obj)
        .reduce((ref, k) => ref.concat(obj[k]), [])    // get the references array
        .sort((a, b) => b[1] - a[1])                   // sort it
        .forEach((e, i) => e.push("rank-" + (i + 1))); // assign the rank
}


var sourceDictionary = {"200" : [[ "a", 5 ],[ "al", 6 ],[ "xl", 8 ]],"201" : [[ "b", 2 ],[ "al", 16 ],[ "al", 26 ],[ "al", 9 ],[ "al", 3 ]],"202" : [[ "lm", 7 ]]};

rankify(sourceDictionary);
console.log(sourceDictionary);

Marking this as the best solution as execution/performance time is minimum compared to other solutions... — deepg, Feb 24 '17 at 19:14

fafl · Answer 2 · 2017-02-24T16:41:02.467

This can be done in a few lines:

var sourceDictionary = {
    "200" : [
        [ "a", 5 ],
        [ "al", 6 ],
        [ "xl", 8 ]
    ],
    "201" : [
        [ "b", 2 ],
        [ "al", 16 ],
        [ "al", 26 ],
        [ "al", 9 ],
        [ "al", 3 ]
    ],
    "202" : [
        [ "lm", 7 ]
    ]
}

var flatten = arr => [].concat.apply([], arr)
var ranks = flatten(Object.keys(sourceDictionary)
    .map(k => sourceDictionary[k].map(t => t[1]))
  )
  .sort((a, b) => b - a)
  .filter( function( item, index, inputArray ) {
      // remove duplicates
      return inputArray.indexOf(item) == index;
  });

Object.keys(sourceDictionary)
  .forEach(k => sourceDictionary[k]
    .forEach(t => t.push("rank-" + (1 + ranks.indexOf(t[1])))))

console.log(sourceDictionary)

Instead of sorting then reversing just sort in the other order (`b - a`). — ibrahim mahrir, Feb 24 '17 at 16:34

score 0 · Answer 3 · answered Feb 24 '17 at 16:35

You can first reduce it to array that stores key|index from original object and then sort it and add rank property and then again create object.

var data = {
  "200" : [ [ "a", 5 ], [ "al", 6 ], [ "xl", 8 ] ],
  "201" : [ [ "b", 2 ], [ "al", 16 ], [ "al", 26 ], [ "al", 9 ], [ "al", 3 ] ],
  "202" : [ [ "lm", 7 ] ]
}

var o = Object.keys(data).reduce(function(r, e) {
  data[e].forEach((a, i) => r.push([e + '|' + i, a]))
  return r;
}, [])

o.sort((a, b) => b[1][1] - a[1][1]).map(function(e, i) {
  e[1][2] = 'rank-' + (i + 1)
})

var result = o.reduce(function(r, e) {
  var key = e[0].split('|')
  if (!r[key[0]]) r[key[0]] = []
  r[key[0]][key[1]] = e[1]
  return r
}, {})

console.log(result)

Why would you join key and index by a `|` character instead of storing them separately? — Bergi, Feb 24 '17 at 16:36

Sort dictionary containing array as value and rank

3 Answers3