logo标签列表

将数组中的每个元素与其他每个元素进行比较

javascriptarrayscomparereduceoverlap
3

我需要比较日程表是否有重叠，可以是2个到无限个日程表。

例如，一个包含3个日程表的数组如下所示：

var dateRanges =  [
    {
      DaysOfWeek: ['Sun', 'Mon'],
      StartTime: "01:00",
      StopTime: "17:00",
      AllDay: false
    },
    {
      DaysOfWeek: ['Tues', 'Wed'],
      StartTime: "12:00",
      StopTime: "21:59",
      AllDay: true
    },
            {
      DaysOfWeek: ['Thur', 'Sun'],
      StartTime: "12:00",
      StopTime: "21:59",
      AllDay: true
    }
  ]

我正在努力想方设法比较所有数组。目前我有以下代码：

checkScheduleForOverlap: function (dateRanges) {

  var result = dateRanges.reduce((result, current, i, arr) => {
    // console.log(previous, current);

    // get the previous range
    if (i === 0) { return result; }
    var previous = arr[i - 1];

    // Schedule1
    var startTime1 = new Date('1970-01-01T' + previous.StartTime + 'Z');
    var stopTime1 = new Date('1970-01-01T' + previous.StopTime + 'Z');

    // Schedule2
    var startTime2 = new Date('1970-01-01T' + current.StartTime + 'Z');
    var stopTime2 = new Date('1970-01-01T' + current.StopTime + 'Z');

    previous.DaysOfWeek.forEach(function (prevDay) {

      console.log(prevDay);
      current.DaysOfWeek.forEach(function (currDay) {
        console.log(currDay);

        if (prevDay === currDay) {
          var overlap = (startTime1 <= stopTime2) && (stopTime1 >= startTime2);

          // store the result
          if (overlap) {
            // yes, there is overlap
            result.overlap = true;
            // store the specific ranges that overlap
            result.days.push(currDay);
          }
        }
      });
    });

    return result;

    // seed the reduce
  }, { overlap: false, days: [] });

  // return the final results
  console.log(result);
  return result;

}

但是它只比较第二个数组与第一个数组，以及第三个数组与第二个数组。 它还需要将第三个数组与第一个数组进行比较。(如果有4个时间表，则每个时间表都需要相互比较。)
我这样做是否正确？还有什么可以做到使每个“DaysOfWeek”时间表比较“StartTime”和“StopTime”与其他时间表的值？
我使用静态日期创建了一个虚假的日期对象，并且只比较时间值。
如果这不是一种有效的方法，我也可以用完全不同的方式来处理它。
1
我相信你的意思是有限的，而不是无限的日程安排。 - Keith
我的意思是无限的，因为用户可以添加无限数量的日程安排，并且所有日程安排都必须相互检查以避免重叠。 - TetraDev
1
一个用户可以添加无限数量的日程安排。不，他们不能。 - Keith
你为什么这样说？我知道我的项目需求。 - TetraDev
1
在这个宇宙中，用户不可能无限次地执行某些操作。您可能需要类似于“将数组中的每个元素与其他每个元素进行比较”的操作。您可以尝试使用 moment-range 库：https://github.com/rotaready/moment-range/blob/master/README.md - CertainPerformance
2
将数组中的每个元素与其他每个元素进行比较。是的，没错，我不知道自己在引发哲学困境。我已经更新了标题 :-D - TetraDev
2个回答
5

让我们专注于您问题中涉及到的多个数组之间比较部分。目前为止，比较的实际逻辑并不重要。

这一切都始于一个嵌套的 for 循环：

var arr1 = [ "A", "B", "C" ];
var arr2 = [ "1", "2", "3" ];

// Runs arr1.length * arr2.length = 9 times
for (let i = 0; i < arr1.length; i += 1) {
  for (let j = 0; j < arr2.length; j += 1) {
    console.log(
      "run", i * arr2.length + j, 
      "result", arr1[i], arr2[j]
    );
  }
}

当您拥有一个循环遍历两个数组中所有对的函数时，接下来要做的就是从一个数组列表中找到所有可能的对：

const arrays = [ [ "A" ], [ "B" ], [ "C" ] ];

for (let i = 0; i < arrays.length - 1; i += 1) {
//                                ^^^
  for (let j = i + 1; j < arrays.length; j += 1) {
//             ^^^^^
    console.log(
      JSON.stringify(arrays[i]), 
      JSON.stringify(arrays[j])
    );
  }
}

