On the small 13 element array your implementation appears to be fairly performant, but since you request a "faster" implementation I took a stab at one myself.
Implementation
In this implementation I wanted to remove the multiple loops and use a data structure that lent itself to faster lookups, so I used plain javascript objects as maps. I also defined each array function callback outside where it'd be used to only instantiate a single copy.
function findDupsMiss2(arr) {
const processedNumbers = {};
const duplicates = {};
const noDuplicates = {};
const checkDupOrNot = (el, i) => {
if (processedNumbers[el]) {
duplicates[el] = el;
delete noDuplicates[el];
} else {
noDuplicates[el] = el;
}
processedNumbers[el] = el;
};
arr.forEach(checkDupOrNot);
const missedReduceFn = (missed, el, i, arr) =>
el + 1 !== arr[i + 1] ? el : missed;
const missed = [
...Array(
processedNumbers[Object.values(processedNumbers).length - 1]
).keys()
].reduce(missedReduceFn, null);
return [missed, Object.values(duplicates)];
}
Testing
This is the function I defined to measure how performant a function is:
const measurePerf = (fn, data, runs = 1000000) =>
[...Array(runs).keys()]
.map(() => {
const start = performance.now();
fn(data);
const end = performance.now();
return end - start;
})
.reduce((total, current) => total + current) / runs;
This takes a function and measures how long it takes to execute, sums the total time then divides by the # of runs to get an average execution time.
Used as such
measurePerf(findDupsMiss, data); // uses default 1 million iterations
measurePerf(findDupsMiss, data, 1000);
Initial Results
Using the default 1-million iteration performance measure
findDupsMiss1
[7, Array[4]]
0: 7
1: Array[4]
0: 2
1: 3
2: 5
3: 9
0.0021040050006413367
findDupsMiss2
[7, Array[4]]
0: 7
1: Array[4]
0: 2
1: 3
2: 5
3: 9
0.0023690749967063313
At first this may seem like your code is already faster (or my implementation is slower), but this isn't the entire story.
If we analyze the Big-O complexity of your implementation we find it is O(n^2). Of the outer loops (3x O(n) forEach loops and 2x O(nLog_n) sorts) each of the forEach loops has an additional O(n) search loop to find either an index or if an element is already included, bumping the Big-O to O(n^2).
The other implementation has also 4x loops (1x forEach, 1x array spread, 1x array reduce, 1x object.values), but has no inner loops, each loop uses an O(1) lookup in a map, so has an O(n) complexity.
But where is the sort?
When using an object as a map with number-like keys, they are inserted in numerical order, so we get "sorting" for free. (in reality there is probably some minimal search though).
Further Results & Extended Examination
What does this Big-O O(n^2) vs O(n) mean?
This has to do with how much work there is to do based upon input size. When an algorithm's Big-O complexity is O(n) then when the input size doubles the output should roughly double, i.e. something like 2n (hand wavey), whereas when an algorithm's Big-O complexity is O(n^2) then the output size something more like 4n.
Here's a rough table of output. Because of performance I had to drop the test performance iterations to 100 (versus10^6), but figured 100 runs is still enough to gather enough data for decent comparisons.
TBH the average is less relevant here as this table is more to illustrate the ratio between the two algorithms, with a secondary comparison in parenthesis to highlight the ratio of output from the previous iteration
const measurePerf = (fn, data, runs = 1000000) =>
[...Array(runs).keys()]
.map(() => {
const start = performance.now();
fn(data);
const end = performance.now();
return end - start;
})
.reduce((total, current) => total + current) /runs;
function findDupsMiss1(arr) {
// your code here
var noDuplicates = [];
var missedNum;
var duplicates = [];
var sortedDuplicates = [];
arr.forEach((el, i) => {
if (noDuplicates.includes(el) == false) {
noDuplicates.push(el);
}
});
var sortedArr = noDuplicates.sort((a, b) => a - b);
for (var i = 0; i < sortedArr.length - 1; i++) {
if (sortedArr[i] + 1 !== sortedArr[i + 1]) {
missedNum = sortedArr[i] + 1;
}
}
arr.forEach(el => {
if (arr.indexOf(el) != arr.lastIndexOf(el)) {
duplicates.push(el);
}
});
duplicates.forEach(el => {
if (sortedDuplicates.includes(el) == false) {
sortedDuplicates.push(el);
}
});
var lastdup = sortedDuplicates.sort((a, b) => a - b);
return [missedNum, lastdup];
}
function findDupsMiss2(arr) {
const processedNumbers = {};
const duplicates = {};
const noDuplicates = {};
const checkDupOrNot = (el, i) => {
if (processedNumbers[el]) {
duplicates[el] = el;
delete noDuplicates[el];
} else {
noDuplicates[el] = el;
}
processedNumbers[el] = el;
};
arr.forEach(checkDupOrNot);
const missedReduceFn = (missed, el, i, arr) =>
el + 1 !== arr[i + 1] ? el : missed;
const missed = [
...Array(
processedNumbers[Object.values(processedNumbers).length - 1]
).keys()
].reduce(missedReduceFn, null);
return [missed, Object.values(duplicates)];
}
const data = [10, 9, 8, 9, 6, 1, 2, 4, 3, 2, 5, 5, 3];
const perf1 = measurePerf(findDupsMiss1, data);
console.log(findDupsMiss1(data), perf1);
const perf2 = measurePerf(findDupsMiss2, data);
console.log(findDupsMiss2(data), perf2);
const processIterations = async () => {
const results = [];
// # elements 1, 2, 4, 8, 16, 32, 64, ..., 262144, 524288
for (let i = 0; i < 20; i++) {
const dataLength = 1 << i;
const randData = [...Array(dataLength).keys()].map(() =>
Math.floor(Math.random)
);
const [t1, t2] = await Promise.all([
// For your sanity, start skipping findDupsMiss1 here at 11.
// Maybe don't go more than 15 unless you like creating space heaters.
i < 11 ? measurePerf(findDupsMiss1, randData, 100) : "skipped",
measurePerf(findDupsMiss2, randData, 100)
]);
results.push({
iteration: i,
dataLength,
t1: Number.isFinite(t1) ? Number(t1).toFixed(3) : t1,
t2: Number.isFinite(t2) ? Number(t2).toFixed(3) : t2
});
}
return results;
};
processIterations().then(results => {
console.log(`\t# Elements\tt1\tt2\tt2:t1 ratio`);
results.forEach(({ iteration, dataLength, t1, t2 }, i, arr) => {
const prev = arr[i - 1] || {};
const t2t1Ratio = Number(t2 / t1).toFixed(2);
const t1Ratio = Number(t1 / prev.t1).toFixed(1);
const t2Ratio = Number(t2 / prev.t2).toFixed(1);
console.log(
`${iteration}\t${dataLength}\t${t1}(${t1Ratio})\t${t2}(${t2Ratio})\t${t2t1Ratio}`
);
});
});
# Elements t1 avg t2 avg t2:t1 ratio
0 1 0.002(NaN) 0.003(NaN) 1.50
1 2 0.002(1.0) 0.004(1.3) 2.00
2 4 0.003(1.5) 0.005(1.3) 1.67
3 8 0.006(2.0) 0.006(1.2) 1.00
4 16 0.005(0.8) 0.012(2.0) 2.40
5 32 0.011(2.2) 0.016(1.3) 1.45
6 64 0.031(2.8) 0.029(1.8) 0.94
7 128 0.084(2.7) 0.048(1.7) 0.57
8 256 0.270(3.2) 0.094(2.0) 0.35
9 512 1.032(3.8) 0.186(2.0) 0.18
10 1024 4.696(4.6) 0.372(2.0) 0.08
11 2048 16.303(3.5) 0.749(2.0) 0.05
12 4096 67.092(4.1) 1.492(2.0) 0.02
13 8192 266.986(4.0) 3.018(2.0) 0.01
14 16384 1081.774(4.1) 6.785(2.2) 0.01
15 32768 skipped(NaN) 12.298(1.8) NaN
16 65536 skipped(NaN) 25.941(2.1) NaN
17 131072 skipped(NaN) 49.775(1.9) NaN
18 262144 skipped(NaN) 99.556(2.0) NaN
19 524288 skipped(NaN) 195.841(2.0) NaN
Notes:
- Average time is in milliseconds
- Item in
() is the ratio to the previous time (i.e. line above)
- Each iteration 100 runs for performance measuring
- Stopped measuring algorithm 1 after 15 iterations, it's just too slow
Conclusion
As can be seen, the table confirms your algorithm, after a certain point, appears to settle into roughly a 4x output size based upon 2x input, where the other algorithm appears to settle around 2x, as expected. Also, a tipping point appears to consistently be around iteration #6 / 64 elements when algorithm #2 overtakes algorithm #1 and is more performant.
