[javascript] 자바 스크립트에서 배열 교차를위한 가장 간단한 코드

자바 스크립트에서 배열 교차를 구현하기위한 가장 간단한 라이브러리가없는 코드는 무엇입니까? 쓰고 싶다

intersection([1,2,3], [2,3,4,5])

그리고 얻다

[2, 3]

답변

의 조합 사용 Array.prototype.filter과 Array.prototype.indexOf:

array1.filter(value => -1 !== array2.indexOf(value))

또는 주석에서 vrugtehagel이 제안한 것처럼 Array.prototype.includes더 간단한 코드를 위해 최신 코드를 사용할 수 있습니다 .

array1.filter(value => array2.includes(value))

이전 브라우저의 경우 :

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

답변

입력이 정렬되어 있다고 가정 할 경우 특히 파괴적인 것으로 보입니다.

/* destructively finds the intersection of
 * two arrays in a simple fashion.
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *  State of input arrays is undefined when
 *  the function returns.  They should be
 *  (prolly) be dumped.
 *
 *  Should have O(n) operations, where n is
 *    n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b)
{
  var result = [];
  while( a.length > 0 && b.length > 0 )
  {
     if      (a[0] < b[0] ){ a.shift(); }
     else if (a[0] > b[0] ){ b.shift(); }
     else /* they're equal */
     {
       result.push(a.shift());
       b.shift();
     }
  }

  return result;
}

비파괴는 색인을 추적해야하기 때문에 더 복잡해야합니다.

/* finds the intersection of
 * two arrays in a simple fashion.
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *
 *  Should have O(n) operations, where n is
 *    n = MIN(a.length(), b.length())
 */
function intersect_safe(a, b)
{
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
}

답변

환경이 ECMAScript 6 Set을 지원하는 경우 간단하고 효율적인 방법 (사양 링크 참조) :

function intersect(a, b) {
  var setA = new Set(a);
  var setB = new Set(b);
  var intersection = new Set([...setA].filter(x => setB.has(x)));
  return Array.from(intersection);
}

더 짧지 만 읽기 쉽지 않습니다 (추가 교차점을 만들지 Set않음).

function intersect(a, b) {
      return [...new Set(a)].filter(x => new Set(b).has(x));
}

새로운 방지 Set에서 b모든 시간 :

function intersect(a, b) {
      var setB = new Set(b);
      return [...new Set(a)].filter(x => setB.has(x));
}

집합을 사용할 때 고유 한 값만 얻을 수 있으므로로 new Set[1,2,3,3].size평가됩니다 3.

답변

사용 Underscore.js 또는 lodash.js을

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]

답변

ES6 용어에 대한 나의 기여. 일반적으로 인수로 제공된 무한한 수의 배열과 배열의 교차점을 찾습니다.

Array.prototype.intersect = function(...a) {
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
     arr = [0,1,2,3,4,5,6,7,8,9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

스 니펫 확장

답변

// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

// Example:
console.log(intersect([1,2,3], [2,3,4,5]));

스 니펫 확장

큰 입력에서 다른 구현보다 우수한 간결한 솔루션을 권장합니다. 작은 입력의 성능이 중요한 경우 아래 대안을 확인하십시오.

대안 및 성능 비교 :

대체 구현에 대해서는 다음 스 니펫을 참조 하고 성능 비교는 https://jsperf.com/array-intersection-comparison 을 확인 하십시오 .

코드 스 니펫 표시

function intersect_for(a, b) {
  const result = [];
  const alen = a.length;
  const blen = b.length;
  for (let i = 0; i < alen; ++i) {
    const ai = a[i];
    for (let j = 0; j < blen; ++j) {
      if (ai === b[j]) {
        result.push(ai);
        break;
      }
    }
  }
  return result;
}

function intersect_filter_indexOf(a, b) {
  return a.filter(el => b.indexOf(el) !== -1);
}

function intersect_filter_in(a, b) {
  const map = b.reduce((map, el) => {map[el] = true; return map}, {});
  return a.filter(el => el in map);
}

function intersect_for_in(a, b) {
  const result = [];
  const map = {};
  for (let i = 0, length = b.length; i < length; ++i) {
    map[b[i]] = true;
  }
  for (let i = 0, length = a.length; i < length; ++i) {
    if (a[i] in map) result.push(a[i]);
  }
  return result;
}

function intersect_filter_includes(a, b) {
  return a.filter(el => b.includes(el));
}

function intersect_filter_has_this(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

function intersect_filter_has_arrow(a, b) {
  const set = new Set(b);
  return a.filter(el => set.has(el));
}

function intersect_for_has(a, b) {
  const result = [];
  const set = new Set(b);
  for (let i = 0, length = a.length; i < length; ++i) {
    if (set.has(a[i])) result.push(a[i]);
  }
  return result;
}

스 니펫 확장

Firefox 53의 결과 :

대형 어레이의 연산 / 초 (10,000 개 요소) :

filter + has (this)               523 (this answer)
for + has                         482
for-loop + in                     279
filter + in                       242
for-loops                          24
filter + includes                  14
filter + indexOf                   10

소형 어레이 (100 개 요소)의 Ops / sec :

for-loop + in                 384,426
filter + in                   192,066
for-loops                     159,137
filter + includes             104,068
filter + indexOf               71,598
filter + has (this)            43,531 (this answer)
filter + has (arrow function)  35,588

답변

연관 배열을 사용하는 것은 어떻습니까?

function intersect(a, b) {
    var d1 = {};
    var d2 = {};
    var results = [];
    for (var i = 0; i < a.length; i++) {
        d1[a[i]] = true;
    }
    for (var j = 0; j < b.length; j++) {
        d2[b[j]] = true;
    }
    for (var k in d1) {
        if (d2[k])
            results.push(k);
    }
    return results;
}

편집하다:

// new version
function intersect(a, b) {
    var d = {};
    var results = [];
    for (var i = 0; i < b.length; i++) {
        d[b[i]] = true;
    }
    for (var j = 0; j < a.length; j++) {
        if (d[a[j]])
            results.push(a[j]);
    }
    return results;
}