@aleshaykovlev
html, css, js, node, webpack, sass, react

Как улучшить производительность данного кода?

Написал решение задачи для codewars, но из-за производительности ругается. Подскажите, что убрать или поправить и желательно объяснить почему так быстрее

function countContiguousDistinct(k, arr) {
	const res = [];

	for (let i = 0; i < arr.length; i++) {
		const window = [];

		for (let j = i; j < k + i; j++) {
			const n = arr[j];
			window.push(n);
		}

		if (window.every(el => el !== undefined)) {
			const resNum = filt(window).length;
			if (resNum) res.push(resNum);
		}
	}

	function filt(arr) {
		function onlyUnique(value, index, self) {
			return self.indexOf(value) === index;
		}

		return arr.filter(onlyUnique);
	}

	return res;
}

const arr = [2, 4, 20, 6, 0, 30, 28];
const k = 4;

console.log(countContiguousDistinct(k, arr)); // [ 4, 4, 4, 4 ]


Если интересно, то вот задачка: https://www.codewars.com/kata/5945f0c207693bc53100...
  • Вопрос задан
  • 134 просмотра
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Дополню ответ Сергей Соколов.
В данном случае на входе целые числа, причём небольшие. Значит можно держать массив со счётчиками чисел внутри окна. При сдвиге окна счётчик числа, удаляемого слева, уменьшается на 1. Если он стал нулём, то количество уникальных уменьшается на 1. Счётчик числа, добавляемого справа, увеличивается на 1. Если счётчик был нулём, то количество уникальных увеличивается на 1.
spoiler
function countContiguousDistinct(k, arr) {
  const counts = [];
  let distinct = 0;
  const result = [];
  for (let i = 0; i < k; i += 1) {
    const val = arr[i];
    if (counts[val] === undefined) {
      counts[val] = 0;
      distinct += 1;
    }
    counts[val] += 1;
  }
  result.push(distinct);
  for (let i = k; i < arr.length; i += 1) {
    const lVal = arr[i - k];
    counts[lVal] -= 1;
    if (counts[lVal] === 0) {
      distinct -= 1;
    }
    const rVal = arr[i];
    if (counts[rVal] === undefined) {
      counts[rVal] = 0;
    }
    if (counts[rVal] === 0) {
      distinct += 1;
    }
    counts[rVal] += 1;
    result.push(distinct);
  }
  return result;
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
sergiks
@sergiks Куратор тега JavaScript
♬♬
не нужно на каждой позиции составлять окно заново.

Заполнили окно в самой левой позции. Посчитали его "кардинальность" (число уникальных).

Далее на каждом шаге удаляется 1 элемент слева и добавляется 1 элемент справа. Смотрим, изменилась ли кардинальность:
- удаляемый элемент ещё есть в оставшихся? Нет – значит мы уменьшили кардинальность на 1.
- то же с добавляемым: уже есть такой в середине окна? Нет – значит, увеличили кардинальность на 1.

Такое решение прокатило и по перформансу, хотя там есть вложенные мини-циклы для поиска удаляемого/добавляемого значений в остающемся огрызке. Наверняка, есть более элегантные решения.
spoiler
function countContiguousDistinct(k, arr) {
  let cardinality = 0;
  for (let i = 0; i < k; i++) {
    if (i === arr.indexOf(arr[i])) cardinality++;
  }
  const result = [cardinality];
  
  const isNotInWindow = (value, arr, start, finish) => {
    for (let j = start; j < finish; j++) {
      if (arr[j] === value) return false;
    }
    return true;
  }
  
  for (let i = 0; i < arr.length - k; i++) {
    const L = arr[i];
    const R = arr[i + k];
    if (L !== R) {
      if (isNotInWindow(L, arr, i + 1, i + k)) cardinality--;
      if (isNotInWindow(R, arr, i + 1, i + k)) cardinality++;
    }
    result.push(cardinality);
  }
  
  return result;
}
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы