Sort array with goal to minimize sequence repeat

Question

Ok so I have an array of websocket client connections. Imagine that this array contains connections to several different machines. Imagine that each different letter (1,2,3, etc) represents a different host. It might look like this:

const conns = [1,1,1,3,3,1,3,2,2,2,2,3,2,1,1,2,2];

what I would like to do, is sort the array like so:

const conns = [1,2,3,1,2,3,1,2,3, ... etc];

the rationale is if a client does not respond, I don't want to retry to the same host, I would like to try sending a message to a client on a different host, and only come back to the original host later. This is basically like a round-robin type thing.

I assume the best way to sort the array like this is:

  1. find all the different hosts (unique letters) in the array
  2. Iterate over this unique list, and splice off items from the original array as I go.

Here is the JS code I have for the above algorithm:

const list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];

const _ = require('lodash');

function findAndRemoveFirstMatch(m, list){
    for(var i = 0; i < list.length; i++){
        if(m === list[i]){
            return list.splice(i,1)[0];
        }
    }
}

function getSorted(list){

    const ret = [];

    const set = _.uniqBy(list, function(x){
        return x;
    });

    while(list.length > 0){

        var i = 0;
        while(i < set.length && list.length > 0){
            var item;
            if(item  = findAndRemoveFirstMatch(set[i],list)){
                ret.push(item);
            }
            i++;
        }

    }

    return ret;

}

console.log(getSorted(list));

//given the above input, we get:

[ 1, 2, 3, 4, 5, 11, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 3, 4, 1, 3, 4, 1, 3, 1, 3, 1, 1, 1 ]

I am not proud of this code, and am wondering if there is a better way to do it. The above works for this input, but looking for a good way to clean it up and make it more generic.

Is there a better/faster way to do this?


Show source
| sorting   | node.js   | arrays   | algorithm   | array-difference   2016-12-28 05:12 1 Answers

Answers to Sort array with goal to minimize sequence repeat ( 1 )

  1. 2016-12-28 10:12

    You can do it differently:

    • sort input - it will help later

    • find maximum count of equal elements (10 in your example, for element=1), cnt

    • create cnt buckets to distribute elements over them

    • put elements in sorted order one by one into next bucket with round-robin principle

    • merge buckets

    This way you get longer series in the end, 1 less than at the beginning.

    [1, 2, 4, 1, 2, 4, 1, 2, 4, 1, 3, 4, 1, 3, 4, 1, 3, 5, 1, 3, 5, 1, 3, 11, 1, 3, 1, 3]
    

    Bad case is when one element appears more than n/2 times, but that's unavoidable.

    var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];
    var a = list.sort(function(a, b) { return a - b; });
    var cnt = a.reduce(function(res, cur) {
      if (cur == res[0]) 
        return [cur, res[1]+1, Math.max(res[1]+1, res[2])]
      else
        return [cur, 1, Math.max(1, res[2])];
    }, [null, 0, 0])[2];
    
    var buckets = [];
    for (var i = 0; i < cnt; i++)
      buckets[i] = [];
    
    var j = 0;
    for (var i = 0; i < a.length; i++) {
      buckets[j].push(a[i]);
      j = (j+1)%cnt;
    }
    
    var res = buckets.reduce(function(r, cur) {
      return r.concat(cur);
    });
    

    If you insist on full list of key from beginning, it's also possible:

    var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];
    var a = list.sort(function(a, b) { return a - b; });
    var cnt = a.reduce(function(res, cur) {
        if (cur == res[0]) 
            return [cur, res[1]+1, Math.max(res[1]+1, res[2])]
        else
            return [cur, 1, Math.max(1, res[2])];
    }, [null, 0, 0])[2];
    
    var buckets = [];
    for (var i = 0; i < cnt; i++)
        buckets[i] = [];
    
    var j = 0;
    var cur = null;
    for (var i = 0; i < a.length; i++) {
        if (cur != a[i]) 
            j = 0;
        buckets[j].push(a[i]);
        j = j+1;
    }
    
    var res = buckets.reduce(function(r, cur) {
        return r.concat(cur);
    });
    

Leave a reply to - Sort array with goal to minimize sequence repeat

◀ Go back