N 个排序整数数组的交集有限制

Question

给定 N 个排序的整数数组（无重复项），我想计算它们交集中的第一个 limit 个整数。

例如，给定以下数组：

[2, 5, 7, 8, 10, 12, 13, 15, 20, 24]
[3, 4, 5, 6, 9, 10, 11, 17, 20]
[1, 2, 3, 5, 6, 10, 12, 20, 23, 29]

交集是[5, 10, 20]，所以如果limit = 2，结果应该是[5, 10]。

不应改变给定的数组。

我的尝试如下。 Playground here.

是否有更有效（更快）的方法来实现此目的？

将不胜感激 jsperf 比较。

function intersection(sortedArrays, limit) {
  var arraysCount = sortedArrays.length;
  var indices = sortedArrays.map(function(array) { return 0; });
  var values, maxValue, valuesAreSame, reachedEnd, i, result = [];

  while (true) {
    reachedEnd = indices.some(function(index, i) {
      return index === sortedArrays[i].length;
    });

    if (reachedEnd) {
      return result;
    }

    values = sortedArrays.map(function(array, i) { return array[indices[i]]; });
    valuesAreSame = values.every(function(value, i) { return value === values[0]; });

    if (valuesAreSame) {
      result[result.length] = values[0];

      if (result.length === limit) {
        return result;
      }

      for (i = 0; i < arraysCount; i++) {
        indices[i]++;
      }
    } else {
      maxValue = Math.max.apply(null, values);

      for (i = 0; i < arraysCount; i++) {
        if (values[i] < maxValue) {
          indices[i]++;
        }
      }  
    }  
  }
}

console.log(intersection([[0, 3, 8, 11], [1, 3, 11, 15]], 1));
// => [3]

Answer 1

更快（但远不如其他答案快）：

function intersectMultiple(sortedArrays, limit) {
    var set = {}, result = [],
        a = sortedArrays.length,
        l = Math.max.apply(null, sortedArrays.map(function (a) {
            return a.length;
        })), i, j, c = 0, val;

    for (i = 0; i < l && c < limit; i++) {
        for (j = 0; j < a && c < limit; j++) {
            val = sortedArrays[j][i];
            if (!set.hasOwnProperty(val)) set[val] = 0;
            if (++set[val] === a) result[c++] = val;
        }
    };
    return result;
}

和

var s = [
    [2, 5, 7, 8, 10, 12, 13, 15, 20, 24],
    [3, 4, 5, 6, 9, 10, 11, 17, 20],
    [1, 2, 3, 5, 6, 10, 12, 20, 23, 29]
];

intersectMultiple(s, 2);

// [5, 10]

http://jsperf.com/intersect-multiple

Answer 2

第一个挑战是使函数正确。一旦正确，我们就可以担心速度了。

有些事情可能会像这样使函数出错：

南
错误限制
重复的数字
只有 1 个输入数组（或根本 none）

您的原始函数可以处理重复的数字，例如 [[9,9,9,9],[9,9,9]]，但如果任何值为 NaN，就会陷入无限循环，并处理限制为 0，就好像根本没有限制一样。

这是我的 (Mk3) 尝试：

function intersection( arrs, limit ) {
    var result = [], posns = [];
    var j, v, next, n = arrs.length, count = 1;
    if( !n || limit <= 0 ) {
        return result; // nothing to do
    }
    if( n === 1 ) {
        // special case needed because main loop cannot handle this
        for( j = 0; j < arrs[0].length && result.length < limit; ++ j ) {
            v = arrs[0][j];
            if( v === v ) {
                result.push( v );
            }
        }
        return result;
    }
    for( j = 0; j < n; ++ j ) {
        if( !arrs[j].length ) {
            return result; // no intersection
        }
        posns[j] = 0;
    }
    next = arrs[n-1][0];
    ++ posns[n-1];
    while( true ) {
        for( j = 0; j < n; ++ j ) {
            do {
                if( posns[j] >= arrs[j].length ) {
                    return result; // ran out of values
                }
                v = arrs[j][posns[j]++];
            } while( v < next || v !== v );

            if( v !== next ) {
                count = 1;
                next = v;
            } else if( (++ count) >= n ) {
                result.push( next );
                if( result.length >= limit ) {
                    return result; // limit reached
                }
                if( posns[j] >= arrs[j].length ) {
                    return result; // ran out of values
                }
                next = arrs[j][posns[j]++];
                count = 1;
            }
        }
    }
}

