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

Intersection of N sorted integer arrays with limit

给定 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]

更快(但远不如其他答案快):

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

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

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

  • 错误限制
  • 重复的数字
  • 只有 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)。

这是另一种算法,其思想是计算我们看到每个数字的次数。一旦我们看到它 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;
}