Disclaimer: в этой статье будет очень много бредовых примеров и сверх очевидных утверждений. Если для вас предельно очевидно, что ... внутри .reduce даёт вам O(n^2), то можно сразу прыгать к разделу "Критика" или просто проигнорировать статью. Если же нет, милости прошу под cut.

Предисловие

Все мы знаем про стандартную конструкцию for (;;) которая чаще всего, в реальном коде, имеет примерно такой вид:

for (let idx = 0; idx < arr.length; ++ idx) {
  const item = arr[idx];
  // ...
}

Далеко не все из нас любят ей пользоваться (только давайте обойдёмся без холиваров на эту тему, статья не об этом), особенно в простых сценариях, т.к. когнитивная нагрузка довольно высока ― очень много малозначительных или даже ненужных деталей. Например в таком вот сценарии:

const result = [];
for (let idx = 0; idx < arr.length; ++ idx) {
  const item = arr[idx];  
  result.push(something(item));
}
return result;

Большинство из нас предпочтёт более компактную и наглядную версию:

return arr.map(something); 
// или
return arr.map(item => something(item)); 

note: 2-й вариант избавит вас от потенциальных проблем в будущем, когда something может внезапно обзавестись вторым аргументом. Если он будет числовым, то даже Typescript вас не убережёт от такой ошибки.

Но не будем отвлекаться. О чём собственно речь?

Всё чаще и чаще мы видим в живом коде такие методы как:

  • .forEach

  • .map

  • .reduce

  • и другие

В общем и в целом они имеют ту же bigO complexity, что и обыкновенные циклы. Т.е. до тех пор, пока речь не заходит об экономии на спичках, программист волен выбирать ту конструкцию, что ему ближе и понятнее.

Однако всё чаще и чаще вы можете видеть в обучающих статьях, в библиотечном коде, в примерах в документации код вида:

return source.reduce(
  (accumulator, item) => accumulator.concat(...something(item)), 
  []
);

или даже:

return Object
  .entries(object) 
  .reduce(
    (accumulator, value, key) => ({
      ...accumulator, 
      [key]: something(value)
    }), 
    {}
  );

Возможно многие из вас зададутся вопросом: а что собственно не так?

Ответ: вычислительная сложность. Вы наблюдаете разницу между O(n) и O(n^2) .

Давайте разбираться. Можно начать с ... -синтаксиса. Как эта штука работает внутри? Ответ: она просто итерирует всю коллекцию (будь то элементы массива или ключи-значения в объекте) с 1-го до последнего элемента. Т.е.:

const bArray = [...aArray, 42]

это примерно тоже самое, что и:

const bArray = [];
for (let idx = 0; idx < aArray.length; ++ idx)
  bArray.push(aArray[idx]);

Как видите, никакой магии. Просто синтаксический сахар. Тоже самое и с объектами. На лицо очевидная сложность O(n).

Но давайте вернёмся к нашему .reduce. Что такое .reduce? Довольно простая штука. Вот упрощённый полифил:

Array.prototype.reduce = function(callback, initialValue) {
  let result = initialValue;
  for (let idx = 0; idx < this.length; ++ idx)
    result = callback(result, this[idx], idx);
  return result;
}

Наблюдаем всё тот же O(n). Уточню почему - мы пробегаем ровно один раз по каждому элементу массива, которых у нас N.

Что же тогда у нас получается вот здесь:

return source.reduce(
  (accumulator, item) => accumulator.concat(...something(item)), 
  []
);

Чтобы это понять надо, ещё посмотреть, а что такое .concat. В документации вы найдёте, что он возвращает новый массив, который состоит из переданных в него массивов. По сути это поэлементное копирование всех элементов. Т.е. снова O(n).

Так чем же плох вышеприведённый код? Тем что на каждой итерации в .reduce происходит копирование всего массива accumulator. Проведём мысленный эксперимент. Заодно упростим пример (но проигнорируем существование .map, так как с ним такой проблемы не будет):

return source.reduce(
  (accumulator, item) => accumulator.concat(something(item)),    
  [] 
);

Допустим наш source.length === 3. Тогда получается, что .reduce сделает 3 итерации.

  • На 1-й итерации наш accumulator пуст, поэтому по сути мы просто создаём новый массив из одного элемента. // []

  • на 2-й итерации наш accumulator уже содержит один элемент. Мы вынуждены скопировать его в новый массив. // [1]

  • на 3-й итерации уже 2 лишних элемента. // [1, 2]

Похоже на то, что мы делаем лишнюю работу. Представьте что length === 1000. Тогда на последней итерации мы будем впустую копировать уже 999 элементов. Напоминает алгоритм маляра Шлемиля, не так ли?

Как нетрудно догадаться, чем больше length , тем больше лишней работы выполняет процессор. А это в свою очередь:

  • замедляет программу

  • т.к. Javascript однопоточный - препятствует работе пользователя с UI

  • тратит батарейку ноутбука или телефона на бесполезную работу

  • греет ваше устройство и заставляет работать кулер

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

Но что можно с этим поделать? Много чего. Самое главное - переиспользовать тот же самый массив\объект:

