5

ソートされた整数の配列 (重複なし) が与えられた場合、それらの交点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]。

指定された配列は変更しないでください。

私の試みは以下です。ここの遊び場。

これを達成するためのより効率的な（より速い）方法はありますか？

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]
4

3 に答える 3

3

最初の課題は、関数を正しくすることです。それが正しければ、速度について心配することができます。

次のような関数をつまずかせる可能性のあるものがいくつかあります。

  • NaN
  • 悪い制限
  • 繰り返される数字
  • 入力配列は 1 つだけ (またはまったくない)

元の関数は [[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;
            }
        }
    }
}

(フィドル: http://jsfiddle.net/kn2wz2sc/4/ )

これは元の方法とほぼ同じように機能しますが、いくつかの最適化が行われています。次にどの数値を探しているかを常に認識しており、少なくともその大きさの数値が見つかるまで、各配列をすばやく反復処理します。数値が大きすぎる場合は、探している数値を更新します。

Mk2 では、毎回 0-n からチェックするのではなく、一致をカウントする Casey の方法からインスピレーションを得ました。これにより、いくつかの比較を簡単に行うことができます (Casey は現在インデックスを使用しているため、両方の方法は非常に似ています)。 . Mk3 では、さらにマイクロ最適化を行い、インデックスを熱心にインクリメントして、内部ループを必要としないようにしました。

これは、上に挙げたすべての基準に対して安全であり (NaN!=NaN であるため NaN を無視するため、交差点に存在することはありません)、数値に限定されず、制限に達するとすぐに終了します。

jsperf は、Mk3 がこれまでのところ最速の方法であることを示しています: http://jsperf.com/sorted-intersect/5 (そして、重複や NaN に対しては安全です)。

于 2015-05-10T08:59:22.593 に答える
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

于 2015-05-10T08:29:38.033 に答える