4

I found this code in vue.js. But what is the advantage between writing a template repeat using snippet-1 over snippet-2.

Snippet - 1 - Source

const repeat = (str, n) => {
    let res = ''
    while (n) {
      if (n % 2 === 1) res += str
      if (n > 1) str += str
      n >>= 1
    }
    return res
  }

Snippet - 2

const repeat = (str, n) => {
  let res = ''
  while (n--) {
    res += str;
  }
  return res
}
skirtle
  • 27,868
  • 4
  • 42
  • 57
Rajkeshwar Prasad
  • 869
  • 8
  • 11
  • 1
    readability is more important than nanoseconds - and the difference would be nanoseconds – Jaromanda X Aug 22 '19 at 09:19
  • The first snippet is using a standard algorithm. A common use for this algorithm is efficient exponentiation. e.g. See https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Computation_by_powers_of_2. The more general problem is known as an [addition chain](https://en.wikipedia.org/wiki/Addition_chain), a name which comes from precisely this type of use case. – skirtle Aug 22 '19 at 10:18

3 Answers3

4

It's the number of iterations that differ.

In the second snippet you have n iterations. But in the first snippet you have roughly log n iterations. Which means the complexity of the function goes from O(n) down to O(log n) which for huge n might matter.

How does it work? Here as a starter the logic summarized in an oversimplified way: If we half our iterations, we can double what we add to the result.

So >> 1 works kind of like integer division by 2. Integer divisions means for 5 / 2 we get 2 as a result. But so that means we are missing out on iterations!?

On every odd number we add the current string before doubling it to the result, so we kinda save that iteration's sum (the current str) in our result before continuing. So knowing our iterations are save we iterate down by kind off halving our remaining iterations each step while doubling what we soon add to the result.

By this duplication we skip a lot of iterations, which is the key to the lowered complexity.

For n = 5:

1 'str: ' 'kk' 'res: ' 'k'
2 'str: ' 'kkkk' 'res: ' 'k'
3 'str: ' 'kkkk' 'res: ' 'kkkkk'

For n = 10:

1 'str: ' 'kk' 'res: ' ''
2 'str: ' 'kkkk' 'res: ' 'kk'
3 'str: ' 'kkkkkkkk' 'res: ' 'kk'
4 'str: ' 'kkkkkkkk' 'res: ' 'kkkkkkkkkk'

For n = 11

1 'str: ' 'kk' 'res: ' 'k'
2 'str: ' 'kkkk' 'res: ' 'kkk'
3 'str: ' 'kkkkkkkk' 'res: ' 'kkk'
4 'str: ' 'kkkkkkkk' 'res: ' 'kkkkkkkkkkk'
claasic
  • 1,050
  • 6
  • 14
1

String concatenation in Javascript has historically created a lot of discussion and many approaches have been tried over the years (flat concat, array of strings into join, etc).

The main difference between the two approaches is performance — you can read a more indepth explanation of the algorithm itself in Assoron's answer, but the key consideration is that Vue is a library and as such, internal readability doesn't always champion over performance.

Looking at how the method is actually used, we can see that it's further wrapped in a loop:

tree.map((vm, i) => `${
    i === 0 ? '---> ' : repeat(' ', 5 + i * 2)
}...`

Meaning any performance difference would be further amplified.

Given that the performance difference is considerable at high iteration counts, it seems justified to pick performance over readability in this regard:

Sample performance result

Etheryte
  • 24,589
  • 11
  • 71
  • 116
0

it really will be faster

can see here

const takeTime = (f,...arg) => {
  const st = Date.now()
  const result = f(...arg)
  const et = Date.now()
  return {time: et - st, result}
}

console.log(takeTime(repeat1.bind(null,"string",1000000)))
console.log(takeTime(repeat2.bind(null,"string",1000000)))

I have in chrome 76 a difference of 100 milliseconds in this example

Thanks you!

Сергей Каракулов
  • 16
  • 3