code

자바스크립트 배열을 사용하여 집합 차이를 계산하는 가장 빠르고 우아한 방법은 무엇입니까?

starcafe 2023. 10. 30. 21:10
반응형

자바스크립트 배열을 사용하여 집합 차이를 계산하는 가장 빠르고 우아한 방법은 무엇입니까?

허락하다A그리고.B두 세트가 나다나는 정말 빠르고 우아한 세트 차이를 계산하는 방법을 찾고 있습니다 (A - B아니면A \B에 ) 두 는 제목처럼 배열로 저장 및 조작됩니다두 세트는 제목처럼 자바스크립트 배열로 저장 및 조작됩니다.

주의:

  • 도마뱀 특유의 묘기는 괜찮습니다.
  • 기본 기능을 사용하고 싶지만 훨씬 빠른 경우 경량 라이브러리를 사용할 수 있습니다.
  • JS는 봤지만 테스트는 안 했어요.설정(이전 포인트 참조)

편집: 중복 요소가 포함된 세트에 대한 코멘트가 눈에 띄었습니다.제가 "set"이라고 말할 때 저는 수학적 정의를 말하는 것인데, 이것은 (무엇보다도) 중복되는 요소를 포함하지 않는다는 것을 의미합니다.

이것이 가장 효과적인지는 모르겠지만, 아마도 가장 짧을 것입니다.

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = A.filter(function(x) {
  return B.indexOf(x) < 0;
});

console.log(diff); // [2]

ES6로 업데이트됨:

const A = [1, 2, 3, 4];
const B = [1, 3, 4, 7];

const diff = A.filter(x => !B.includes(x));

console.log(diff); // [2]

7년 후 ES6의 세트(Set) 객체를 사용하면 꽤 쉽습니다. 하지만 파이썬의 것만큼 콤팩트하지는 않습니다. A - B), 그리고 보도에 따르면 보다 더 빠릅니다.indexOf대규모 어레이의 경우:

console.clear();

let a = new Set([1, 2, 3, 4]);
let b = new Set([5, 4, 3, 2]);

let a_minus_b = new Set([...a].filter(x => !b.has(x)));
let b_minus_a = new Set([...b].filter(x => !a.has(x)));
let a_intersect_b = new Set([...a].filter(x => b.has(x))); 
let a_union_b = new Set([...a, ...b]); 

console.log(...a_minus_b);     // {1}
console.log(...b_minus_a);     // {5}
console.log(...a_intersect_b); // {2,3,4}
console.log(...a_union_b);     // {1,2,3,4,5}

이러한 솔루션을 많이 보면 작은 경우에도 효과가 있습니다.그러나 백만 개의 아이템까지 날려 버리면 시간의 복잡성은 점점 더 우습게 됩니다.

 A.filter(v => B.includes(v))

그것은 O(N^2) 솔루션처럼 보이기 시작합니다.O(N) 솔루션이 있기 때문에 그것을 사용해 봅시다. JS 실행 시간에 대한 최신 정보가 없다면 생성기가 되지 않도록 쉽게 수정할 수 있습니다.

    function *setMinus(A, B) {
      const setA = new Set(A);
      const setB = new Set(B);

      for (const v of setB.values()) {
        if (!setA.delete(v)) {
            yield v;
        }
      }

      for (const v of setA.values()) {
        yield v;
      }
    }

    a = [1,2,3];
    b = [2,3,4];

    console.log(Array.from(setMinus(a, b)));

이것은 다른 많은 솔루션보다 조금 더 복잡하지만, 목록이 많을 때는 훨씬 더 빠를 것입니다.

0~10,000 사이의 1,000,000개의 임의 정수 집합에서 실행하는 성능 차이에 대해 간단히 살펴봅시다. 다음과 같은 성능 결과를 확인할 수 있습니다.

setMinus time =  181 ms
    diff time =  19099 ms


function buildList(count, range) {
  result = [];
  for (i = 0; i < count; i++) {
    result.push(Math.floor(Math.random() * range))
  }
  return result;
}

function *setMinus(A, B) {
  const setA = new Set(A);
  const setB = new Set(B);

  for (const v of setB.values()) {
    if (!setA.delete(v)) {
        yield v;
    }
  }

  for (const v of setA.values()) {
    yield v;
  }
}

function doDiff(A, B) {
  return A.filter(function(x) { return B.indexOf(x) < 0 })
}

