Title might not make much sense, but how would you do something like:
a = [1, 2, 2, 3, 3, 3];
b = [1, 2, 3];
a.subtract(b);
I want this to return [2, 3, 3], and not [] like the other answers for a similar question would, which only keeps the items that are not in the other array at all instead of removing only how many are in the other array.
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();
return this.filter(function (a) {
var p = array.indexOf(a);
if (p === -1) {
return true;
}
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;
});
return this.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));
Set
Map, it was actually 13% slower than your plain object approach.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)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))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 this
Object.defineProperty(Array.prototype, 'subtract', {
configurable: true,
value: function subtract (array) {
return this.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
}, new Map()
)
)
},
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;
});
return this.filter(function (a) {
return !hash[a] || (hash[a]--, false);
});
}
Object.defineProperty(Array.prototype, 'patrickSubtract', {
configurable: true,
value: function subtract (array) {
return this.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
}, new Map()
)
)
},
writable: true
})
let a = [1, 2, 2, 3, 3, 3]
let b = [1, 2, 3]
let ninaStart = 0
let ninaStop = 0
let patrickStart = 0
let 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;
});
return this.filter(function (a) {
return !hash[a] || (hash[a]--, false);
});
}
Object.defineProperty(Array.prototype, 'patrickSubtract', {
configurable: true,
value: function subtract (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 = 0
let ninaStop = 0
let patrickStart = 0
let 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: function subtract (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))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.