Вложенные массивы: разбор задачи с собеседования

Photo by Alex on Unsplash

Вопрос о вложенных массивах может поначалу показаться сложным. Но если как следует разобраться, всё станет легко и понятно. К тому же, знание особенностей вложенных массивов даёт возможность здорово оптимизировать код. После этой статьи вы сможете порадовать своих интервьюеров некоторыми идеями по этой теме, о которых они, может, и не догадывались!

В чём заключается задача о вложенных массивах?

Давайте разбираться.

На входе мы имеем целочисленный массив arr длинной n. Целые числа в массиве представляют собой перемешанные индексы. Составление исходного массива для задачи выглядит следующим образом:

function scrambleArray(arr) {
  const tmpArray = Array.from(arr);
  const scrambledArray = new Array(arr.length).fill(1);
  let index = 0;
  while (tmpArray.length) {
    const randomIndex = Math.floor(Math.random() * (tmpArray.length - 1));
    scrambledArray[index++] = tmpArray.splice(randomIndex, 1)[0];
  }
  return scrambledArray;
}

Для каждого элемента перемешанного массива необходимо посчитать последовательность по следующей логике:

s[k] = [arr[k], arr[arr[k]], arr[arr[arr[k]], ...]

Последовательность для каждого числа записывается ровно до тех пор, пока очередное число не совпадёт с уже обработанным элементом (повторяющееся число мы не включаем в массив). В конце нужно вернуть самую длинную последовательность в s.

Пример вложенного массива

Возьмём следующий массив: [6, 5, 7, 8, 0, 4, 3, 2, 1, 9].

Из этого массива создаются следующие последовательности:

  [3, 8, 1, 5, 4, 0, 6],
  [4, 0, 6, 3, 8, 1, 5],
  [2, 7],
  [1, 5, 4, 0, 6, 3, 8],
  [6, 3, 8, 1, 5, 4, 0],
  [0, 6, 3, 8, 1, 5, 4],
  [8, 1, 5, 4, 0, 6, 3],
  [7, 2],
  [5, 4, 0, 6, 3, 8, 1],
  [9]

Здесь можно легко увидеть, что наибольшая длина последовательности – 7 цифр.

Если вы никогда ранее не брались за подобные задачи, то советую вам попробовать прямо сейчас, потому что дальше будут спойлеры! Найти аналогичную задачу можно на  leetcode.

Но если вас больше интересует самая «сочная» часть, продолжайте читать!

Как решить задачу со вложенными массивами на собеседовании?

Решая такую задачу, вы, вероятно, будете действовать по следующей схеме:

  1. Создадите брутфорс-решение
  2. Оптимизируете его

Давайте и пойдём по этому пути.

Брутфорс-решение

Алгоритм довольно прост:

function getNestedArraysMaxLength(inputArray) {
	let maxLength = -Infinity;

	inputArray.forEach(value => {
		const seriesLength = findSeriesLength(inputArray, value);
		maxLength = Math.max(seriesLength, maxLength);
	});

	return maxLength;
}

Мы делаем в точности то, о чём нас просят. Для каждого элемента inputArray мы узнаём seriesLength и сохраняем наибольшую найденную длину. В результате мы возвращаем максимальную длину, что от нас и требовалось.

Теперь нам нужно реализовать функцию findSeriesLength:

function findSeriesLength(arr, nextValue) {
	const series = {[nextValue]: true};

	while (true) {
		nextValue = arr[nextValue];
		if (series[nextValue]) {
			return Object.keys(series).length;
		}
		series[nextValue] = true;
	}
}

Это более сложная часть алгоритма. Функция принимает на вход массив и следующее значение (первое значение в последовательности). Последовательность в любом случае имеет первый элемент, поэтому мы установим его для каждого вложенного массива. Затем мы заполняем последовательность, пока снова не дойдем до того же числа. Как только мы это сделаем, сможем вернуть длину вложенного массива.

Сложность нашего непродуманного, но рабочего брутфорс-решения составляет O(n2). В наихудшем случае мы бы прошлись по всем числам в исходном массиве, а потом, в ходе составления последовательностей, для каждого числа проходили бы по всем числам снова. Но обычно на собеседовании можно предложить решение получше.

Оптимизация по времени

Глядя на пример выше, мы можем выделить следующую закономерность:

Рисунок 1: Полученный паттерн. Первая серия чисел начинается с 3 и заканчивается на 6 (белые стрелочки). Следующая начинается с 6, потом идет 3 и так же доходит до 0, после которого всегда идет 6 (голубая стрелочка) и т.д.

Рисунок 1 иллюстрирует циклическую природу наших последовательностей. В данном случае последовательности – это просто периодически повторяющиеся наборы чисел. Это можно использовать для оптимизации алгоритма. Добавим массив memory, чтобы сохранить количество значений, которые мы уже обработали.

function getNestedArraysMaxLength(inputArray) {
	let maxLength = -Infinity;
	const memory = [];

	inputArray.forEach(value => {
		memory[value] = findSeriesLength(inputArray, value, memory);
		maxLength = Math.max(maxLength, memory[value]);
	});

	return maxLength;
}

function findSeriesLength(arr, nextValue, memory) {
	const series = {[nextValue]: true};

	while (true) {
		nextValue = arr[nextValue];
		if (memory[nextValue]) {
			return memory[nextValue];
		}

		if (series[nextValue]) {
			return Object.keys(series).length;
		}
		series[nextValue] = true;
	}
}

Перечислим все изменения:

  • В 3 строке объявляется массив memory.
  • В 6 строке счетчик заносится в массив memory, а не в переменную. Теперь мы используем это значение в строке 7 вместо переменной seriesLength.
  • Функция findSeriesLength теперь использует массив memory, который она получает в качестве входных данных, чтобы проверить, есть ли у нас уже счетчик для определенного значения (строки 18–20).

Давайте посмотрим на сложность («O» большое) этого решения. Мы по-прежнему просматриваем n значений в inputArray. Но каждую последовательность, показанную на рисунке 1, мы будем проходить только один раз.

Наша сложность теперь O(n) (линейная), потому что единственное место, где мы перебираем n элементов, – это основной цикл forEach. Наша пространственная сложность теперь O(n), потому что мы используем вспомогательный массив memory.

Сравнение

Изучим разницу между оптимизированным и исходным алгоритмами. Используем для этих целей сайт jsben.ch. Начнём наши замеры с n = 10 (да, этого немного, но пусть будет так).

Рисунок 2: результаты многократного запуска двух решений. Мы видим, что решение с использованием memory работает на 15% быстрее.

Рисунок 2 демонстрирует успешную оптимизацию (результат сравнительного анализа здесь). Но… мы же ожидали куда большего, правда? Ведь мы заметно уменьшили сложность алгоритма!

Возможна ли дополнительная оптимизация?

Есть несколько способов оптимизировать наш алгоритм.

Будет полезно пояснить для начинающих, что происходит, когда мы используем счётчик вместо series в функции findSeriesLength. Изменим функцию следующим образом:

function findSeriesLength(arr, nextValue) {
	const startingNumber = nextValue;
	let count = 1;

	while (true) {
		nextValue = arr[nextValue];

		if (startingNumber === nextValue) {
			return count;
		}
		count++;
	}
}

В этом коде, вместо создания последовательностей, что от нас и не требуется по заданию (нам нужно лишь вернуть длину), мы сохраняем первое число в переменной startingNumber и создаём счётчик.

Сравнительный анализ для этой функции представлен на рисунке 3 (и здесь).

Рисунок 3: результаты сравнения брутфорс-решения со счётчиком (верхний) с просто брутфорс-решением и оптимизированным алгоритмом (в середине). Из-за значительного сокращения сбора мусора первый алгоритм O(n*n) оказался даже эффективнее второго – O(n).

Что бы та же оптимизация сделала со сложностью алгоритма? Результаты на рисунке 4 вас удивят.

Рисунок 4: Результаты сравнения O(n) и O(n*n) с оптимизированной функцией findSeriesLength. Сюрприз: алгоритм O(n) выполняется медленнее брутфорс-алгоритма!

Что же здесь происходит? Может ли топорный алгоритм O(n2) выполняться быстрее, чем O(n)?

Сбор мусора (Garbage Collection) – основной фактор, определяющий производительность кода на JavaScript.

Если функция создаёт и уничтожает множество объектов/массивов, это дорого нам обойдётся: JS будет производить выделение памяти для них и сбор мусора. А это требует времени. При масштабировании вашего кода это будет занимать даже еще больше времени.

Вдобавок, как вы можете видеть, алгоритм O(n) не даёт нам ожидаемого преимущества, хотя теоретически он должен быть быстрее O(n2). Всё это из-за очень маленького n. Если увеличить его до 1000, картина будет совершенно иной. На рисунке 5 показаны результаты для n=1000.

Рисунок 5: Код тот же, но на этот раз длина исходного массива 1000. Здесь можно посмотреть демонстрацию.

Так что тут мы узнаём 2 вещи:

  1.  Уменьшение сложности алгоритма полезно только при больших n.
  2. Сбор мусора может стать основной слабостью вашего кода на JavaScript.

Оптимизация временной и пространственной сложности

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

Вместо создания нового массива memory мы можем просто установить маркер в нашем массиве:

function getNestedArraysMaxLength(inputArray) {
	let maxLength = -Infinity;

	inputArray.forEach((value, index) => {
		const seriesLength = findSeriesLength(inputArray, index);
		maxLength = Math.max(maxLength, seriesLength);
	});

	return maxLength;
}

function findSeriesLength(arr, nextIndex) {
	let count = 0;

	while (true) {

		let nextValue = arr[nextIndex];

		if (nextValue === null) {
			return count;
		}

		arr[nextIndex] = null;
		nextIndex = nextValue;

		count++;
	}
}

Заметьте, что мы убрали все упоминания memory. Хитрость в том, что мы присваиваем null (или какое-нибудь другое известное значение) всем обработанным переменным. И теперь каждый раз, когда мы встречаем null, мы знаем, что уже проверяли данный цикл, и нет смысла идти дальше.

Результаты на рисунке 6 выглядят довольно убедительно. Использование алгоритма со сложностью O(n) и затем оптимизация расхода памяти до O(1) также увеличивают производительность. И мы уже знаем причину этому: выделение памяти и сбор мусора.

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

Рисунок 6: Сравнение всех алгоритмов на данный момент с оптимизацией сложности алгоритма до O(n) и расходов памяти до O(1). Результаты тестов здесь

Чтобы подтвердить нашу гипотезу, мы можем легко избежать сборки мусора в решении с расходом памяти O(n). Меняем строчку:

const memory = [];

на

const memory = new Array(inputArray.length).fill(1);

Таким образом мы зарезервируем память перед выполнением функции, и, как следствие, сократим количество циклов сборки мусора и выделения памяти. Результат – на рисунке 7.

Рисунок 7: Результат оптимизации O(n): динамическое выделение памяти (внизу) требует куда больше времени, чем выделение памяти заранее (в середине). Коду с заранее выделенной памятью требуется примерно столько же времени, сколько коду, оптимизированному полностью. Программа здесь

Можно ли сделать что-нибудь ещё?

Конечно! Но это уже будет микро-оптимизациями, которые будут зависеть от вашего браузера или движка JS. Например, если мы заменим цикл forEach на for, то получим следующий результат:

Рисунок 8: результаты замены цикла forEach на for. Можно заметить небольшое увеличение производительности. Результат может меняться в зависимости от браузера и движка JS. Код тут

Заключение

Вложенные массивы – относительно простая задача на собеседовании. У нее довольно простое брутфорс-решение, которое легко оптимизировать. Вы можете либо сохранять результаты предыдущих вычислений, либо использовать некий флаг на самих данных.

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

В нашей задаче – обнаружении наибольших последовательностей – мы производили различные оптимизации: либо сохраняли счётчик, либо использовали заранее зарезервированный массив memory.

Я надеюсь, что теперь, если вам зададут данный вопрос на собеседовании, вы сможете удивить своего интервьюера глубоким пониманием проблемы и подробными объяснениями про выделение памяти, сбор мусора и О-нотацию.

Перевод статьи «Deep dive into an interview question: Array Nesting».

[customscript]techrocks_custom_after_post_html[/customscript]

[customscript]techrocks_custom_script[/customscript]

Оставьте комментарий

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

Прокрутить вверх