const listA = buildList(100_000, 100_000_000); 
const listB = buildList(100_000, 100_000_000); 

let t0 = process.hrtime.bigint()

const _x = Array.from(setMinus(listA, listB))

let t1 = process.hrtime.bigint()

const _y = doDiff(listA, listB)

let t2 = process.hrtime.bigint()

console.log("setMinus time = ", (t1 - t0) / 1_000_000n, "ms");
console.log("diff time = ", (t2 - t1) / 1_000_000n, "ms");

사용하시는 경우Sets, 매우 단순하고 성능이 뛰어납니다.

function setDifference(a, b) {
  return new Set(Array.from(a).filter(item => !b.has(item)));
}

부터.Set후드 아래에 해시 함수*를 사용합니다.has기능은 보다 훨씬 빠릅니다.indexOf(예를 들어, 100개 이상의 품목이 있는 경우 이 문제가 중요합니다.)

객체를 지도로 사용하여 선형 스캔을 피할 수 있습니다.B요소별로A사용자 187291의 답변과 같이:

function setMinus(A, B) {
    var map = {}, C = [];

    for(var i = B.length; i--; )
        map[B[i].toSource()] = null; // any other value would do

    for(var i = A.length; i--; ) {
        if(!map.hasOwnProperty(A[i].toSource()))
            C.push(A[i]);
    }

    return C;
}

non-standard 메서드는 고유한 속성 이름을 얻는 데 사용됩니다. 만약 모든 요소가 이미 고유한 문자열 표현을 가지고 있다면(숫자의 경우와 마찬가지로) 코드를 삭제하여 속도를 높일 수 있습니다.toSource()

jQuery를 사용하여 가장 짧은 것은 다음과 같습니다.

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = $(A).not(B);

console.log(diff.toArray());
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

배열 B를 해시한 다음 B에 없는 배열 A의 값을 유지합니다.

function getHash(array){
  // Hash an array into a set of properties
  //
  // params:
  //   array - (array) (!nil) the array to hash
  //
  // return: (object)
  //   hash object with one property set to true for each value in the array

  var hash = {};
  for (var i=0; i<array.length; i++){
    hash[ array[i] ] = true;
  }
  return hash;
}

function getDifference(a, b){
  // compute the difference a\b
  //
  // params:
  //   a - (array) (!nil) first array as a set of values (no duplicates)
  //   b - (array) (!nil) second array as a set of values (no duplicates)
  //
  // return: (array)
  //   the set of values (no duplicates) in array a and not in b, 
  //   listed in the same order as in array a.

  var hash = getHash(b);
  var diff = [];
  for (var i=0; i<a.length; i++){
    var value = a[i];
    if ( !hash[value]){
      diff.push(value);
    }
  }
  return diff;
}

언더스코어.js 사용(기능적 JS용 라이브러리)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]

@milan의 답변에서 차용한 간단한 기능 몇 가지:

const setDifference = (a, b) => new Set([...a].filter(x => !b.has(x)));
const setIntersection = (a, b) => new Set([...a].filter(x => b.has(x)));
const setUnion = (a, b) => new Set([...a, ...b]);

용도:

const a = new Set([1, 2]);
const b = new Set([2, 3]);

setDifference(a, b); // Set { 1 }
setIntersection(a, b); // Set { 2 }
setUnion(a, b); // Set { 1, 2, 3 }

Christoph의 아이디어를 통합하고 배열 및 객체/해시에 대한 몇 가지 비표준 반복 방법 가정 (each그리고 친구들), 우리는 총 20개의 선에서 선형 시간의 설정 차이, 결합 및 교차점을 얻을 수 있습니다.

var setOPs = {
  minusAB : function (a, b) {
    var h = {};
    b.each(function (v) { h[v] = true; });
    return a.filter(function (v) { return !h.hasOwnProperty(v); });
  },
  unionAB : function (a, b) {
    var h = {}, f = function (v) { h[v] = true; };
    a.each(f);
    b.each(f);
    return myUtils.keys(h);
  },
  intersectAB : function (a, b) {
    var h = {};
    a.each(function (v) { h[v] = 1; });
    b.each(function (v) { h[v] = (h[v] || 0) + 1; });
    var fnSel = function (v, count) { return count > 1; };
    var fnVal = function (v, c) { return v; };
    return myUtils.select(h, fnSel, fnVal);
  }
};

