Merge consecutive numbers in array into a range

Question

Input: I have sorted array of numbers [ 12, 15, 16, 17, 19, 21, 22 ]

Output: I need to merge all consecutive numbers into a dash-separated ranges like this "12, 15-17, 19, 21, 22"

I came up with such code (jsbin - https://jsbin.com/dusuvihiko/edit?js,console):

const input = [ 12, 15, 16, 17, 19, 21, 22 ];
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: [],
})
console.log(output.out.join(', '));

But I can see it looking ugly and not really optimized (code duplicating)

I would appreciate any suggestions on how to improve the code and make it look better and possibly work faster

• AJD: Not js coder myself, but just because inline functions exist doesn't mean they have to be used. The in-lining of a complex function makes it harder to read or understand what is happening.

Answer 1

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

1. 25,793μs ±1,853μs. Using strings
2. 30,418μs ±1,346μs. Using arrays and array.join
3. 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(', ');
}