JavaScript 배열을 사용하여 세트 차이를 계산하는 가장 빠르거나 가장 우아한 방법은 무엇입니까?
-
19-09-2019 - |
문제
허락하다 A
그리고 B
두 세트가 되십시오. 내가 찾고 있어요 진짜 세트 차이를 계산하는 빠르거나 우아한 방법 (A - B
또는 A \B
, 당신의 선호도에 따라) 그들 사이. 제목이 말한 것처럼 두 세트는 JavaScript 배열로 저장 및 조작됩니다.
메모:
- Gecko-Specific 트릭은 괜찮습니다
- 나는 기본 기능을 고수하는 것을 선호합니다 (그러나 더 빠른 가벼운 라이브러리에 열려 있습니다).
- 나는 보았지만 테스트하지 않았다. js. 세트 (이전 요점 참조)
편집하다: 중복 요소가 포함 된 세트에 대한 의견을 발견했습니다. 내가 "set"이라고 말할 때 나는 수학적 정의를 언급하고 있습니다. 이것은 중복 요소가 포함되어 있지 않다는 것을 의미합니다.
해결책
이것이 가장 효과적인지 모르지만 아마도 가장 짧은
A = [1, 2, 3, 4];
B = [1, 3, 4, 7];
diff = A.filter(function(x) { return B.indexOf(x) < 0 })
console.log(diff);
ES6으로 업데이트 :
A = [1, 2, 3, 4];
B = [1, 3, 4, 7];
diff = A.filter(x => !B.includes(x) );
console.log(diff);
다른 팁
글쎄, 7 년 후 ES6 세트 객체는 매우 쉽지만 (여전히 파이썬 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)));
console.log([...a_minus_b]) // {1}
console.log([...b_minus_a]) // {5}
console.log([...a_intersect_b]) // {2,3,4}
객체를지도로 사용하여 선형 스캔을 피할 수 있습니다. B
각 요소에 대해 A
에서와 같이 user187291의 답변:
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;
}
비표준 toSource()
방법 고유 한 속성 이름을 얻는 데 사용됩니다. 모든 요소가 이미 고유 한 문자열 표현이있는 경우 (숫자의 경우와 같이) 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를 해시 한 다음 배열에서 값을 유지합니다.
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;
}
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
키/값 쌍fnSelector
진실을 반환합니다.
그만큼 select()
일반적인 LISP에서 느슨하게 영감을 받았으며 단지 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의 요소가있는 두 세트를 제공합니다. 이러한 값을 사용하면 AB는 약 75ms를, 연합과 교차로는 각각 약 150ms입니다. (Mac Safari 4.0, 타이밍에 JavaScript 날짜를 사용합니다.)
나는 그것이 20 줄의 코드에 대한 괜찮은 보상이라고 생각합니다.
사용 aUNDSCORE.JS (기능적 JS를위한 라이브러리)
>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
@밀라노의 답변에서 빌린 몇 가지 간단한 기능 :
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 }
금식 방식에 관해서는, 이것은 그렇게 우아하지는 않지만 확실하게 테스트를 실행합니다. 하나의 배열을 물체로로드하는 것은 대량으로 처리하는 것이 훨씬 빠릅니다.
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.
이것은 작동하지만 다른 것이 훨씬 더 짧고 우아하다고 생각합니다.
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;