Как создать матрицу расстояний для больших наборов данных с помощью Google Script?

Question

В настоящее время я создаю скрипт, который сравнивает список из примерно 90 адресов друг с другом. Результатом скрипта должен быть список, который содержит время, затраченное на перемещение по каждому адресу друг от друга.

Я столкнулся с рядом проблем, пытаясь решить эту проблему. Основная проблема заключается в том, что полученная матрица расстояний будет иметь 8100 элементов. Максимальное время выполнения скрипта Google составляет 30 минут, и поэтому время ожидания скрипта истекает.

Есть ли способы улучшить скрипт, чтобы он работал быстрее?

Цель этого скрипта - создатьсписок с StartID, EndID и временем. Тогда я смогу отфильтровать список, чтобы найти адреса в течение часа друг от друга.

Спасибо!

function maps(origin, destination) {
  var driving = Maps.DirectionFinder.Mode.DRIVING
  var transit = Maps.DirectionFinder.Mode.TRANSIT
  var modeSet = driving
  var directions = Maps.newDirectionFinder()
  .setOrigin(origin)
  .setDestination(destination)
  .setMode(modeSet)
  .setOptimizeWaypoints(true)
  .getDirections()
  var result = directions
  return result;  
}


function GoogleMaps() {
 //get distance
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("ABC");
  var outputSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("EFG");
  var lastrow = sheet.getLastRow();
  var lastcolumn = sheet.getLastColumn();
  var range = sheet.getRange(2, 3, lastrow-1, 3);
  //var range = sheet.getRange(2, 3, 3, 3);
     //Origin is in row 2, column 3
  var values = range.getValues();
  var output = []
  for (var i = 0; i < values.length; ++i)
  {
    var loop1 = values[i]
    var start = values[i][1]
    var startId = values[i][0]
    for (var j = 0; j < values.length; j++) {
      var loop2 = values[j]
      var end = values[j][1]
      var endId = values[j][0]
      var result = maps(start, end)
      var status = result.status
      try{
        var time = result.routes[0].legs[0].duration.value / 60;
        var row = [startId, endId, time]
        output.push(row)
      } catch(err){
        Logger.log(err);
      }
    }
   }    
  var outputLength = output.length
  var outputRange = outputSheet.getRange(1,1,outputLength,3);
  outputRange.setValues(output);
}

РЕДАКТИРОВАТЬ: обновленное количество элементов в списке

Answer 1

Первое, что вы хотите сделать, - это уменьшить количество операций, которые вы выполняете в циклах for. Итак, давайте начнем с анализа этого сначала, но с алгоритмической точки зрения.

В текущей реализации вы в основном вычисляете декартово произведение на наборе из 90 значений, чтобы получить новый набор, состоящий из 8100 значений.

Однако в этом наборе результатов есть ряд избыточных значений, таких как:

1. Набор результатов включает вычисления, в которых оба адреса используются в качестве начальногои конечное местоположение.

2. Расстояние между двумя адресами рассчитывается дважды;такой, что адрес A является начальным адресом, а адрес B является конечным адресом, а в другой итерации адрес A является конечным адресом, а адрес B является начальным адресом.

   ПРЕДУПРЕЖДЕНИЕ: Яделая предположение, что вы проходите одно и то же расстояние во время транзита между двумя адресами независимо от направления транзита (т. е. A-to-B или B-to-A). Это может быть не так в вашем сценарии.

Вы можете устранить эти избыточности с помощью области дискретной математики, называемой комбинаторикой;более конкретно, используя эту прекрасную формулу:

Если мы допустим n = 90 и r = 2 мы получаем следующее:

Это означает, что в нашем наиболее оптимальном случае нам нужен алгоритм, который производит не более 4005 пар адресов.

С этой целью [щелкает пальцами] пришло время написать более оптимальный алгоритм! Но для наглядности и в целях краткости давайте используем меньший размер выборки из 4 адресов, состоящих из одной буквы. Следующего массива должно быть достаточно:

var addresses = ['a', 'b', 'c', 'd'];

Используя вышеупомянутую формулу, мы выводим, что есть 6 уникальных пар адресов, которые мы можем представить следующим образом:

ab  bc  cd
ac  bd
ad

Так, как генерировать этипары?

Если вы посмотрите на приведенное выше представление, вы заметите несколько вещей:

• Количество столбцов на единицу меньше количества адресов в массиве
• В каждом последующем столбце (слева направо) количество пар адресов в столбце уменьшается на 1;то есть. Есть 3 пары, которые начинаются с «a», 2, которые начинаются с «b», 1, который начинается с «c».
• Также обратите внимание, что при переходе от одного столбца к следующему в последовательных столбцах не будет пар с начальным символом предыдущих столбцов;то есть. во втором столбце нет пар, начинающихся с «а», а в третьем столбце нет пар, начинающихся с «а» или «b»

Обобщим эти наблюдения. Учитывая массив из n адресов, мы можем сгенерировать n - 1 столбцов. Длина каждого столбца уменьшается на 1, так что в первом столбце есть пары n - 1 , во втором столбце - n - 2 пары, 3-й столбец n - 3 пары и т. д., где каждый столбец состоит из парных комбинаций, в которых пропускаются адреса из предыдущих столбцов.

На основе этих правил мы можемнастройте цикл for следующим образом (запустите скрипт, и он сгенерирует коллекцию объектов, чьи свойства start и end представляют уникальные пары адресов):

var addresses = ['a', 'b', 'c', 'd'];
var pairs = [];
var numColumns = addresses.length - 1;
var columnHeight;
var columnIndex;
var rowIndex;

for (columnIndex = 0; columnIndex < numColumns; columnIndex++) {

    columnHeight = numColumns - columnIndex;

    for (rowIndex = 0; rowIndex < columnHeight; rowIndex++) {
        pairs.push({
            "start":addresses[columnIndex],
            "end":addresses[columnIndex + rowIndex + 1]
        });
    }
 
}

console.log(pairs);

Таким образом, вышеприведенное обрабатывает алгоритмическую оптимизацию, вам нужно настроить ее для использования с вашей реализацией, но это должно послужить хорошей отправной точкой. Однако, хотя генерирование 4005 пар адресов является относительно быстрым, обработка этих пар адресов для определения расстояния, пройденного с помощью API-интерфейса Map, вероятно, будет занимать много времени.

В случае, если вам все еще удается исчерпать 30-минутную квоту выполнения сценария, вы можете рассмотреть возможность использования методов пакетной обработки, когда вы настраиваете свое приложение для выполнения вычислений на меньших пакетах пар адресов, по одному пакету за разв течение определенного периода. Вы даже можете обрабатывать несколько пакетов одновременно, если вы правильно настроили приложение. Но это пост в другой раз.

Answer 2

Возможно, это не лучше, чем то, что у вас есть для производительности, но попробуйте разбить ее здесь на более модульное решение, тогда вы можете решить, какую часть оптимизировать, возможно, выполняя это в некотором подмножестве за раз;

function getValuesArray(values) {
  let valueArray = [];
  for (let i = 0; i < values.length; ++i) {
    valueArray.push({
      id: values[i][0],
      value: values[i][1]
    });
  }
  return valueArray;
}

function GoogleMaps() {
  //get distance
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("ABC");
  var outputSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("EFG");
  var lastrow = sheet.getLastRow();
  var lastcolumn = sheet.getLastColumn();
  var range = sheet.getRange(2, 3, lastrow - 1, 3);
  //var range = sheet.getRange(2, 3, 3, 3);
  //Origin is in row 2, column 3
  var values = range.getValues();
  var output = [];
  let list1 = getValuesArray(values);
  // deep clone
  const clone = (items) => items.map(item => Array.isArray(item) ? clone(item) : { ...item
  });
  // might only need list1 but usin two for clarity here
  const list2 = clone(list1);
  const listWork = [];
  for (var a = 0; a < list1.length; a++) {
    for (var j = 0; j < list2.length; j++) {
      listWork.push({
          dest: list2[j].value,
          destId: list2[j].id,
          origin: list1[a].value,
          originId: list1[a].id
        }
      }
    }
  }
  let results = [];
  for (let w = 0; w < listWork.length; w++) {
    results.push(startId: listWork.originId, endId: listWork.destId, map: maps(listWork.origin, listWork.dest));
  }
  for (let r = 0; r < results.length; r++) {
    let result = results[r];
    // seems to not be used 
    //var status = result.map.status;
    let route = !!result.map.routes && result.map.routes[0] ? result.map.routes[0] : null;
    if (route !== null &&
      route.legs &&
      route.legs[0] &&
      route.legs[0].duration &&
      route.legs[0].duration.value) {
      let time = route.legs[0].duration.value / 60;
      let row = [result.startId, result.endId, time];
      output.push(row);
    }
  }

  let outputLength = output.length;
  let outputRange = outputSheet.getRange(1, 1, outputLength, 3);
  outputRange.setValues(output);
}