javascript - JS - 迭代列表内列表的有效方法

Question

在另一个列表中查找项目的最有效算法是什么？让我尝试写一个例子:

• 我有以下结构:
  • 雇主:[{"id": 1, "skill": 10},{"id": 2, "skill": 90}];
  • 客户:[{"id": 12, "mood": 5},{"id": 2, "mood": 70}]。

该信息由数组表示:

• 雇主数组:[[1, 10], [2, 90]];
• 客户数组:[[12, 5], [2, 70]]。

就我而言，雇主只能与情绪低于其技能的客户互动。我的函数的返回应该是交互次数最多的雇主。

我已经编写了一个可以执行此规则的函数，但当我有大量雇主或客户时，它的速度相当慢 - 需要 7 秒以上才能完成。

function countEmployersByMoodAtt(operatos, customers) {
    let distribution = [];
    //sort operators by skill so I can guarantee that big skills won't come first
    operatos.sort((a, b) => a[1] - b[1]);

    operatos.forEach(cs => {
        let skill = cs[1];        
        //map to extract only the customer id
        let customersAvailable = customers
            .filter(customer => customer[1] <= skill)
            .map(x => x[0]);
        //convert to set because i've wrote it's fast
        let customerAvSet = new Set(customersAvailable);
        //include on result list
        distribution.push([cs[0], customersAvailable.length]);
        //remove customers already assigned
        customers = customers.filter(([cs]) => !customerAvSet.has(cs));
    });
    //sort to first position be hightest score    
    distribution.sort((a, b) => b[1] - a[1]);

    //return operator
    return distribution[0][0];    
}

示例输入是:

• 运算符 = [[1, 60], [3, 90]];
• 客户 = [[1, 30], [1, 40], [1, 60], [1, 70]];

输出应为 1。

主要规则:不能获得最高的运算符(operator)技能并将其全部放在上面。我需要在运算符(operator)之间取得平衡 - 我需要从较低技能迭代到较高技能。

有关如何优化它的任何提示？

提前致谢。

Answer 1

此函数应按 O(c*o) 的顺序运行，其中 c 是客户计数，o 是运算符(operator)计数。

  var o = [[1, 60], [3, 90]];
  var c = [[1, 30], [1, 40], [1, 60], [1, 70]];

  function countEmployersByMoodAtt(operatos, customers) {
  var cInt = [];
  var gInt = {};
  var i, j;
  var opIndex;

  for (i = 0; i < customers.length; i++) {
    // find lowest possible operator to interact with
    opIndex = null;
    for (j = operatos.length - 1; j >= 0; j--) {
      if (operatos[j][1] < customers[i][1]) {
        // can't interact. continue to next operator
        continue;
      }

      if (opIndex !== null) {
        if (operatos[j][1] < operatos[opIndex][1]) {
          opIndex = j;
        }
      } else {
        opIndex = j;
      }
    }

    if (opIndex === null) {
      cInt.push(null);
    } else {
      cInt.push(operatos[opIndex][0]);
    }
  }


  for (i = 0; i < cInt.length; i++) {
    if (gInt[cInt[i]] === undefined) {
      gInt[cInt[i]] = 0;
    }

    gInt[cInt[i]] += 1;
  }

  var maxId = null, maxOp = 0;
  var keys = Object.keys(gInt);

  for (i = 0; i < keys.length; i++) {
    if (gInt[keys[i]] > maxOp) {
      maxId = keys[i];
      maxOp = gInt[keys[i]];
    }
  }

  return maxId;
}

console.log(countEmployersByMoodAtt(o, c));

基准:

var o = [];
var c = [];

for (var k = 0; k < 10000; k++) {
  o.push([k + 1, Math.floor(Math.random() * 1000000)]);
  c.push([k + 1, Math.floor(Math.random() * 1000000)]);
}

function myCountEmployersByMoodAtt(operatos, customers) {
  var cInt = [];
  var gInt = {};
  var i, j;
  var opIndex;

  for (i = 0; i < customers.length; i++) {
    // find lowest possible operator to interact with
    opIndex = null;
    for (j = operatos.length - 1; j >= 0; j--) {
      if (operatos[j][1] < customers[i][1]) {
        // can't interact. continue to next operator
        continue;
      }

      if (opIndex !== null) {
        if (operatos[j][1] < operatos[opIndex][1]) {
          opIndex = j;
        }
      } else {
        opIndex = j;
      }
    }

    if (opIndex === null) {
      cInt.push(null);
    } else {
      cInt.push(operatos[opIndex][0]);
    }
  }


  for (i = 0; i < cInt.length; i++) {
    if (gInt[cInt[i]] === undefined) {
      gInt[cInt[i]] = 0;
    }

    gInt[cInt[i]] += 1;
  }

  var maxId = null, maxOp = 0;
  var keys = Object.keys(gInt);

  for (i = 0; i < keys.length; i++) {
    if (gInt[keys[i]] > maxOp) {
      maxId = keys[i];
      maxOp = gInt[keys[i]];
    }
  }

  return maxId;
}

function yourCountEmployersByMoodAtt(operatos, customers) {
  let distribution = [];
  //sort operators by skill so I can guarantee that big skills won't come first
  operatos.sort((a, b) => a[1] - b[1]);

  operatos.forEach(cs => {
    let skill = cs[1];
    //map to extract only the customer id
    let customersAvailable = customers
      .filter(customer => customer[1] <= skill)
      .map(x => x[0]);
    //convert to set because i've wrote it's fast
    let customerAvSet = new Set(customersAvailable);
    //include on result list
    distribution.push([cs[0], customersAvailable.length]);
    //remove customers already assigned
    customers = customers.filter(([cs]) => !customerAvSet.has(cs));
  });
  //sort to first position be hightest score
  distribution.sort((a, b) => b[1] - a[1]);

  //return operator
  return distribution[0][0];
}

var t0 = performance.now();
console.log('MyResult: ' + myCountEmployersByMoodAtt(o, c));
var t1 = performance.now();
console.log('Your result: ' + yourCountEmployersByMoodAtt(o, c));
var t2 = performance.now();
console.log('My time: ' + (t1 - t0));
console.log('Your time: ' + (t2 - t1));