シーケンスを最小限にする目的で配列を並べ替えます。

Question

私はwebsocketクライアント接続の配列を持っています。この配列に複数の異なるマシンへの接続が含まれているとします。それぞれの異なる文字（1,2,3など）が異なるホストを表しているとします。それは次のようになります。私がやりたい

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

何、ソートそうのような配列されています。クライアントが応答しない場合

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

根拠がある、私はしたくありません同じホストに再試行すると、別のホストのクライアントにメッセージを送信し、後で元のホストに戻ってみることができます。これは基本的にラウンドロビン型のものに似ています。

私はこのような配列をソートするための最良の方法があると仮定します。

1. このユニークなリストの上に配列
2. 反復内のすべての異なるホスト（独自の文字）を見つけ、そしてから項目をオフにスプライス元の配列私は行くように。ここで

は、上記のアルゴリズムのために私が持っているJSコードです：

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)); 

//上記の入力を与え、我々が得る：

[ 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 ] 

私はこのコードを誇りに思っていないです、それを行うより良い方法があるかどうか疑問に思っています。上記はこの入力には役立ちますが、それをクリーンアップしてより一般的なものにする良い方法を探しています。

これを行うためのより良い/より速い方法がありますか？

Answer 1

あなたは違った操作を行うことができます。

• ソート入力を - それは後で

• が等しい要素の最大数（要素のためのあなたの例では10、= 1）、CNTを見つけましょう

それらの上の要素を配布する CNTバケットを作成します

• は、ラウンドロビンの原則で次のバケットに1によってソートされた順序1に冒頭未満

• マージバケット

あなたが最後に長いシリーズを得るこの方法で、1を要素を入れました。

[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] 

悪い場合は、1つの要素がn/2回を超えて表示されますが、それは避けられません。

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); 
}); 

あなたは最初から、キーの完全なリストを主張した場合は、それも可能です：

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); 
});