이는 다음과 같이 가정합니다.each그리고.filter어레이에 대해 정의되며, 두 가지 유틸리티 방법이 있습니다.

  • myUtils.keys(hash): 해시 키가 있는 배열을 반환합니다.

  • myUtils.select(hash, fnSelector, fnEvaluator): 호출 결과와 함께 배열을 반환합니다.fnEvaluator키/에 대한 키fnSelectortrue를 반환합니다.

select()커먼 리스프에서 느슨하게 영감을 받았고, 단지filter()그리고.map()하나로 합쳐졌습니다. (그것들을 정의하는 것이 더 나을 것입니다.Object.prototype, 하지만 그렇게 하는 것은 jQuery에 큰 피해를 입히기 때문에 저는 정적 유틸리티 방법에 만족했습니다.)

성능:테스트 대상

var a = [], b = [];
for (var i = 100000; i--; ) {
  if (i % 2 !== 0) a.push(i);
  if (i % 3 !== 0) b.push(i);
}

는 50,000 및 66,666 요소로 구성된 두 세트를 제공합니다.이 값을 사용할 경우 A-B는 약 75ms가 소요되며, 유니언과 교차는 각각 약 150ms가 소요됩니다. (Mac Safari 4.0, 타이밍은 자바스크립트 Date를 사용합니다.)

20줄의 코드에 대한 적절한 보상이라고 생각합니다.

빠른 방법에 대해서 말하자면, 이것은 우아하지 않지만 확실하게 하기 위해 몇 가지 테스트를 해봤습니다.하나의 어레이를 객체로 로드하는 것이 대량으로 처리하는 데 훨씬 빠릅니다.

var t, a, b, c, objA;

    // Fill some arrays to compare
a = Array(30000).fill(0).map(function(v,i) {
    return i.toFixed();
});
b = Array(20000).fill(0).map(function(v,i) {
    return (i*2).toFixed();
});

    // Simple indexOf inside filter
t = Date.now();
c = b.filter(function(v) { return a.indexOf(v) < 0; });
console.log('completed indexOf in %j ms with result %j length', Date.now() - t, c.length);

    // Load `a` as Object `A` first to avoid indexOf in filter
t = Date.now();
objA = {};
a.forEach(function(v) { objA[v] = true; });
c = b.filter(function(v) { return !objA[v]; });
console.log('completed Object in %j ms with result %j length', Date.now() - t, c.length);

결과:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

그러나 이것은 문자열에서만 작동합니다.번호가 매겨진 집합을 비교하려는 경우 parseFloat을 사용하여 결과를 매핑할 수 있습니다.

아래 함수는 Python의 클래스에서 찾을 수 있는 메소드의 포트이며 TC39 Set 메소드 제안서를 따릅니다.

const
  union = (a, b) => new Set([...a, ...b]),
  intersection = (a, b) => new Set([...a].filter(x => b.has(x))),
  difference = (a, b) => new Set([...a].filter(x => !b.has(x))),
  symetricDifference = (a, b) => union(difference(a, b), difference(b, a)),
  isSubsetOf = (a, b) => [...b].every(x => a.has(x)),
  isSupersetOf = (a, b) => [...a].every(x => b.has(x)),
  isDisjointFrom = (a, b) => !intersection(a, b).size;

const
  a = new Set([1, 2, 3, 4]),
  b = new Set([5, 4, 3, 2]);

console.log(...union(a, b));              // [1, 2, 3, 4, 5]
console.log(...intersection(a, b));       // [2, 3, 4]
console.log(...difference(a, b));         // [1]
console.log(...difference(b, a));         // [5]
console.log(...symetricDifference(a, b)); // [1, 5]

const
  c = new Set(['A', 'B', 'C', 'D', 'E']),
  d = new Set(['B', 'D']);
  
console.log(isSubsetOf(c, d));            // true
console.log(isSupersetOf(d, c));          // true

const
  e = new Set(['A', 'B', 'C']),
  f = new Set(['X', 'Y', 'Z']);
  
console.log(isDisjointFrom(e, f));        // true
.as-console-wrapper { top: 0; max-height: 100% !important; }

이것도 효과가 있지만, 다른 것이 훨씬 짧고 우아하다고 생각합니다.