// вместо
(accumulator, item) => accumulator.concat(...something(item))
// вот так
(accumulator, item) => {
   accumulator.push(...something(item));
   return accumulator; // это ключевая строка
}
// вместо
(accumulator, value, key) => ({
  ...accumulator, 
  [key]: something(value)
}, 

// вот так
(accumulator, value, key) => {
  accumulator[key] = something(value);
  return accumulator;
}

Стало чуть менее нагляднее (возможно), но разительно быстрее. Или нет? Давайте разбираться.

Как я уже сказал выше, всё зависит от размера коллекции. Чем больше итераций, тем больше разница. Я провёл пару простых тестов в Chrome и Firefox:

Firefox
Chrome

При length=30 разница не очень убедительная (13 vs 3). При length=1000 уже становится особенно больно (2600 vs 30).

Критика

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

1. При малых N вы не заметите разницу

Что же, это valid point. Если N=3, то разница столь невелика, что едва ли вы хоть когда-нибудь столкнётесь с её последствиями. Правда ваши друзья из мира C++ перестанут с вами здороваться. Особенно в мире Javascript, который как известно скриптовый язык с динамической типизацией, и, поэтому, не предназначен для решения задач, которые требуют настоящей производительности. Что впрочем не мешает ему проникать даже в эти отрасли, вызывая потоки гнева

А что если у нас не 3 элемента, а скажем 30. На моих синтетических "наколеночных" тестах получилась разница в 4 раза. Если этот участок кода выполняется единожды, а не, скажем, в цикле, то вы, скорее всего, точно также не сможете ничего заметить. Ещё бы, ведь речь идёт о долях миллисекунды.

Есть ли тут подводные камни? На самом деле да. Я бы сказал, что тут возможны (как минимум) две проблемы.

  • Первая проблема: сегодня ваш код исполняется единожды. Завтра вы запускаете его для какого-нибудь большого списка. Скорее всего даже не заглянув внутрь (в больших проектах это может быть очень непросто). В итоге та изначально небольшая разница, может начать играть весомую роль. И моя практика показывает, что хочешь рассмешить бога, расскажи ему о своих планах мы слишком часто ошибаемся в своих суждениях относительно того, как наш код будет использоваться в будущем.

  • Вторая проблема: у вас ваш код запускается для 30 элементов. Okay. Но среди ваших пользователей есть 5% таких, у которых немного нестандартные потребности. И у них уже почему-то не 30, а 300. Кстати, возможно эти 5% пользователей делают 30% вашей выручки.

Приведу пример. На немецком сайте Ikea (надеюсь они это уже исправили) была проблема: при попытке купить больше 10-12 товаров корзина заказа начинала настолько люто тормозить, что почти любая операция с ней сводилась к 40 секундным задержкам. Т.е. до глупого забавная ситуация: человек хочет купить больше, т.е. отдать компании больше денег, но т.к. где-то внутри сокрыты алгоритмы маляра Шлемиля, он не может этого сделать. Полагаю разработчики ничего об этом не знали. И QA отдел тоже (если он у них есть). Не переоценивайте ваших посетителей, далеко не каждый будет готов ждать по 40 секунд на действие. Признаю, что пример экстремальный. Зато показательный.

Итого: в принципе всё верно. Для большинства ситуаций вы и правда не заметите разницы. Но стоит ли это того, чтобы экономить одну единственную строку? Ведь для того, чтобы избежать этой проблемы, не требуется менять алгоритм, не требуется превращать код в нечитаемый ад. Достаточно просто мутировать итерируемую коллекцию, а не создавать новую.

По сути всё сводится к: каковы мои трудозатраты и каков мой результат. Трудозатраты - одна строка. Результат - гарантия того, что у вас не возникнут "тормоза" на абсолютно ровном месте.

2. Чистые функции в каждый дом

Кто-то может возразить, что пока мы возвращаем в каждой итерации новый массив наша функция чиста, а как только мы начинаем в ней что-нибудь мутировать, мы теряем драгоценную purity. Ребята, любящие FP, у меня для вас замечательная новость: вы можете сколько угодно мутировать в своих чистых функциях state. Они от этого не перестают быть чистыми. И тут в меня полетели камни.

Да, это не шутка (собственно настоящие FP-ы об этом прекрасно знают). Ваша функция должна удовлетворять всего двум критериям, чтобы оставаться чистой:

  • быть детерминированной

  • не вызывать side effect-ов

И да, мутация это effect. Но обратите внимание на слово "side". В нём вся соль. Если вы мутируете то, что было целиком и полностью создано внутри вашей функции, то вы не превращаете её в грязную. Условно:

const fn = () => {
  let val = 1;
  val = 2;
  val = 2;
  return val;
}

Это всё ещё чистая функция. Т.к. val существует только в пределах конкретного вызова метода и он для неё локален. А вот так уже нет:

let val = 1;
const fn = () => {
  val = 2;
  return val;
}

Т.е. не нужно идти ни на какие сделки с совестью (а лучше вообще избегать всякого догматизма), даже если чистота ваших функций вам важнее чистоты вашего тела.

3. Умный компилятор всё оптимизирует

Тут я буду краток: нет, не оптимизирует. Попробуйте написать свой, и довольно быстро поймёте, что нет никакой магии. Да внутри v8 есть разные оптимизации, вроде этой (Fast_ArrayConcat). И да, они не бесполезны. Но не рассчитывайте на магию. Увы, но мы не в Хогвартсе. Математические законы превыше наших фантазий.

По сути для того чтобы избежать O(n^2) в такой ситуации, компилятору необходимо догадаться, что сия коллекция точно никому не нужна и не будет нужна в текущем виде. Как это гарантировать в языке, в котором почти ничего нельзя гарантировать (из-за гибкости и обилия абстракций)?

Причина

Зачем эта статья? От безысходности и отчаяния. Мне кажется основной причиной этой широко распространённой проблемы является React и Redux, с их любовью к иммутабельности. Причём не сами эти библиотеки, а различные материалы к ним (коих тысячи), где встречается этот "паттерн". Если по началу это можно было объяснить тем, что хочется приводить максимально простые примеры, то сейчас это стало mainstream-ом.

Вот например:

PS: coming-out - часто делаю concat внутри reduce ???? в 99% задач вроде не сильно афектит

Или вот:

getDependencies(nodes) {
  this.processQueue();
  return nodes.reduce(
    (acc, node) => acc.concat(Array.from(this.dependencies.get(node) || [])),
    []
  );
}

I'm pretty surprised that this has any impact, I don't have a good rationale for why but it appears to be dramatically faster to update the array in place.

Складывается ощущение, что этот "паттерн" применяется почти в каждой второй статье про Javascript. Я думаю настало время что-то с этим делать. Люди на собеседованиях не видят никакой проблемы в вызове .includes внутри .filter и подобных штуках. ...-синтаксис по их мнению работает за O(1). А v8 переполнен магией. Люди с 7-ю+ годами боевого опыта делают удивлённые глаза и не понимают, что может пойти не так. Впрочем это уже другая история.

P.S. по вопросам опечаток и стилистических ошибок просьба обращаться в личку.

Комментарии (336)


  1. Druj
    22.11.2021 15:14
    +19

    «Достаточно умный компилятор это оптимизирует»© — неизвестный FP адепт.


    1. faiwer Автор
      22.11.2021 15:24
      +5

      В целом, статически типизированным чистым FP языкам доступны очень хитрые оптимизации.
      Но ничего. Вот завезут к нам immutable data structures (где-то лежал черновик спецификации), заживём


      1. vkni
        23.11.2021 04:19
        +2

        Как правило, на статически типизированных чистых FP языках, не пишут "не приходя в сознание". В смысле, там, конечно, есть "неявная" мемоизация, и т.д., но

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

        Ну и явная мемоизация в Clean, кмк, лучше, чем неявная в Haskell.


        1. 0xd34df00d
          23.11.2021 20:51
          +2

          То, что есть в хаскеле — это не неявная мемоизация, а ленивая стратегия вычислений. Функцию fac n = if n > 0 then n * fac (n - 1) else 1 никто мемоизировать не будет.


          А вот хороша или нет лень по умолчанию — отдельный вопрос.


          1. csl
            23.11.2021 21:39

            Как только убежусь, что она плоха - отключу лень (конечно, если только в стратегии был боттлнек).


            1. 0xd34df00d
              23.11.2021 23:06
              +2

              Ну, если честно, я в требовательном к производительности коде давно отключаю лень по умолчанию (и начинаю файл с {-# LANGUAGE Strict #-}).


          1. vkni
            23.11.2021 23:14

            То, что есть в хаскеле — это не неявная мемоизация, а ленивая стратегия вычислений.

            Ну вы же знаете про динамическое программирование на Хаскеле.


            1. 0xd34df00d
              23.11.2021 23:24
              +1

              Я и узел там завязывать умею, но не могу назвать это неявной мемоизацией.


              1. vkni
                23.11.2021 23:35

                Я конкретно про вот это - https://jelv.is/blog/Lazy-Dynamic-Programming/

                fib' max = go max
                  where go 0 = 0
                        go 1 = 1
                        go n = fibs ! (n - 1) + fibs ! (n - 2)
                        fibs = Array.listArray (0, max) [go x | x <- [0..max]]

                В Клине же есть явное описание того, что мемоизуется, а что - перевычисляется:

                // Global constant graph versus global constant function definition: biglist1 is a graph which is computed only once, biglist3 and biglist2 is a constant function which is computed every time it is ap­plied.
                
                biglist1 =   [1..10000]                // a constant function (if defined globally)
                
                biglist2 =:  [1..10000]                // a graph
                
                biglist3 =>  [1..10000]                // a constant function

                https://clean.cs.ru.nl/download/html_report/CleanRep.2.2_12.htm#_5.2_Defining_Graphs


          1. PsyHaSTe
            25.11.2021 01:34
            +1

            Как говорил один мой знакомый

            любой прод-реди функциональный строгий язык это не

            map f [] = []
            map f (x:xs) = f x : map f xs

            а
            
            map f xs = go [] xs
              where
                go r [] = reverse r
                go r (x:xs) = go (f x:r) xs


            и так с каждой фунцией

            Так что мб ленивость по дефолту это и не так уж плохо


            1. transcengopher
              25.11.2021 16:48
              +1

              Если это про понятность, то мне, честно говоря, первая версия более понятна, чем вторая — а я даже не на функциональных языках пишу, а на Java 8+ (ну ещё на ECMA 6, но это мелочи).


              1. mayorovp
                25.11.2021 16:59
                +2

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


                1. Alexandroppolus
                  25.11.2021 17:11

                  а оптимизации хвостовой рекурсии там разве не предусмотрено?


                  1. mayorovp
                    25.11.2021 17:45
                    +3

                    Так она хвостовая только во втором примере.


  1. Drag13
    22.11.2021 15:16
    +7

    Хороший пост, спасибо. Я бы еще добавил что часто такая проблема возникает в Реакте когда мы рендерим списки из БД потому что
    * Мы вызываем этот On2 на каждый рендер
    * Рендеры происходят часто
    * Списки из базы имееют тенденцию к росту.

    И вот то что у дева не тормозит (потому что на тестовой базе 10 записей и дев машина сильнее среднестатистической) на проде уже лагает или даже ощутимо вешает юай.


    1. Alexandroppolus
      22.11.2021 16:57

      В Реакте - смотря как реализовано. Допустим, есть массив каких-то объектов, и мы по нему рендерим список. Когда в массиве что-то добавляется или удаляется, то будет перерендер списка, но не будет перерендера каждого элемента (при условии, что не забыли React.memo для элементов). Когда обновляется итем, то в иммутабельном стиле (Редукс и т.д.) тоже будет перерендер списка, а с МобХ уже не будет (если, конечно, элементы списка обернуты в observer и получают итем с наблюдаемыми полями).


      1. Drag13
        22.11.2021 17:07

        часто !== всегда, так что ваш пункт валиден, но уже учтен


      1. eeeMan
        23.11.2021 11:26
        -2

        не будет перерендера не потому что memo а потому что используешь key правильно


        1. faiwer Автор
          23.11.2021 11:27
          +3

          На всякий случай уточню — вы же в курсе что правильно выставленный key не спасет от re-render-а? Я даже больше скажу, он с ним не связан. Key в React и Vue нужен для сопоставления элементов в списках. Он не используется в целях мемоизации


          1. eeeMan
            23.11.2021 12:01

            я про то, что кей не даст перерендера элементами массива если они не изменились


            1. mayorovp
              23.11.2021 12:11

              А вам говорят про то, что сам массив в любом случае будет рендерится при каждом своём изменении. И этот рендер работает в лучшем случае за O(N), где N — длина массива, а в обсуждаемом случае — за O(N2)


            1. faiwer Автор
              23.11.2021 12:11
              +1

              Слишком много опечаток в комментарии. Я не понимаю его смысла. Key не даст перерендерить элементы массива если они не изменились? Даст.


              1. eeeMan
                23.11.2021 12:12
                -3

                нет


                1. faiwer Автор
                  23.11.2021 12:20

                  Запустите это

                  import React from "react";
                  import "./styles.css";
                  
                  const Inner = () => {
                    console.log('render Inner');
                    return <div>inner</div>;
                  }
                  
                  export default function App() {
                    const [, setState] = React.useState({});
                  
                    return (<div>
                      <Inner key="key"/>
                      <button 
                        onClick={() => setState({})}
                      >
                        rerender Outer
                      </button>
                    </div>);
                  }


                  1. eeeMan
                    23.11.2021 12:24
                    -9

                    щас бы в качестве ключа использовать "key", ты хоть почитай или видео посмотри какие-то про работу реакта) а то прям не совсем слабенько


                    1. faiwer Автор
                      23.11.2021 12:36
                      +10

                      Честно говоря я не очень рекомендую смотреть видео. Я всегда предпочитал первоисточник. В случае React он здесь. Рекомендую прочитать от корки до корки её всю (не эту статью, а всю документацию). Сейчас вы говорите глупости, ввиду полного непонимания предметной области.


                      1. eeeMan
                        23.11.2021 12:49
                        -7

                        увидев key="key" на собеседовании я бы скорее всего Вам отказал


                      1. faiwer Автор
                        23.11.2021 12:55
                        +19

                        Я понимаю. И знаете мы бы сэкономили друг другу уйму времени. Потому что я бы не справился с вашим обучением. Одно дело когда человек чего-то не знает. Но совсем другое дело когда человек в своём невежестве воинственнен.


                  1. nin-jin
                    23.11.2021 14:27

                    Что-то я не пойму, почему Inner ререндерится? У него же пропсы не меняются.


                    1. Drag13
                      23.11.2021 14:30
                      +2

                      Функциональные компоненты ре-рендеряться всегда, даже если их пропсы не менялись


                      1. nin-jin
                        23.11.2021 14:38
                        +5

                        Какой зашквар....

                        А как сделать, чтобы не ререндерились, если пропсы не поменялись? Ну, кроме прикручивания мобх.


                      1. Drag13
                        23.11.2021 14:46
                        +2

                        • Reac.memo для функциональных компонентов

                        • React.PureComponent для классовых

                        UPD под всегда я имел ввиду всегда когда перерендеривается родитель.


                      1. Alexandroppolus
                        23.11.2021 19:38
                        +1

                        Ну, кроме прикручивания мобх.

                        МобХ в этом плане ничего особого не дает, его декоратор observer дополнительно работает ещё и как React.memo - чтобы не надо было заморачиваться и вешать два декоратора, да и вспоминать какой сначала а какой потом. Зато, в отличии от того же редукса, позволяет экономить ререндеры родительских компонентов, если мутабельно менять что-то в объекте, за некоторыми исключениями.


                      1. ShadF0x
                        23.11.2021 22:53
                        +2

                        Кто о чем, а vintage опять про smol.


                  1. nsinreal
                    23.11.2021 18:04

                    deleted


            1. Alexandroppolus
              23.11.2021 12:20

              Не будет перерендера дома, но будет перерендер виртуального дома. В рамках "оптимизации реакта" обычно говорится о том, как сократить перерендеры vdom


              1. eeeMan
                23.11.2021 12:37
                -1

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


                1. faiwer Автор
                  23.11.2021 12:41

                  В работе React есть две фазы: render и commit. Render это построение списка изменений за счёт реконсилирования двух virtualDom деревьев. А изменения в настоящем DOM это commit. Так вот ваша "вызывает функция рендер" это как раз render. Вышеописанный memo тоже работает на стадии render. А key нужен только для сопоставления однородных элементов во время работы алгоритма реконсиляции.


                  1. eeeMan
                    23.11.2021 12:57
                    -4

                    как я уже говорил ранее, рендер функция компонента в любом случае вызовется потому что произошло изменение массива (а если ничего не менялось то она и не вызовется), рендер в браузере вызовется только для элемента который изменился, либо в Вашем случае для всех элементов потому что key="key", ещё и ворнинг выдаст из-за одинаковых ключей для всего списка.


                    1. faiwer Автор
                      23.11.2021 13:04
                      +6

                      рендер функция компонента в любом случае вызовется

                      Не в любом. С самого начала вам сказали про memo. Вот если обернуть дочерние компоненты memo (и соблюсти ряд условий), то они не будут пере-render-ены. Кроме тех конкретных instance-ов, элементы которых были изменены.


                      Массив ведь меняется не целиком, а частично. Добавили новый элемент. Изменили существующие. Удалили элемент. Любое из этих изменений вызовет ререндер компонента списка. Но при правильно организованном коде дочерние компоненты лишний раз вызываться не будут.


                      Вашем случае для всех элементов потому что key="key"

                      Для каких всех? Я для вас привёл сверх-простой пример где всего один элемент. У него уникальный key (тот самый который key="key", но вы можете поменять это на любую другую константу). Задача для key — позволить React-у сопоставлять элементы между render-ми.


                      Умоляю, откройте уже документацию. Вы не понимаете о чём вы спорите.


      1. Nikitakun1
        23.11.2021 11:49

        В последнем кейсе в MobX перерендера списка не будет, если массив вручную мутировать, но если у нас такая ситуация, когда на каждый экшн нужно перезапрашивать весь список с бэкенда и перерисовывать, то при присвоении этого нового массива в observable-свойство все перерисуется, верно ведь?


        1. Alexandroppolus
          23.11.2021 12:01

          то при присвоении этого нового массива в observable-свойство все перерисуется, верно ведь?

          Само собой. MobX рулит только на точечных мутациях.


    1. zuek
      23.11.2021 11:15
      +3

      О, кажется, Вы открыли мне глаза на тормоза одного из наших внутренних продуктов, заказанных "на стороне" - пока шла разработка, всё "летало", а как запустили в прод, буквально через полгода начались тормоза... при чём тормоза (по несколько минут на отрисовку) при работе с не особо большими таблицами - буквально по паре тысяч строк, при том, что мой "костыль" на php обрабатывал их за доли секунд. Да, наш "внутренний продукт" был написан на Реакте, в котором я разбираюсь едва ли более, чем никак, собственно, из-за чего я и не смог предложить внятного решения, кроме как резать ежемесячно таблицы...

      Напомнило, как лет 20 назад "программист 1С" (на самом деле, не 1С, а RS-Balance, но суть это меняет не сильно), очень удивился, когда его отчёт вместо привычных 15-20 минут стал выполняться за 5-7 секунд, всего лишь после того, как я порекомендовал всю логику унести на серверную сторону, в то время как в изначальном виде, "отчёт" по OLE создавал файл в Excel, выгружал в него "необработанные данные" и уже "на листе Excel" их обрабатывал (группировал, сортировал, и вообще творил всякие вычисления)... по OLE... я не программист, но даже мне это было "странно".


      1. vladkorotnev
        03.12.2021 07:54
        +1

        OLE/COM-интеропы это та ещё жопа в производительности. Как-то раз писали хреньку для миграции документов из ворда в другой вид ворда (и да, на реакте :-). Обработка в цикле таблицы в строк так 500 через интероп — занимала, чтоб не соврать, ну минут 15. Переделали на генерацию скрипта на VB6, передачу его в ворд, с последующим возвратом склеенного из строк подобия JSON'а — та же самая таблица на 500 строк уже обрабатывалась за 300-400 миллисекунд!


    1. efkz
      24.11.2021 15:00
      +1

      Поэтому у дева должен быть старый Пень с экраном 1024х768 и дайлапом )))


  1. aamonster
    22.11.2021 16:01

    Поддерживаю основную мысль, но ваш пример переиспользования объекта – плохо.
    И дело именно в том, что функция не чистая. Не та, которая вызывает reduce, а та, которую вы передаёте в reduce. Та самая коротенькая
    (accumulator, item) => {
    accumulator.push(...something(item));
    return accumulator; // это ключевая строка
    }
    То, что вы передаёте в reduce не чистую функцию – полбеды. Беда в том, что вы её передаёте в reduce :-). В смысле, сама сигнатура reduce заточена под чистую функцию, и передача туда "нечистой" сбивает с толку (есть возвращаемое значение, а вы модифицируете входное).

    А проблема на самом деле в использовании reduce там, где должен быть map или filter.


    1. faiwer Автор
      22.11.2021 16:17
      +15

      А проблема на самом деле в использовании reduce там, где должен быть map или filter.

      Вы уходите в частности не имеющие отношение к обсуждаемой теме. Тело функции-callback-а, передаваемого в .reduce может быть сколь угодно сложным и витееватым. Ключевым (относящимся к теме) является — мутируем ли мы результат, или возвращаем копию+изменение.


      Причём если с массивом вы в этом тривиальном примере (специально тривиальном, чтобы не морочить голову), можете обойтись .flatMap-ом. То что вы будете делать с формированием не массива, а объекта? Возвращать [key, value] и писать какой-нибудь мутабельный zipObject?


      И дело именно в том, что функция не чистая. Не та, которая вызывает reduce, а та, которую вы передаёте в reduce. Та самая коротенькая

      Я знаю. Но nobody cares, ведь так, да? ;-) Догматизм — зло


      1. mayorovp
        22.11.2021 22:06
        +1

        Может, догматизм и зло, но если нас от всего reduce интересует лишь обход массива — почему, блин, не воспользоваться семантически верным forEach?


        1. faiwer Автор
          22.11.2021 22:17
          +2

          Можно. А смысл? Те же проблемы, что и у for-of. Можно сразу взять for-of, зачем forEach?


          // ^ рвём цепочку
          const data = {};
          for (const [key, value] of Object.entries(obj))
            data[key] = something(value);
          // возобновляем цепочку (если надо)

          Вариант с reduce позволит не рвать цепочку и не перегружать код (имхо). Но я понимаю, что это вкусовщина. Главное не тащить сюда квадрат.


          1. mayorovp
            22.11.2021 22:21
            +1

            Ну, я и у for-of никаких проблем не вижу.


      1. PsyHaSTe
        25.11.2021 01:40

        Ну на самом деле я согласен, что мутировать хорошо локально, но только когда это явно видно, Ну знаете, `runST` и вот это все. reduce все же рассчитывает на чистую функцию, и если завтра объект аккумулятора начнется как-нибудь хитро кэшироватьяс между разными вызовами редьюсов то можно будет ловить веселые приколы. Видел подобное в плюсовом коде, где значение после мува использовали как «проицинициализированный пустотой объект», а оно так какое-то время было а потом хоп и изменилось.

        Вы можете в этой функции мутировать внешний по отношению к редьюсу стейт, это правда. Но вот аргументы редьюса трогать это плохая практика.

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

        В общем, по сути статьи я согласен, но в деталях скрылся дьявол


        1. faiwer Автор
          25.11.2021 01:45
          +3

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

          В пределах одного вызова reduce? Это как? Если же нет, то не совсем понял проблему, т.к. мы же всегда создаём новый аккумулятор (2-ым аргументом).


          воспользоваться флатмапом

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


          не устраивала результирующая производительность

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


          1. PsyHaSTe
            25.11.2021 02:01
            +3

            В пределах одного вызова reduce? Это как? Если же нет, то не совсем понял проблему, т.к. мы же всегда создаём новый аккумулятор (2-ым аргументом).

            Я не придумал в конкретном случае) Но если это дается как общий совет, то такие случаи когда что-то там мемоизировалось и мутировалось у меня бывали, и последствия были плачевные.


            С мутабельностью удобно работать когда в сигнатуре видишь (State m) => ... -> m Number, а без этого знание что формально мы можем представить что всё чистое… Ну мы можем точно так же представить, что любая сишная программа чистая, просто var x = y это на самом деле не let а монадический бинд, а все функции написаны в IO. Формально будет верно, по факту никаких гарантий не добавит, и код как был ногострельным так и останется.


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

            Ну, я в принципе так и подумал, что это упрощение ради примера) Надо подумать — ломать не строить. Если придумаю — напишу. Но как простой ответ можно как раз сказать "редьюс тут плохо подходит по семантики из-за сложности, но вот есть флатмап". По сути это ведь и есть флатмап. Как вариант или взять его из стандартной поставки, или написать свой. Но если писать свой то наверное лучше использовать родной for, а не редьюс. Хотя бы как семантический фактор "здесь происходит нечто что плохо ложится на существующие комбинаторы". По крайней мере у меня такой подход обычно — если пихание мутирующих функций в редьюс выглядит чужеродно, то оно так и есть, и стоит его избегать. У меня по крайней мере такое впечатление.


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

            Прекрасно понимаю и сочувствую. Сам на ревью на прошлой работе практически настроил автоматический возврат кода на доработку если там есть авейт в цикле. Но они продолжали приходить.


            Все что остается — писать подобные образовательные статьи и надеяться на постепенный рост средней квалификациии разработчиков. Не впадая в "а вот в наше время были богатыри — не вы", сейчас качество разработчиков очень выросло. Что ни говори, DDD была овер хайпанутая тема 10-15 лет назад, а ведь по сути там все сводится к "не запускайте ракеты из класса юзера". Чуть позже откровением был SOLID — щас разработчики просто плечами пожимают "ну да, а как ещё разрабатывать, говно ж выйдет".


            Понемногу идем. Но да, чтобы процесс шел нужны обучающие материалы вроде этой статьи. За что спасибо


            1. Vilaine
              26.11.2021 11:36

              Сам на ревью на прошлой работе практически настроил автоматический возврат кода на доработку если там есть авейт в цикле.
              А как быть, если каждая итерация берёт данные из предыдущей итерации?


              1. PsyHaSTe
                26.11.2021 11:38

                Ну тогда очевидно никак. Но в 99% никаких зависимостей нет и код выглядит так:


                const orders = [];
                for (let orderId of orderIds) {
                  orders.push(await getOrder(orderId));
                }

                И тут как бы печально от этого цикла становится


                1. nin-jin
                  26.11.2021 11:58
                  +1

                  Зато с таким кодом нагрузка на сервер более равномерная.)


                  1. PsyHaSTe
                    26.11.2021 12:09

                    Это правда. Но я считаю что сервер если не справляется с нагрузкой должен сам троттлить запросы клиента, а не клиенты должны писаться с осторожностью. Потому что только сервер знает реальную нагрузку и если его внезапно оптимизируют/переведут на более мощное железо то идти искать все места где его щадят.


                    Вероятно я отвечаю на сарказм, но раз уж написал то пусть будет


                    1. nin-jin
                      26.11.2021 12:18

                      Троллтить, всмысле возвращать ошибку "вы сделали слишком много запросов в минуту, поэтому мы заблокировали вас на 5 минут и просим решить зубодробительную каптчу"?

                      Сарказм, конечно, но в любом сарказме есть доля суровой реальности.


                      1. PsyHaSTe
                        26.11.2021 12:19

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


                    1. mayorovp
                      26.11.2021 13:39

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


                1. Vilaine
                  26.11.2021 13:17
                  +1

                  Но в 99% никаких зависимостей
                  Да, но линтер не пропускает этот 1% случаев. =) Хотя в Javascript большинство линтеров поддерживают игнор.


                  1. PsyHaSTe
                    26.11.2021 13:25

                    Да, это как раз такой случай, когда иногда это может быть корректно, но почти всегда нет. И да, линтер по идее должен уметь различать случаи когда есть явная зависимость между итерациями result = await foo(result.Something, somehingElse)


                    1. Alexandroppolus
                      26.11.2021 13:38

                      И да, линтер по идее должен уметь различать случаи когда есть явная зависимость между итерациями result = await foo(result.Something, somehingElse)

                      Зависимость может быть и неявной. Например, на позапрошлой работе, помнится, были запросы на получение рекламы. С требованием "только один запрос в любой момент времени", чтобы не перетерлись изменения в куках.

                      Но это совсем уж редкие кейсы..


                      1. PsyHaSTe
                        26.11.2021 15:08

                        Да, и редкие кейсыы уже можно заткнуть // disable-lint i know what I do


                1. Alexandroppolus
                  26.11.2021 13:35
                  +2

                  Этот цикл особенно печален тем, что бэк не сделал (или сделал, но фронты не знают) сервис для getOrders(orderIds), чтобы одним запросом.


                  1. PsyHaSTe
                    26.11.2021 15:10
                    +1

                    Это частая история на самом деле. например возьмем гитхаб апи — как получить информацию по репозиториям если у нас есть массив их айдишек?
                    Или телеграм апи — как получить описание групп если у нас есть список их названий?


    1. faiwer Автор
      22.11.2021 16:20
      +3

      сама сигнатура reduce заточена под чистую функцию

      Забыл отметить, что пока у нас нет настоящих immutable data structures не так важно, как .reduce задумывался (в FP мире). В scala для таких вещей у ребят есть специальные древовидные коллекции с O(logN) на операцию. А у нас шиш.


      1. faiwer Автор
        22.11.2021 16:29
        +2

        Кстати в lodash есть _.transform, который изначально игнорирует возврат из callback-а (точнее поддерживает только ранний выход из итерирования). Лично мне не хватает его в стандартной библиотеке.


        1. aamonster
          22.11.2021 16:51
          +4

          Вот! В _.transform всё сделано так, что сразу понятно, что она ждёт не чистую функцию, а функцию, модифицирующую аккумулятор. Собственно, можно reduce завернуть аналогично.
          Дело-то не в догматизме, а в "принципе наименьшего удивления".

          А так, конечно, тут не хватает линейных типов. Чтобы если вы передали accumulator в качестве аргумента reduce – то всё, дальше по коду ваш accumulator недействителен.


          1. faiwer Автор
            22.11.2021 16:57
            +2

            Дело-то не в догматизме, а в "принципе наименьшего удивления".

            Ну вот если бы речь не шла об O(n^2) вместо O(n) я бы с вами согласился. Можно было бы говорить про удивление, чистоту кода и т.д… Но увы, на другой чаше весов куда более серьёзный аргумент.


            И да, было бы классно иметь transform в Array.prototype.. Тогда сам вопрос бы отпал как таковой.


            1. aamonster
              22.11.2021 17:04
              -1

              Так кто мешает? Array.prototype.transform=function(...)

              И не надо говорить про чаши весов. Заверните reduce (или даже цикл) в функцию с понятной сигнатурой и пользуйтесь. Если, конечно, не хватит map/filter.

              В смысле, я ратую за то, чтобы писать O(n), но понятное O(n) :-)


              1. faiwer Автор
                22.11.2021 17:11
                +7

                Так кто мешает? Array.prototype.transform=function(...)

                За это бьют ногами. История prototypeJS до сих пор всем аукается.


                Заверните reduce (или даже цикл) в функцию с понятной сигнатурой и пользуйтесь

                Как только завезут |> первым делом так и сделаю. Текущее же положение вещей в JS community приводит к тому, о чём я написал в статье. Люди блин даже пишут:


                I'm pretty surprised that this has any impact

                Чувак создал PR где заменил O(n^2) на O(n) и удивлён что это вообще что-то дало. Что характерно, этого ему показалось мало. Ведь "оно должно работать" быстро и он нашёл ещё одну причину. Но вот на O(n) у него глаз не дёрнулся. С его точки зрения, получается, это не проблема (хотя лекарство и помогло). Он полез в кишки v8 и затем целую написал про Symbol.isConcatSpreadable. Дескать в этом проблема (хотя признаю, что в этом тоже есть проблема — "магическая оптимизация" сорвалась).


                И такой вот софт где народ не думая городит ну вот прямо на пустом месте аховую асимптотику всё больше и больше.


                1. aamonster
                  22.11.2021 22:50
                  +1

                  Ok, за Array.prototype.... прошу прощения. Но никто не мешает иметь то же самое отдельной функцией. С понятной сигнатурой и сложностью O(n). Для этого даже композиция функций не нужна.


                  1. faiwer Автор
                    22.11.2021 22:55
                    +1

                    Но никто не мешает иметь то же самое отдельной функцией

                    На самом деле мешает. Сейчас в JS нет удобной возможности не рвать цепочки, т.к. pipe-оператор уже многие годы висит среди незавершённых спецификаций. По сути говоря любой метод, которого нет в chain-е вынуждено заставит вас разворотить всю цепочку трансформаций. Вот с ним такой проблемы уже не будет.


                    Но мне кажется наш разговор зашёл куда-то не туда. С вашей точки зрения нарушать кем-то придуманную семантику reduce это большой грех. А с моей точки зрения — нет. И то и другое — субъективщина. Поэтому предлагаю на этом и закончить. А то мы скатимся в какой-нибудь холивар про "читаемый\нечитаемый код", "признаки оценки качества кода", "роль семантики в разработке ПО" и пр.


                    1. nin-jin
                      23.11.2021 08:38
                      +6

                      Я тоже любил цепочки. С ними код такой лаконичный. Пока не начал пользоваться отладчиком. А дебажить цепочки - это просто ад. Гораздо удобнее, когда есть отддльная переменная на отдельной строке. Тогда и брейкпоинт можно поставить, и значения на каждом шаге посмотреть, перепрыгнуть шаг-другой, ну и мелкие изменения не приводят к куче правок в коде с разрывами цепочек.


                1. platinum355
                  23.11.2021 17:01

                  Но вот на O(n) у него глаз не дёрнулся.

                  А почему у него на 0(n) должен был глаз дёрнуться ? Разве можно собрать зависимости всех нод, не пройдясь по всем нодам ? Удивите)


                  1. faiwer Автор
                    23.11.2021 17:01

                    Не удивлю, это опечатка :) Имел ввиду N^2, конечно же


                    1. platinum355
                      23.11.2021 17:46
                      +2

                      Тогда извиняюсь)


                1. vkni
                  23.11.2021 18:00

                  Чувак создал PR где заменил O(n^2) на O(n) и удивлён что это вообще что-то дало.

                  Это означает, что он явно не понимает, что пишет. Так делать нельзя.

                  > И такой вот софт где народ не думая городит ну вот прямо на пустом месте аховую асимптотику всё больше и больше.

                  Это просто "кодирование не приходя в сознание". Там может быть много причин - низкая квалификация, повышенные требования по скорости, выгорание, следование хайпам и т.д.


                  1. faiwer Автор
                    23.11.2021 18:12

                    Это просто "кодирование не приходя в сознание". Там может быть много причин — низкая квалификация, повышенные требования по скорости, выгорание, следование хайпам и т.д.

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


                    Пока меня пугает сам тренд на "всё что не убивает меня, делает меня сильнее не имеет значения", кого-то пугает что ещё есть люди, которые видят в этом проблему :)


                    1. vkni
                      23.11.2021 19:21
                      +2

                      Пока меня пугает сам тренд на "всё что не убивает меня, делает меня сильнее не имеет значения", кого-то пугает что ещё есть люди, которые видят в этом проблему :)

                      Это непосредственное следствие культуры "х*як-х*як и в продакшн", которая непосредственное следствие высококонкурентной среды и коротких горизонтов планирования, которая есть просто рыночная экономика. Поэтому я как-то к этому очень по-философски отношусь - снявши голову, по волосам не плачут.

                      Я, кстати, понял, что даже в кондовейшем квадратно-гнездовом C можно легко воспроизвести ваш случайный O(N^2), если писать не приходя в сознание:

                      void my_string_transform(char *s) {
                          int i;
                          
                          for( i = 0; i < strlen(s); i++) {
                              ....
                          }
                      }
                          

                      То есть, JavaScript, как язык, и функциональщина, как подход, тут не при чём.


                      1. BigBeaver
                        23.11.2021 20:12

                        Проблема в неопнимании связи между буковками на экране и тем, какая работа компьютера за ними стоит.


                      1. AnthonyMikh
                        24.11.2021 12:55

                        Я, кстати, понял, что даже в кондовейшем квадратно-гнездовом C можно легко воспроизвести ваш случайный O(N^2), если писать не приходя в сознание:

                        Формально да, но компиляторы уже давно знают про strlen, так что если строка в цикле не изменяется, то компилятор вполне может вынести strlen из цикла. Но да, так писать всё-таки не стоит.


                      1. apro
                        25.11.2021 02:33
                        +3

                        Не всегда кстати C++ компилятор может убрать вызов функции на каждой итерации. Потому что если в итерации вызывается какая-нибудь функция “f” и компилятор знает только ее сигнатуру, но не реализацию, то вполне может быть что данная функция меняет строку через глобальную переменную и поэтому вызов strlen нельзя кэшировать.


                  1. Drag13
                    23.11.2021 18:15
                    -1

                    Справедливости ради, проблема была не в самом методе конкат.


                    Проблема была в использовании Symbol.isConcatSpreadable где-то в коде, что автоматически замедляло все concat-ы.

                    Вот статья https://engineering.tines.com/blog/understanding-why-our-build-got-15x-slower-with-webpack


                    1. faiwer Автор
                      23.11.2021 18:21

                      Справедливости ради, проблема была не в самом методе конкат

                      Не соглашусь. Там просто две проблемы. Одна с isConcatSpreadable, а другая в .concat in .reduce. Причём ему хватило даже решения второй проблемы. Но чувак дотошный (а почему с wp4 не тормозит?) и он нашёл ещё и 1-ую.


                      Справедливости ради, я думаю, что решение проблемы с isConcatSpreadable даст куда больший impact, т.к. affect-ит сразу всю запускаемую кодовую базу.


                      1. Drag13
                        23.11.2021 18:27

                        Погодите...

                        У него действительно было две проблемы, но я не вижу свидетельства того, что в данном случае проблема была именно в concat.

                        Т.е. осталась ли проблема, в случае если из кодовой базы исчез isConcatSpreadable? Вот это самое интересное и показательное на мой взгляд.


                      1. faiwer Автор
                        23.11.2021 18:31

                        но я не вижу свидетельства того, что в данном случае проблема была именно в concat

                        Гхм. Всмыыыыысле? Без concat проблемы нет. И не важно стоит ли isConcatSpreadable или нет. Это css-in-JS поделие о котором там речь, работает "drammatically faster" если убрать квадрат. Если это не свидетельство, то что же тогда свидетельство?


                        Полностью согласен с mayorovp, isConcatSpreadable просто заметал проблему под ковёр.


                        Вот давайте проверку на прочность проведём:


                        • Не накатываем патч с O(n). Но накатываем патч с isConcatSpreadable. Проблема решена? Да. Проходит время, N увеличивается. Проблема осталась? Осталась.
                        • Поступаем наоборот. Обе ситуации — всё работает быстро.

                        Ну а вариант — накатываем оба патча, конечно лучше.


                      1. Drag13
                        23.11.2021 18:38

                        Вот давайте проверку на прочность проведём


                        Вот именно это я и имел ввиду. Только я говорил что в их частном случае конкретная проблема была с isConcatSpreadable, а вы отвечаете о случае общем (и правы в этой части).


                        Мы говорим с немного разных ракурсов.


                    1. mayorovp
                      23.11.2021 18:22
                      +1

                      Проблема была именно в квадратичном алгоритме, оптимизированный concat лишь позволял её спрятать.


                    1. vkni
                      23.11.2021 19:22

                      Справедливости ради, проблема была не в самом методе конкат.

                      Проблема в том, что люди не понимают то, что пишут. А метод - это как молоток - инструмент.


      1. Devoter
        22.11.2021 16:45
        -1

        Вообще, да, хотелось бы иметь интерпретатор для JS, ну или хотя бы компилятор типа TS, который умеет вызовы типа arr.map(...).filter(...).reduce(...) разворачивать в O(n).


        1. faiwer Автор
          22.11.2021 16:53

          Как-то слишком много магии, имхо :) Да и вообще нам бы куда более простых инструментов бы завезли. Например, чтобы не писать:


          <Button style={style} onClick={onClick} blabla={blabla} />

          вместо


          <Button { ...{ style, onClick, blabla }} />

          потому что:


          • TS позволяет в этом spread-е передать лишние поля :-(
          • TS не оптимизирует 2-ую конструкцию в 1-ую

          Если 2-е можно сделать плагином для TS, то вот первое уже нет, т.к. TS не умеет в плагины до type-checking-а :(


        1. youngmysteriouslight
          22.11.2021 21:37
          +9

          AFAIK, любой интерпретатор JS исполняет arr.map(x => x + 2).filter(x => x > 0).reduce((a, b) => a + b) за O(n).


          1. dustik
            23.11.2021 14:22

            Вот прямо в точку.

            Тоже хотел написать, что меня выводит из состояния покоя, что есть "черные ящики оптимизации" в компиляторах.

            Можно усиленно стараться и писать алгоритмически красиво, но другой разработчик написал редьюс с O(n^2), но компилятор это увидел на втором шаге и под капотом сложил все в оптимальную структуру, а потом это все еще и отсортировал как нужно.


          1. dustik
            23.11.2021 14:23
            -1

            Кстати, наверное будет всеже что-то близкое к O(n*log(n))


            1. mayorovp
              23.11.2021 15:49

              А логарифм-то тут откуда возьмётся?


              1. dustik
                23.11.2021 17:32

                Это я к своему комментарию написал.

                > под капотом сложил все в оптимальную структуру, а потом это все еще и отсортировал как нужно.

                Т.е. O(n^2) если использовать двоичную кучу, вполне может превратиться в O(n*log(n))


          1. Lynn
            23.11.2021 14:43
            +3

            Ну формально да. Потому что O(3n) === O(n) ????


        1. vkni
          23.11.2021 04:22

          А разве это не любой делает?

          В GHC есть оптимизация этого под названием stream fusion, которая просто засовывает всё в один цикл вместо нескольких последовательных. Но сложность вычислений вот просто так вроде бы не меняется.


          1. 0xd34df00d
            23.11.2021 20:59
            +2

            Иногда меняется :] Компилятор счастливо оптимизирует map negate . map negate в id, например, делая из линейной сложности константную.


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


        1. nin-jin
          23.11.2021 08:47
          +1

          У меня вот такая штука есть. Там, правда, filter и reduce ещё не реализованы.

          Но оно не поможет бороться с алгоритмической сложностью. В частности, ваш код и так линеен.


        1. alexxz
          23.11.2021 12:53

          Приведённый вами пример и отрабатывает за O(n). Три (константа) прохода по списку - это O(n). А вот оптимизация вычислений, чтобы это был один проход, а не 3 - это было бы здорово... Можно написать цикл... Ах, ну да, чтобы не писать циклы это всё и придумано.


          1. Devoter
            23.11.2021 14:17

            Да, пожалуй, неверно выразился. Конечно, речь о том, чтоб все это выполнялось за один проход цикла. Собственно, если не ошибаюсь (не силен в ФП), некоторые языки такое позволяют на этапе компиляции. Не отношусь к фанатам подобных конструкций как раз из-за множества проходов, отсутствия break, не говоря уже о том, что сам по себе forEach и любой из его собратьев медленнее обычного for, хотя сейчас уже прикрутили какие-то оптимизации в движках.


            1. LEXA_JA
              23.11.2021 15:54
              +2

              Это можно сделать за один проход и без ФП, через итераторы. Если не ошибаюсь, то в Rust такие вещи разворачиваются.
              В JS это можно сделать через генераторы.

              function* map(mapper, iterable) {
                for (const item of iterable) {
                  yield mapper(item);
                }
              }
              
              function* filter(predicate, iterable) {
                for (const item of iterable) {
                  if (predicate(item)) {
                    yield item;
                  }
                }
              }
              
              function reduce(reducer, initial, iterable) {
                let result = initial;
              
                for (const item of iterable) {
                  result = reducer(result, item);
                }
              }
              
              reduce(
                (a, b) => a + b,
                0,
                filter(
                  (x) => x > 2,
                  map((x) => x + 1, [1, 2, 3, 4, 5])
                )
              );
              



  1. YChebotaev
    22.11.2021 16:43
    +1

    А потом на ревью прилетит «а че ты так сделал, а не через .../[]?». И доказывай что не занимаешься преждевременной оптимизацией.

    Раньше был такой такой чеклист, от авторов Bluebird, в котором были собраны техники оптимизации для оптимизирующего компилятора хрома. Все им пользовались и считали за бест-практайс. На интервью спрашивали. А потом выпустили новый движок и все оптимизации стали не актуальны. Думаю, так же произойдет и с тем о чем вы рассказываете: допилят оптимизации на уровне движка и все ухищрения на уровне кода станут дремучим легаси.


    1. faiwer Автор
      22.11.2021 16:49
      +9

      И доказывай потом что не занимаешься преждевременной оптимизацией.

      Заниматься обучением своих коллег — не грех. Если сильно непробиваемые, можно сменить команду. В конце концов это ваш выбор, с кем вы работаете.


      Думаю, так же произойдет и с тем о чем вы рассказываете

      Не произойдёт. См. раздел "3. Умный компилятор всё оптимизирует" в статье.


      1. YChebotaev
        22.11.2021 18:06
        -5

        Заниматься обучением своих коллег — не грех

        Я и сам-то не уверен что это не преждевременная оптимизация

        Если сильно непробиваемые, можно сменить команду. В конце концов это ваш выбор, с кем вы работаете

        Простите, но я не готов отстаивать эту тему настолько, чтобы терять из за нее работу )

        Не произойдёт. См. раздел "3. Умный компилятор всё оптимизирует" в статье.

        У вас там все очень категорично, не могу на это конструктивно ответить.
        Могу только это прокомментировать:

        Как это гарантировать в языке, в котором почти ничего нельзя гарантировать

        А зачем что-то гарантировать? Аргументация построена на введении излишнего и заведомо не выполнимаого ограничения, которого нет в реальности. В JS-е ничего не гарантировано, но связка из трех компиляторов со всем справляется и быстро. Собственно, тут вопрос не принципиального ограничения, а просто пока что у инженеров V8 руки до этого кейса не дошли


        1. faiwer Автор
          22.11.2021 18:16
          +7

          Я и сам-то не уверен что это не преждевременная оптимизация

          Я в статье разобрал ситуацию когда это может быть преждевременной оптимизацией. Когда у вас гарантировано малый N. Там просто разница в производительности не делает погоду.


          но я не готов отстаивать эту тему настолько, чтобы терять из за нее работу )

          Зачем же доводить до крайностей. Вы видите участок кода, которые является проблемным. Вам задают вопрос — почему так написано. Вы объясняете почему. Предположим с вами не согласны. Вы приводите аргументацию. Вам приводят свою. Если выясняется, что вы не правы, пишете исправляете. Если выясняется, что вы правы, но ваши коллеги не убеждены — работаем над своими soft-skill-ми.


          Но изначально писать откровенно плохой код по причине, а вдруг на ревью кто-то подкопается, это очень плохо.


          А зачем что-то гарантировать?

          Вы понимаете, что единственная серьёзная оптимизация, которая вам тут может быть доступна (нужно вместо O(n^2) сделать O(n)) — мутировать коллекцию под капотом. И компилятор не может себе этого позволить не убедившись в том, что коллекция гарантировано никому не доступна кроме итогового адресата у .reduce? И теперь вопрос — как вы собираетесь это проверять?


          Какие эвристики? Какие контракты? Какие оптимизации? Какие затыки? Можно чуть менее магическим языком, конкретику? ;-)
          Я ещё напомню, что речь идёт ДАЖЕ не о TypeScript где у компилятора есть хоть какие-то зацепки.


          1. faiwer Автор
            22.11.2021 18:31
            +28

            А вообще с этими "преждевременными оптимизациями" народ кажется сходит с ума. Одно дело когда нужно перепахать кодовую базу, переписав алгоритм до неузнаваемости. Или скажем когда нужно сильно усложнить архитектуру, дабы добавить что-то, что возможно не пригодится. Или когда экономия происходит там, где от этого почти никакого толку, при наличии настоящих bottle necks.


            Например мне запомнился товарищ, который на JAVA backend-е писал все HTML шаблоны в обычных JAVA class method-ах используя string builder и ручное экранирование всего и вся. Он же для всех сетевых взаимодействий использовал web-socket-ы, чтобы избегать лишних заголовков и overhead-а на JSON. Вот это я понимаю preliminary optimizations.


            Но когда речь идёт об одной единственной примитивной строке в очевидно опасном месте… Кажется люди стали использовать эту фразу ("преждевременная оптимизация") чтобы ничего никогда никак не оптимизировать, пока к ним Task-а в Jira не прилетит. На мой взгляд, это очень плохо характеризует всю нашу индустрию. Становится понятно, почему многие ассоциируют слово "javascript" исключительно с негативом.


            1. YChebotaev
              22.11.2021 20:43

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

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

              И теперь вопрос — как вы собираетесь это проверять?

              Тут я вступаю в тему, в которой мало смыслю, но разве виртуальная машина не ведет подсчет ссылок? Если ссылка всего одна, и она в параметрах reduce, то это значит что объект никому кроме тела этой reduce не доступен.


              1. faiwer Автор
                22.11.2021 20:49
                +4

                не ведет подсчет ссылок?

                Кажется в Swift и Objective C ведёт. А у нас Garbage collector. Для поиска неиспользуемых нод алгоритм пробегает от корня до листьев древа и помечает ноды как достигаемые. А потом пробегает по всем нодам вообще и те, что не помечены, удаляются. Это в общих чертах.


                По сути желаемая оптимизация потенциально возможно в функциональных языках со строгой типизацией и мощной системой типов. Ну во всяком случае я думаю что возможно она им доступна. У них там прямо очень много что возможно, по целому ряду причин. Например т.к. там настоящая иммутабельность, что гарантирует то, что никакие изменения не прилетят "сбоку" откуда не ждали. И, мне кажется, компилятору (не в runtime) проще отследить те места, в которых можно точно сказать, что на сий объект больше никто точно не может ссылаться. Но тут надо спросить у самих FP-ов, насколько мои фантазии к ним применимы.


              1. transcengopher
                22.11.2021 21:28
                +10

                Это же ECMAScript. Поэтому всегда может найтись прибитый сбоку оверрайд Array.prototype.push, который делает персональные данные массива доступными для неопределённого круга лиц. И даже если так делать давно не принято, сам факт существования такой возможности делает множество видов ссылочных оптимизаций де-факто нерабочими.


          1. fransua
            24.11.2021 06:43

            Я в статье разобрал ситуацию когда это может быть преждевременной оптимизацией. Когда у вас гарантировано малый N. Там просто разница в производительности не делает погоду.

            Есть еще вариант - когда рядом еще более тяжелый O(N^2).

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


    1. vkni
      23.11.2021 20:29
      +1

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

      Завязка на оптимизации делает код хрупким, поэтому крайне нежелательна. Для ухода от хрупкости, скажем, в C++ ввели constexpr, в Ocaml ставят явную аннотацию [@tailcall], чтобы даже 40 лет как имеющаяся оптимизация срабатывала или несрабатывала явно.


  1. Alexandroppolus
    22.11.2021 16:51
    +1

    Плюсую, тоже не раз и не два замечал эти конкаты и тому подобное.


  1. DarthVictor
    22.11.2021 18:12
    +1

    Если не нравится лишняя строчка, то вместо

    (accumulator, value, key) => {
      accumulator[key] = something(value);
      return accumulator;
    }, {}

    можно писать

    (accumulator, value, key) => 
      accumulator.set(key, something(value)),
      new Map()


  1. Tiendil
    22.11.2021 18:30

    Потому что

    Explicit is better than implicit (c) PEP-20

    Не надо создавать и использовать микроскопы в среде, которая проектировалась под молотки.


    1. faiwer Автор
      22.11.2021 18:39
      +3

      Не совсем понял ваш аргумент. Вы имеете ввиду не надо играть в immutability в языке, в котором для этого ничего нет? И по сути просто не пользоваться .reduce, т.к. он неявно подразумевает O(n)? Так в python тоже есть reduce.


      Или вы в целом за for (;;) конструкции, которые явным образом демонстрируют все действия над коллекцией? Мне как-то пришло на проверку тестовое задание, где человек сделал что-то вроде:


      // суть задания была написать простейший полифил
      Array.prototype.map = function(callback) {
        let result = [];
        for (let idx = 0; idx < this.length; ++ idx) {
          result = [...result, callback(this[idx])];
          //        ^^^^^^^^^
        }
        return result;
      }

      Правда такой уникум был только один :)


      1. Tiendil
        22.11.2021 18:56
        +7

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

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

        Так в python тоже есть reduce

        Это не значит, что его надо использовать везде и всегда :-)

        Или вы в целом за for (;;)

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

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


      1. TheShock
        22.11.2021 20:36
        +8

        Вы имеете ввиду не надо играть в immutability в языке, в котором для этого ничего нет? И по сути просто не пользоваться .reduce, т.к. он неявно подразумевает O(n)? Так в python тоже есть reduce.

        Да, было бы неплохо поуменьшить использование редьюс, особенно с такими костыльными конструкциями. Лучше использовать более читаемые и подходящие под текущую ситуацию методы вплоть до for'ов.


        1. faiwer Автор
          22.11.2021 20:37
          +2

          Где-то вдалеке заплакал "redux-программист" :-)


          1. nsinreal
            23.11.2021 00:09

            А при чем тут redux? Нормальные люди давно используют redux-toolkit, где не нужно изгаляться.


            1. faiwer Автор
              23.11.2021 00:18
              +1

              Рад за них. Я чуть менее нормальныепрогрессивные продолжают писать ...-пирамидки.


              1. nsinreal
                23.11.2021 18:19
                +1

                Под капотом redux-toolkit используется immerjs, который можно подключить в отдельных местах. Оно конечно, делает некоторую деградацию по перфомансу, но это увеличение константны, а не асимптотики.


                1. faiwer Автор
                  23.11.2021 18:25
                  +2

                  Угу, я знаю. Я где-то 4 года назад написал собственную версию immerjs, просто потому что кто-то на хабре упомянул саму идею того, что при помощи proxy такое можно реализовать. А найти готовое решение мне не удалось. Оказалось несложно, но то и дело что-нибудь отваливалось (например так я познакомился со всякими хитрыми Symbol.*, о которых раньше либо не знал, либо забыл. В общем были свои tricky cases.


                  Об immer я узнал из уст одного из интервьюверов. Попросили рассказать что-нибудь интересное, я рассказал про этот solution, а мне в ответ — чувак, ты изобрёл велосипед. Держи immer ("всегда" по-немецки). Было даже немного обидно :-D


                  1. nsinreal
                    23.11.2021 20:58
                    +2

                    Мне было обиднее. Я пытался написать реализацию, довольно схожую, но с дополнительными идеями. В итоге я не смог, а потом вышел immer и у меня очень горело


      1. vkni
        23.11.2021 06:21
        +1

        Вы имеете ввиду не надо играть в immutability в языке, в котором для этого ничего нет?

        Ну в каждом языке есть свои выразительные средства, органичные для него. И если что-то влезает с огромным трудом, то может быть не надо?

        Функции высших порядков, кстати, всю жизнь работают в нечистых функциональных языках, вроде ML (SML, OCaml) или Scheme. Просто там как-то привыкли что да, могут появиться от неаккуратного использования примитивов разные странные штуки. Но в целом никаких особенных оптимизаций в том же Ocaml нет - компилятор отрабатывает за 0.5 сек даже большие файлы, всё просто и квадратно-гнездово. Это не GHC.


        1. 0xd34df00d
          23.11.2021 21:01
          +1

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


          А ещё бывает такое веселье.


  1. dom1n1k
    22.11.2021 19:20

    Меня с самого начала напрягал spread-оператор — вот этой соблазнительной и обманчивой внешней простотой. Сам-то оператор не виноват, но было понятно что многие начнут его совать везде, где можно и нельзя — что и подтвердилось потом на практике.


    1. faiwer Автор
      22.11.2021 19:27
      +6

      Со spread-оператором выяснилась (на десятках собеседований) интересная ситуация. Почти никто не знает, как он на самом деле работает. Я не шучу. И нет, я не про Symbol в прототипе.


      Я предпочитаю на code-interview не заставлять человека писать код, а подсовывать ему кусочки кода и смотреть на реакцию. Так вот — ПОЧТИ ВСЕ думают, что ... spread operator копирует объекты в глубину. Я не шучу. 8 из 10, наверное. Причём кандидаты на senior позицию.


      И нет, речь не про "ой, что-то я затупил, да, конечно, это работает не так". Мне несложно подсказать. Мне плевать если кандидат не ответил сразу правильно. Важно понять — человек в целом понимает что это и с чем это едят, или нет. А вот прямо делают удивлённое лицо и "ого, а я всегда думал что это полное копирование в глубину". И после всего этого уже я сижу с круглым лицом и думаю. Ну ок, положим ты и правда не знал этого до сего момента. Ну с кем не бывает. Но ведь ты наверняка уже пару сотен раз его использовал в своём коде (или тысяч). Не приходила в голову мысль "о боже я копирую большой объект в глубину, это должно быть охрененно долго"? :-) Видимо нет.


      1. sebres
        22.11.2021 21:00
        +1

         ПОЧТИ ВСЕ думают, что ... spread operator копирует объекты в глубину.

        Ну spread operator как бы вообще ничего не копирует (ни в глубину, ни на плоскости), это тупо expand arguments сахар (разворачавающий итерируемое и подменяющий apply и т.п.), вовсе не обязательно создающий shadow копию или новый список ссылок, если можно просто iterate & yield.

        Или вы про это вот?

        let clone_of_O = { ...O };
        let clone_of_A = [ ...A ];

        Неужели действительно находятся те кто думает, что результат будет "глубже" чем у того же assign или slice?!

        Т. е. понимания что на самом деле делает spread нет в принципе? Мой следующий вопрос был бы, а что в этом примере содержит b:

        a = [[1, 2, 3]]
        b = [a[0], a[0], a[0]]
        c = [...a, ...a, ...a]

        И если ответ будет 3 references of a[0], то что вдруг меняется для c, когда aтам просто тупо развернуто.


        1. faiwer Автор
          22.11.2021 21:09
          +2

          Или вы про это вот?

          Да, про него.


          Неужели действительно находятся те кто думает, что результат будет "глубже" чем у того же assign или slice?!

          Да, почти все.


          1. DSL88
            22.11.2021 22:41

            Соглашусь с вами: очень много людей думает, что они так копируют объект. Сколько уже исправлений этого мной написано - не пересчитать.

            Я пришёл в js из софта, потому такие ошибки часто бросаются в глаза.

            forEach недолюбливаю за невозможность остановки по break. Понятно, что есть every или some, но, как показывает практика, многие с такой конструкцией не знакомы


            1. JordanoBruno
              22.11.2021 23:17

              Вы будете смеяться, но серьезные такие ребятки из AirBnB .forEach вместо for() жестко насаждают через Policy. Причем факт того, что по break не выйти из итерации их никак не смущает.


              1. DSL88
                22.11.2021 23:34
                +1

                Для этого есть финты в виде every и some...Но все равно это кривость...

                Я, когда на сайте реакта читал о хуках и для чего они их сделали, жестко приуныл и уже тогда начать думать куда мылить лыжи из фронтенда: ползти в бакенд или уходить в С++ софт/игры...


                1. JordanoBruno
                  22.11.2021 23:39
                  -2

                  финты в виде every и some

                  Break позволяет чутка экономить время, в отличие от предлагаемых Вами финтов.

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


                  1. DSL88
                    22.11.2021 23:44

                    Break позволяет чутка экономить время, в отличие от предлагаемых Вами финтов.

                    это не я предлагаю, а они.


                  1. mayorovp
                    23.11.2021 00:07
                    +3

                    Справедливости ради, финты под названием every и some тоже позволяют экономить время.


                    1. nin-jin
                      23.11.2021 09:13

                      Выходить из нескольких уровней циклов с ними всё равно больно.


                    1. nin-jin
                      23.11.2021 22:02

                      Потому что я говорю не только о себе?


                1. nin-jin
                  23.11.2021 09:10

                  На $mol ползите, у нас такой ерунды нет.)


              1. antonkrechetov
                23.11.2021 00:14
                +2

                Вы будете смеяться, но серьезные такие ребятки из AirBnB .forEach вместо for() жестко насаждают через Policy. Причем факт того, что по break не выйти из итерации их никак не смущает.
                А какое обоснование? в чем плюсы?


                1. faiwer Автор
                  23.11.2021 00:22

                  Скорее всего консистентность кодовой базы. Чтобы каждый не лез кто в лес, кто по дрова выбрали что-то одно. Да и в целом нынче такой тренд, мол for ;; слишком "сложный". Кажется в swift от него вообще отказались, оставив только for in .. и итераторную версию.


                1. JordanoBruno
                  23.11.2021 00:22

                  Вот тут у них написано.

                  Вкратце:

                  Why? This enforces our immutable rule. Dealing with pure functions that return values is easier to reason about than side effects.


                  1. mayorovp
                    23.11.2021 02:08
                    +3

                    Только вот фокус в том, что как раз цикл for-of можно использовать для построения той самой pure functions that return values, в то время как forEach уже сам по себе основан на сайд-эффектах.


                    1. JordanoBruno
                      23.11.2021 02:16

                      На самом деле что у for, что у .foreach side-эффектов не так уж и много. Более того, я использую их оба и не вижу какого-либо реального препятствия, почему нужно выбрать один из них. Я лишь привел этот пример, как даже в больших компаниях и весьма опытные товарищи могут легко заблуждаться.


                  1. some_x
                    23.11.2021 12:49

                    В общем "функциональность головного мозга". Мне один такой пациент с похожим обоснованием пытался запретить использовать let и var.


                    1. JordanoBruno
                      23.11.2021 13:22
                      +2

                      var-то правильно, а let видать за компанию? Тоже встречал такого, правда там вопрос решился проще, я был главным и защитил "let" :). Правда оставил товарищу возможность писать с "const", очень уж упертый был, ну а политика по коду у меня весьма мягкая в предпочтениях.


            1. JSmitty
              23.11.2021 00:16
              -1

              справедливости ради конструкция вида { ... obj } действительно делает поверхностную копию объекта


              1. sebres
                23.11.2021 17:31
                -1

                справедливости ради конструкция вида { ... obj } действительно делает поверхностную копию объекта

                Ну вот первый кандидат на "учить мат-часть"...

                Нет, не делает... Она создает новый объект, и передает в него spreaded итератор в виде "списка" object literal аргументов aka key-value pairs...

                Т.е. вот эти вот выражения практически эквивалентны в плане нативного исполнения (и последнее не создает никакой копии напрямую):

                r = { height: 10, width: 20 };
                r = Object.assign({}, r);
                r = { ...r };

                Т.е. такой flat clone (без prototype) просто короткая альтернатива Object.assign(). И его же и вызывает кстати, а не то, что вы себе там придумали...

                PoC на коленке:

                > class Rect { constructor(h, w) { this.height = h; this.width = w; } };
                > r = new Rect(10, 20); r
                Rect {height: 10, width: 20}
                > r2 = {...r}; r2
                { height: 10, width: 20 }
                > r instanceof Rect
                true
                > r2 instanceof Rect
                false


                1. faiwer Автор
                  23.11.2021 17:39
                  +3

                  Вы, кажется, говорите об одних и тех же вещах, но разными словами.


                  Она создает новый объект, и передает в него spreaded итератор в виде "списка" object literal аргументов aka key-value pairs...

                  Вы только что описали один из способов сделать shallow object copy. Та самая "поверхностная" (shallow) копия объекта.


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


                  Но… это уже нюансы. Концептуально поведение объекта по-умолчанию — создать его shallow копию.


                  1. sebres
                    23.11.2021 17:53
                    -1

                    Только человек мне ниже написал, что можно вызвать spread для неитерируемого. Из чего был сделан вывод, что понимания как spread работает в принципе - нет.


        1. JSmitty
          23.11.2021 00:23

          Ну spread operator как бы вообще ничего не копирует (ни в глубину, ни на плоскости), это тупо expand arguments сахар (разворачавающий итерируемое и подменяющий apply и т.п.)

          Объект в общем случае (для object spread) не обязан быть итерируемым, чтобы к нему можно было применить object spread. Для использования в контексте списка значений - да, обязан.


          1. sebres
            23.11.2021 17:38
            -1

            Нет! Обязан (ибо он работает не так как вы себе представляете).
            Попробуйте передать туда неитерируемый объект, или переопределите его iterator, чтобы он выкидывал исключение. Я вас уверяю вы его (исключение) обязательно поймаете.


          1. sebres
            23.11.2021 18:05
            +2

            Посыпаю голову пеплом и выражаю глубочайшие извинения ув. @JSmitty

            Только что написал в консоль {...10} и оно создало мне пустой объект... Хотя я мог бы поклясться, что уже делал такое как-то и оно вылетало с ошибкой. Возможно Object.assign переделали с той поры... или это просто старость.

            Еще раз прошу прощения если кого ввел в заблуждение.


            1. mayorovp
              23.11.2021 18:30
              +2

              Потому что {...obj} и [...seq] — это разные конструкции, и работают они по-разному. Как раз вторая и требует итератор, который можно переопределить и т.п.


              А первая просто копирует перечислимые собственные свойства объекта, независимо ни от чего. Переопределить тут можно разве что Proxy подсунув.


            1. RAX7
              23.11.2021 18:33

              Вероятно вы перепутали работу spread оператора для объектов и массивов. Для массивов требуется рабочий Symbol.iterator, для объектов - нет (его у них и нет)

              ({})[Symbol.iterator] // -> undefined
              ([])[Symbol.iterator] // -> values() { [native code] }


              1. sebres
                23.11.2021 21:53

                Я знаю что [Symbol.iterator] у объектов нет, просто когда (в proposal ES2018 если не ошибаюсь) речь велась про object literals, это определялось как "pass all key:value pairs from an object", что и подтверждает пример вроде:

                > let o1 = { x: 1, y: 2 };
                  let o2 = { x: 42, z: 3 };
                  let o3 = { ...o1, ...o2 }; o3
                
                < {x: 42, y: 2, z: 3}

                Иначе бы такая merge конструкция не очень работала, по крайней мере с assign такое нельзя (там только два аргумента - target и source)... И я готов был поклясться, что assign не работал для неитерируемых... Что они уже после ES2018 накрутили, чтобы даже скалярный объект воспринимался как валидный, мне не очень понятно (как и для чего это собственно есть нужно и хорошо). Для меня это выглядит как жуткий баг/хак (UB на худой конец), но то такое...
                JS, слава богу, не мой язык - я его пользую (вынужден) только поскольку без оного в браузерах никуда (к моему большому сожалению). Во всех же других языках "Object" (aka keyed collections, dictionaries, maps или associative arrays) вполне себе iterable (или как минимум enumerable) и никакого ментального диссонанса при использовании spreading / expanding операторов не возникает, даже если по умолчанию оно за бортом и реализовано с помощью тех же assign-подобных конструкций (чтобы, производительности ради, не разворачивать списки от дефолтных "итераторов" в стек).


                1. mayorovp
                  23.11.2021 22:06

                  просто когда (в proposal ES2018 если не ошибаюсь) речь велась про object literals, это определялось как "pass all key:value pairs from an object"…

                  …что как раз и означает взятие всех перечислимых собственных свойств объекта. Если что, перечислимость свойств — куда более древнее понятие, нежели Symbol.iterator. Собственно, оно древнее символов.


                  по крайней мере с assign такое нельзя (там только два аргумента — target и source)

                  Э-э-э, но ведь у assign можно указать произвольное число аргументов!


                  Что они уже после ES2018 накрутили, чтобы даже скалярный объект воспринимался как валидный, мне не очень понятно

                  А почему он, собственно, не должен восприниматься как валидный, если spread operator в контексте литерала объекта изначально создавался для работы со скалярными объектами?


                1. RAX7
                  24.11.2021 12:44
                  +1

                  даже скалярный объект воспринимался как валидный

                  У примитивов нет свойств и методов https://javascript.info/primitives-methods , поэтому если сделать "pass all key:value pairs from an object", то получим в результате пустой объект. В этом нет ничего противоречивого, хотя с непривычки может выглядеть странно.

                  Во всех же других языках "Object" (aka keyed collections, dictionaries, maps или associative arrays) вполне себе iterable

                  Всё же object и collections, dictionaries, maps разные типы. Оbject является базовым для всех них, но итерабельным эти типы делает наличие специальных методов/свойств реализованных в этих типах.

                  Возьмем в к примеру C#

                  object o = new { Name = "John", Age = 21 };
                  foreach (var item in o) { }
                  // Error CS1579  foreach statement cannot operate on variables
                  // of type 'object' because 'object' does not contain a public instance
                  // or extension definition for 'GetEnumerator'

                  Есть некий объект с анонимным типом, который привели к базовому типу object, но для итерации требуется наличие метода GetEnumerator. Так же и в JavaScript объект - это всего лишь базовый тип, а то, что его используют как словарь/ассоциативный массив так это только потому, что в js изначально не было специальных типов для коллекций.


      1. nin-jin
        23.11.2021 09:07

        По спредам, кстати, можно в статью добавить, что если передача массива в функцию - константная сложность, то передача элементов через спред - это уже линейная, ибо компилятору проходится копировать массив в стек. Соответственно, получаем ещё и риск переполнения стека.


  1. anonymous
    00.00.0000 00:00


  1. anonymous
    00.00.0000 00:00


    1. Ritan
      22.11.2021 19:33
      +3

      Вся проблема в вайтишниках


  1. maximzhukov
    22.11.2021 19:30
    +3

    Сама статья является хорошим напоминаем помнить об алгоритической сложности кода который вы пишите, но ни reduce ни destructuring assignment сами по себе не дают вам O(n^2). Есть тысяча и один способ написать код неэффективно.


    1. faiwer Автор
      22.11.2021 19:42

      по себе не дают вам O(n^2)

      Как кстати, такие вещи более точно посчитать? И как записать? Умом то я понимаю, что "чистый квадрат" был бы если бы и на первых итерациях было N операций. Получается что это O(((1 + N) ^ N) / 2). Но какая-то шибко мудрёная запись. Кажется в пределе получается O((N^2) / 2), что по сути эквивалентно O(N^2)


      Есть тысяча и один способ написать код неэффективно.

      Но больше всего мне "краше" именно этот. Потому что его прямо пропихивают из каждого утюга. По сути это становится стандартом жанра.


      upd.


      но ни reduce ни destructuring assignment сами по себе не дают вам O(n^2)

      Кажется я не сразу вас понял. Я подумал вы про то, что я неправильно BigO посчитал. А вы имели ввиду то, что по отдельности они O(n) и не страшны? Да, согласен. Нормальные инструменты. Ничего против не имею.


      1. maximzhukov
        22.11.2021 20:15

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


      1. mayorovp
        22.11.2021 22:19
        +2

        Получается что это O(((1 + N) ^ N) / 2). Но какая-то шибко мудрёная запись.

        Наверное, вы O(((1 + N) * N) / 2) имели в виду, а не возведение в степень и не xor.
        Так вот, O(((1 + N) * N) / 2) строго равно O(N ** 2), причём это верно в обе стороны.


        1. faiwer Автор
          22.11.2021 22:21
          +1

          Да, конечно, спасибо. Немного спешил и получилась ерунда, я имел ввиду * N. Это формула суммы членов арифметической прогрессии.


          1. Medeyko
            22.11.2021 23:27
            +1

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

            Учитывая, что 1 <= N выполняется для всех натуральных N:

            \frac {(1 + N) N} 2 \le \frac {(N + N) N} 2 = \frac {2 N^2} 2 = N^2

            Это в одну сторону. А в другую, учитывая, что 0 <= N выполняется для всех натуральных N:

            N^2 = 0 + N^2 \le N + N^2 = (1 + N) N = 2 \frac{(1 + N) N} 2 = C \frac{(1 + N) N} 2

            Т.е. с точностью до константы, как подразумевает О-нотация. (C = 2)


      1. aamonster
        22.11.2021 23:02
        +1

        O(n) + O(1) == O(n). Большее слагаемое поглощает меньшее.

        O(n*2) == O(n). Константный множитель неважен.

        Можете теорию почитать, но на практике достаточно этого (и памяти, что все эти O – только при n стремящемся к бесконечности)


        1. faiwer Автор
          22.11.2021 23:05

          Разве я не тоже самое написал? :) (если учесть опечатку с ^ вместо *)


          1. aamonster
            22.11.2021 23:31
            +3

            На итог то же самое. Просто коммент создал ощущение какой-то неуверенности в том, как работать с O(...), вот и позволил себе напомнить несложные правила их упрощения. Извиняюсь, если задел.


            1. faiwer Автор
              23.11.2021 00:15

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


              1. vkni
                23.11.2021 06:34

                Да там первые 50 страниц Уиттекера Ватсона. Очень просто всё.


                1. aamonster
                  23.11.2021 16:02

                  Не оверкилл?
                  А за упоминание книги спасибо, возможно, пора освежить в памяти матан, и она как раз подойдёт.


                  1. vkni
                    23.11.2021 17:40

                    Да нет, не оверкилл. Это же проходят все студенты по тех. специальностям. Зато после нормального курса по рядам все эти интервьюшные задачи O(N) вызывают лишь один вопрос - "а проблема-то, собственно, в чём?".


                    1. aamonster
                      23.11.2021 17:47

                      Не, ну так-то для себя лишним не будет, конечно. Я имел в виду – для такой задачки нет "математической" сложности в подсчёте, сложность только в наработке рефлексов типа "а вот тут ещё внутренний цикл вылезает, надо не забыть его учесть".


                    1. 0xd34df00d
                      23.11.2021 21:03
                      +1

                      Бывают алгоритмы, где для более точной оценки надо брать всякие интегралы (и там тогда видно, что алгоритм n logn, а не n²). Это уже не так очевидно.


                      1. vkni
                        23.11.2021 23:26

                        Бывают варианты, когда обыкновенные диффуры надо решать (метод, описанный у Кнута в "Конкретной математике" и у Седжвика на Курсере) :-). Но без хорошей базы в виде семестра-двух банального матана (пределы, последовательности, ряды и асимптотики) про сложность алгоритмов лучше вообще не заикаться.


                      1. csl
                        23.11.2021 23:33

                        А, например, в "Алгоритмах" Кормена (если читали) есть о диффурах?


                      1. vkni
                        23.11.2021 23:38
                        +1

                        Диффуров там точно нету.

                        Я может быть ошибаюсь, и уже не помню, но эта книжка мне показалась именно переусложнённой из-за того, что рассчитана на студентов, не изучавших нормально матан.


      1. vkni
        23.11.2021 06:30
        +2

        Если вы хотите считать точно, то вам нужно

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

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

        По второму пункту есть отличный курс профессора Cеджвика - https://www.coursera.org/learn/analytic-combinatorics

        Но он требует ТФКП (теория функций комплексной переменной), а именно - теории вычетов + курс по Обыкновенным Дифференциальным Уравнениям.


  1. RiverFlow
    22.11.2021 22:39
    -19

    ну вы и душнилы...


  1. JordanoBruno
    22.11.2021 23:10
    -7

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

    Настоящей - это какой? Так-то nodejs даже на embedded-системах запускают. А во-вторых, есть вполне себе возможности выполнить родной бинарный код через C/C++/WASM, который очень все быстро посчитает, если надо.

    Большинству разработчиков даже особо задумываться не приходится нынче, настолько производительные системы и V8 на текущий момент. Вот раньше было да, на iPhone 3G, если не ошибаюсь, был лимит в 256 Кбайт на страницу, там приходилось аккуратно писать, с учетом перформанса и расхода памяти.


    1. mayorovp
      23.11.2021 00:08
      +4

      А во-вторых, есть вполне себе возможности выполнить родной бинарный код через C/C++/WASM, который очень все быстро посчитает, если надо.

      Но ведь это и называется "не предназначен для решения задач, которые требуют настоящей производительности"


      1. JordanoBruno
        23.11.2021 00:28
        -2

        Если бы был не предназначен, то не было бы 1100+ модулей, использующих C/C++: https://www.npmjs.com/package/node-gyp?activeTab=dependents

        И это только то, что в npm.


    1. faiwer Автор
      23.11.2021 00:24

      WASM

      Мой небольшой опыт показывает, что WASM как раз быстро вам не посчитает. У нас получалась 10 кратная разница в сравнении с бинарником.


      1. JordanoBruno
        23.11.2021 01:09

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


        1. faiwer Автор
          23.11.2021 01:13

          Это был алгоритм SHA1 который прогонял через себя сотни тысяч коротки строчек (примерно по 50 символов). Написан на C, скомпилирован через empscripten. Других деталей дать не могу, увы, ибо NDA. Asm.js версия в chrome была равна по скорости WASM.


          Полагаю, что очень опытный системный программист смог бы всё отладить и переписать так, чтобы обойти все трудоёмкие для WASM-машины места. Но это не я, я не настоящий сварщик. То что я смог это всё собрать и запустить — уже удача :)


          1. JordanoBruno
            23.11.2021 01:21

            В бенчмарке по моей ссылке тестируется SHA256.


          1. nin-jin
            23.11.2021 09:22

            Если строчки из js приходят, то ничего удивительного - их приходится сериализовывать в нужное бинарное представление, чтобы в васм передать.


            1. faiwer Автор
              23.11.2021 11:06

              Нет. Строчка всего одна. Остальные сотни тысяч производятся уже на стороне WASM-а.


  1. souls_arch
    23.11.2021 00:24
    -3

    В 1ом пункте сами же все сказали: при малых n разницы никто не видит . И возможные проблемы верно указали. Но основная мощь стримов и лямбд именно в поддерживаемости кода и лучшей читаемости. Понятно, что потом до кода может добраться безголовый джун, но сташие не дадут и заставят переделать. А умный и опытный городить огород на таких конструкциях не станет.


    1. faiwer Автор
      23.11.2021 00:29
      +5

      Ну дык никто не запрещает вам мутировать аккумулятор в лямбде. И волки сыты, и овцы целы. Разве что внутренний перфекционист может немного негодовать, что идеалы попёрты и семантика искажена. Но лучше бы этот внутренний перфекционист переживал за более насущные проблемы, относящиеся к business value.


      А умный и опытный городить огород на таких конструкциях не станет

      Повторюсь, этот "паттерн" стал НАСТОЛЬКО популярен, что лезет изо всех щелей. Люди вообще не видят в этом проблемы. И такой код уходит в прод. А потом у людей "react тормозит". Хотя тормозят они, кажется, сами.


  1. antonkrechetov
    23.11.2021 00:28
    +3

    Я считаю, корень проблемы — в дизайне стандартной библиотеки. Как раз на такой случай должен быть модифицирующий метод для объединения массивов, который ведет себя, как concat(), но меняет массив и возвращает его же. Да, объединять массивы можно с помощью push() или splice(), но оба этих метода:
    1. Не возвращают сам массив, из-за чего их неудобно использовать.
    2. Это не самые очевидные функции для объединения массивов. Не уверен, что все помнят, что push() принимает произвольное количество параметров. В то время, как concat() — «сертифицированный» аутентичный способ.

    Собственно, все эти npm-пакеты из одной функции тоже намекают, что в библиотеке есть, что улучшать.


  1. emaxx
    23.11.2021 00:31

    Примеры красивые, но есть какие-нибудь данные о том, насколько часто "квадраты" в реальном коде возникают в таких "локальных" ситуациях - т. е. когда весь относящийся к "квадрату" код представляет собой несколько строк кода внутри одной функции?

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

    И тогда может оказаться, что оптимизация работы отдельных .map()/.reduce()/и т. п. - это просто экономия на спичках, потому что настоящее бутылочное горлышко будет в других, менее очевидных местах. В таком случае чрезмерный акцент на этих локальных оптимизациях как не даст ощутимого прироста в производительности, так и, возможно, увеличит вероятность багов из-за менее читаемого кода.


    1. faiwer Автор
      23.11.2021 00:40
      +1

      Статистики нет. Не уверен что кто-то вообще такие вещи собирает и анализирует. Всем надо фичи в прод доставлять. Но для меня давно очевидно, что, при прочих равных, лучше писать такой код, который гарантировано не вызовет проблем в будущем (на всякий случай повторю — при прочих равных). Ведь в будущем вы просто переиспользуете готовый рабочий, возможно даже протестированный, механизм, не вникая во все его нюансы изнутри (потому что на это нет решительного никакого времени, читать эти тыщи строк кода). Примерно прикините: ну тут нечему тормозить, потому что оно под капотом должно делать А, B & C. А оно на самом деле делает (AA + BB) * C, потому что разработчику этого хватало на его "кошках" в дев-режиме. Что самое печальное, возможно и вам этого хватит. А вот конечный юзер уже взвоет. Его жалоба дойдёт до вас через полгода. Сколько денег за это время упустит бизнес?


      И при всём при этом речь идёт об одной строке кода, необходимость которой, очевидно ещё до её написания. Нелепая ведь ситуация. Речь ведь не об "перемудрёной архитектуре" или "сложном алгоритме", который требует кучу времени на реализацию и поддержку. Просто… одна… строка… кода.


      Живой пример. Есть такая библиотека для тестирования react-компонент — enzyme. Я использовал её для одного средних размеров проекта. В какой-то момент я понял что мои тесты непозволительно тормозят, там где этого ну категорически быть не должено. Там ведь тупо нечему тормозить. Оказалось ребята из airbnb (кажется) смогли сделать обход дерева в ширину за O(n^2) (или даже хуже). Я monkey-patch-ул метод простой наколеночной реализацией и всё залетало. С тех пор я опасаюсь пользоваться их npm-пакетами.


      1. emaxx
        23.11.2021 00:59

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

        Но ведь в реальности обычно по-другому, и нет "белого" или "чёрного". Разработчик работает с километрами кодовой базы, в которой то тут, то там спрятаны квадраты. И какие-то поправить совсем легко, какие-то посложнее, а для каких-то потребуется уже отдельный мини-проект. Копья в code-review будут ломать как раз вокруг этого случая "посложнее", когда ускорение кода возможно путём некоторой потери читабельности или, скажем, расширяемости. Практический толк от каждой из таких оптимизаций будет, скорее всего, мизерным - до тех пор, пока в коде остаются другие квадраты.


        1. faiwer Автор
          23.11.2021 01:09
          +1

          какие-то посложнее, а для каких-то потребуется уже отдельный мини-проект

          Всё так. Но данная статья про один (ну ок два) конкретных use-cases. Ни больше, ни меньше. Я не продвигаю тут идею, что за BigO надо стоять горой и слать всех коллег на три буквы. Всегда и везде есть конкретные обстоятельства, в которые нужно вникать.


          Практический толк от каждой из таких оптимизаций будет, скорее всего, мизерным — до тех пор, пока в коде остаются другие квадраты.

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


          Например я не призываю отказываться от регулярных выражений. Хотя если переписать вручную почти все места их использования в типовом приложении оно только выиграет по производительности. Но сильно проиграет по цене разработки. К тому же вполне вероятно эта победа по скорости никем не будет замечена. Скажем какой смысл писать руками сложный валидатор на имя пользователя, если это можно сделать одной строкой. У меня есть знакомые программисты, которые никогда не пишут регулярок, потому что "они медленные". Я их не понимаю. Каждому инструменту своё применение.


          1. Alexandroppolus
            23.11.2021 02:24

            Регулярки регуляркам рознь. Некоторые работают за линейное время (от длины строки), без возвратов, и вряд ли можно заменить их на код более быстрый; а иные - за экспоненциальное время, если написать по-дурацки. Хотя тут опять же от движка зависит. Сафари меня удивил, он умеет плохие реги разрулить.


            1. aamonster
              23.11.2021 16:10

              Плохие – это какие?
              В смысле, это всё ещё регулярные выражения, просто "неудобные" для рекурсивного алгоритма (но нормально обрабатываемые Thompson's construction)? Или нечто с backreferences, что, вообще говоря, не является регулярным выражением, просто впихнуто в их синтаксис?


              1. Alexandroppolus
                23.11.2021 16:26
                +1

                это всё ещё регулярные выражения, просто "неудобные" для рекурсивного алгоритма (но нормально обрабатываемые Thompson's construction)?

                Скорее всего они самые.

                Вот тут неплохо раскрыто: https://learn.javascript.ru/regexp-catastrophic-backtracking


                1. aamonster
                  23.11.2021 17:15

                  Ага. Первый случай, да: нет ни единой осмысленной причины им так медленно работать (ну, кроме того, что авторы движка не читали теорию регэкспов). Прямо-таки иллюстрация по теме статьи, только гипертрофированная, вместо жалких квадратов – экспонента.


                  1. Alexandroppolus
                    23.11.2021 19:28

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


        1. Fragster
          23.11.2021 16:20
          +5

          до тех пор, пока в коде остаются другие квадраты.

          Странный это был отдел. Лозунг у них был такой: «Познание бесконечности требует бесконечного времени». С этим я не спорил, но они делали из этого неожиданный вывод: «А потому работай не работай - все едино». И в интересах неувеличения энтропии Вселенной они не работали.


      1. mrsantak
        23.11.2021 11:21
        +6

        Оказалось ребята из airbnb (кажется) смогли сделать обход дерева в ширину за O(n^2) (или даже хуже). 

        Пфффф, вообще фигня. Мы пару месяцев назад нарвались на багу, из-за которой coursier (он у нас в билд системе используется для выкачивания зависимостей) при билде падал в ООМ. Ему около 50 гигов оперативки стало требоваться для построения репорта в json формате. Как выяснилось там ребята как раз посчитали, что метод + у списка должен обновлять существующий список, а на деле он создавал новый. Как результат у них алгоритм обхода дерева в глубину начал обходить граф по всем возможным маршрутам в графе. А там уже что-то околоэкспоненциальное вылезает. При этом они там умудрились этот алгоритм еще и по нескольким местам раскопировать в коде.


  1. JordanoBruno
    23.11.2021 02:30
    -4

    Люди на собеседованиях не видят никакой проблемы в вызове .includes внутри .filter и подобных штуках.

    Меня больше пугает, что есть люди, которые видят в этом какие-то проблемы. По-моему весьма глубокому опыту, проблемы с производительностью возникают из-за неверно выбранной архитектуры как софта, так и баз данных. Как показывает практика, один кривоватый запрос или неверная структура базы могут поставить жирнющий такой крест на всех JS-оптимизациях. Или еще хуже - пачка запросов в цикле, иногда скрытых в ORM. Именно это мне приходилось часто исправлять за многими разработчиками, причем некоторые были весьма опытные. И на собеседованиях я спрашиваю, как кандидат умеет оптимизировать софт по производительности, это многое показывает и рассказывает получше любых тестов. А если уж алгоритмы в JS начинают тормозить, то есть отличный вариант - вынести его в микросервис, написанный на чем-то быстром, либо вшить нативный/wasm кусок.


    1. Alexandroppolus
      23.11.2021 02:54
      +8

      А если уж алгоритмы в JS начинают тормозить, то есть отличный вариант - вынести его в микросервис, написанный на чем-то быстром, либо вшить нативный/wasm кусок.

      Сначала поправить асимптотику до оптимальной. А там, глядишь, и не надо будет возиться с нативщиной. Сабж о том, что незачем на ровном месте делать n^2 вместо n.


    1. faiwer Автор
      23.11.2021 11:14
      +1

      Судя по вашему комментарию вы про nodeJS backend (SQL, ORM, micro-services). Там своя специфика. Вы там не сталкиваетесь с описываемой мною проблемой, потому что на backend стороне никто не играет в immutability. Вот вам и кажется что проблема надуманная.


      1. JordanoBruno
        23.11.2021 13:09
        -4

        Вы там не сталкиваетесь с описываемой мною проблемой

        Я бы так сказал - важность проблемы сильно преувеличена. Намного чаще встречаются на фронте другие ошибки в архитектуре, от которых производительность проседает весьма заметно. Как пример могу привести npm модуль react-dates от той же компании AirBnB. На всякий случай напомню, что это виджет с массой фич по выбору дат, периода дат, отображения календаря и т.д. Там постоянно народ жалуется, что виджет подтормаживает, например, вот. Проблем с производительностью там масса и корни разные, я даже изучал эту проблему внимательно, хороший кейс. Как Вы наверное догадались, проблемы не связаны с теми, которые Вы описали. Не буду раскрывать заранее карты и оставляю Вам возможность изучить реальные причины проблем с производительностью в React-проектах. Может напишете еще одну статью :).


        1. faiwer Автор
          23.11.2021 13:30
          +5

          Я бы так сказал — важность проблемы сильно преувеличена

          Можно пример преувеличений с моей стороны?


          от той же компании AirBnB

          Похоже это уже не случайность, а закономерность


          оставляю Вам возможность изучить реальные причины проблем с производительностью в React-проектах

          Пройденный этап? Да я в состоянии написать цикл статьей про архитектурные проблемы React SPA. Но мне лень — это очень большой объём работ.


          А теперь главное. О чём статья:


          • есть проблема
          • может быть критичной, может не быть
          • очень широко распространена
          • потому что огромный процент обучающих материалов повторяют эту ошибку
          • она элементарно избегается ещё на стадии написании кода и не относится к preliminary optimizations
          • ей подвержены разработчики самых разных уровней
          • её лёгко продемонстрировать, её легко объяснить

          Вышестоящего по вашему не достаточно для того чтобы привлечь к этому внимание?


          Нет ну так то я могу написать и статью про "Обращение к Javascript сообществу: перестаньте выполнять сетевые запросы последовательно" и многие другие. Это как-то отменяет необходимость конкретно этой статьи?


          P.S. мне стыдно за JS сообщество, что приходится объяснять что O(n^2) вместо O(n) это плохо, а когда разница заключается в одной строке, это прямо позорно.


          1. faiwer Автор
            23.11.2021 14:01
            +9

            JordanoBruno вопрос. Я тут подумал… А если я напишу статью про вредные последствия последовательных сетевых запросов вместо параллельных, вы не напишете что-нибудь вроде:


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

            Вы не будет отстаивать позицию, что сразу писать await Promise.all вместо серии await это предварительная оптимизация, а внимание стоит уделять более серьёзных архитектурным факапам?


            Или если я напишу статью про "не запрашивайте записи из РСУБД по ID по одной, сделайте это в одном запросе", вы не скажете, что я перегибаю палку, т.к. существуют более серьёзные архитектурные проблемы, и если latency к СУБД меньше 2мс то никто не заметит разницы в производительности? И что вообще есть же кеширование, так что проблема не так ярко выражена, и лучше написать статьи про более серьёзные проблемы.


            А если я напишу статью про "умоляю, начните валидировать данные пришедшие с клиента"? Не появятся комментарии про "ну безопасность надо гарантировать на всех слоях приложения, а не только на уровне валидации\санитации\whatever"?


            Я просто всё никак не могу взять в толк, откуда такое яростное сопротивление (не только у вас), в очевидно косячном куске частотного кода, который сверх-тривиально фиксится и должен был быть так написан с самого начала.


            1. JordanoBruno
              23.11.2021 14:08
              -1

              А если я напишу статью..

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

              Я просто всё никак не могу взять в толк, откуда такое яростное сопротивление

              Нет никакого яростного сопротивления, о чем Вы? Я лишь к тому, что описанная Вами проблема не критичная для большинства, да и проблемой не является вобщем. Это как красить двери у покосившегося дома.


              1. faiwer Автор
                23.11.2021 14:27
                +10

                Есть масса случаев, когда те же последовательные запросы выгоднее параллельных

                Пример? Сразу даю вводную: браузер, latency=1000ms. Я весь во внимании. Любые примеры про пул-запросов отбрасываю (т.к. там есть параллельные запросы).


                Это как красить двери у покосившегося дома.

                Спасибо за пример. На нём хорошо видно в чём проблема. Итак, дано:


                • покосившийся дом
                • некрашеные обшарпанные двери

                Правильное решение:


                1. срочно исправляем проблему с каркасом дома
                2. красим дверь, покрываем лаком
                3. При постройке новых домов — нанимаем адекватного архитектора, чтобы дом проблем с каркасом не возникло
                4. Малярам выдаём более качественную долговечную краску и не забываем про лак

                Решение от JordanoBruno (то как я вижу вашу позицию):


                1. срочно исправляем проблему с каркасом дома
                2. дверь не красим, т.к. это не проблема. Нет ну правда. Вот покосившийся дом это проблема, да. А дверь… эх, вот дом вспомните, кривой какой был! Ух вот это была проблеееема. Да что вы пристали ко мне с этой дверью? Идите лучше ещё один дом постройте. А я вам потом отзыв оставлю.


          1. JordanoBruno
            23.11.2021 14:25
            -4

            Можно пример преувеличений с моей стороны?

            Пожалуйста:

            замедляет программу

            Очень не значительно, по сравнению с другими ошибками в архитектуре

            т.к. Javascript однопоточный - препятствует работе пользователя с UI

            Чтобы препятстовать работе пользователя, это должны быть заметные лаги, то есть 0.2 сек. и более. Это ж какие алгоритмы и объем данных должны ворочаться? Вы так уверены, что большинство с таким сталкивается? Я что-то сомневаюсь.

            тратит батарейку ноутбука или телефона на бесполезную работу
            греет ваше устройство и заставляет работать кулер

            Крайне незначительно по сравнению с тремя десятками открытых табов. И уж кулер точно не из-за "reduce" работает.

            Но мне лень — это очень большой объём работ.

            Никто ж не говорит, что нужно писать сразу про ВСЕ проблемы разработки в React. Выберите самую популярную причину тормозов БОЛЬШИНСТВА проектов React. Я думаю, это будет очень интересно всем разработчикам.

            Нет ну так то я могу написать и статью про "Обращение к Javascript сообществу: перестаньте выполнять сетевые запросы последовательно" и многие другие. Это как-то отменяет необходимость конкретно этой статьи?

            Не отменяет, Вы можете писать о чем хотите, это ж Хабр.

            P.S. мне стыдно за JS сообщество, что приходится объяснять что O(n^2) вместо O(n) это плохо

            Это весьма очевидные вещи, но практически никак не влияющие на конечный результат. Именно поэтому большинство разработчиков особо не парится по этому поводу.

            Скажем так, когда-то давно я тоже уделял этому время и удивлялся, как это люди допускают такие неэффективные(по-моему мнению) конструкции, ведь можно писать более эффективно. Но потом со временем и опытом понимание пришло - влияние на результат крайне небольшое и большинству заказчиков вообще все равно, будет ли ПО работать в два раза быстрее или два раза медленнее. Потом я побывал на стороне заказчика и понял, что действительно, такие оптимизации особо не влияют на результат. Такая вот правда жизни.


            1. Drag13
              23.11.2021 14:32

              Простите что вмешиваюсь, но

              Это ж какие алгоритмы и объем данных должны ворочаться? Вы так уверены, что большинство с таким сталкивается?

              Тут не всегда проблема с алгоритмами. Бюджетные модели (особенно телефонов) могут иметь такие проблемы. Вот про это https://habr.com/ru/post/564950/


            1. faiwer Автор
              23.11.2021 14:42
              +2

              Очень не значительно, по сравнению с другими ошибками в архитектуре

              1. Значительность зависит от конкретного кейса.
              2. Наличие ошибок в архитектуре не отменяет существования других ошибок

              Выберите самую популярную причину тормозов БОЛЬШИНСТВА проектов React.

              Я открыл ваш профиль и не вижу ни одной такой статьи. Что-то не сходится.


              но практически никак не влияющие на конечный результат

              Неправда. Это зависит от конкретного сценария. Асимптотические ошибки легко приводят к проблемам. Я уже неоднократно с этим сталкивался. Я даже привёл несколько примеров в этой теме. Причём для программиста они могут проявиться весьма неожиданно. Самое худшее — когда это приводит к финансовым потерям (поиск по слову Ikea).


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

              С моей колокольни это не так: большинство разработчиков НЕ ЗНАЕТ как это работает. Мой опыт проведения собеседований прямое тому свидетельство.


              Такая вот правда жизни.

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


              P.S. у меня тоже богатый опыт. И вообще нас тут таких много (это ж хабр). Не стоит писать об этом в каждом 2-м комментарии ;)


              1. JordanoBruno
                23.11.2021 15:16
                -2

                Я открыл ваш профиль и не вижу ни одной такой статьи. Что-то не сходится.

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


                1. faiwer Автор
                  23.11.2021 15:22
                  +5

                  Ну а что вы хотели? Я написал статью, которая будоражит мой мозг, которую я считаю очень важной для подрастающего поколения JS-разработчиков. Приходите вы с бинарными мышлением ("всё что приложение не убивает не существует") и с аргументами вида "лучше бы вы писали статью про что-нибудь важное" и "меня пугает что кто-то считает это важным". А когда я предположил что подобную критику я встречу, даже если напишу другие статьи (вроде последовательных api-запросов), я получил аргумент "ну ты напиши, а я, сделаю, так уж и быть, доброе дело, почитаю и покритикую". Вам не кажется что кто-то немного дерзит? ;) Кто-то с "глубоким опытом" и комментариями ментора.


                  Какое-то показное неуважение.


            1. faiwer Автор
              23.11.2021 14:51
              +2

              Ой, я пропустил кое чего.


              Чтобы препятстовать работе пользователя, это должны быть заметные лаги, то есть 0.2 сек. и более

              • Я регулярно вижу в консоли warning-и о том что какой-то код не уложился в кадр.
              • Асимптотическим проблемам 0.2 сек вообще не рубеж. Проблемы с bigO это зачастую не конкретная строка, а сочетание нескольких методов (к примеру: медленный кусок кода прогоняется в цикле)
              • Если это внутри анимации то 0.2 это очень много

              Крайне незначительно по сравнению с тремя десятками открытых табов.

              Chrome гасит неактивные вкладки, если это возможно. Поэтому десятки открытых табов это больше проблема памяти.


              В целом я много раз натыкался на приложения которые соло выедают батарейку за кратчайшие сроки. Асимптотические проблемы, имхо, это один из главных кандидатов на эту роль. Но надо, конечно, разбирать каждый случай по отдельности. FAANG-и считают что это один из наиболее критичных навыков разработчика.


              1. BigBeaver
                23.11.2021 14:57
                +3

                Вы знаете, если в фоне двигать раздел или ядро компилировать, то эти ваши 0,2 секунды превращаются в 5 иногда. И если оно реально решается добавлением одной строки, то её надо добавить. Я понимаю, что время программистов дорогое и всё такое, но не настолько.


    1. BigBeaver
      23.11.2021 13:50
      +4

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


      1. JordanoBruno
        23.11.2021 13:56
        -3

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


        1. BigBeaver
          23.11.2021 14:30
          +4

          А преждевременная оптимизация — зло, как известно.
          Я не специалист по сабжу, но вы можете привести пример потенциальных проблем, вызываемых этой «оптимизацией»? Просто, по мне, она выглядит абсолютно бесплатной.


          1. JordanoBruno
            23.11.2021 14:47
            -4

            Дожили, разработчики уже не знают цитат классиков )).

            Как писал в свое время Дональд Кнут:

            Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

            Данное высказывание настолько известно и популярно, что мало кем оспаривается. Хотя мне больше нравится оно вот в таком виде:

            What Hoare and Knuth are really saying is that software engineers should worry about other issues (such as good algorithm design and good implementations of those algorithms) before they worry about micro-optimizations such as how many CPU cycles a particular statement consumes.


            1. BigBeaver
              23.11.2021 14:53
              +3

              Так я и не оспариваю это утверждение. С чего вы взяли обратное?
              Речь скорее о его применимости к сабжу, и вот полная цитата тут как раз скорее против вас, тк ни какого «waste enormous amounts of time thinking about, or worrying» тут нет. Это настолько же является «оптимизацией», насколько ей являются правила типа «всегда оборачивать тело if скобками», «писать default в switch», всегда экранировать строки и тд и тд. Понимаю, что примеры не являются полными аналогиями, но тем не менее.


              1. JordanoBruno
                23.11.2021 15:09
                -2

                Вы немного неверно поняли как Кнутовское высказывание, так и его интерпретацию. Смотрите, вот тут полная его статья, откуда это высказывание, страница(268), почитайте, там весьма интересно:

                http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6084&rep=rep1&type=pdf

                Надо понимать, что в 1974-м году программы исполнялись на весьма медленных процессорах и памяти там было с гулькин нос(по нынешним меркам), поэтому тогда скорость программы играла намного более существенную роль, так же как и расход по памяти. Но даже в те времена Кнут рассказывает, почему важно сначала написать программу, а потом уже ее оптимизировать(если потребуется и захочется). Про «всегда оборачивать тело if скобками» я вообще не понял, это не имеет отношения ни к статье, ни к кнутовскому высказыванию, чисто code style rules.


                1. BigBeaver
                  23.11.2021 15:16
                  +5

                  Не очень ясно, почему вы считаете, что я совсем ничего не читал и ничего не понимаю.

                  Про «всегда оборачивать тело if скобками» я вообще не понял, это не имеет отношения ни к статье, ни к кнутовскому высказыванию, чисто code style rules.
                  Это просто пример good practice аналогичный сабжу по трудоемкости. Ну то есть, написать лишнюю строчку из статьи не сильно труднее и не сильно дольше, чем нарисовать пару лишних скобок.
                  а потом уже ее оптимизировать
                  Я пытаюсь указать вам на то, что конкретное решение изначально обходится дешевле чем не только «оптимизация потом» но даже дешевле, чем создание тикета «попозже глянуть производительность».

                  Вас послушать, так можно и обход массива по столбцам вместо строк делать — потом оптимизируем, если что.


                  1. JordanoBruno
                    23.11.2021 15:36
                    -1

                    Вас послушать, так можно и обход массива по столбцам вместо строк делать — потом оптимизируем, если что.

                    Эх, а я раньше считал, что у меня получается аргументированно пояснять свою точку зрения. Ну ладно, отвечу словами военного из известного мема: "На этом наши полномочия всё".


            1. faiwer Автор
              23.11.2021 15:03
              +7

              Дожили, разработчики уже не знают цитат классиков

              Да знаем мы её. И да она нам осточертела. Но не потому что плоха, а потому что, по нашему мнению, вы её не правильно трактуете. Вот из вашей же цитаты:


              about micro-optimizations such as how many CPU cycles a particular statement consumes

              Что такое CPU cycles — это уже нюансы той самой константы, которую вытеснили из bigO. А что у нас тут?


              and good implementations of those algorithms

              А тут у нас bigO. А почему он тут среди "важных" вещей? А потому что, потенциально это бомба. Это не "small efficiencies".


              Может ли описанная в статье проблема изменить bigO нагруженной части приложения? Легко. Просто поместите её туда как кусочек кода в цикле.


              1. ookami_kb
                23.11.2021 17:01
                +9

                Это просто маятник сильно качнулся в другую сторону. Если в 70-е надо было разработчиков убеждать не тратить много времени на преждевременное вылизывание кода, то теперь приходится их убеждать потратить хоть немного времени, чтобы превратить O(n^2) в O(n).


            1. transcengopher
              23.11.2021 15:04
              +4

              Замена O(n2) на O(n) — это как раз "good algorithm design".
              Даже если на вашей машине разработчика это будет разница между 0.17мс и 0.2мс, то на машине пользователей вместо ваших тестовых десяти элементов легко может быть тысяча, и разница станет куда заметнее. Мой постулат состоит в том, что писать сразу более оптимальный алгоритм стоит куда меньше, чем переписывать готовый код когда он уже начал вызывать проблемы.
              Для контекста. Самый большой репорт в моей памяти на данный момент составляет 35 тысяч строк, и каждая строка там тоже не из одного элемента. И нынешнее наше требование — поддерживать по 50 тысяч строк (с запасом чтобы). А по факту просто из-за хорошей гигиены, когда нам пришло обновлённое требование (цифра до этого была около 500), мы всего лишь нагенерировали нужное количество данных и убедились, что всё по-прежнему работает удовлетворительно. Код менять даже не пришлось.


              1. JordanoBruno
                23.11.2021 15:28
                -2

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

                Кнут - дядька опытный, зря не будет телеги прогонять, я бы все же прислушался ).

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


                1. transcengopher
                  23.11.2021 16:39
                  +4

                  Мысль его понятна — в сложной программе даже не всегда сразу понятно, где именно тормозит, нужно профайлить или как-то по-другому замерять скорость участков кода.

                  Одно другому не мешает. Если у вас где-то сложный код и вы там сразу не нашли O(n2), то это простительно, бывает со всеми. Бывает и так, что O(n2) — это вообще лучшая асимптотика из возможных.


                  Сложная — это, грубо, человеко-месяцы затрат, а не пример из статьи, где и оптимизировать-то особо нечего.

                  Оптимизация таких мелких примеров, где весь код вообще на одной странице монитора — не попадает в моих глазах под критерии premature optimization. Эти вещи не нужно искать с профайлером, понимаете? Достаточно немного подумать и поменять буквально пару строк кода, всё. У меня такие случаи занимают дополнительно ну максимум минут десять, а success story этого подхода я выше уже приводил в пример.


                1. bbc_69
                  23.11.2021 17:08
                  +2

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

                  Готов поспорить, что он был бы сейчас не стороне тех, кто против скобочек.


                  1. movl
                    24.11.2021 06:43
                    -1

                    На сколько я помню, Кнут стремился чуть ли не к физическим обоснованиям эффективности алгоритмов. По сути, у него делается упор не на абстрактные алгоритмы и языки, а именно на их непосредственное исполнение в физическом мире. Его слова, наверное, можно трактовать как "минимальная форма частного, зачастую не является тем, что вам действительно нужно". Я не думаю, что эта проблема имеет какой-то временной характер. И действительно, если даже брать разбор с этими спреад операторами, то это легко можно оптимизировать во время интерпретации, при условии, конечно, что прототипы базовых классов не менялись, но это уже совсем другая проблема.


                    1. bbc_69
                      25.11.2021 10:03
                      +1

                      На сколько я помню, он говорил о том, что свои силы надо тратить эффективно. Среди примеров неэффективности был момент, когда разработчики правили код, который отвечал за ничего не делание.

                      Применительно к данной теме: Затраты на то, чтобы писать/не писать скобочки исчезающе малы, фактически отсутствуют. А профит есть и очевидный.

                      Не думаю, что в данном случае Кнута вообще стоит вспоминать, он писал совсем не о том.


                      1. movl
                        25.11.2021 19:30

                        Да зачастую flatMap решает половину проблем связанных с reduce ...spread, и только сокращает количество скобочек. Сам я, стараюсь как можно реже допускать неявное увеличение асимптотической сложности алгоритмов. Spread оператор, мной воспринимается исключительно как средство выразительности языка. Проблема в том, что всё, так или иначе относящееся к стилю кода, обычно имеет множество субъективных критериев оценки. Не в том смысле, что это какая-то прихоть, а в том, что различные измеряемые критерии, могут быть очень важными для одних, и совершенно ничего не значить для других.

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

                        http://elib.ict.nsc.ru/jspui/bitstream/ICT/882/3/knuth_1974.pdf

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

                        В остальном же, я согласен с автором на 90%. Просто потому что реальные инструменты далеки от идеальных, и сам произвожу подобные "оптимизации" практически на автомате.


          1. crazymax11
            23.11.2021 15:03

            Проблем нет. Ощутимой пользы, в подавляющем большинстве случаев, тоже.


            1. faiwer Автор
              23.11.2021 15:10
              +3

              А скрытых случаев недостаточно чтобы взять это за правило? Под скрытыми случаями понимаю те самые ситуации где предположения программиста оказались ошибочными (вместо 5 языков или стран в деве на проде подсунили 200, вместо 5 разных товаров, покупатель купил 20, вместо одной записи, потребовалось показать 250, и т.д.)?


              Если чему меня опыт и научил, так это в первую очередь тому, что мы все регулярно ошибаемся в своих оценках.


              Для того чтобы этой проблемы не было обязательно ждать таску в Jira? Вот эта строка кода стоит того?


              1. crazymax11
                23.11.2021 15:21
                -1

                потребовалось показать 250

                Судя по бенчмаркам, 250 элементов обработаются достаточно быстро.

                Для того чтобы этой проблемы не было обязательно ждать таску в Jira? Вот эта строка кода стоит того

                Эта строка кода не гарантирует, что проблем не будет. Проблема не в том, что concat писали, а в том, что проектировали под список из 10-20 элементов. Ну будет вместо concat что-то более оптимизированное, а рендер не оптимизировали и UX неудобный т.к. изначально не предполагали больше 10 элементов в списке.


                1. faiwer Автор
                  23.11.2021 15:28
                  +1

                  Судя по бенчмаркам, 250 элементов обработаются достаточно быстро

                  Повторюсь — это вопрос конкретных условий как и где эти 250 элементов обрабатываются. Вы не натыкались на то что неправильный полифил на Object.assign уничтожает производительность в старых бразуерах? Я натыкался. В IE8 (или IE7) календарики на форме инициализировались почти минуту. В Chrome такого поведения не было, т.к. полифил не применялся (да и v8 быстрее).


                  Эта строка кода не гарантирует, что проблем не будет.

                  Давайте я перефразирую ваше же предложение:


                  Эта строка кода гарантирует, что этой проблемы не будет.

                  ну как? :)


                  1. crazymax11
                    23.11.2021 15:38
                    -2

                    это вопрос конкретных условий как и где эти 250 элементов обрабатываются.

                    Согласен, всегда следует оттакливаться от контекста. Есть контексты, где это важная оптимизация, которая ускорит процесс. Но, по моим ощущениям, их очень мало. А в большинстве контекстов неважно, concat там будет или не concat

                    ну как? :)

                    Если честно, я не понял вашу мысль.


                    1. faiwer Автор
                      23.11.2021 15:41
                      +2

                      Если честно, я не понял вашу мысль.

                      Эта строка гарантирует что именно этой проблемы не будет. А это уже много стоит. Уж точно этой самой строки.


                      Есть контексты, где это важная оптимизация, которая ускорит процесс

                      Я вот сейчас понял… Я в принципе не воспринимаю эту штуку как оптимизацию. Это ведь никакая не оптимизация. Это код по-умолчанию.


                      Вы ведь не пишете:


                      source
                        .map(something)
                        .slice(5)

                      а пишете:


                      source
                        .slice(5)
                        .map(something)

                      Является ли 2-ая версия оптимизацией. На мой взгляд нет. Просто первая версия кривая.


                      1. crazymax11
                        23.11.2021 16:18

                        Это ведь никакая не оптимизация

                        Смотря что понимать под оптимизацией. Но я не знаю определения, по которому код с pushменее оптимальный, чем код с concat

                        Это код по-умолчанию.

                        Просто первая версия кривая.

                        Это звучит очень субьективно


                      1. faiwer Автор
                        23.11.2021 16:22
                        +2

                        Это звучит очень субьективно

                        Если у вас 1-ая версия (где slice после map, а не наоборот) может пройти code-review, я рад что не работаю у вас :) На мой взгляд это уже настоящее разгильдяйство.


                      1. crazymax11
                        23.11.2021 16:38
                        +1

                        Если у вас 1-ая версия (где slice после map, а не наоборот) может пройти code-review

                        Да, такой код может пройти code-review (как и код с concat), если учитывать контекст применения кода. Например, если нам достаточно, чтобы код корректно работал и выполнялся не дольше минуты.

                        я рад что не работаю у вас :) На мой взгляд это уже настоящее разгильдяйство

                        Стало еще более субьективно. А как же условия, контексты?

                        Предлагаю на этом сообщений завершить тред, т.к. от цифр мы пришли к обвинению в непрофессионализме, как в настоящем холиваре :)


                      1. faiwer Автор
                        23.11.2021 16:39
                        +5

                        Предлагаю на этом сообщений завершить тред

                        Согласен. На мой взгляд это уже за гранью добра и зла. Дальше смысла спорить нет. Мы друг друга не поймём.


                      1. Bronx
                        03.12.2021 07:33
                        +2

                        Это звучит очень субьективно

                        -- Зубы нужно держать в порядке, чтобы изо рта не воняло и других проблем позже не возникло.

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


                      1. crazymax11
                        03.12.2021 08:50

                        Это очень спекулятивная аналогия.

                        В статье и комментариях есть замеры - reduce + concat на массиве из 1000 элементов отрабатывает около 2мс.

                        При обработке 1000 элементов, скорее всего, не эта операция окажется узким местом.

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


                      1. Bronx
                        03.12.2021 09:43
                        +4

                        Использование ополаскивателя требует действий сверх базовой гигиены. Использование линейного reduce+push или flatMap вместо квадратичного reduce+concat не требует ничего, кроме навыков базовой гигиены. Ну просто уже одно только знание, что concat создаёт новый массив, а reduce гоняет цикл, и мы одно вставляем в другое, должно вызвать органолептическую реакцию "фу, грязь" и позыв найти нормальный способ.

                        Я понимаю, если кто-то просто не знал/забыл про особенность concat -- это ок, со всяким бывает. Если же знает, но сознательно выбирает из двух равноценных вариантов более грязный -- и даже настаивает на этом! -- и при этом у него нет серьёзных причин для такого выбора, то это явно проблемы с гигиеной.


                      1. Chamie
                        06.12.2021 20:01
                        -1

                        У кого квадраты с «чистыми» функциями вызывают реакцию «фу, грязь», а у кого мутирование массива push'ем.


                      1. Bronx
                        06.12.2021 20:23

                        Здесь не мутирование абы какого массива, а мутирование внутреннего аккумулятора, специально для этого предназначенного. Чистота сохраняется, внешних эффектов нет, полная детерминированность. Сможете показать, как тут нарушена чистота?


                      1. mayorovp
                        06.12.2021 20:54
                        +1

                        Нарушена чистота внутренней функции, переданной в reduce. С внешней-то понятное дело что всё в порядке.


                      1. Bronx
                        06.12.2021 23:16

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


                      1. mayorovp
                        06.12.2021 23:51

                        Причём тут вообще зубы?


                      1. Bronx
                        06.12.2021 23:58

                        См выше по треду, про гигиену.


                      1. Chamie
                        07.12.2021 15:09

                        Продолжая аналогию с зубами, у нас нет цели держать зубы чистыми ежесекундно и чистить их после каждого откушенного куска булочки. Это уже будет другая крайность — обсессивно-компульсивный синдром.
                        Так ведь той же аналогией можно описать и избегание «квадратов» при обходе массива в 5 элементов.


                      1. Bronx
                        08.12.2021 04:46

                        Не всякое избегание — обессивное расстройство. Эдак вы дойдёте до идеи что "гигиена — это тоже ОКР, ритуальное избегание грязи". Нужно же учитывать диапазон последствий. Что отличает здоровую гигиену от обсессивного растройства?


                        • Гигиена: в худшем случае — бесполезна, в лучшем случае — может сильно помочь.
                        • Обсессивное расстройство: в лучшем случае — безвредно, а в худшем — может сильно навредить.

                        Случай в 5 элементов — это то где reduce+concat ещё безвреден, а reduce+push ещё бесполезен. Это то место, где гигиена и ОКР могут показаться неотличимыми, но это не значит, что их можно приравнивать.


                      1. Chamie
                        08.12.2021 17:54

                        Слушайте, ну ваши аргументы же точно так же можно развернуть в обратную сторону: в случае, когда у нас push в маленькой функции, в которой мы можем отследить побочные эффекты — он ещё безвреден, а concat — ещё бесполезен…


                      1. Bronx
                        09.12.2021 04:10

                        А в где worst case у push? На каких даных он становится вреден? И в чём best case у concat, когда он становится полезен?


                      1. Cerberuser
                        09.12.2021 05:30
                        +2

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


                      1. Bronx
                        09.12.2021 09:03
                        +2

                        Ну в таком разрезе как бы да, если рассматривать независимые оси "код vs данные", то про push в маленькой функции можно сказать, что по оси "код" это "лучший случай ", а с ростом кода всё хуже. Но в процессе развития системы шанс случайно и непреднамеренно напороться на большие данные всё же выше, чем шанс случайно и непреднамеренно превратить двустрочник в функцию на пару экранов с кучей эффектов. Код ты сам контролируешь, а данные приходят в reduce извне, сегодня 5 элементов, а завтра 100500. Этот код какой-нибудь джун скопипастит не приходя в сознание, проблема вылезет у него -- а винить он будет того, у кого он код этот взял. Для общей кармы плохо :)


                      1. Chamie
                        09.12.2021 14:52

                        Этот код какой-нибудь джун скопипастит не приходя в сознание, проблема вылезет у него — а винить он будет того, у кого он код этот взял. Для общей кармы плохо :)
                        Именно! Скопипастит и расширит, не следя за сайд-эффектами. Плюсы иммутабельно-функционального подхода же, в основном, как раз не в повышении производительности, а в упрощении контроля. А джун пусть лучше сначала пишет медленный, но гарантированно рабочий и модульный код, чем быстрый, но требующий вдумчивости в применении.


                      1. faiwer Автор
                        09.12.2021 15:01

                        Chamie боюсь сложность "иммутабельно-функционального подхода" настолько велика, что junior-а к такому коду вообще подпускать страшно. А если FP запущен во взрослому, то ниже senior-а уже не вариант.


                      1. Bronx
                        10.12.2021 00:10

                        Скопипастит и расширит

                        P(скопипастит) > P(скопипастит)*P(расширит|скопипастит)


                        Ну и если закладываться на "расширит", то ничто ему не мешает до куба расширить :)


                        не следя за сайд-эффектами

                        Как уже говорилось, сайд-эффектов тут нет. Есть эффекты, изолированные внутри чистой функции, т.е. очищенные.


                      1. Chamie
                        10.12.2021 02:37

                        Ну и если закладываться на «расширит», то ничто ему не мешает до куба расширить :)
                        Да просто передаст в качестве второго параметра не пустой массив, а какой-нибудь существующий.
                        Как уже говорилось, сайд-эффектов тут нет. Есть эффекты, изолированные внутри чистой функции, т.е. очищенные.
                        Давайте определимся: где «тут»? Функция, в которой этот reduce используется? Функция-редьюсер? Метод reduce?
                        Главная функция у нас будет чистая только если мы за этим проследим (этакий unsafe-код) это и есть «следя за сайд-эффектами» (что они не просачиваются наружу), функция-редьюсер у нас точно не чистая, а метод reduce так и вообще просто вызывает её в цикле, никак не ограничивая её в мутировании см. тот же пример выше с передачей существующего массива в качестве стартового значения «аккумулятора» (мне о нём больше нравится думать как об объекте межитерационного обмена).


                      1. Bronx
                        10.12.2021 05:02

                        Давайте определимся: где «тут»?

                        Функция


                        (items) => items.reduce(
                            (acc, item) => {...}, 
                            [])

                        — является чистой что с concat, что с push вместо ....


                        Да просто передаст в качестве второго параметра не пустой массив, а какой-нибудь существующий.

                        Легко:


                        (items, init) => items.reduce(
                            (acc, item) => { acc.push(item); return acc; }, 
                            [...init])

                        — сложность кода такая же, эффективность на месте, никаких эффектов наружу не просачивается.


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


            1. BigBeaver
              23.11.2021 15:10
              +3

              О чем и речь. Но при нулевых затратах даже «меньшинство» случаев означает огромную пользу для человечества, тк даже «меньшинство» это, как правило, очень много (в штуках), если мы говорим о вебе — при миллионе пользователей (запросов?) в день даже 1% это много.


  1. Keyten
    23.11.2021 05:34
    +13

    Кстати, знаете, как сделать вот этот код...

    for (let idx = 0; idx < arr.length; ++ idx) {
      const item = arr[idx];
      result.push(something(item));
    }

    ...читаемее в три раза?

    Вот так:

    for (let i = 0; i < arr.length; i++) {
      const item = arr[i];
      result.push(something(item));
    }


  1. Zoolander
    23.11.2021 09:27
    -4

    Согласен, описанные в статье практики могут выстрелить в ногу. Но они выстрелят в некоторых случаях. В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.

    Поэтому стандартизированные общие практики в итоге позволяют экономить больше ресурсов, так как большинство кодеров в фронтенде не сталкивается с проблемой высоконагруженных систем.

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


    1. faiwer Автор
      23.11.2021 11:19
      +6

      В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.

      И насколько у нас упала "читабельность"? Код стал непонятным? :) Really?


    1. JordanoBruno
      23.11.2021 14:31

      В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.

      Поддержу тут.

      большинство кодеров в фронтенде не сталкивается с проблемой высоконагруженных систем

      И тут тоже. В основном надо писать быстро, так как сроки поджимают.

      тем, кто пишет серверный код - уже стоит призадуматься

      Там все перекроют потери если лишний раз сходишь в базу. Лучше там пооптимизировать.


    1. adam4leos
      27.11.2021 07:05

      Я бы не откидывал фронтенд так просто. Вот, пару лет назад писал большую статью об огромной полезности знаний алгоритмов и структур данных во фронтенде на dou, с примерами применения.


  1. crazymax11
    23.11.2021 09:59

    Сделал бенч на jsbench.me и выглядит, что чтобы не уложится в 16 мс, нужно пару сотен элементов в массиве.

    Это я не к тому, что использовать concat в reduce - хорошая практика. Но из статьи выглядит, будто бы уже при 30 элементах в массиве будет проседать перформанс, однако это не так. Граница, когда все становится плохо, находится дальше и там, возможно, concat будет не самой большой проблемой

    Бенч: https://jsbench.me/45kwbqj1xj/1


    1. Finesse
      23.11.2021 10:20
      +3

      Пара сотен это не так много, как кажется. В 16 милисекунд нужно уложить не только обработку данных, но и модификацию DOM-дерева, и ещё оставить браузеру время на обработку изменений DOM-дерева, отрисовку интерфейса и обработку событий. На 5-летних устройствах всё это будет происходить раза в 2 медленнее. По-хорошему, обработка данных должна занимать не больше 1мс на железе разработчика.


    1. faiwer Автор
      23.11.2021 11:24
      +1

      Я так понимаю вы сделали следующие допущения:


      • код запускается не в цикле (или циклах)
      • код запускается всего один раз
      • это единственный код который вообще запускается

      В целом да. 30^2 операций не так много, чтобы соло создать performance bottleneck :) На моих примерах разница с линейной версией была всего в 4 раза.


      1. crazymax11
        23.11.2021 11:36

        Я повторил бенч из скриншотов из Firefox и Chrome. Там где сравниваются 2600 vs 30


        1. faiwer Автор
          23.11.2021 11:40

          Там по 3 примера: 1000, 100, 30. Ну просто для наглядности различий между O(n) и O(n^2). 2600:30 это не количество элементов, это количество миллисекунд. И такая большая разница была как раз при 1000 элементах. При 30 всего 16:3. Что полностью соответствует теории — чем выше N, тем больше дистанция. Чем ниже N, тем меньше дистанция.


          1. crazymax11
            23.11.2021 11:52
            -1

            Мне, при беглом прочтении статьи, показалось, что обработка 1000 элементов через concat занимает 2 секунды , а через push - 30 мс.

            Но там делается 1000 прогонов по 1000 элементов и потом замеряется общее время. Получается, concat на 1000 элементов в среднем выполнялся за 2мс. Это, конечно, много и повлияет на рендер, но не прям драмматично.

            Если нам нужно эти 1000 элементов еще и отрендерить, то полезнее будет заняться оптимизацией рендера, а не заменой concat


            1. faiwer Автор
              23.11.2021 12:01
              +5

              Это, конечно, много и повлияет на рендер, но не прям драмматично.

              Да, всё зависит от обстоятельств. К примеру я не так давно долго ковырялся с MapBox картами. Мне нужно было "на лету" генерировать текстуры картинок, которые нужно показывать на карте. Возможных картинок до 170.


              Первая рабочая версия была слишком долгой. На одну картинку (генерацию её blob-а) уходило 20ms. Пришла в голову идея переиспользовать существующий canvas между картинками (затирать часть областей и рисовать поверх). Удалось сократить с 20ms на 0.2ms.


              Казалось бы — успех, ура. Но всё равно меньше 2ms на картинку не получалось достичь, т.к. даже готовую картинку mapbox съедает не меньше чем за 2ms. Просто тупо копирует ImageData побайтово целых 2ms. В случае картинки для retina в 4-6 раз медленнее.


              А картинок до 170. Тут не то что в кадр не уложиться… тут вообще беда-беда. Стало очевидно что надо это дело дробить на чанки. Взял requestAnimationFrame. Работает. Теперь общее время работы не условных 400-900ms а 11 секунд. Это никуда не годится. Но такова плата за асинхронность. Любые мои попытки как-то разбить вычисления на чанки приводили к тому что ломался JIT и всё замедлялось в разы (пусть и отзывчиво).


              К чему это всё я? К 2мс.


              то полезнее будет заняться оптимизацией рендера, а не заменой concat

              Безусловно, в первую очередь надо браться за bottleneck. А касательно concat их не убирать надо. Их просто не надо писать. Всё просто. Не нужно с самого начала писать бредовый код.


            1. faiwer Автор
              23.11.2021 12:09

              Если нам нужно эти 1000 элементов еще и отрендерить

              Кстати не факт, что нужно рендерить. Не все данные нужны для отображения.


              Пример. Писал приложение для ручного формирования расписаний. Там были достаточно большие данные (почти все данные школы), чтобы ни в коем случае, нельзя было забивать на bigO, но выводилось их весьма ограниченное количество. Все проблемы с performance были на стороне объекто-дробилок (всякие фильтрации, вычисление подходящих окон для размещения урока, валидация и пр. и пр.). Вся эта объекто-вакханалия перевычислялась на лету при малейших изменениях.


              Для примера стоило начать drag-n-drop-ать условный "Математика 2А класс Савельева Е.В." с панели "неразмеченных уроков" на "текущая проекция расписания" как нужно было за <16ms пересчитать все допустимые ячейки. Где-то у 2А уже урок, где-то нельзя, так как нормативы нагрузки перевыполнятся, где-то у учителя другой урок, где-то кабинет занят физиком, ну и т.д… Естественно это всё ещё и реактивное (иначе бы я вечность это писал).


              Любые попытки написать это игнорируя квадратичную сложность на ровном месте просто уничтожили бы проект.


  1. PoetLuchnik
    23.11.2021 12:13
    +3

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

    Порой у меня создается ощущение что программирование это не про здравый смысл, а про моду и стиль. Используются популярные решения, а не эффективные. (надеюсь кто то скажет мне что я не прав)


    1. debagger
      23.11.2021 17:22

      Тут еще проблема в том, что при сдаче проекта редко кто пробует тестировать на рабочих объемах данных. А на тестовых всё работает, фичи не падают, анимации плавные и в целом замечаний нет.


  1. debagger
    23.11.2021 17:18
    +1

    У меня был случай лет 15 назад, когда на вопрос к разработчику, почему так тормозят расчеты в программе (Delphi + MSSQL) был ответ - это не мои проблемы, томозит - купите сервер помощнее. Пришлось самому лезть разбираться (пока он был в отпуске), в итоге тормоза пропали после добавления пары хинтов в SQL-запрос. Когда ему показал, как я решил проблему, в ответ было - ну давай везде эти хинты навешаем.

    К слову - человек к тому времени уже лет 5 занимался исключительно клепанием CRUD-двухзвенок на этой связке, а я только начал тогда изучать работу с БД.

    К чему я это рассказываю - ничего не поменялось за эти годы. Если человек не видит потенциальной проблемы в том, что список покупок в корзине обновляется 40 секунд, или что документ по уникальному реквизиту в системе документооборота ищется 5 минут, и если за такое ему не бьют линейкой по пальцам, а послушно докупают более мощные серверы и терпят убытки из-за потерянных покупателей - ничего не поменяется. Если повезет, придет другой разработчик, который парится за производительность и вычистит из кода квадраты, кубы и прочие экспоненты, но это должно еще повезти.


  1. MFilonen2
    23.11.2021 20:57
    +4

    Удивлён, что это вызвало такую большую дискуссию. Всегда был уверен, что переход от N к N2 – ну никак не незначительная потеря производительности. И классики говорили все же про оптимизации, изменяющие константу возле big O.
    А уж если ради того, чтобы убрать одну строку кода на такое идут – что ж, теперь я понимаю, почему так много плохих сайтов в Интернете.


    1. Alexandroppolus
      23.11.2021 21:34
      +5

      Самое смешное, что всякие алгоритмические мегамозги придумывают хитрейшие алгоритмы на 100500 строк, ради того чтобы выкинуть из bigO лишний ln N, и никто не утверждает, что они заняты фигнёй. А тут по сути на халяву разница на целый N, причем как в скорости, так и во вспомогательной памяти.


  1. isergey87
    23.11.2021 22:00
    +10

    Удивляет как здравый смысл (не делать ненужных действий) многие называют преждевременной оптимизацией.

    В следующий раз когда пойдете в магазин возьмите тележку. Когда захотите положить туда товар - вернитесь возьмите новую тележку, положите туда товар. Когда снова понадобится положить товар - опять вернитесь и возьмите новую тележку, переложите все товары в новую тележку и добавьте новый товар. И так повторяйте каждый раз с новым товаром. Интересно использование одной тележки вы будете называть оптимизацией или просто здравым смыслом?

    P.S. А потом выйдет GC из подсобки и будет очень рад числу ненужных тележек, оставленных по всему магазину.


    1. interhin
      24.11.2021 11:22

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


  1. 0x450x6c
    24.11.2021 11:13

    Справедливости ради, в случае массива, можно использовать flatMap:
    ![](https://habrastorage.org/webt/ty/by/qj/tybyqjr9ihk96jdibc4pewgnixi.png

    В случае объекта, там обычно не бывает тысячи полей.

    В принципе поддерживаю, но лучше приведите больше примеров.


    1. faiwer Автор
      24.11.2021 11:16

      В случае объекта, там обычно не бывает тысячи полей.

      Всё как обычно: это зависит от обстоятельств. На моей практике было очень много примеров когда в массиве были сотни и тысячи полей. Просто словарик. Сейчас для таких целей завезли Map, и я предпочитаю использовать его. Но ImmutableMap у нас нет :)


      Плюс я намеренно не стал сильно углубляться в объекты, сказав, что там всё сложно. Потому что в зависимости от реализации, любая операция с объектом может затребовать O(logN) действий (если он скажем сделан при помощи binary search tree). В общем и целом — объекты не массивы, они и сложнее и тяжелее.


      1. nin-jin
        24.11.2021 12:49

        В тайпскрипте есть ReadonlyMap.


        1. faiwer Автор
          24.11.2021 12:53

          Я же не про типы. Я про оптимизированную структуру данных, с которой можно работать иммутабельно, без больших пенальти по производительности.


          1. nin-jin
            24.11.2021 12:57

            Так объекты тут ничем не отличаются. Даже медленнее работают из-за жонглирования скрытыми классами.


            1. faiwer Автор
              24.11.2021 12:58

              Да, я знаю. Я не имел ввиду того, что Map хуже чем {}. Наверное слишком косноязычно написал. Просто пожаловался на отсутствие желаемого. Но нас ждут #{} и #[] с ними будет поинтереснее.


              1. Nikitakun1
                24.11.2021 13:25

                А вы же тут с самого начала обсуждаете пересоздание объектов? Не доступ по ключу? Доступ по ключу и у {}, и у Map всегда же будет O(1)?


                1. faiwer Автор
                  24.11.2021 13:34

                  Я видимо с утра сильно непонятно пишу. Sorry. Я ни в коем случае не имел ввиду что Map имеет другие bigO, нежели {}. Выбор между map и {} это больше вопрос семантики и привычки. Я предпочитаю map, т.к. никакие прототипы уже не играют никакой роли и явный вызов .get, .set, .has позволяет с первого взгляда понять, мы имеем дело со словарём. В то время как obj[key] = оставляет много возможных вариантов, и требуется больше вникать в код. Плюс, если объект не был создан как-нибудь так Object.create(null), то не стоит забывать про уже существующие свойства из прототипа объекта, который в случае Map не будет. Плюс nin-jin правильно написал про hidden-classes. Но в случае Map у нас меньше сахара. В общем Map vs {} это тема для отдельного занудного топика.


                  и у Map всегда же будет O(1)?

                  Я бы не стал ручаться за все движки. Можно реализовать и за logN. Плюс обратите внимание на "всегда". Если взять операцию записи (не чтения), то она будет O(1) только амортизированно. Т.е. в какой-то момент там будут все O(n), т.к. под капотом система будет вынуждена пересоздать весь hashmap, но уже большего размера


      1. 0x450x6c
        24.11.2021 13:31
        +1

        Всё как обычно: это зависит от обстоятельств. На моей практике было очень много примеров когда в массиве были сотни и тысячи полей. Просто словарик. Сейчас для таких целей завезли Map, и я предпочитаю использовать его. Но ImmutableMap у нас нет :)

        Всё так, только количество таких словарей мало, большинство объектов имеют мало полей.

        Как вариант, для объектов вместо reduce можно использовать map + Object.fromEntries.

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

        На firefox, ожидаемо занимает много времени: https://i.imgur.com/FUljbwl.png

        Но интересно, что chrome смог это оптимизировать: https://i.imgur.com/IlA84PE.png


        1. faiwer Автор
          24.11.2021 13:37

          Как вариант, для объектов вместо reduce можно использовать map + Object.fromEntries

          Да, можно. Страшненько получается правда, поэтому не совсем понятно зачем. ИМХО читаемость куда ниже.


          1. Alexandroppolus
            24.11.2021 14:01
            +1

            Страшненько получается правда, поэтому не совсем понятно зачем

            Когда мы поштучно добавляем новые поля в {}, меняются скрытые классы для него. Object.fromEntries, реализованный нативно, теоретически мог бы избежать этой проблемы. Хотя не знаю, как дело обстоит сейчас и что быстрее. Оно там внутри постоянно меняется.


          1. 0x450x6c
            24.11.2021 14:14
            +1

            Этот вариант может быть предпочтительнее, для тех кто хочет обходиться иммутабельними структурами.

            Я не против мутировать accumulator, но например eslint пока не сможет везде запретить мутации кроме accumulator'a, поэтому приходиться либо запретить везде либо разрешить.

            Если вы решили запретить мутабельные структуры, то такой вариант (Object.fromEntries) вам подходить, во всех остальных случаях мутация accumulator'а предпочтительнее.

            ---
            Читаемость можно улучшить с помощью вспомогательных функций, например:

            pipe(
              source,
              array.map(n => [n, n]),
              dict.fromEntries,
            );


            Либо в будущем так:

            source
              |> %.map(n => [n, n])
              |> Object.fromEntries(%)


    1. Lynn
      24.11.2021 17:16
      +2

      В случае объекта, там обычно не бывает тысячи полей.

      Недавно на ruSO был вопрос как обойти ограничение браузера на (кажется) 48 миллионов(!) полей в объекте… O_o


      1. Alexandroppolus
        24.11.2021 18:43

        Чуваку посоветовали использовать Map?


        1. mayorovp
          24.11.2021 21:57

          Да, но у него был легаси в состоянии "страшно трогать".


      1. PsyHaSTe
        25.11.2021 01:51

        А можно ссылоку? Не могу найти.

        cc mayorovp если в курсе о чем речь)



  1. Smoquin
    24.11.2021 11:16

    Может ли кто-либо, пожалуйста, привести пример неудачного includes внутри .filter? И пример оптимизации. Не уверен, что понял. Заранее благодарю!


    1. faiwer Автор
      24.11.2021 11:19

      • .includes пробегает по всему массиву, поэтому там O(n)
      • .filter тоже пробегает по всему массиву, поэтому там O(n)
      • итого если одно вызывается в другом, то вы получаете O(n^2) или O(n * m) (если это разные массивы)

      В простых случаях, когда N и M крошечные, можно пренебречь (ну или нельзя, решайте сами). В остальных стоит задуматься — можно ли это дело исправить? В целом да и довольно просто. Надо просто один из массивов преобразовать в, скажем, new Set. А потом уже использовать вместо arr2.includes(arr1val) а arr2set.has(arr1val). Разница на этой операции будет O(n) vs O(1) (либо O(logN) если Set сделан через binary search tree).


      На преобразование тоже уйдёт память и время. По времени O(n) в случае hashmap, и O(n logN) в случае tree. Но эта операция не выполняется внутри .filter поэтому погоды уже не делает.


      Ещё раз уточню. Если ваши N и M равны, скажем, четырём, то сидеть колупать код резона нет :)


      1. Alexandroppolus
        24.11.2021 11:42

        На преобразование тоже уйдёт время и память.  O(n logN) в случае tree.

        Откуда там logN? Дерево занимает O(n) памяти

        upd: а, это время


        1. faiwer Автор
          24.11.2021 11:43

          Я про время, не про память. Сорри что запутал. Поправил комментарий (переставил слова)


      1. tvictor
        30.11.2021 21:38

        Подскажите, что лучше использовать в данной ситуации? Есть массив строк и поле для ввода. По мере ввода пользователя нужно фильтровать этот массив строк - в выборку должны попадать лишь те, что содержат введённую строку.
        Когда массив строк не очень велик, вариант arr.filter(str => str.includes(value)) работает без тормозов, да. Когда нужно было это сделать на большом массиве строк (если правильно помню, 5000 строк), то использовал arr.filter(str => str.match(value)). На Includes были заметны тормоза, на match - летало.


        1. faiwer Автор
          30.11.2021 21:49

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


          Ещё добавлю, что в рамках такой задачи не помешает предварительно:


          • trim-ать строки
          • str.normalize — нормализовывать
          • приводить к одному case-у (например lower)

          Ещё можно дробить поисковый запрос на слова и искать отдельно по каждому слову. Частенько это лучше покрывает желания пользователя, чем просто поиск в лоб.


          1. tvictor
            01.12.2021 08:25

            Спасибо за ответ. Тоже каждый раз это были маленькие объёмы. Лишь один раз на тестовом задании был набор из 5000 строк. Даже не строк, а объектов с несколькими строками внутри, по которым надо было искать. Как писал выше, там меня match выручил.
            Про trim знаю, да. Пойду почитаю про другие способы )


        1. Alexandroppolus
          30.11.2021 22:07
          +3

          Как вариант, сохранять и переиспользовать предыдущие выборки. Наиболее типовой сценарий здесь - когда в текстовом поле набивается слово, и с каждой новой буквой делается поиск. И, допустим, имея на руках выборку для "abc", которая существенно меньше исходного полного набора слов, из неё очень быстро сделаем выборку для "abcd", ничего не потеряв. В общем, для некоторой введённой строки S ищем среди предыдущих запросов запрос для наиболее длинной подстроки S, и выбираем из него.

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


          1. Bronx
            03.12.2021 08:26
            +1

            Заодно можно не торопиться делать поисковый запрос с первой же введённой буквы, а подождать, скажем, двух-трёх, чтобы первая же выборка оказалась достаточно маленькой. Плюс, имеет смысл ограничить поиск лишь первыми N вхождениями, юзер всё равно не будет просматривать все 10000.


            1. Chamie
              06.12.2021 20:04
              +2

              …а потом наткнуться на то, что группу «The Who» в поиске не найти, потому что он выкидывает артикли, личные местоимения и слова меньше 4 символов.


        1. wataru
          30.11.2021 22:17
          +1

          Если строки должны начинаться со ввода, то отличный вариант — построить бор из фильтруемых строк, при вводе пользователя спускаться по этому бору и потом при поиске обходить бор с этой вершины и выводить все строки в этом поддереве.


          Если запрос пользователя должен входить как подстрока, то можно разбить все строки на 3-граммы (3 подряд идущих символа), для каждого набора построить список из всех строк, которые его содержат (отсортированные по id). Потом при запросе эти списки мерджить и искать только в этих строках.


          Еще, я не знаю, что там у String.includes под капотом, но может ручная реализация какого-нибудь KMP будет быстрее.


          Самый быстрый и сложный в реализации метод будет таким: построить суффиксные деревья для всех строк, потом объединить их в одно дерево. Потом в каждой вершине сохранить Set всех строк, кончающихся в поддереве. Чтобы быстро строить и не занимать очень много памяти, надо каждый Set хранить в виде персистентного бинарного сбалансированного дерева. Тогда построить это счастье можно за O(L log n) и памяти оно столько же занимать будет. Тут L — суммарная длина всех строк, n — их количество. Зато время поиска будет O(1) на каждый введенный символ и вывод всех строк будет за O(k), где k — длина ответа. Быстрее вообще никак. Но этот метод будет проигрывать совсем наивным на маленьких размерах из-за оверхеда и по настоящему засияет только при больших наборах данных. Но бонусом тут можно дерево предпостроить на сервере и выдать сразу его на клиент.


          Но никакие эти структуры, естественно, не встроены никуда, а на js наверно даже не реализованы нигде ни разу.


        1. nin-jin
          30.11.2021 22:42

          Из простых решений можно чуть доработать ваше: соединяем все строки через перевод строки, после чего через match натравливаем на неё регулярку. Например:

          'foo bar\nbar\nfoo'.match( /^.*bar.*$/migu ) // ['foo bar', 'bar']


        1. mayorovp
          30.11.2021 22:53
          +1

          Предположу, что вы делали не просто match по строке, а по заранее подготовленному регулярному выражению. В таком случае ничего удивительного нет — ведь includes тоже делает подготовку, пусть и более простую — зато каждый раз.


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


  1. alexskakun
    24.11.2021 19:07

    Синтаксис { ...acc, newProp: value } настолько привлекателен, что порой действительно забываешь, что он может сильно повлиять на производительность.

    Уже точно не помню где, давно было, читал, что добавление/удаление свойств существующему объекту достаточно тяжёлые операции. Для себя сделал "правило" стараться не расширять объекты вот так: obj[property] = value, где это может повлиять на производительность. В контексте статьи, решение для себя нашёл такое:

    const newObject = Object.fromEntries(source.reduce((acc, item, i) => {
      acc.push([i, item]);
      return acc;
    }, []));

    Если количество элементов source равно количеству свойств у newObject, то можно вообще избавиться от `push()`, а записывать в acc по индексу:

    const newObject = Object.fromEntries(source.reduce((acc, item, i) => {
      acc[i] = [i, item];
      return acc;
    }, new Array(source.length)));

    Но разница уже совсем не принципиальная. В хроме при n = 10 000 всего несколько миллисекунд.


    1. faiwer Автор
      24.11.2021 19:13

      Если количество элементов source равно количеству свойств у newObject

      Просто замените .reduce на .map.


      Для себя сделал "правило" стараться не расширять объекты вот так: obj[property] = value

      Честно говоря я рекомендую вам провести замеры. Есть немалая вероятность что экономии нет, или она крошечная. Вы исходите из того, что Object.fromEntries очень мощно оптимизирован. Может быть оно так и есть. А может быть и нет. А ещё может быть что потери на игры с ненужным массивом перебивают любую выгоду от финта ушами с Object.fromEntries. В общем я рекомендую вначале прогнать простые тесты на нужных вам платформах. А то может быть вы зря мучаетесь :)


      Ну и стоит отметить, что асимптотической разницы там быть не должно. И если речь не про высоконагруженный участок кода какой-нибудь числодробилки то едва ли игра стоит свеч.


      1. alexskakun
        25.11.2021 14:09

        Просто замените .reduce на .map.

        Действительно, что-то я увлёкся редьюсом)

        Честно говоря я рекомендую вам провести замеры.

        Я проверил. Object.fromEntries() работает намного быстрее, чем { ...acc, props val }, но обычное добавление свойства всё же быстрее. Если оценивать сложность то она одинаковая: O(n) (простое добавление) против O(2n) (Object.fromEntries), а вот в абсолютном времени простое добавление свойства побыстрее.


        1. faiwer Автор
          25.11.2021 14:24

          На всякий случай уточню O(n) это ровно тоже самое что O(100500 * N). Т.е. O(n) === O(2n). То о чём вы говорите (2) это константа. Время, которое тратится на отдельно взятую операцию. У разных алгоритмов она, разумеется, разная. Поэтому когда мы говорим об bigO мы в первую очередь говорим о больших объёмах данных, т.к. чем больше данные, тем меньше влияния константы при разных bigO. Даже если у одного алгоритма константа в 20 раз выше, чем у другого, если тот другой имеет bigO(n!), а первый O(n), то роль этих "в 20 раз" уже не важна на объёмах. 20х алгоритм будет настолько ультимативно быстрее, что ...


          В отдельно взятых ситуациях берут в рассчёт уже и константы. И прочие обстоятельства. К примеру есть много вариаций binary search tree. У большинства из них (или всех, не знаю) одни и те же bigO. Но разница в константе (и прочих нюансах непокрытых bigO) заставляет применять разные деревья. Понятное дело это касается нагруженных участков кода.


          1. alexskakun
            25.11.2021 15:06

            Да, я именно это я и написал. Возможно, не совсем точно выразил мысль. С точки зрения оценки сложности алгоритма O(n) = O(2n).


  1. Vilaine
    27.11.2021 04:44
    -1

    Иммутабельность обычно требует некоторых жертв (копирования), но это не касается самих коллекций. Если это не Haskell с его изощренными оптимизациями связанных списков или finger trees, то для всех коллекций следует избегать immutability. Если речь о гарантированно малых величинах, то скорее всего это малые величины являются частью домена и поэтому должны быть инкапсулированы в какое-нибудь (иммутабельное или нет) перечисление. Например, список допустимых статусов. Если они не являются частью ограниченного домена, то они и гарантированно малыми не являются.

    Это, правда, по опыту backend. Смею предположить, что оператор "..." может быть попросту неудачен и не должен быть добавлен в язык именно потому, что он в 99% случаев ведёт к O(N) вместо O(1), что неизбежно приведёт к O(N^x) системах с бОльшей цикломатической сложностью, которую вовсе не всегда можно удержать в голове. Или, как минимум, к лишнему множителю o(xN). По-моему, ЯП не должен проектироваться с таким подходом, когда сахар замедляет программу в типичном случае без убер-оптимизатора, пусть якобы немного в этом типичном случае.


    1. mayorovp
      27.11.2021 11:16

      На самом деле, оператор "..." вполне удачен, потому что у него есть куча применений когда без него совсем плохо.


      Например, вызов функции с передачей произвольного числа аргументов: fn(foo, bar, ...baz) без этого оператора выглядел бы так: fn.apply(null, [foo, bar].concat(baz)). И да, у нормальных функций никогда не бывает слишком много аргументов.


      1. Vilaine
        28.11.2021 04:15
        -1

        Например, вызов функции с передачей произвольного числа аргументов: fn(foo, bar, ...baz)
        Пример так себе, потому что в этом случае можно обойтись fn(foo, bar, baz), объявив функцию соответствующим образом. Заодно ничего никуда копироваться не будет. Я думаю, функции с произвольным числом аргументов — это не пример отличного дизайна. Оператор для неудачного дизайна — не лучшая идея.

        Про кучу применений я как раз не в курсе. Чисто логически я вижу, что этот оператор поощряет неудачный дизайн кода, когда можно или нужно использовать другие пути — при разработке и развитии ЯП хотелось бы таких решений избегать.


        1. mayorovp
          28.11.2021 10:01

          Если это декоратор — то надо работать с тем что есть. И с чего вы вообще взяли, что у функции переменное число аргументов?


          1. Vilaine
            28.11.2021 18:23
            -1

            Если это декоратор — то надо работать с тем что есть.
            Не совсем понимаю, но специальный оператор для работы «с тем что есть» — такое себе.
            И с чего вы вообще взяли, что у функции переменное число аргументов?
            А зачем ещё код вроде fn(foo, bar, ...baz)? Если функция имеет фиксированные аргументы, и в массиве эти аргументы, то это даже ещё хуже. Аргументы к функциям должны быть явными, а не разворачиваться из массива, потому что в массиве может быть что угодно.


            1. transcengopher
              30.11.2021 22:53

              А зачем ещё код вроде fn(foo, bar, ...baz)?

              Например, для каррирования и прочих функций высокого порядка.


  1. rewlad-dev
    28.11.2021 03:35

    Я прекрасно понимаю алгоритмичесую сложность, но мутировать в что-то лишний раз, тем более в reduce, не буду:

    1. Это плохой пример другим. Товарищи решат, что так можно везде, и начнут, например, удалять элементы из массива по которому проходят. А потом товарищи перейдут на бакенд, который многопоточный. И про "memory model" не прочитают. Оптимизировать безопасный код проще, чем вылавливать плохо повтояемые баги.

    2. Итак, у меня 1000 элементов, для которых описанная оптимизация имеет значение. А они точно нужны на клиенте? Может, в качестве первой оптимизации, их не присылать, а взять только те 20, которые пользователь видит.

    3. Ну хорошо, в этот раз у меня канвас на UHD и элементов правда нужно много. А использовать библиотеку с дополнительными структурами данных не разрешили. Я ведь могу написать свой минимальный "util.js", в котором внутри всё будет в стиле "for(;;)" и "let", а снаружи чисто.

    4. Есть линтеры, которые заставляют помечать небозопасные конструкции. Возможно есть/будет и для js такой инструмент. И я стараюсь писать код так, чтобы легко интегрировать его в будущем.


    1. faiwer Автор
      28.11.2021 13:21

      Смешались в кучу люди кони… И не-JS backend с многопоточностю, и мутация итерируемых коллекций, и канвас. Ух. Но я и не настаиваю на .reduce. Если согласно вашим правилам, принятым в команде, мутации в .reduce это большой грех, то:


      • используйте вместо него.flatMap, там где это возможно
      • не используйте .reduce, там где получается O(n^2) на пустом месте. Есть множество способов сделать тоже самое, без него

      Главное не ставьте аргументы из п1. выше чем bigO. Над нами уже весь IT мир потешается.