现在我们已经掌握了基础知识，可以将它们串联起来进行重构。我不得不承认重构有点个人喜好的问题，只将 for 循环包装在函数中而不进行其他更改是完全可以的。
我将第一个原则命名为组合，使用 reduce 和 map 代替了 for 循环。第二个 for 循环现在包含在 allPairs 中。 

// Utilities:
const combinations = ([xs, ys]) => 
  xs.reduce(
    (cs, x) => cs.concat(ys.map(y => [x, y])),
    []
  );
  
const allPairs = (xs) => 
  xs.reduce(
    (ps, x, i) => ps.concat(xs.slice(i + 1).map(y => [x, y])),
    []
  );

const flatten = xxs => xxs.reduce((xs, ys) => xs.concat(ys))

const findMatches = (matchFn, arrays) => flatten(
    allPairs(arrays).map(combinations)).filter(matchFn);

// App:
// Let's just stick to an easy example
const overlap = ([x, y]) => x === y;

console.log(
  findMatches(
    overlap, 
    [ [ 1, 2 ], [ 1, 3 ], [ 1, 2, 3], [ 4, 5 ], [ 1 ] ]
  )
);

这种方法会返回重叠元素的对。你需要自己编写overlaps函数。通过使用find而不是filter可以提高效率，后者将返回第一个重叠的对。如果你真的想在构建所有配对组合之前尽早返回，你还需要移动一些其他内容（但我想性能不会成为问题）。

谢谢你的全面回答！你的方法和我不同，我可以从中学习到东西。在你回答之前，我已经发布了一个答案来展示我最终创建的内容。我会看看能从你的答案中融入什么来让我的代码更好。 - TetraDev
1

我使用以下代码使其正常工作。它可能可以提高效率，但对于小列表来说，它很好用。

 /**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
checkScheduleForOverlap: function (dateRanges) {

  function dateRangeOverlaps (a_start, a_end, b_start, b_end) {
    if (a_start <= b_start && b_start <= a_end) return true; // b starts in a
    if (a_start <= b_end && b_end <= a_end) return true; // b ends in a
    if (b_start < a_start && a_end < b_end) return true; // a in b
    return false;
  }

  function multipleDateRangeOverlaps () {
    var i, j;
    if (arguments.length % 2 !== 0)
      throw new TypeError('Arguments length must be a multiple of 2');
    for (i = 0; i < arguments.length - 2; i += 2) {
      for (j = i + 2; j < arguments.length; j += 2) {
        if (
          dateRangeOverlaps(
            arguments[i], arguments[i + 1],
            arguments[j], arguments[j + 1]
          )
        ) return true;
      }
    }
    return false;
  }

  var result = {
    overlappingDays: [],
    overlap: false
  };

  // for every Schedule
  for (let i = 0; i < dateRanges.length; i++) {
    var current = dateRanges[i];

    // current Schedule
    var startTime1 = current.StartTime;
    var stopTime1 = current.StopTime;

    current.DaysOfWeek.forEach(function (currDay) {

      // console.log('currentScheduleDay', currDay);

      // for every OTHER schedule
      for (let j = 0; j < dateRanges.length; j++) {
        var nextSchedule = dateRanges[j];

        if (j === i) {
          continue;
        }

        nextSchedule.DaysOfWeek.forEach(function (nextDay) {
          // console.log('nextScheduleDay', nextDay);

          if (nextDay === currDay) {

            // next Schedule
            var startTime2 = nextSchedule.StartTime;
            var stopTime2 = nextSchedule.StopTime;

            // var overlap = (startTime1 <= stopTime2) && (stopTime1 >= startTime2);
            var overlap = multipleDateRangeOverlaps(startTime1, stopTime1, startTime2, stopTime2);

            // store the result
            if (overlap) {
              // yes, there is overlap
              result.overlap = true;
              // store the specific ranges that overlap
              result.overlappingDays.push(currDay);
            }

          }
        });
      }

    });
  }

  // remove duplicates in result

  var obj = {};

  for (var i = 0, len = result.overlappingDays.length; i < len; i++) {
    obj[result.overlappingDays[i]] = result.overlappingDays[i];
  }

  result.overlappingDays = new Array();

  for (var key in obj) {
    result.overlappingDays.push(obj[key]);
  }

  if (result.overlappingDays) {
    this.scheduleDaysOverlap = result.overlappingDays;
  }

}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接