Как ускорить функцию?

Question

[Quintis]

Есть рабочая функция для задачки с codewars - https://www.codewars.com/kata/5672682212c8ecf83e000050

function dblLinear(n) {
  // your code
  let uArray = [1, 3, 4];

  let currentPosition = 1;

 while (currentPosition <= n) {
    let x = uArray[currentPosition];
    let y = 2 * x + 1;
    let z = 3 * x + 1;
    uArray.push(y, z);
   uArray = [...new Set(uArray),y,z]
  uArray = uArray.sort((a, b) => a - b);
   currentPosition++
 }
return uArray[n]
}

Работает нормально но на тестах выбивает ошибка по ограничению времени -

Execution Timed Out (12000 ms)

Как ее ускорить ?

Comments

[Александр]

Если цель не +1 к выполненному, а разобраться - вот.

[Quintis]

Александр, спасибо

[Tim]

https://github.com/tuobaye0711/codewars/blob/maste...

Answer 1

[Василий Банников]

Придумать более оптимальный алгоритм.

Например тут точно можно избавиться от:
1. Set
2. Реаллокации массива
3. Сортировки массива
4. Лишних вычислений
Как-то так например

const seq = [1];
let upper = 0;
let lower = 0;
const dblLinear = n => {
    while (n >= seq.length) {
        const y = seq[lower] * 2 + 1;
        const z = seq[upper] * 3 + 1;
        if (y < z) {
            seq.push(y);
            lower += 1;
        }
        else {
            seq.push(z);
            upper += 1;
        }
    }
    return seq[n];
}

Ещё можно оптимизировать, если хранить не всю последовательность, а только то, что нужно для вычисления следующих чисел.

Comments

[Quintis]

Ещё мне кажется, что можно вывести какую-нибудь формулу для вычисления f(n) и не использовать цикл

То есть использовать рекурсию ?

[Василий Банников]

Quintis, Нет. Обычную неитеративную формулу. Но я не уверен на счёт этого.
Добавил код, который может работать.

[Quintis]

Василий Банников, а как сделать проверку на уникальные значения и отсортировать ?

[Василий Банников]

Quintis, алгоритм такой, что на каждом шаге мы получаем массив из уникальный возрастающих чисел.
По тому сортировать не нужно.
А нет. Я просчитался. Извиняюсь

[Василий Банников]

Quintis, Короче нашёл интересное свойство - можно эту последовательность записать в два массива.

[Quintis]

Василий Банников, А где нашли? У вас какая то книга по алгоритмам ?

[Василий Банников]

Quintis, не, просто изучаю саму последовательность. Но есть книга "алгоритмы. Их построение и анализ"
В общем тут две вещи надо сделать:
1. Не пытаться посчитать всю последовательность, если в ней уже лежит искомое число
2. Вычислять новое число последовательности так, чтобы не нарушать инварианты:
- возрастающий порядок
- уникальность всех элементов

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