Optimization review
Q1
But I can see it looking ugly and not really optimized (code duplicating)
Ugly is somewhat subjective (2 spaced indents are ugly in my book), and sometimes unavoidable, as long as it is readable then looks don't matter.
Code duplication is not a code optimization problem, in fact it is often code duplication that creates the optimal performance. Duplication is a source code management / maintenance issue. Case in point 10th line the join string missing a space while the duplicated line 18 has the space. Duplication is a easy place to introduce a bug, it is a place where the brain will say "same" for what is just a little different
Duplication is simple to rectify using functions.
You have two identical blocks of code (lines 7-11 and 15-19). You can wrap those lines in a function and call the function rather than have the code inline. You may opt to pass the function the arguments or use closure to hold the variable and access them directly.
function collapseSequences(input){
function pushResult(acc){
const cs = acc.currSet;
acc.out.push(cs.length > 2 ?
`${cs.shift()}-${cs.pop()}` :
cs.join(',')
);
}
const output = input.reduce((acc, curr, i, arr) => {
if (curr - 1 === arr[i - 1] || i === 0) {
acc.currSet.push(curr);
} else {
pushResult(acc);
acc.currSet = [curr];
}
if (i === arr.length - 1) {
pushResult(acc);
}
return acc;
}, { out: [], currSet: [] }
);
return output.out.join(', ');
}
Q2
I would appreciate any suggestions on how to improve the code and make it look better and possibly work faster.
As a function
Always use a function to wrap any code. Code running in global scope is inherently slower due to how JS manages variables. The whole code should look more like
function collapseSequences(input) {
... the code
// return the result
return output.out.join(', ');
}
console.log(
collapseSequences([ 12, 15, 16, 17, 19, 21, 22 ])
);
Use strict mode
Adding the run-time directive "use strict"; to the first line of a function or first line of a script allows the execution environment to make some assumptions and take some shortcuts improving performance (also forces you to write better Javascript)
Iteration
Loops are faster than iterators
const acc = foo;
for(const x of values) { ... code }
// or
const acc = foo;
for(let i = 0; i <values.length; i ++){ const x = values[i]; ...code }
will always be faster than
values.reduce((acc, x)=>{ ...code }, foo );
Strings
Strings are quicker than arrays. A common pattern is to use arrays when a string result requires a separator.
// CPU benchmark 4.6 lower is faster
function test(values){
const res = [];
for(const x of values){
res.push(x * 10);
}
return res.join(", ");
}
In terms of memory use GC impact, and CPU use the following can do the same in ~70% the time and much less memory.
// CPU benchmark 3.8 lower is faster
function test(values){
var result = "";
var join = "";
for(const x of values){
result += join + (x * 10);
if (!join) { join = ", " }
}
return result;
}
- Growing a string is quicker than growing an array.
- A string uses less memory than an array.
Array.join requires an additional iteration of items to build the string.
If you can, use a string rather than an array.
Benchmarking
If you want to write fast code then it is well worth investing time to learn how to correctly benchmark JS .
Bench-marking is one of the most difficult JS coding skills to master.
Assuming code is faster based on time complexity is a common performance trap in JS . There is not always a 1 to 1 relation between bench-marked performance, and apparent time complexity. This is because complexity can be hidden in the native code.
JS performance is not always intuitive, nor can you assume that optimizations that worked yesterday still work today, or that slower code yesterday is still slower today. Browsers can update daily and updates do not always mean faster (New language features are particularly dynamic in terms of performance between updates)
Rewrite
Taking in the above performance points the function can be rewritten as
function collapseSequences(arr) {
var i, val;
var idx = 0; // Array index
var str = ""; // The result string
const len = arr.length; // This is for readability not performance
// The loop is terminated in its body to manage the seperator
while (true) {
i = 0;
str += (val = arr[idx++]);
// Look ahead for a sequence
while(idx + i < len && arr[idx + i] === val + i + 1 ) {
i++;
}
// Was here a sequence found ?
if (i > 1) { // add it to the string and skip over the sequence
str += "-" + arr[(idx += i) - 1];
}
if (idx === len ) { // All done then return result
return str;
}
str += ", "; // add the separator
}
}
Resulting in a 3 fold improved execution time.
Bench-marking details.
Tests results show mean execution time on same data sets
- 25,793µs ±1,853µs. Using strings
- 30,418µs ±1,346µs. Using arrays and array.join
- 79,534µs ±1,142µs. Your code
The test functions run on Win10 Firefox, run in strict mode.
//===============================================================
// Test 1 Using strings. 25,793µs ±1,853µs
function collapseSequences(arr){
var i, idx = 0, str = "", val, len = arr.length;
while (idx < len) {
i = 0;
str += (val = arr[idx++]);
while(idx + i < len && arr[idx + i] === val + i + 1 ) { i++ }
if (i > 1) { str += "-" + arr[(idx += i) - 1] }
if (idx === len ) { return str }
str += ", "
}
}
//===============================================================
// Test 2 using arrays and array.join. 30,418µs ±1,346µs.
function collapseSequences(arr){
var i, idx = 0, val, len = arr.length;
const res = [];
while (idx < len) {
i = 0;
val = arr[idx++];
while(idx + i < len && arr[idx + i] === val + i + 1 ) { i++ }
res.push(val + (i > 1 ? "-" + arr[(idx += i) - 1] : "") );
}
return res.join(", ")
}
//===============================================================
// Test 3 OP original. 79,534µs ±1,142µs.
function collapseSequences(input){
const output = input.reduce((acc, curr, i, arr) => {
if (curr - 1 === arr[i - 1] || i === 0) {
acc.currSet.push(curr);
} else {
if (acc.currSet.length > 2) {
acc.out.push(`${acc.currSet.shift()}-${acc.currSet.pop()}`);
} else {
acc.out.push(acc.currSet.join(','));
}
acc.currSet = [curr];
}
if (i === arr.length - 1) {
if (acc.currSet.length > 2) {
acc.out.push(`${acc.currSet.shift()}-${acc.currSet.pop()}`);
} else {
acc.out.push(acc.currSet.join(', '));
}
}
return acc;
}, {
out: [],
currSet: [],
})
return output.out.join(', ');
}
