반응형
자바 스크립트에서 배열 교차를위한 가장 간단한 코드
자바 스크립트에서 배열 교차를 구현하기위한 가장 간단한 라이브러리가없는 코드는 무엇입니까? 쓰고 싶다
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>");연관 배열을 사용하는 것은 어떻습니까?
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;
}
정렬 된 프리미티브 배열에 대한 @atk의 구현 성능은 .shift가 아닌 .pop을 사용하여 향상시킬 수 있습니다.
function intersect(array1, array2) {
var result = [];
// Don't destroy the original arrays
var a = array1.slice(0);
var b = array2.slice(0);
var aLast = a.length - 1;
var bLast = b.length - 1;
while (aLast >= 0 && bLast >= 0) {
if (a[aLast] > b[bLast] ) {
a.pop();
aLast--;
} else if (a[aLast] < b[bLast] ){
b.pop();
bLast--;
} else /* they're equal */ {
result.push(a.pop());
b.pop();
aLast--;
bLast--;
}
}
return result;
}
jsPerf를 사용하여 벤치 마크를 만들었습니다 : http://bit.ly/P9FrZK . .pop을 사용하는 것이 약 3 배 빠릅니다.
// 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
jQuery 사용 :
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
- 그것을 정렬
- 인덱스 0에서 하나씩 확인하고 그로부터 새 배열을 만듭니다.
이런 식으로 잘 테스트되지는 않았습니다.
function intersection(x,y){
x.sort();y.sort();
var i=j=0;ret=[];
while(i<x.length && j<y.length){
if(x[i]<y[j])i++;
else if(y[j]<x[i])j++;
else {
ret.push(x[i]);
i++,j++;
}
}
return ret;
}
alert(intersection([1,2,3], [2,3,4,5]));
추신 : 알고리즘은 숫자 및 일반 문자열에만 사용되며 임의의 객체 배열의 교차가 작동하지 않을 수 있습니다.
문자열이나 숫자 만 포함하는 배열의 경우 다른 답변 중 일부에 따라 정렬하여 무언가를 수행 할 수 있습니다. 임의의 객체 배열의 일반적인 경우에는 먼 길을 피할 수 없다고 생각합니다. 다음은 매개 변수로 제공된 여러 배열의 교차점을 제공합니다 arrayIntersection.
var arrayContains = Array.prototype.indexOf ?
function(arr, val) {
return arr.indexOf(val) > -1;
} :
function(arr, val) {
var i = arr.length;
while (i--) {
if (arr[i] === val) {
return true;
}
}
return false;
};
function arrayIntersection() {
var val, arrayCount, firstArray, i, j, intersection = [], missing;
var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array
// Search for common values
firstArray = arrays.pop();
if (firstArray) {
j = firstArray.length;
arrayCount = arrays.length;
while (j--) {
val = firstArray[j];
missing = false;
// Check val is present in each remaining array
i = arrayCount;
while (!missing && i--) {
if ( !arrayContains(arrays[i], val) ) {
missing = true;
}
}
if (!missing) {
intersection.push(val);
}
}
}
return intersection;
}
arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"];
ES2015와 Sets를 사용하면 꽤 짧습니다. 문자열과 같은 배열 형 값을 허용하고 중복을 제거합니다.
let intersection = function(a, b) {
a = new Set(a), b = new Set(b);
return [...a].filter(v => b.has(v));
};
console.log(intersection([1,2,1,2,3], [2,3,5,4,5,3]));
console.log(intersection('ccaabbab', 'addb').join(''));JavaScript 객체를 사용하여 배열 중 하나에서 값의 색인을 작성하는 가장 작은 것 (여기서 filter / indexOf 솔루션 ) 을 약간 조정하면 O (N * M)에서 "아마도"선형 시간으로 줄입니다. 소스 1 소스 2
function intersect(a, b) {
var aa = {};
a.forEach(function(v) { aa[v]=1; });
return b.filter(function(v) { return v in aa; });
}
이것은 가장 간단한 해결책이 아니며 ( filter + indexOf 보다 더 많은 코드 ), 가장 빠르지도 않습니다 (아마 intersect_safe () 보다 상수 인자만큼 느릴 수도 있음 ).하지만 꽤 좋은 균형처럼 보입니다. 그것은에 매우 좋은 성능을 제공하고 사전 분류 입력을 필요로하지 않는 동안, 간단한 쪽.
한 번에 여러 개의 배열을 처리 할 수있는 또 다른 인덱스 접근 방식 :
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = 0;
index[v]++;
};
};
var retv = [];
for (var i in index) {
if (index[i] == arrLength) retv.push(i);
};
return retv;
};
문자열로 평가할 수있는 값에 대해서만 작동하며 다음과 같은 배열로 전달해야합니다.
intersect ([arr1, arr2, arr3...]);
...하지만 객체를 매개 변수 또는 교차 할 요소로 투명하게 수용합니다 (항상 공통 값의 배열을 반환합니다). 예 :
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
편집 : 방금 이것은 약간의 버그가 있음을 알았습니다.
즉 : 입력 배열 자체에는 반복이 포함될 수 없다고 생각했습니다 (제공된 예에서는 그렇지 않음).
그러나 입력 배열에 반복이 포함되면 잘못된 결과가 생성됩니다. 예 (아래 구현 사용) :
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
다행스럽게도 간단히 2 단계 색인을 추가하여 쉽게 해결할 수 있습니다. 그건:
변화:
if (index[v] === undefined) index[v] = 0;
index[v]++;
으로:
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
...과:
if (index[i] == arrLength) retv.push(i);
으로:
if (Object.keys(index[i]).length == arrLength) retv.push(i);
완전한 예 :
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
};
};
var retv = [];
for (var i in index) {
if (Object.keys(index[i]).length == arrLength) retv.push(i);
};
return retv;
};
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
for (j=0; j<B.length; j++) {
if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
result.push(A[i]);
}
}
}
return result;
}
데이터에 약간의 제한이 있으므로 선형 시간으로 할 수 있습니다 !
내용은 양의 정수 :는 "본 / 보이지 않는"부울에 값을 매핑 배열을 사용합니다.
function intersectIntegers(array1,array2) {
var seen=[],
result=[];
for (var i = 0; i < array1.length; i++) {
seen[array1[i]] = true;
}
for (var i = 0; i < array2.length; i++) {
if ( seen[array2[i]])
result.push(array2[i]);
}
return result;
}
객체에 대해서도 비슷한 기술이 있습니다 . 더미 키를 가져 와서 array1의 각 요소에 대해 "true"로 설정 한 다음 array2의 요소에서이 키를 찾으십시오. 완료되면 정리하십시오.
function intersectObjects(array1,array2) {
var result=[];
var key="tmpKey_intersect"
for (var i = 0; i < array1.length; i++) {
array1[i][key] = true;
}
for (var i = 0; i < array2.length; i++) {
if (array2[i][key])
result.push(array2[i]);
}
for (var i = 0; i < array1.length; i++) {
delete array1[i][key];
}
return result;
}
물론 키가 이전에 나타나지 않았는지 확인해야합니다. 그렇지 않으면 데이터가 손상 될 수 있습니다.
나는 나에게 가장 잘 맞는 것에 공헌 할 것이다.
if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {
var r = [], o = {}, l = this.length, i, v;
for (i = 0; i < l; i++) {
o[this[i]] = true;
}
l = arr1.length;
for (i = 0; i < l; i++) {
v = arr1[i];
if (v in o) {
r.push(v);
}
}
return r;
};
}
IE 9.0, chrome, firefox, opera, "indexOf",
function intersection(a,b){
var rs = [], x = a.length;
while (x--) b.indexOf(a[x])!=-1 && rs.push(a[x]);
return rs.sort();
}
intersection([1,2,3], [2,3,4,5]);
//Result: [2,3]
이것은 아마도 list1.filter (n => list2.includes (n)) 외에 가장 간단한 것입니다.
var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']
var list2 = ['bread', 'cherry', 'ice cream', 'oats']
function check_common(list1, list2){
list3 = []
for (let i=0; i<list1.length; i++){
for (let j=0; j<list2.length; j++){
if (list1[i] === list2[j]){
list3.push(list1[i]);
}
}
}
return list3
}
check_common(list1, list2) // ["bread", "ice cream"]IE를 제외한 모든 브라우저에서 사용할 수 있습니다.
const intersection = array1.filter(element => array2.includes(element));
또는 IE의 경우 :
const intersection = array1.filter(element => array2.indexOf(element) !== -1);
'use strict'
// Example 1
function intersection(a1, a2) {
return a1.filter(x => a2.indexOf(x) > -1)
}
// Example 2 (prototype function)
Array.prototype.intersection = function(arr) {
return this.filter(x => arr.indexOf(x) > -1)
}
const a1 = [1, 2, 3]
const a2 = [2, 3, 4, 5]
console.log(intersection(a1, a2))
console.log(a1.intersection(a2))ES2015를 통한 기능적 접근
기능적 접근 방식은 부작용없이 순수한 기능 만 사용하는 것을 고려해야하며, 각 기능은 단일 작업에만 관련됩니다.
이러한 제한은 관련된 기능의 구성 성과 재사용 성을 향상시킵니다.
// small, reusable auxiliary functions
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run it
console.log( intersect(xs) (ys) );Set조회 유형이 유리한 기본 유형이 사용됩니다.
중복 방지
분명히 첫 번째 항목에서 반복적으로 발생하는 항목 Array은 유지되고 두 번째 항목 Array은 중복 제거됩니다. 원하는 동작 일 수도 있고 아닐 수도 있습니다. 고유 한 결과가 필요한 경우 dedupe첫 번째 인수 에만 적용 하십시오.
// auxiliary functions
const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// de-duplication
const dedupe = comp(afrom) (createSet);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// unique result
console.log( intersect(dedupe(xs)) (ys) );Arrays 의 교집합 계산
당신의 임의의 수의 교차점 계산하려면 ArrayS를 단지 구성 intersect으로 foldl. 다음은 편리한 기능입니다.
// auxiliary functions
const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// intersection of an arbitrarily number of Arrays
const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];
// run
console.log( intersectn(xs, ys, zs) );간단하게하기 위해 :
// Usage
const intersection = allLists
.reduce(intersect, allValues)
.reduce(removeDuplicates, []);
// Implementation
const intersect = (intersection, list) =>
intersection.filter(item =>
list.some(x => x === item));
const removeDuplicates = (uniques, item) =>
uniques.includes(item) ? uniques : uniques.concat(item);
// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];
const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];
// Example Usage
const intersection = allGroups
.reduce(intersect, allPeople)
.reduce(removeDuplicates, []);
intersection; // [jill]
혜택:
- 간단한 흙
- 데이터 중심
- 임의의 수의 목록에 작동
- 임의의 길이의 목록에서 작동
- 임의의 유형의 값에 작동
- 임의의 정렬 순서로 작동
- 모양 유지 (어떤 배열에서든 첫 번째 출현 순서)
- 가능한 경우 일찍 나가다
- 메모리 안전, 기능 / 배열 프로토 타입을 통한 탬 퍼링 부족
단점 :
- 더 높은 메모리 사용량
- 더 높은 CPU 사용량
- 감소에 대한 이해가 필요하다
- 데이터 흐름에 대한 이해가 필요합니다
이것을 3D 엔진 또는 커널 작업에 사용하고 싶지 않지만 이벤트 기반 앱에서 실행하는 데 문제가 있으면 디자인에 더 큰 문제가 있습니다.
.reduce지도를 만들고 .filter교차로를 찾습니다. delete내에서 .filter두 번째 배열을 고유 한 세트처럼 취급 할 수 있습니다.
function intersection (a, b) {
var seen = a.reduce(function (h, k) {
h[k] = true;
return h;
}, {});
return b.filter(function (k) {
var exists = seen[k];
delete seen[k];
return exists;
});
}
이 접근법은 추론하기가 매우 쉽습니다. 일정한 시간에 수행됩니다.
교차하는 여러 배열을 처리 해야하는 경우 :
const intersect = (a, b, ...rest) => {
if (rest.length === 0) return [...new Set(a)].filter(x => new Set(b).has(x));
return intersect(a, intersect(b, ...rest));
};
console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) // [1,2]ES6 스타일의 간단한 방법.
const intersection = (a, b) => {
const s = new Set(b);
return a.filter(x => s.has(x));
};
예:
intersection([1, 2, 3], [4, 3, 2]); // [2, 3]
underscore.js 구현 은 다음과 같습니다 .
_.intersection = function(array) {
if (array == null) return [];
var result = [];
var argsLength = arguments.length;
for (var i = 0, length = array.length; i < length; i++) {
var item = array[i];
if (_.contains(result, item)) continue;
for (var j = 1; j < argsLength; j++) {
if (!_.contains(arguments[j], item)) break;
}
if (j === argsLength) result.push(item);
}
return result;
};
출처 : http://underscorejs.org/docs/underscore.html#section-62
function getIntersection(arr1, arr2){
var result = [];
arr1.forEach(function(elem){
arr2.forEach(function(elem2){
if(elem === elem2){
result.push(elem);
}
});
});
return result;
}
getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]
indexOf를 사용하는 대신 Array.protype.includes 를 사용할 수도 있습니다 .
function intersection(arr1, arr2) {
return arr1.filter((ele => {
return arr2.includes(ele);
}));
}
console.log(intersection([1,2,3], [2,3,4,5]));두 번째 배열이 항상 집합 으로 처리되는 경우 두 번째 배열에 대한 함수 내에 중간 변수를 선언 할 필요가 없습니다 .
다음 솔루션은 두 배열 모두에서 발생하는 고유 한 값의 배열을 반환합니다.
const intersection = (a, b) => {
b = new Set(b); // recycling variable
return [...new Set(a)].filter(e => b.has(e));
};
console.log(intersection([1, 2, 3, 1, 1], [1, 2, 4])); // Array [ 1, 2 ]
참고 URL : https://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript
반응형
'Programing' 카테고리의 다른 글
| jQuery 팁과 요령 (0) | 2020.02.12 |
|---|---|
| Visual Studio Code의 사이드 바에서 특정 파일을 숨기려면 어떻게합니까? (0) | 2020.02.12 |
| 쉼표로 구분 된 문자열을 ArrayList로 변환하는 방법? (0) | 2020.02.12 |
| 모든 줄을 클립 보드에 복사 (0) | 2020.02.12 |
| 언제 빌더 패턴을 사용 하시겠습니까? (0) | 2020.02.12 |