按频率计数订购电子邮件地址数组

Question

我有一个重复的数组.一种基于重复计数对阵列进行排序的有效算法,例如:

['d@me.com', 'z@gmail.com', 'e@me.com', 'b@me.com', 'c@me.com', 'z@gmail.com', 'z@gmail.com', 'b@me.com', 'e@me.com']
=>
['z@gmail.com', 'e@me.com', 'b@me.com', 'd@me.com', 'c@me.com']

因为计数如下 [3, 2, 2, 1, 1]

我提出了:

const itemCounts = {}
const ordereditems = []
for (let i = 0; i < allitems.length; i++) {
  let item = allitems[i];
  itemCounts[item] = itemCounts[item] ? itemCounts[item] + 1 : 1
}
const tuples = []
for (let key in itemCounts) {
  tuples.push([key, itemCounts[key]])
}
return tuples.sort((a, b) => a[1] < b[1]).map(x => x[0])

这是关于?(3 N + N log N)什么的？

也许用lodash更快的东西？

也许保持排序的优先级队列,因为我做计数？

也许使用某种基数？

Answer 1

这是我的尝试，也是第一次尝试编写片段:)

var allitems = ['d', 'a', 'e', 'b', 'c', 'a', 'a', 'b', 'e'];

function original_code(allitems) {
  const itemCounts = {}
  const ordereditems = []
  for (let i = 0; i < allitems.length; i++) {
    let item = allitems[i];
    itemCounts[item] = itemCounts[item] ? itemCounts[item] + 1 : 1
  }
  const tuples = []
  for (let key in itemCounts) {
    tuples.push([key, itemCounts[key]])
  }
  return tuples.sort((a, b) => a[1] < b[1]).map(x => x[0])
}

function myTry(allitems) {
  var arr;
  const dic = {};
  arr = [];
  for (let i = 0; i < allitems.length; i++) {
    let item = allitems[i];
    if (!dic.hasOwnProperty(item)) {
      dic[item] = 1;
      arr.push(item);
    } else
      dic[item]++;
  }
  arr.sort((a, b) => dic[b] - dic[a]);
  return arr;
}



//measure attempts
{ //original code
  var t0 = performance.now();
  var res;
  for (let j = 0; j < 10000; j++) {
    res = original_code(allitems);
  }
  var t1 = performance.now();
  console.log("original " + (t1 - t0) + " milliseconds.");
  console.log("original " + res);
}

{ //my try
  var t0 = performance.now();
  var res;
  for (let j = 0; j < 10000; j++) {
    res = myTry(allitems);
  }
  var t1 = performance.now();
  console.log("myTry " + (t1 - t0) + " milliseconds.");
  console.log("myTry " + res);
}



{ //my try
  var t0 = performance.now();
  var res;
  for (let j = 0; j < 10000; j++) {
    res = myTry(allitems);
  }
  var t1 = performance.now();
  console.log("myTry2 " + (t1 - t0) + " milliseconds.");
  console.log("myTry2 " + res);
}

{ //original code
  var t0 = performance.now();
  var res;
  for (let j = 0; j < 10000; j++) {
    res = original_code(allitems);
  }
  var t1 = performance.now();
  console.log("original2 " + (t1 - t0) + " milliseconds.");
  console.log("original2 " + res);
}

编辑
我试图做出更可靠的测量。如果有更好的方法，请告诉我，我将不胜感激。

+ 更改了排序。