Сложность методов сцепления в javascript - PullRequest
Новая
       4

Сложность методов сцепления в javascript

0 голосов
/ 18 января 2020

У меня есть проблема, чтобы определить сложность моего алгоритма, потому что он использует функции ES6 и, конечно, это цепочечные методы. Я уже знаю некоторые основные сложности этого метода, например, сложность Array.prototype.map равна O (n) . Но когда мы хотим определить сложность алгоритма, как мы управляем цепным методом?

Например, представьте, что у нас есть функция, которая возвращает для массива сумму его положительных чисел 

let sumPositive = arr => arr.filter(i => i > 0).reduce((a, b) => a + b, 0);

console.log(sumPositive([1, 2, 3, -4])); // 6
console.log(sumPositive([1, 2, 3, 4])); // 10

Следовательно, какова сложность этой функции ?

Другим примером является этот алгоритм, который для данной строки возвращает количество каждого символа в строке 

let charCount = str =>  str.split('').map(
  (c,_,str) => str.filter(i => i===c)
  ).reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

console.log(charCount("hi")); // {"h": 1, "i": 1}

console.log(charCount("hello to you")); // {"h": 1, "e": 1, "l": 2, "o": 3, " ": 2, "t": 1, "y": 1, "u": 1}

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

Так что любой общий метод определения сложности такого алгоритма приветствуется.

Примечание : Вся сложность в этом вопросе - сложность времени, а не пространства

Спасибо

Ответы [ 2 ]

2 голосов
/ 18 января 2020

Методы цепочки на самом деле просто для удобства. map() или filter() возвращает массив. Теперь вы можете сначала поместить имя в массив, например let result = arr.map(...), а затем выполнить другие действия с этим result массивом, или , которые вы можете напрямую сделать с массивом, возвращаемым map() (или filter()), как map().filter().<more chaining if you want>.

Итак, это эквивалентно последовательному выполнению. Рассмотрим этот пример: 

let sumPositive = arr => arr.filter(i => i > 0)
                            .reduce((a, b) => a + b, 0);

let arr = [1, 2, 3, -4];

let filteredArray = arr.filter(i => i > 0); // O(n)
let reducedResult = filteredArray.reduce((a, b) => a + b, 0); // O(n)

console.log(sumPositive(arr)); // 6
console.log(reducedResult) // 6

Теперь вы видите, что filter() принимает O(n), а затем reduce() принимает O(n), поэтому вы получаете O(n) + O(n) ==> O(n) в качестве окончательного уровня сложности.

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

1 голос
/ 18 января 2020

@ Аджай Дабас ответил на ваш вопрос; Я отвечаю на ваш вопрос в комментариях:

Итак, не могли бы вы дать мне пример того, что я могу сделать для улучшения кода, или некоторые полезные ссылки

Ваш первый Пример не станет проще, но вы можете уменьшить временную сложность вашего второго алгоритма: 

let charCount = str =>  str.split('')
  .map((c,_,str) => str.filter(i => i===c))
  .reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

Вы можете сделать это, не используя метод filter(). Нет необходимости делать это, если вы поддерживаете индекс всех ключей и их текущий счет ... и вы уже делаете это с reduce(): 

    let charCount = str => 
        return str.split('').reduce(
            (acc, nextChar) => {
                return {
                    ...acc,
                    [nextChar]: (acc[nextChar] || 0) + 1
                };
            },
            Object.create(null)
        );
    };

Это должно быть O(n) - Мы повторяем массив только дважды. Обратите внимание, что нам не нужно filter() результаты, потому что все, что нам нужно сделать, это взять существующее количество для этого символа в аккумуляторе и увеличить его на единицу.

Использование Object.create(null) - это создание новый объект с null прототипом - это означает, что нам не нужно использовать hasOwnProperty().

. Следует иметь в виду, что только то, что что-то является O(n^2), не означает, что существует проблема с производительностью , Обозначение Big O просто описывает поведение некоторого кода при увеличении входных данных. Оптимизируйте код только тогда, когда вы знаете, что это проблема.

...