(fiddle: http://jsfiddle.net/kn2wz2sc/4/)

这与您的原始方法的工作方式大致相同，但有几处优化。它总是知道下一个要查找的数字，并会快速遍历每个数组，直到找到一个至少有那么大的数字。如果数字太大，它会更新它正在寻找的数字。

在 Mk2 中，我从 Casey 的计算匹配项的方法中获得了一些灵感，而不是每次都从 0-n 检查，这允许它缩短一些比较（并且由于 Casey 现在使用索引，这两种方法变得非常相似）。在 Mk3 中，我做了一些微优化，急切地增加索引，这样它就不需要内部循环了。

这对于我上面列出的所有标准都是安全的（它忽略 NaN，因为 NaN!=NaN 因此永远不会在交集），不限于数字，一旦达到任何限制就会迅速退出.

jsperf 表明 Mk3 是迄今为止最快的方法：http://jsperf.com/sorted-intersect/5（并且它仍然可以安全地防止重复和 NaN）。

Answer 3

这是另一种算法，其思想是计算我们看到每个数字的次数。一旦我们看到它 arrs.length 次，我们就知道它在十字路口。如果它甚至不在一个列表中，它也不在交叉点中，我们可以跳到该列表中的下一个数字。原来很多faster!

此方法改变了数组，但更易于阅读。

function intersection(arrs, limit) {
    var intersections = [];

    // Keep track of how many times we've seen the largest element seen so far.
    var largest = -Infinity;
    var count = 0;

    while (intersections.length < limit) {
        for (var i = 0; i < arrs.length; i++) {

            // Drop elements less than `largest`.
            while (arrs[i].length && arrs[i][0] < largest)
                arrs[i].shift();

            // Ignore repeated elements (not needed if you don't have repeated elements).
            while (arrs[i].length >= 2 && arrs[i][0] == largest && arrs[i][1] == largest)
                arrs[i].shift();

            // If we ran out of elements, we're done.
            if (!arrs[i].length)
                return intersections;

            // Look at the next element.
            var next = arrs[i].shift();
            if (next == largest)
                count++;
            else {
                count = 1;
                largest = next;
            }

            // Once we see it enough times, we can be sure it's in the intersection!
            if (count == arrs.length)
                intersections.push(largest);
        }
    }

    return intersections;
}

这个方法没有，但是比较难读。

function intersection(arrs, limit) {
    var intersections = [];
    var indices = [];
    for (var i = 0; i < arrs.length; i++)
        indices[i] = 0;

    // Keep track of how many times we've seen the largest element seen so far.
    var largest = -Infinity;
    var count = 0;

    while (intersections.length < limit) {
        for (var i = 0; i < arrs.length; i++) {

            // Skip past elements less than `largest`.
            while (indices[i] < arrs[i].length && arrs[i][indices[i]] < largest)
                indices[i]++;

            // If we ran out of elements, we're done.
            if (indices[i] >= arrs[i].length)
                return intersections;

            // Look at the next element.
            var next = arrs[i][indices[i]++];
            if (next == largest)
                count++;
            else {
                count = 1;
                largest = next;
            }

            // Once we see it enough times, we can be sure it's in the intersection!
            if (count == arrs.length)
                intersections.push(largest);
        }
    }

    return intersections;
}

N 个排序整数数组的交集有限制

Intersection of N sorted integer arrays with limit

javascript

arrays

algorithm

intersection

set-intersection