A = [1, 'a', 'b', 12];
B = ['a', 3, 4, 'b'];

diff_set = {
    ar : {},
    diff : Array(),
    remove_set : function(a) { ar = a; return this; },
    remove: function (el) {
        if(ar.indexOf(el)<0) this.diff.push(el);
    }
}

A.forEach(diff_set.remove_set(B).remove,diff_set);
C = diff_set.diff;

새 메소드 제안서를 폴리필하는 데 사용:

import "core-js"

new Set(A).difference(B)

이론적으로 시간의 복잡성은Θ(n),어디에n는 에 있는 원소의 개수입니다.B.

@koblas에서 제공하는 답변은 좋으나 두 배열 모두에 있는 항목도 반환합니다.차액을 얻고자 하는 저의 사용 사례에 대해 약간의 수정(ES6에서)과 함께(새로운 항목을 검색할 의도로)array_j, 의 항목과 마찬가지로array_i없는array j별도의 출력 어레이로서 다음과 같은 3가지 주요 방법을 제공합니다.

var arr_i = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"];
var arr_j = ["a", "c", "d", "f", "g", "h", "j", "k", "l", "n"];

정답은 배열 j의 새 항목이어야 합니다.['b', 'e', 'i']배열 j에 없는 배열 i의 항목뿐만 아니라['k', 'l', 'n']

// Convert to Set
var set_i = new Set(arr_i);
var set_j = new Set(arr_j);

const changes = (arr1, arr2) => {
  // Using Array method
  let turn_on = arr2.filter((x) => !arr1.includes(x));
  let turn_off = arr1.filter((x) => !arr2.includes(x));
  return { turn_on, turn_off };
};

const setChanges = (set1, set2) => {
  // Using Set method
  let turn_on = new Set([...set2].filter((x) => !set1.has(x)));
  let turn_off = new Set([...set1].filter((x) => !set2.has(x)));
  return { turn_on, turn_off };
};

function* setMinus(setA, setB) {
  // Using Set method with generator by @koblas
  for (const v of setB.values()) {
    // .delete returns true if value was already in Set; otherwise false.
    if (!setA.delete(v)) {
      yield v;
    }
  }
}

const changesGenerator = (set1, set2) => {
  let turn_off = Array.from(setMinus(set2, set1));
  let turn_on = Array.from(setMinus(set1, set2));
  return { turn_on, turn_off };
};

세 가지 방법 모두 반환됩니다.

{ turn_on: [ 'k', 'l', 'n' ], turn_off: [ 'b', 'e', 'i' ] }

5000개 항목이 포함된 [0,10000] 범위의 숫자를 포함한 랜덤 배열에서 타이밍 조정

let arr_i = Array.from({ length: 5000 }, () =>
  Math.floor(Math.random() * 10000)
);
let arr_j = Array.from({ length: 5000 }, () =>
  Math.floor(Math.random() * 10000)
);

var set_i = new Set(arr_i);
var set_j = new Set(arr_j);

console.time("Array method");
changes(arr_i, arr_j);
console.timeEnd("Array method");

console.time("Set method");
setChanges(set_i, set_j);
console.timeEnd("Set method");

console.time("Generator method");
changesGenerator(set_i, set_j);
console.timeEnd("Generator method");

반환:

Array method: 36.894ms
Set method: 1.14ms
Generator method: 2.155ms

그래요, 그냥 사용해요.

let set1_minus_set2 = new Set([...set1].filter((x) => !set2.has(x)));

언급URL : https://stackoverflow.com/questions/1723168/what-is-the-fastest-or-most-elegant-way-to-compute-a-set-difference-using-javasc

반응형

'code' 카테고리의 다른 글

코드 점화기에서 mysql AND OR 쿼리 결합  (0) 2023.10.30
jQuery 체크 ifjQuery 체크 if존재하며 값을 갖습니다.존재하며 값을 갖습니다.  (0) 2023.10.30
아콘다 루트 환경 재설정 방법  (0) 2023.10.30
오류 메시지 없이 PL/SQL 컴파일이 실패함  (0) 2023.10.30
PowerShell에서 Windows Credential Manager 액세스  (0) 2023.10.30

'code'의 다른글

  • 현재글자바스크립트 배열을 사용하여 집합 차이를 계산하는 가장 빠르고 우아한 방법은 무엇입니까?

관련글

댓글

티스토리툴바