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

Question

[Алексей Яковлев]

Написал решение задачи для 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...

Comments

[Сергей Соколов]

вроде неверный цикл с окном: должен быть до i < arr.length - k

[WbICHA]

Тебе надо не код оптимизировать, а алгоритм. Дам подсказку: цикла в цикле быть не должно.

[Сергей Соколов]

WbICHA, че-т не получилось без цикла-в-цикле: надо ж каждый раз понимать уникальность добавленного/удалённого значения.

[WbICHA]

Сергей Соколов, у меня получилось.)
Дам вторую подсказку: не надо каждый раз пересчитывать все значения в диапазоне.

[Сергей Соколов]

WbICHA, всякие объекты-словари или сеты под капотом всеиравно перебирают..

[WbICHA]

Сергей Соколов, в смысле объекты перебирают? В этом как бы и соль объектов же, что там не тупой перебор.

[Сергей Соколов]

WbICHA, решение с объектом в качестве хэш-мэпа у меня не прошло по производительности.

[WbICHA]

Сергей Соколов,

spoiler

function countContiguousDistinct(k, arr) {
  const numsCount = {};
  
  for(let i = 0; i < k - 1; i++) {
    const curr = arr[i];
    numsCount[curr] = (numsCount[curr] ?? 0) + 1;
  }
  
  const result = [];
  let count = Object.keys(numsCount).length;
  
  for(let start = 0, end = k - 1; end < arr.length; start++, end++) {
    const first = arr[start];
    const last = arr[end];
    
    numsCount[last] = (numsCount[last] ?? 0) + 1;
    
    if(numsCount[last] === 1) {
      count++;
    }
    
    result.push(count);
    
    numsCount[first]--;
    
    if(numsCount[first] === 0) {
      count--;
    }
  }
  
  return result;
}

Answer 1

[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;
}

Answer 2

[Сергей Соколов]

не нужно на каждой позиции составлять окно заново.

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

Далее на каждом шаге удаляется 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;
}