Строчки, точки и JavaScript

На своих проектах мы часто сталкиваемся с простыми, но интересными задачами. Мы их складируем и даем джунам/стажерам для ускорения обучения. Одной из таких задач стала задача с размещением одной или более точек между букв внутри слова всеми возможными способами.

Например программа на вход получает 'abc'

> abc
['abc', 'a.bc', 'ab.c', 'a.b.c']

Ее можно решить несколькими способами, но разобрать я хочу 2 из них.

Вы могли заметить, что размещение точек очень напоминает бинарные числа

00
01
10
11

Это первый вариант решения к которому мы прибегнули, называем его `побитовой/бинарной маской`. Надеюсь это соответствующее название.

Вот код:

function generateStrings(string) {
  const total = Math.pow(2, string.length - 1);
  const arr = str.split("");
  const strings = new Array(total);
  for (let i = 1; i < total; i++) {
    let mapped = "";
    for (let index = 0; index < arr.length; index++) {
      mapped += arr[index];
      if (index < arr.length - 1) {
        mapped += ((i >> index) & 1) == 1 ? "." : "";
      }
    }
    strings[i] = mapped;
  }
return strings;

Второй вариант которым мы решили задачу — рекурсия, очень напоминает бинарное дерево.

function recursive(chars, string = "", skip = 0, strings = []) {
  if (chars.length - skip === 1) {
    const res = string + chars[skip];
    strings.push(res);
  } else {
    const char = chars[skip];
    const next = string + char;
    recursive(chars, next + ".", skip + 1, strings);
    recursive(chars, next, skip + 1, strings);
  }
  return strings;
}

После этого мы решили сравнить перформанс и потребление памяти. Результаты, скажу честно, оказались весьма неожиданными.

Время выполнения и потребление памяти

Все тесты мы проводили на строке из 20 символов «abcdeabcdeabcdeabcde»

Интернет наполнен обсуждениями того может ли быть рекурсия быстрее циклов и большинство придерживается мнения что нет, за исключением определенных частных случаев, которые зависят от реализованной бизнес логики и от языка, на котором это все написано.

А вот что мы получили:



Рекурсия лихо уделала циклы примерно в 6 раз и достаточно неочевидно почему так происходит. Наверное это как-то связано с оптимизацией рекурсий на мультикор (если у вас есть ответ или где почитать/ как проверить — напишите плиз).

Но самое интересное происходит с потреблением памяти:



Рекурсивный способ решения потребляет 55mb vs 301mb императивный и как видно на графике сборщик мусора срабатывает гораздо реже. И у нас нет ни малейшей догадки почему так происходит… Если можете обьяснить — гоу в комментарии.

Всем спасибо