JS - эффективный способ перебора списков внутри списков - PullRequest
0 голосов
/ 24 июня 2018

Какой самый эффективный алгоритм поиска предметов внутри другого списка?Позвольте мне попытаться написать пример:

  • У меня есть следующая структура:
    • Работодатели: [{"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];    
}

Пример ввода:

  • operators = [[1, 60], [3, 90]];
  • customers = [[1, 30], [1, 40], [1, 60], [1, 70]];

Выходдолжно быть 1.

Главное правило: не может получить наивысший операторский навык и поставить все на него.Мне нужно балансировать между операторами - мне нужно переходить от более низкого навыка к более высокому.

Любой совет, как я могу его оптимизировать?

Заранее спасибо.

Ответы [ 3 ]

0 голосов
/ 24 июня 2018

Хорошо, ваш вопрос был неясен, но чтение кода имеет смысл. Работодатели могут взаимодействовать с клиентами с настроением ниже их квалификации, но они не могут взаимодействовать с клиентом, с которым может взаимодействовать и другой сотрудник с более низким уровнем квалификации. Давайте решим это.

С одной стороны, нет особого смысла фильтровать, затем копировать результат этого в набор, а затем запускать другой фильтр, где вы отфильтровываете все, что только что отфильтровали. Звучит как беспорядок, верно? Это.

Вместо этого просто создайте свой набор изначально для всех клиентов. Затем запустите forEach и удалите клиентов из набора, которые могут обслуживать самые мелкие работники, увеличивая счетчик для каждого клиента, для которого вы делаете это. Вы на самом деле не отправляли идентификаторы клиентов вместе с рассылкой, поэтому нет смысла вообще их использовать.

Алгоритм будет примерно таким: Сортировка сотрудников и клиентов в соответствии с навыком и настроением. Создайте переменную счетчика. Итерация по клиентам. Для каждого клиента, если его настроение <навык текущего сотрудника, увеличьте счетчик. Если нет, сохраните счет в вашем дистрибутиве вместе с текущим идентификатором сотрудника. Затем перейдите к следующему идентификатору сотрудника. </p>

Повторите. На самом деле не получил шанс использовать набор. Я не думаю, что они заказали. Это работает хорошо, хотя, и вы можете сделать это за один проход после сортировки.

function countEmployersByMoodAtt(operators, customers) {
  console.log("Sorting operators.");
  operators.sort((a, b) => a[1] - b[1]);
  console.log("Sorting customers");
  customers.sort((a, b) => a[1] - b[1]);
  console.log("Starting processing.");

  let distribution = [];
  let opIndex = 0;
  let customersServed = 0;
  let bestEmployeeID;
  let mostServed = -1;
  let skill = operators[opIndex][1];

  for (let i = 0; i < customers.length; ++i) {
    let mood = customers[i][1];
    if (mood < skill) 
      ++customersServed;
    else {
      // check if new record.
      if (customersServed > mostServed) {
        mostServed = customersServed;
        bestEmployeeID = operators[opIndex][0];
        customersServed = 1; // this will count toward the employee found in while() loop.
      }
      // find next qualified employee.
      while (mood > skill && ++opIndex < operators.length) {
        skill = operators[opIndex][1];
      }
      // no employees can serve customer.
      if (opIndex >= operators.length) {
        console.log("No employees skilled enough for remaining customers.")
        return [bestEmployeeID, mostServed];
      }
    }
  }
  // need to do this one more time for the last set of customers. 
  // because 'else' case won't run if customer is served adequately.
  // and if a new employee is selected for the last customer, bestEmployee won't be set.
  if (customersServed > mostServed) {
    mostServed = customersServed;
    bestEmployeeID = operators[opIndex[0]];
  }
  return [bestEmployeeID, mostServed];
}
0 голосов
/ 24 июня 2018

Я предлагаю использовать массив с навыками, отсортированными по убыванию и итерировать клиентов, который итерирует массив счетчиков и проверяет настроение m.

Если m меньше, чем навык, то увеличить счетчик, в противном случае выйти извнутренний цикл.

counter содержит счетчик для каждого уровня навыка.

var employers = [[1, 10], [2, 90]],
    customers = [[12, 5], [2, 70]],
    counter = employers.map(([, v]) => [v, 0]).sort(([a], [b]) => b - a);
    
customers.forEach(([m]) => counter.every(a => m < a[0] && ++a[1]));

console.log(counter);
0 голосов
/ 24 июня 2018

Эта функция должна выполняться в порядке O(c*o), где c - количество клиентов, а o - количество операторов.

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

Benchmark:

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));
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...