Строчки, точки и 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»

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

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

image

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

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



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

Всем спасибо
Tags:
javascript, memory management

You can't comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author's username will be hidden by an alias.