Nodejs - Subtract Array From Array, Not Removing All Duplicates
Solution 1:
You could create a prototype for Array and filter the array by checking and eliminating the found element.
Array.prototype.subtract = function (array) {
array = array.slice();
returnthis.filter(function (a) {
var p = array.indexOf(a);
if (p === -1) {
returntrue;
}
array.splice(p, 1);
});
}
var a = [1, 2, 2, 3, 3, 3],
b = [1, 2, 3];
console.log(a.subtract(b));Faster version with a hash table:
Array.prototype.subtract = function (array) {
var hash = Object.create(null);
array.forEach(function (a) {
hash[a] = (hash[a] || 0) + 1;
});
returnthis.filter(function (a) {
return !hash[a] || (hash[a]--, false);
});
}
var a = [1, 2, 2, 3, 3, 3],
b = [1, 2, 3];
console.log(a.subtract(b));Solution 2:
You can use filter() and indexOf() to check if element exists in other array and if it does delete it using splice()
var a = [1, 2, 2, 3, 3, 3];
var b = [1, 2, 3];
var result = a.filter(function(e) {
let i = b.indexOf(e)
return i == -1 ? true : (b.splice(i, 1), false)
})
console.log(result)Solution 3:
Here's a way you can do this: loop through the array b and check if it exists in the array a. If so, insert a undefined at the its index. Return the a array filtered to remove all undefined elements.
EDIT: actually no need for the filter use splice() has the others did.
let a = [1, 2, 2, 3, 3, 3];
let b = [1, 2, 3];
let sub = function(a, b) {
for (i in b) {
let index = a.indexOf(b[i]);
if (index != -1) {
a.splice([index],1)
}
}
return a
}
console.log(sub(a, b))Solution 4:
The answers here that suggest the use of indexOf() to check for existence are inefficient O(n^2) runtime. A more efficient approach would be to use a Map and check for existence with has(), bringing the runtime down to O(n):
// see the bottom of the answer for a more efficient implementation than thisObject.defineProperty(Array.prototype, 'subtract', {
configurable: true,
value: functionsubtract (array) {
returnthis.filter(
function (element) {
const count = this.get(element)
if (count > 0) {
this.set(element, count - 1)
}
return count === 0
}, array.reduce(
(map, element) => {
if (map.has(element)) {
map.set(element, map.get(element) + 1)
} else {
map.set(element, 1)
}
return map
}, newMap()
)
)
},
writable: true
})
let a = [1, 2, 2, 3, 3, 3]
let b = [1, 2, 3]
console.log(a.subtract(b))Here's a testbench to show the efficiency of this solution compared to @Nina's answer:
Array.prototype.ninaSubtract = function (array) {
var hash = Object.create(null);
array.forEach(function (a) {
hash[a] = (hash[a] || 0) + 1;
});
returnthis.filter(function (a) {
return !hash[a] || (hash[a]--, false);
});
}
Object.defineProperty(Array.prototype, 'patrickSubtract', {
configurable: true,
value: functionsubtract (array) {
returnthis.filter(
function (element) {
const count = this.get(element)
if (count > 0) {
this.set(element, count - 1)
}
return count === 0
}, array.reduce(
(map, element) => {
if (map.has(element)) {
map.set(element, map.get(element) + 1)
} else {
map.set(element, 1)
}
return map
}, newMap()
)
)
},
writable: true
})
let a = [1, 2, 2, 3, 3, 3]
let b = [1, 2, 3]
let ninaStart = 0let ninaStop = 0let patrickStart = 0let patrickStop = 0
ninaStart = performance.now()
for (let i = 100000; i > 0; i--) {
a.ninaSubtract(b)
}
ninaStop = performance.now()
patrickStart = performance.now()
for (let i = 100000; i > 0; i--) {
a.patrickSubtract(b)
}
patrickStop = performance.now()
console.log('Nina time: ', ninaStop - ninaStart, 'ms')
console.log('Patrick time: ', patrickStop - patrickStart, 'ms')Running it several times on my laptop using Chrome v60 indicates that Nina's updated answer using a plain object is approximately 13% faster than my answer.
Let's try to beat that by improving upon her answer:
Array.prototype.ninaSubtract = function (array) {
var hash = Object.create(null);
array.forEach(function (a) {
hash[a] = (hash[a] || 0) + 1;
});
returnthis.filter(function (a) {
return !hash[a] || (hash[a]--, false);
});
}
Object.defineProperty(Array.prototype, 'patrickSubtract', {
configurable: true,
value: functionsubtract (array) {
const lookup = Object.create(null)
const output = []
for (let index = 0; index < array.length; index++) {
const element = array[index]
lookup[element] = element in lookup ? lookup[element] + 1 : 1
}
for (let index = 0; index < this.length; index++) {
const element = this[index]
if (!(element in lookup) || lookup[element]-- <= 0) {
output.push(element)
}
}
return output
},
writable: true
})
let a = [1, 2, 2, 3, 3, 3]
let b = [1, 2, 3]
let ninaStart = 0let ninaStop = 0let patrickStart = 0let patrickStop = 0
ninaStart = performance.now()
for (let i = 100000; i > 0; i--) {
a.ninaSubtract(b)
}
ninaStop = performance.now()
patrickStart = performance.now()
for (let i = 100000; i > 0; i--) {
a.patrickSubtract(b)
}
patrickStop = performance.now()
console.log('Nina time: ', ninaStop - ninaStart, 'ms')
console.log('Patrick time: ', patrickStop - patrickStart, 'ms')That is a lot more performant, though a bit less canonical since it avoids the use of reduce(), forEach() or filter() in order to reduce context switches from function calls. This solution executes in almost half the time of Nina's updated answer (about 43% faster):
Object.defineProperty(Array.prototype, 'subtract', {
configurable: true,
value: functionsubtract (array) {
const lookup = Object.create(null)
const output = []
for (let index = 0; index < array.length; index++) {
const element = array[index]
lookup[element] = element in lookup ? lookup[element] + 1 : 1
}
for (let index = 0; index < this.length; index++) {
const element = this[index]
if (!(element in lookup) || lookup[element]-- <= 0) {
output.push(element)
}
}
return output
},
writable: true
})
let a = [1, 2, 2, 3, 3, 3]
let b = [1, 2, 3]
console.log(a.subtract(b))Update
The reason for the discrepancy in performance before was because my previous algorithm using Set was not correct. If b were to contain non-unique elements, then the output would not have been correct.
Post a Comment for "Nodejs - Subtract Array From Array, Not Removing All Duplicates"