Comments 355
В целом, статически типизированным чистым FP языкам доступны очень хитрые оптимизации.
Но ничего. Вот завезут к нам immutable data structures (где-то лежал черновик спецификации), заживём
Как правило, на статически типизированных чистых FP языках, не пишут "не приходя в сознание". В смысле, там, конечно, есть "неявная" мемоизация, и т.д., но
1. Можно посмотреть промежуточный код, включая ассемблер.
2. Обычно люди, всё-таки, представляют последствия того, что оптимизация не сработала.
Ну и явная мемоизация в Clean, кмк, лучше, чем неявная в Haskell.
Как только убежусь, что она плоха - отключу лень (конечно, если только в стратегии был боттлнек).
То, что есть в хаскеле — это не неявная мемоизация, а ленивая стратегия вычислений.
Ну вы же знаете про динамическое программирование на Хаскеле.
Я конкретно про вот это - 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 applied.
biglist1 = [1..10000] // a constant function (if defined globally)
biglist2 =: [1..10000] // a graph
biglist3 => [1..10000] // a constant functionhttps://clean.cs.ru.nl/download/html_report/CleanRep.2.2_12.htm#_5.2_Defining_Graphs
любой прод-реди функциональный строгий язык это не
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
и так с каждой фунцией
Так что мб ленивость по дефолту это и не так уж плохо
В Реакте - смотря как реализовано. Допустим, есть массив каких-то объектов, и мы по нему рендерим список. Когда в массиве что-то добавляется или удаляется, то будет перерендер списка, но не будет перерендера каждого элемента (при условии, что не забыли React.memo для элементов). Когда обновляется итем, то в иммутабельном стиле (Редукс и т.д.) тоже будет перерендер списка, а с МобХ уже не будет (если, конечно, элементы списка обернуты в observer и получают итем с наблюдаемыми полями).
не будет перерендера не потому что memo а потому что используешь key правильно
На всякий случай уточню — вы же в курсе что правильно выставленный key не спасет от re-render-а? Я даже больше скажу, он с ним не связан. Key в React и Vue нужен для сопоставления элементов в списках. Он не используется в целях мемоизации
я про то, что кей не даст перерендера элементами массива если они не изменились
А вам говорят про то, что сам массив в любом случае будет рендерится при каждом своём изменении. И этот рендер работает в лучшем случае за O(N), где N — длина массива, а в обсуждаемом случае — за O(N2)
Слишком много опечаток в комментарии. Я не понимаю его смысла. Key не даст перерендерить элементы массива если они не изменились? Даст.
нет
О сколько чудных вам открытий ещё предстоит сделать.
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>);
}и просто понажимайте кнопку. Каждый клик даст вам render Inner. А потом добавьте Memo. Удивитесь
щас бы в качестве ключа использовать "key", ты хоть почитай или видео посмотри какие-то про работу реакта) а то прям не совсем слабенько
Честно говоря я не очень рекомендую смотреть видео. Я всегда предпочитал первоисточник. В случае React он здесь. Рекомендую прочитать от корки до корки её всю (не эту статью, а всю документацию). Сейчас вы говорите глупости, ввиду полного непонимания предметной области.
Что-то я не пойму, почему Inner ререндерится? У него же пропсы не меняются.
Какой зашквар....
А как сделать, чтобы не ререндерились, если пропсы не поменялись? Ну, кроме прикручивания мобх.
Ну, кроме прикручивания мобх.
МобХ в этом плане ничего особого не дает, его декоратор observer дополнительно работает ещё и как React.memo - чтобы не надо было заморачиваться и вешать два декоратора, да и вспоминать какой сначала а какой потом. Зато, в отличии от того же редукса, позволяет экономить ререндеры родительских компонентов, если мутабельно менять что-то в объекте, за некоторыми исключениями.
Кто о чем, а vintage опять про smol.
deleted
Не будет перерендера дома, но будет перерендер виртуального дома. В рамках "оптимизации реакта" обычно говорится о том, как сократить перерендеры vdom
именно это и имел в виду, то что там вызывается функция рендер это уже второстепенное, она в любом случае вызовется, тк мы же изменили массив
В работе React есть две фазы: render и commit. Render это построение списка изменений за счёт реконсилирования двух virtualDom деревьев. А изменения в настоящем DOM это commit. Так вот ваша "вызывает функция рендер" это как раз render. Вышеописанный memo тоже работает на стадии render. А key нужен только для сопоставления однородных элементов во время работы алгоритма реконсиляции.
как я уже говорил ранее, рендер функция компонента в любом случае вызовется потому что произошло изменение массива (а если ничего не менялось то она и не вызовется), рендер в браузере вызовется только для элемента который изменился, либо в Вашем случае для всех элементов потому что key="key", ещё и ворнинг выдаст из-за одинаковых ключей для всего списка.
рендер функция компонента в любом случае вызовется
Не в любом. С самого начала вам сказали про memo. Вот если обернуть дочерние компоненты memo (и соблюсти ряд условий), то они не будут пере-render-ены. Кроме тех конкретных instance-ов, элементы которых были изменены.
Массив ведь меняется не целиком, а частично. Добавили новый элемент. Изменили существующие. Удалили элемент. Любое из этих изменений вызовет ререндер компонента списка. Но при правильно организованном коде дочерние компоненты лишний раз вызываться не будут.
Вашем случае для всех элементов потому что key="key"
Для каких всех? Я для вас привёл сверх-простой пример где всего один элемент. У него уникальный key (тот самый который key="key", но вы можете поменять это на любую другую константу). Задача для key — позволить React-у сопоставлять элементы между render-ми.
Умоляю, откройте уже документацию. Вы не понимаете о чём вы спорите.
В последнем кейсе в MobX перерендера списка не будет, если массив вручную мутировать, но если у нас такая ситуация, когда на каждый экшн нужно перезапрашивать весь список с бэкенда и перерисовывать, то при присвоении этого нового массива в observable-свойство все перерисуется, верно ведь?
О, кажется, Вы открыли мне глаза на тормоза одного из наших внутренних продуктов, заказанных "на стороне" - пока шла разработка, всё "летало", а как запустили в прод, буквально через полгода начались тормоза... при чём тормоза (по несколько минут на отрисовку) при работе с не особо большими таблицами - буквально по паре тысяч строк, при том, что мой "костыль" на php обрабатывал их за доли секунд. Да, наш "внутренний продукт" был написан на Реакте, в котором я разбираюсь едва ли более, чем никак, собственно, из-за чего я и не смог предложить внятного решения, кроме как резать ежемесячно таблицы...
Напомнило, как лет 20 назад "программист 1С" (на самом деле, не 1С, а RS-Balance, но суть это меняет не сильно), очень удивился, когда его отчёт вместо привычных 15-20 минут стал выполняться за 5-7 секунд, всего лишь после того, как я порекомендовал всю логику унести на серверную сторону, в то время как в изначальном виде, "отчёт" по OLE создавал файл в Excel, выгружал в него "необработанные данные" и уже "на листе Excel" их обрабатывал (группировал, сортировал, и вообще творил всякие вычисления)... по OLE... я не программист, но даже мне это было "странно".
OLE/COM-интеропы это та ещё жопа в производительности. Как-то раз писали хреньку для миграции документов из ворда в другой вид ворда (и да, на реакте :-). Обработка в цикле таблицы в строк так 500 через интероп — занимала, чтоб не соврать, ну минут 15. Переделали на генерацию скрипта на VB6, передачу его в ворд, с последующим возвратом склеенного из строк подобия JSON'а — та же самая таблица на 500 строк уже обрабатывалась за 300-400 миллисекунд!
Поэтому у дева должен быть старый Пень с экраном 1024х768 и дайлапом )))
Поддерживаю основную мысль, но ваш пример переиспользования объекта – плохо.
И дело именно в том, что функция не чистая. Не та, которая вызывает reduce, а та, которую вы передаёте в reduce. Та самая коротенькая
(accumulator, item) => {
accumulator.push(...something(item));
return accumulator; // это ключевая строка
}
А проблема на самом деле в использовании reduce там, где должен быть map или filter.
А проблема на самом деле в использовании reduce там, где должен быть map или filter.
Вы уходите в частности не имеющие отношение к обсуждаемой теме. Тело функции-callback-а, передаваемого в .reduce может быть сколь угодно сложным и витееватым. Ключевым (относящимся к теме) является — мутируем ли мы результат, или возвращаем копию+изменение.
Причём если с массивом вы в этом тривиальном примере (специально тривиальном, чтобы не морочить голову), можете обойтись .flatMap-ом. То что вы будете делать с формированием не массива, а объекта? Возвращать [key, value] и писать какой-нибудь мутабельный zipObject?
И дело именно в том, что функция не чистая. Не та, которая вызывает reduce, а та, которую вы передаёте в reduce. Та самая коротенькая
Я знаю. Но nobody cares, ведь так, да? ;-) Догматизм — зло
Может, догматизм и зло, но если нас от всего reduce интересует лишь обход массива — почему, блин, не воспользоваться семантически верным forEach?
Можно. А смысл? Те же проблемы, что и у for-of. Можно сразу взять for-of, зачем forEach?
// ^ рвём цепочку
const data = {};
for (const [key, value] of Object.entries(obj))
data[key] = something(value);
// возобновляем цепочку (если надо)Вариант с reduce позволит не рвать цепочку и не перегружать код (имхо). Но я понимаю, что это вкусовщина. Главное не тащить сюда квадрат.
Вы можете в этой функции мутировать внешний по отношению к редьюсу стейт, это правда. Но вот аргументы редьюса трогать это плохая практика.
В вашем примере если вам не устраивала результирующая производительность стоило воспользоваться флатмапом, который семантически ровно то, что нужно. И рассчитывать, что вот флатмап как раз оптимизирован чтобы не переаллоцировать буфер между итерациями.
В общем, по сути статьи я согласен, но в деталях скрылся дьявол
объект аккумулятора начнется как-нибудь хитро кэшироватьяс между разными вызовами редьюсов то можно будет ловить веселые приколы
В пределах одного вызова reduce? Это как? Если же нет, то не совсем понял проблему, т.к. мы же всегда создаём новый аккумулятор (2-ым аргументом).
воспользоваться флатмапом
Я просто не хотел переусложнять пример. Если у вас есть под рукой подходящий пример где точно нужен reduce, но он не отвлекает на себя много внимания, я был бы рад :)
не устраивала результирующая производительность
Категорически не устраивает. Но не в моём коде, а в чужом, который мне приходится запускать у себя. Людей устраивает. А не должна. От этого и бомбит.
В пределах одного вызова reduce? Это как? Если же нет, то не совсем понял проблему, т.к. мы же всегда создаём новый аккумулятор (2-ым аргументом).
Я не придумал в конкретном случае) Но если это дается как общий совет, то такие случаи когда что-то там мемоизировалось и мутировалось у меня бывали, и последствия были плачевные.
С мутабельностью удобно работать когда в сигнатуре видишь (State m) => ... -> m Number, а без этого знание что формально мы можем представить что всё чистое… Ну мы можем точно так же представить, что любая сишная программа чистая, просто var x = y это на самом деле не let а монадический бинд, а все функции написаны в IO. Формально будет верно, по факту никаких гарантий не добавит, и код как был ногострельным так и останется.
Я просто не хотел переусложнять пример. Если у вас есть под рукой подходящий пример где точно нужен reduce, но он не отвлекает на себя много внимания, я был бы рад :)
Ну, я в принципе так и подумал, что это упрощение ради примера) Надо подумать — ломать не строить. Если придумаю — напишу. Но как простой ответ можно как раз сказать "редьюс тут плохо подходит по семантики из-за сложности, но вот есть флатмап". По сути это ведь и есть флатмап. Как вариант или взять его из стандартной поставки, или написать свой. Но если писать свой то наверное лучше использовать родной for, а не редьюс. Хотя бы как семантический фактор "здесь происходит нечто что плохо ложится на существующие комбинаторы". По крайней мере у меня такой подход обычно — если пихание мутирующих функций в редьюс выглядит чужеродно, то оно так и есть, и стоит его избегать. У меня по крайней мере такое впечатление.
Категорически не устраивает. Но не в моём коде, а в чужом, который мне приходится запускать у себя. Людей устраивает. А не должна. От этого и бомбит.
Прекрасно понимаю и сочувствую. Сам на ревью на прошлой работе практически настроил автоматический возврат кода на доработку если там есть авейт в цикле. Но они продолжали приходить.
Все что остается — писать подобные образовательные статьи и надеяться на постепенный рост средней квалификациии разработчиков. Не впадая в "а вот в наше время были богатыри — не вы", сейчас качество разработчиков очень выросло. Что ни говори, DDD была овер хайпанутая тема 10-15 лет назад, а ведь по сути там все сводится к "не запускайте ракеты из класса юзера". Чуть позже откровением был SOLID — щас разработчики просто плечами пожимают "ну да, а как ещё разрабатывать, говно ж выйдет".
Понемногу идем. Но да, чтобы процесс шел нужны обучающие материалы вроде этой статьи. За что спасибо
Сам на ревью на прошлой работе практически настроил автоматический возврат кода на доработку если там есть авейт в цикле.А как быть, если каждая итерация берёт данные из предыдущей итерации?
Ну тогда очевидно никак. Но в 99% никаких зависимостей нет и код выглядит так:
const orders = [];
for (let orderId of orderIds) {
orders.push(await getOrder(orderId));
}И тут как бы печально от этого цикла становится
Зато с таким кодом нагрузка на сервер более равномерная.)
Это правда. Но я считаю что сервер если не справляется с нагрузкой должен сам троттлить запросы клиента, а не клиенты должны писаться с осторожностью. Потому что только сервер знает реальную нагрузку и если его внезапно оптимизируют/переведут на более мощное железо то идти искать все места где его щадят.
Вероятно я отвечаю на сарказм, но раз уж написал то пусть будет
Троллтить, всмысле возвращать ошибку "вы сделали слишком много запросов в минуту, поэтому мы заблокировали вас на 5 минут и просим решить зубодробительную каптчу"?
Сарказм, конечно, но в любом сарказме есть доля суровой реальности.
Но это получится только если сервер и правда умеет управлять ресурсами, причём его управление ресурсами совпадает с требуемым. А реализовать такое управление ресурсами — куда более сложная задача, нежели ограничить число параллельных исходящих запросов.
Но в 99% никаких зависимостейДа, но линтер не пропускает этот 1% случаев. =) Хотя в Javascript большинство линтеров поддерживают игнор.
Да, это как раз такой случай, когда иногда это может быть корректно, но почти всегда нет. И да, линтер по идее должен уметь различать случаи когда есть явная зависимость между итерациями result = await foo(result.Something, somehingElse)
И да, линтер по идее должен уметь различать случаи когда есть явная зависимость между итерациями
result = await foo(result.Something, somehingElse)
Зависимость может быть и неявной. Например, на позапрошлой работе, помнится, были запросы на получение рекламы. С требованием "только один запрос в любой момент времени", чтобы не перетерлись изменения в куках.
Но это совсем уж редкие кейсы..
Этот цикл особенно печален тем, что бэк не сделал (или сделал, но фронты не знают) сервис для getOrders(orderIds), чтобы одним запросом.
сама сигнатура reduce заточена под чистую функцию
Забыл отметить, что пока у нас нет настоящих immutable data structures не так важно, как .reduce задумывался (в FP мире). В scala для таких вещей у ребят есть специальные древовидные коллекции с O(logN) на операцию. А у нас шиш.
Кстати в lodash есть _.transform, который изначально игнорирует возврат из callback-а (точнее поддерживает только ранний выход из итерирования). Лично мне не хватает его в стандартной библиотеке.
Вот! В _.transform всё сделано так, что сразу понятно, что она ждёт не чистую функцию, а функцию, модифицирующую аккумулятор. Собственно, можно reduce завернуть аналогично.
Дело-то не в догматизме, а в "принципе наименьшего удивления".
А так, конечно, тут не хватает линейных типов. Чтобы если вы передали accumulator в качестве аргумента reduce – то всё, дальше по коду ваш accumulator недействителен.
Дело-то не в догматизме, а в "принципе наименьшего удивления".
Ну вот если бы речь не шла об O(n^2) вместо O(n) я бы с вами согласился. Можно было бы говорить про удивление, чистоту кода и т.д… Но увы, на другой чаше весов куда более серьёзный аргумент.
И да, было бы классно иметь transform в Array.prototype.. Тогда сам вопрос бы отпал как таковой.
Так кто мешает? Array.prototype.transform=function(...)
И не надо говорить про чаши весов. Заверните reduce (или даже цикл) в функцию с понятной сигнатурой и пользуйтесь. Если, конечно, не хватит map/filter.
В смысле, я ратую за то, чтобы писать O(n), но понятное O(n) :-)
Так кто мешает? 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. Дескать в этом проблема (хотя признаю, что в этом тоже есть проблема — "магическая оптимизация" сорвалась).
И такой вот софт где народ не думая городит ну вот прямо на пустом месте аховую асимптотику всё больше и больше.
Ok, за Array.prototype.... прошу прощения. Но никто не мешает иметь то же самое отдельной функцией. С понятной сигнатурой и сложностью O(n). Для этого даже композиция функций не нужна.
Но никто не мешает иметь то же самое отдельной функцией
На самом деле мешает. Сейчас в JS нет удобной возможности не рвать цепочки, т.к. pipe-оператор уже многие годы висит среди незавершённых спецификаций. По сути говоря любой метод, которого нет в chain-е вынуждено заставит вас разворотить всю цепочку трансформаций. Вот с ним такой проблемы уже не будет.
Но мне кажется наш разговор зашёл куда-то не туда. С вашей точки зрения нарушать кем-то придуманную семантику reduce это большой грех. А с моей точки зрения — нет. И то и другое — субъективщина. Поэтому предлагаю на этом и закончить. А то мы скатимся в какой-нибудь холивар про "читаемый\нечитаемый код", "признаки оценки качества кода", "роль семантики в разработке ПО" и пр.
Я тоже любил цепочки. С ними код такой лаконичный. Пока не начал пользоваться отладчиком. А дебажить цепочки - это просто ад. Гораздо удобнее, когда есть отддльная переменная на отдельной строке. Тогда и брейкпоинт можно поставить, и значения на каждом шаге посмотреть, перепрыгнуть шаг-другой, ну и мелкие изменения не приводят к куче правок в коде с разрывами цепочек.
Но вот на
O(n)у него глаз не дёрнулся.
А почему у него на 0(n) должен был глаз дёрнуться ? Разве можно собрать зависимости всех нод, не пройдясь по всем нодам ? Удивите)
Чувак создал PR где заменил
O(n^2)наO(n)и удивлён что это вообще что-то дало.
Это означает, что он явно не понимает, что пишет. Так делать нельзя.
> И такой вот софт где народ не думая городит ну вот прямо на пустом месте аховую асимптотику всё больше и больше.
Это просто "кодирование не приходя в сознание". Там может быть много причин - низкая квалификация, повышенные требования по скорости, выгорание, следование хайпам и т.д.
Это просто "кодирование не приходя в сознание". Там может быть много причин — низкая квалификация, повышенные требования по скорости, выгорание, следование хайпам и т.д.
Хотелось бы так думать. Но, как вы сами видите, даже здесь в комментариях более чем достаточно людей, которые вообще не видят в этом никакой проблемы. Причём людей с богатым опытом в разработке.
Пока меня пугает сам тренд на "всё что не убивает меня, делает меня сильнее не имеет значения", кого-то пугает что ещё есть люди, которые видят в этом проблему :)
Пока меня пугает сам тренд на "всё что не убивает меня,
делает меня сильнеене имеет значения", кого-то пугает что ещё есть люди, которые видят в этом проблему :)
Это непосредственное следствие культуры "х*як-х*як и в продакшн", которая непосредственное следствие высококонкурентной среды и коротких горизонтов планирования, которая есть просто рыночная экономика. Поэтому я как-то к этому очень по-философски отношусь - снявши голову, по волосам не плачут.
Я, кстати, понял, что даже в кондовейшем квадратно-гнездовом C можно легко воспроизвести ваш случайный O(N^2), если писать не приходя в сознание:
void my_string_transform(char *s) {
int i;
for( i = 0; i < strlen(s); i++) {
....
}
}
То есть, JavaScript, как язык, и функциональщина, как подход, тут не при чём.
Я, кстати, понял, что даже в кондовейшем квадратно-гнездовом C можно легко воспроизвести ваш случайный O(N^2), если писать не приходя в сознание:
Формально да, но компиляторы уже давно знают про strlen, так что если строка в цикле не изменяется, то компилятор вполне может вынести strlen из цикла. Но да, так писать всё-таки не стоит.
Не всегда кстати C++ компилятор может убрать вызов функции на каждой итерации. Потому что если в итерации вызывается какая-нибудь функция “f” и компилятор знает только ее сигнатуру, но не реализацию, то вполне может быть что данная функция меняет строку через глобальную переменную и поэтому вызов strlen нельзя кэшировать.
Справедливости ради, проблема была не в самом методе конкат
Не соглашусь. Там просто две проблемы. Одна с isConcatSpreadable, а другая в .concat in .reduce. Причём ему хватило даже решения второй проблемы. Но чувак дотошный (а почему с wp4 не тормозит?) и он нашёл ещё и 1-ую.
Справедливости ради, я думаю, что решение проблемы с isConcatSpreadable даст куда больший impact, т.к. affect-ит сразу всю запускаемую кодовую базу.
но я не вижу свидетельства того, что в данном случае проблема была именно в concat
Гхм. Всмыыыыысле? Без concat проблемы нет. И не важно стоит ли isConcatSpreadable или нет. Это css-in-JS поделие о котором там речь, работает "drammatically faster" если убрать квадрат. Если это не свидетельство, то что же тогда свидетельство?
Полностью согласен с mayorovp, isConcatSpreadable просто заметал проблему под ковёр.
Вот давайте проверку на прочность проведём:
- Не накатываем патч с
O(n). Но накатываем патч сisConcatSpreadable. Проблема решена? Да. Проходит время, N увеличивается. Проблема осталась? Осталась. - Поступаем наоборот. Обе ситуации — всё работает быстро.
Ну а вариант — накатываем оба патча, конечно лучше.
Проблема была именно в квадратичном алгоритме, оптимизированный concat лишь позволял её спрятать.
Справедливости ради, проблема была не в самом методе конкат.
Проблема в том, что люди не понимают то, что пишут. А метод - это как молоток - инструмент.
Вообще, да, хотелось бы иметь интерпретатор для JS, ну или хотя бы компилятор типа TS, который умеет вызовы типа arr.map(...).filter(...).reduce(...) разворачивать в O(n).
Как-то слишком много магии, имхо :) Да и вообще нам бы куда более простых инструментов бы завезли. Например, чтобы не писать:
<Button style={style} onClick={onClick} blabla={blabla} />вместо
<Button { ...{ style, onClick, blabla }} />потому что:
- TS позволяет в этом spread-е передать лишние поля :-(
- TS не оптимизирует 2-ую конструкцию в 1-ую
Если 2-е можно сделать плагином для TS, то вот первое уже нет, т.к. TS не умеет в плагины до type-checking-а :(
AFAIK, любой интерпретатор JS исполняет arr.map(x => x + 2).filter(x => x > 0).reduce((a, b) => a + b) за O(n).
Вот прямо в точку.
Тоже хотел написать, что меня выводит из состояния покоя, что есть "черные ящики оптимизации" в компиляторах.
Можно усиленно стараться и писать алгоритмически красиво, но другой разработчик написал редьюс с O(n^2), но компилятор это увидел на втором шаге и под капотом сложил все в оптимальную структуру, а потом это все еще и отсортировал как нужно.
Кстати, наверное будет всеже что-то близкое к O(n*log(n))
Ну формально да. Потому что O(3n) === O(n) 😅
А разве это не любой делает?
В GHC есть оптимизация этого под названием stream fusion, которая просто засовывает всё в один цикл вместо нескольких последовательных. Но сложность вычислений вот просто так вроде бы не меняется.
У меня вот такая штука есть. Там, правда, filter и reduce ещё не реализованы.
Но оно не поможет бороться с алгоритмической сложностью. В частности, ваш код и так линеен.
Приведённый вами пример и отрабатывает за O(n). Три (константа) прохода по списку - это O(n). А вот оптимизация вычислений, чтобы это был один проход, а не 3 - это было бы здорово... Можно написать цикл... Ах, ну да, чтобы не писать циклы это всё и придумано.
Да, пожалуй, неверно выразился. Конечно, речь о том, чтоб все это выполнялось за один проход цикла. Собственно, если не ошибаюсь (не силен в ФП), некоторые языки такое позволяют на этапе компиляции. Не отношусь к фанатам подобных конструкций как раз из-за множества проходов, отсутствия break, не говоря уже о том, что сам по себе forEach и любой из его собратьев медленнее обычного for, хотя сейчас уже прикрутили какие-то оптимизации в движках.
Это можно сделать за один проход и без ФП, через итераторы. Если не ошибаюсь, то в 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])
)
);
А потом на ревью прилетит «а че ты так сделал, а не через .../[]?». И доказывай что не занимаешься преждевременной оптимизацией.
Раньше был такой такой чеклист, от авторов Bluebird, в котором были собраны техники оптимизации для оптимизирующего компилятора хрома. Все им пользовались и считали за бест-практайс. На интервью спрашивали. А потом выпустили новый движок и все оптимизации стали не актуальны. Думаю, так же произойдет и с тем о чем вы рассказываете: допилят оптимизации на уровне движка и все ухищрения на уровне кода станут дремучим легаси.
И доказывай потом что не занимаешься преждевременной оптимизацией.
Заниматься обучением своих коллег — не грех. Если сильно непробиваемые, можно сменить команду. В конце концов это ваш выбор, с кем вы работаете.
Думаю, так же произойдет и с тем о чем вы рассказываете
Не произойдёт. См. раздел "3. Умный компилятор всё оптимизирует" в статье.
Заниматься обучением своих коллег — не грех
Я и сам-то не уверен что это не преждевременная оптимизация
Если сильно непробиваемые, можно сменить команду. В конце концов это ваш выбор, с кем вы работаете
Простите, но я не готов отстаивать эту тему настолько, чтобы терять из за нее работу )
Не произойдёт. См. раздел "3. Умный компилятор всё оптимизирует" в статье.
У вас там все очень категорично, не могу на это конструктивно ответить.
Могу только это прокомментировать:
Как это гарантировать в языке, в котором почти ничего нельзя гарантировать
А зачем что-то гарантировать? Аргументация построена на введении излишнего и заведомо не выполнимаого ограничения, которого нет в реальности. В JS-е ничего не гарантировано, но связка из трех компиляторов со всем справляется и быстро. Собственно, тут вопрос не принципиального ограничения, а просто пока что у инженеров V8 руки до этого кейса не дошли
Я и сам-то не уверен что это не преждевременная оптимизация
Я в статье разобрал ситуацию когда это может быть преждевременной оптимизацией. Когда у вас гарантировано малый N. Там просто разница в производительности не делает погоду.
но я не готов отстаивать эту тему настолько, чтобы терять из за нее работу )
Зачем же доводить до крайностей. Вы видите участок кода, которые является проблемным. Вам задают вопрос — почему так написано. Вы объясняете почему. Предположим с вами не согласны. Вы приводите аргументацию. Вам приводят свою. Если выясняется, что вы не правы, пишете исправляете. Если выясняется, что вы правы, но ваши коллеги не убеждены — работаем над своими soft-skill-ми.
Но изначально писать откровенно плохой код по причине, а вдруг на ревью кто-то подкопается, это очень плохо.
А зачем что-то гарантировать?
Вы понимаете, что единственная серьёзная оптимизация, которая вам тут может быть доступна (нужно вместо O(n^2) сделать O(n)) — мутировать коллекцию под капотом. И компилятор не может себе этого позволить не убедившись в том, что коллекция гарантировано никому не доступна кроме итогового адресата у .reduce? И теперь вопрос — как вы собираетесь это проверять?
Какие эвристики? Какие контракты? Какие оптимизации? Какие затыки? Можно чуть менее магическим языком, конкретику? ;-)
Я ещё напомню, что речь идёт ДАЖЕ не о TypeScript где у компилятора есть хоть какие-то зацепки.
А вообще с этими "преждевременными оптимизациями" народ кажется сходит с ума. Одно дело когда нужно перепахать кодовую базу, переписав алгоритм до неузнаваемости. Или скажем когда нужно сильно усложнить архитектуру, дабы добавить что-то, что возможно не пригодится. Или когда экономия происходит там, где от этого почти никакого толку, при наличии настоящих bottle necks.
Например мне запомнился товарищ, который на JAVA backend-е писал все HTML шаблоны в обычных JAVA class method-ах используя string builder и ручное экранирование всего и вся. Он же для всех сетевых взаимодействий использовал web-socket-ы, чтобы избегать лишних заголовков и overhead-а на JSON. Вот это я понимаю preliminary optimizations.
Но когда речь идёт об одной единственной примитивной строке в очевидно опасном месте… Кажется люди стали использовать эту фразу ("преждевременная оптимизация") чтобы ничего никогда никак не оптимизировать, пока к ним Task-а в Jira не прилетит. На мой взгляд, это очень плохо характеризует всю нашу индустрию. Становится понятно, почему многие ассоциируют слово "javascript" исключительно с негативом.
Как видите, карма не позволяет мне слишком углубляться в дискуссии, так что отвечу только на одно.
И компилятор не может себе этого позволить не убедившись в том, что коллекция гарантировано никому не доступна кроме итогового адресата
И теперь вопрос — как вы собираетесь это проверять?
Тут я вступаю в тему, в которой мало смыслю, но разве виртуальная машина не ведет подсчет ссылок? Если ссылка всего одна, и она в параметрах reduce, то это значит что объект никому кроме тела этой reduce не доступен.
не ведет подсчет ссылок?
Кажется в Swift и Objective C ведёт. А у нас Garbage collector. Для поиска неиспользуемых нод алгоритм пробегает от корня до листьев древа и помечает ноды как достигаемые. А потом пробегает по всем нодам вообще и те, что не помечены, удаляются. Это в общих чертах.
По сути желаемая оптимизация потенциально возможно в функциональных языках со строгой типизацией и мощной системой типов. Ну во всяком случае я думаю что возможно она им доступна. У них там прямо очень много что возможно, по целому ряду причин. Например т.к. там настоящая иммутабельность, что гарантирует то, что никакие изменения не прилетят "сбоку" откуда не ждали. И, мне кажется, компилятору (не в runtime) проще отследить те места, в которых можно точно сказать, что на сий объект больше никто точно не может ссылаться. Но тут надо спросить у самих FP-ов, насколько мои фантазии к ним применимы.
Это же ECMAScript. Поэтому всегда может найтись прибитый сбоку оверрайд Array.prototype.push, который делает персональные данные массива доступными для неопределённого круга лиц. И даже если так делать давно не принято, сам факт существования такой возможности делает множество видов ссылочных оптимизаций де-факто нерабочими.
Я в статье разобрал ситуацию когда это может быть преждевременной оптимизацией. Когда у вас гарантировано малый N. Там просто разница в производительности не делает погоду.
Есть еще вариант - когда рядом еще более тяжелый O(N^2).
Вообще я часто пишу неоптимальный код, осознавая это, и исправляю только если это не ухудшает читаемость. Но очень редко это приходится оптимизировать из-за дальнейших проблем с производительностью. В коде есть места, где каждую структуру нужно выбирать аккуратно, а есть места где "гуляй, рванина", и можно сколь угодно медленно писать.
Думаю, так же произойдет и с тем о чем вы рассказываете: допилят оптимизации на уровне движка и все ухищрения на уровне кода станут дремучим легаси.
Завязка на оптимизации делает код хрупким, поэтому крайне нежелательна. Для ухода от хрупкости, скажем, в C++ ввели constexpr, в Ocaml ставят явную аннотацию [@tailcall], чтобы даже 40 лет как имеющаяся оптимизация срабатывала или несрабатывала явно.
Плюсую, тоже не раз и не два замечал эти конкаты и тому подобное.
Если не нравится лишняя строчка, то вместо
(accumulator, value, key) => {
accumulator[key] = something(value);
return accumulator;
}, {}можно писать
(accumulator, value, key) =>
accumulator.set(key, something(value)),
new Map()
Потому что
Explicit is better than implicit (c) PEP-20
Не надо создавать и использовать микроскопы в среде, которая проектировалась под молотки.
Не совсем понял ваш аргумент. Вы имеете ввиду не надо играть в 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;
}Правда такой уникум был только один :)
Я к тому, что нужно блюсти баланс между выразительностью/читабельностью кода, компетенцией людей, которые с ним работают, и возможностями языка по контролю ошибок.
Несоблюдение баланса неизбежно пораждает множество неочевидных проблем. В посте приведён пример неверного использования функциональщины в JS, но это частный случай. Так же можно упороться и в ООП и в других языках.
Так в
pythonтоже естьreduce
Это не значит, что его надо использовать везде и всегда :-)
Или вы в целом за
for (;;)
В языках, которые не рассчитаны явно на функциональный стиль кода, я за явные циклы. Слишком часто видел как даже (очень) опытные люди косячили из-за того, что не заметили сложность, спрятанную за функцией или методом.
И втихую мечтаю о языке/инструменте, который будет статически анализировать вычислительную сложность и писать варнинги.
Вы имеете ввиду не надо играть в immutability в языке, в котором для этого ничего нет? И по сути просто не пользоваться
.reduce, т.к. он неявно подразумеваетO(n)? Так вpythonтоже естьreduce.
Да, было бы неплохо поуменьшить использование редьюс, особенно с такими костыльными конструкциями. Лучше использовать более читаемые и подходящие под текущую ситуацию методы вплоть до for'ов.
Где-то вдалеке заплакал "redux-программист" :-)
А при чем тут redux? Нормальные люди давно используют redux-toolkit, где не нужно изгаляться.
Рад за них. Я чуть менее нормальныепрогрессивные продолжают писать ...-пирамидки.
Под капотом redux-toolkit используется immerjs, который можно подключить в отдельных местах. Оно конечно, делает некоторую деградацию по перфомансу, но это увеличение константны, а не асимптотики.
Угу, я знаю. Я где-то 4 года назад написал собственную версию immerjs, просто потому что кто-то на хабре упомянул саму идею того, что при помощи proxy такое можно реализовать. А найти готовое решение мне не удалось. Оказалось несложно, но то и дело что-нибудь отваливалось (например так я познакомился со всякими хитрыми Symbol.*, о которых раньше либо не знал, либо забыл. В общем были свои tricky cases.
Об immer я узнал из уст одного из интервьюверов. Попросили рассказать что-нибудь интересное, я рассказал про этот solution, а мне в ответ — чувак, ты изобрёл велосипед. Держи immer ("всегда" по-немецки). Было даже немного обидно :-D
Вы имеете ввиду не надо играть в immutability в языке, в котором для этого ничего нет?
Ну в каждом языке есть свои выразительные средства, органичные для него. И если что-то влезает с огромным трудом, то может быть не надо?
Функции высших порядков, кстати, всю жизнь работают в нечистых функциональных языках, вроде ML (SML, OCaml) или Scheme. Просто там как-то привыкли что да, могут появиться от неаккуратного использования примитивов разные странные штуки. Но в целом никаких особенных оптимизаций в том же Ocaml нет - компилятор отрабатывает за 0.5 сек даже большие файлы, всё просто и квадратно-гнездово. Это не GHC.
Со spread-оператором выяснилась (на десятках собеседований) интересная ситуация. Почти никто не знает, как он на самом деле работает. Я не шучу. И нет, я не про Symbol в прототипе.
Я предпочитаю на code-interview не заставлять человека писать код, а подсовывать ему кусочки кода и смотреть на реакцию. Так вот — ПОЧТИ ВСЕ думают, что ... spread operator копирует объекты в глубину. Я не шучу. 8 из 10, наверное. Причём кандидаты на senior позицию.
И нет, речь не про "ой, что-то я затупил, да, конечно, это работает не так". Мне несложно подсказать. Мне плевать если кандидат не ответил сразу правильно. Важно понять — человек в целом понимает что это и с чем это едят, или нет. А вот прямо делают удивлённое лицо и "ого, а я всегда думал что это полное копирование в глубину". И после всего этого уже я сижу с круглым лицом и думаю. Ну ок, положим ты и правда не знал этого до сего момента. Ну с кем не бывает. Но ведь ты наверняка уже пару сотен раз его использовал в своём коде (или тысяч). Не приходила в голову мысль "о боже я копирую большой объект в глубину, это должно быть охрененно долго"? :-) Видимо нет.
ПОЧТИ ВСЕ думают, что
...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там просто тупо развернуто.
Или вы про это вот?
Да, про него.
Неужели действительно находятся те кто думает, что результат будет "глубже" чем у того же assign или slice?!
Да, почти все.
Соглашусь с вами: очень много людей думает, что они так копируют объект. Сколько уже исправлений этого мной написано - не пересчитать.
Я пришёл в js из софта, потому такие ошибки часто бросаются в глаза.
forEach недолюбливаю за невозможность остановки по break. Понятно, что есть every или some, но, как показывает практика, многие с такой конструкцией не знакомы
Вы будете смеяться, но серьезные такие ребятки из AirBnB .forEach вместо for() жестко насаждают через Policy. Причем факт того, что по break не выйти из итерации их никак не смущает.
Для этого есть финты в виде every и some...Но все равно это кривость...
Я, когда на сайте реакта читал о хуках и для чего они их сделали, жестко приуныл и уже тогда начать думать куда мылить лыжи из фронтенда: ползти в бакенд или уходить в С++ софт/игры...
финты в виде every и some
Break позволяет чутка экономить время, в отличие от предлагаемых Вами финтов.
React пытается развиваться, но это колосс на глиняных ногах, к которому надо еще сверху и сбоку прикрутить десяток модулей, чтоб юзабельно было. Но если не лезть в redux и прочие поделки, то вполне жить можно.
На $mol ползите, у нас такой ерунды нет.)
Вы будете смеяться, но серьезные такие ребятки из AirBnB .forEach вместо for() жестко насаждают через Policy. Причем факт того, что по break не выйти из итерации их никак не смущает.А какое обоснование? в чем плюсы?
Скорее всего консистентность кодовой базы. Чтобы каждый не лез кто в лес, кто по дрова выбрали что-то одно. Да и в целом нынче такой тренд, мол for ;; слишком "сложный". Кажется в swift от него вообще отказались, оставив только for in .. и итераторную версию.
Вот тут у них написано.
Вкратце:
Why? This enforces our immutable rule. Dealing with pure functions that return values is easier to reason about than side effects.
Только вот фокус в том, что как раз цикл for-of можно использовать для построения той самой pure functions that return values, в то время как forEach уже сам по себе основан на сайд-эффектах.
В общем "функциональность головного мозга". Мне один такой пациент с похожим обоснованием пытался запретить использовать let и var.
справедливости ради конструкция вида { ... obj } действительно делает поверхностную копию объекта
справедливости ради конструкция вида { ... 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Вы, кажется, говорите об одних и тех же вещах, но разными словами.
Она создает новый объект, и передает в него spreaded итератор в виде "списка" object literal аргументов aka key-value pairs...
Вы только что описали один из способов сделать shallow object copy. Та самая "поверхностная" (shallow) копия объекта.
Конечно всегда можно погрузиться в детали. Например если переопределить метод-итератор, т.е. написать свой собственный, то туда можно хоть числа Фибоначи воткнуть. Или начать обсуждать нюансы того какие поля будут переданы по-умолчанию, а какие нет.
Но… это уже нюансы. Концептуально поведение объекта по-умолчанию — создать его shallow копию.
Ну spread operator как бы вообще ничего не копирует (ни в глубину, ни на плоскости), это тупо expand arguments сахар (разворачавающий итерируемое и подменяющий
applyи т.п.)
Объект в общем случае (для object spread) не обязан быть итерируемым, чтобы к нему можно было применить object spread. Для использования в контексте списка значений - да, обязан.
Нет! Обязан (ибо он работает не так как вы себе представляете).
Попробуйте передать туда неитерируемый объект, или переопределите его iterator, чтобы он выкидывал исключение. Я вас уверяю вы его (исключение) обязательно поймаете.
Посыпаю голову пеплом и выражаю глубочайшие извинения ув. @JSmitty
Только что написал в консоль {...10} и оно создало мне пустой объект... Хотя я мог бы поклясться, что уже делал такое как-то и оно вылетало с ошибкой. Возможно Object.assign переделали с той поры... или это просто старость.
Еще раз прошу прощения если кого ввел в заблуждение.
Потому что {...obj} и [...seq] — это разные конструкции, и работают они по-разному. Как раз вторая и требует итератор, который можно переопределить и т.п.
А первая просто копирует перечислимые собственные свойства объекта, независимо ни от чего. Переопределить тут можно разве что Proxy подсунув.
Вероятно вы перепутали работу spread оператора для объектов и массивов. Для массивов требуется рабочий Symbol.iterator, для объектов - нет (его у них и нет)
({})[Symbol.iterator] // -> undefined
([])[Symbol.iterator] // -> values() { [native code] }Я знаю что [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-подобных конструкций (чтобы, производительности ради, не разворачивать списки от дефолтных "итераторов" в стек).
просто когда (в proposal ES2018 если не ошибаюсь) речь велась про object literals, это определялось как "pass all key:value pairs from an object"…
…что как раз и означает взятие всех перечислимых собственных свойств объекта. Если что, перечислимость свойств — куда более древнее понятие, нежели Symbol.iterator. Собственно, оно древнее символов.
по крайней мере с assign такое нельзя (там только два аргумента — target и source)
Э-э-э, но ведь у assign можно указать произвольное число аргументов!
Что они уже после ES2018 накрутили, чтобы даже скалярный объект воспринимался как валидный, мне не очень понятно
А почему он, собственно, не должен восприниматься как валидный, если spread operator в контексте литерала объекта изначально создавался для работы со скалярными объектами?
даже скалярный объект воспринимался как валидный
У примитивов нет свойств и методов 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 изначально не было специальных типов для коллекций.
По спредам, кстати, можно в статью добавить, что если передача массива в функцию - константная сложность, то передача элементов через спред - это уже линейная, ибо компилятору проходится копировать массив в стек. Соответственно, получаем ещё и риск переполнения стека.
Вся проблема в вайтишниках
Сама статья является хорошим напоминаем помнить об алгоритической сложности кода который вы пишите, но ни reduce ни destructuring assignment сами по себе не дают вам O(n^2). Есть тысяча и один способ написать код неэффективно.
по себе не дают вам 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) и не страшны? Да, согласен. Нормальные инструменты. Ничего против не имею.
Да, я именно про то что по отдельности все эти инструменты (ингридиенты) хорошие. Проблемы возникают уже в процессе их совместного применения (рецепте приготовления).
Получается что это O(((1 + N) ^ N) / 2). Но какая-то шибко мудрёная запись.
Наверное, вы O(((1 + N) * N) / 2) имели в виду, а не возведение в степень и не xor.
Так вот, O(((1 + N) * N) / 2) строго равно O(N ** 2), причём это верно в обе стороны.
Да, конечно, спасибо. Немного спешил и получилась ерунда, я имел ввиду * N. Это формула суммы членов арифметической прогрессии.
Возможно, не всем понятно, почему получается эквивалентность, в обе стороны. Попробую на этом же примере и продемонстрировать, почему.
Учитывая, что 1 <= N выполняется для всех натуральных N:
Это в одну сторону. А в другую, учитывая, что 0 <= N выполняется для всех натуральных N:
Т.е. с точностью до константы, как подразумевает О-нотация. (C = 2)
O(n) + O(1) == O(n). Большее слагаемое поглощает меньшее.
O(n*2) == O(n). Константный множитель неважен.
Можете теорию почитать, но на практике достаточно этого (и памяти, что все эти O – только при n стремящемся к бесконечности)
Разве я не тоже самое написал? :) (если учесть опечатку с ^ вместо *)
На итог то же самое. Просто коммент создал ощущение какой-то неуверенности в том, как работать с O(...), вот и позволил себе напомнить несложные правила их упрощения. Извиняюсь, если задел.
Да не, что вы. Всё ок. Я признаться вообще не силён в математике, и понимаю всё это примерно на том уровне, что вы и описали. Мысленно возвожу всё в предел и убираю лишние константы. По сути наибольшую сложность представляет определить изначальную формулу.
Да там первые 50 страниц Уиттекера Ватсона. Очень просто всё.
Не оверкилл?
А за упоминание книги спасибо, возможно, пора освежить в памяти матан, и она как раз подойдёт.
Да нет, не оверкилл. Это же проходят все студенты по тех. специальностям. Зато после нормального курса по рядам все эти интервьюшные задачи O(N) вызывают лишь один вопрос - "а проблема-то, собственно, в чём?".
Не, ну так-то для себя лишним не будет, конечно. Я имел в виду – для такой задачки нет "математической" сложности в подсчёте, сложность только в наработке рефлексов типа "а вот тут ещё внутренний цикл вылезает, надо не забыть его учесть".
Если вы хотите считать точно, то вам нужно
а) Выделить операции, которые представляют для вас интерес (это может быть доступ по указателю, сложение, деление, вычитание и т.д.). Причём если правильно учитывать архитектуру машины, ответ может быть крайне неочевиден.
б) Выписать кол-во этих операций в зависимости от кол-ва обрабатываемых алгоритмом элементов с нужной вам точностью (как правило - до старшего коэффициента). Как правило, это делается рекурсивной формулой, а дальше с использованием производящих функций переводится в явную.
По второму пункту есть отличный курс профессора Cеджвика - https://www.coursera.org/learn/analytic-combinatorics
Но он требует ТФКП (теория функций комплексной переменной), а именно - теории вычетов + курс по Обыкновенным Дифференциальным Уравнениям.
ну вы и душнилы...
Особенно в мире Javascript, который как известно скриптовый язык с динамической типизацией, и, поэтому, не предназначен для решения задач, которые требуют настоящей производительности.
Настоящей - это какой? Так-то nodejs даже на embedded-системах запускают. А во-вторых, есть вполне себе возможности выполнить родной бинарный код через C/C++/WASM, который очень все быстро посчитает, если надо.
Большинству разработчиков даже особо задумываться не приходится нынче, настолько производительные системы и V8 на текущий момент. Вот раньше было да, на iPhone 3G, если не ошибаюсь, был лимит в 256 Кбайт на страницу, там приходилось аккуратно писать, с учетом перформанса и расхода памяти.
А во-вторых, есть вполне себе возможности выполнить родной бинарный код через C/C++/WASM, который очень все быстро посчитает, если надо.
Но ведь это и называется "не предназначен для решения задач, которые требуют настоящей производительности"
Если бы был не предназначен, то не было бы 1100+ модулей, использующих C/C++: https://www.npmjs.com/package/node-gyp?activeTab=dependents
И это только то, что в npm.
WASM
Мой небольшой опыт показывает, что WASM как раз быстро вам не посчитает. У нас получалась 10 кратная разница в сравнении с бинарником.
Вот здесь разница незначительная в сравнении с бинарником, а где-то даже и быстрее. Мне трудно судить по Вашему случаю, так как неясно, на каких алгоритмах тестировали и как реализовано.
Это был алгоритм SHA1 который прогонял через себя сотни тысяч коротки строчек (примерно по 50 символов). Написан на C, скомпилирован через empscripten. Других деталей дать не могу, увы, ибо NDA. Asm.js версия в chrome была равна по скорости WASM.
Полагаю, что очень опытный системный программист смог бы всё отладить и переписать так, чтобы обойти все трудоёмкие для WASM-машины места. Но это не я, я не настоящий сварщик. То что я смог это всё собрать и запустить — уже удача :)
В 1ом пункте сами же все сказали: при малых n разницы никто не видит . И возможные проблемы верно указали. Но основная мощь стримов и лямбд именно в поддерживаемости кода и лучшей читаемости. Понятно, что потом до кода может добраться безголовый джун, но сташие не дадут и заставят переделать. А умный и опытный городить огород на таких конструкциях не станет.
Ну дык никто не запрещает вам мутировать аккумулятор в лямбде. И волки сыты, и овцы целы. Разве что внутренний перфекционист может немного негодовать, что идеалы попёрты и семантика искажена. Но лучше бы этот внутренний перфекционист переживал за более насущные проблемы, относящиеся к business value.
А умный и опытный городить огород на таких конструкциях не станет
Повторюсь, этот "паттерн" стал НАСТОЛЬКО популярен, что лезет изо всех щелей. Люди вообще не видят в этом проблемы. И такой код уходит в прод. А потом у людей "react тормозит". Хотя тормозят они, кажется, сами.
1. Не возвращают сам массив, из-за чего их неудобно использовать.
2. Это не самые очевидные функции для объединения массивов. Не уверен, что все помнят, что push() принимает произвольное количество параметров. В то время, как concat() — «сертифицированный» аутентичный способ.
Собственно, все эти npm-пакеты из одной функции тоже намекают, что в библиотеке есть, что улучшать.
Примеры красивые, но есть какие-нибудь данные о том, насколько часто "квадраты" в реальном коде возникают в таких "локальных" ситуациях - т. е. когда весь относящийся к "квадрату" код представляет собой несколько строк кода внутри одной функции?
По ощущениям, очень часто самые тяжёлые квадраты появляются из-за неудачных абстракций - и обнаружить их гораздо сложнее, потому что они "живут" на другом уровне, и для их обнаружения требуется держать в голове детали реализации разных компонентов (а исправление может потребовать редизайна абстракций или, скажем, намеренного их нарушения в конкретном месте).
И тогда может оказаться, что оптимизация работы отдельных .map()/.reduce()/и т. п. - это просто экономия на спичках, потому что настоящее бутылочное горлышко будет в других, менее очевидных местах. В таком случае чрезмерный акцент на этих локальных оптимизациях как не даст ощутимого прироста в производительности, так и, возможно, увеличит вероятность багов из-за менее читаемого кода.
Статистики нет. Не уверен что кто-то вообще такие вещи собирает и анализирует. Всем надо фичи в прод доставлять. Но для меня давно очевидно, что, при прочих равных, лучше писать такой код, который гарантировано не вызовет проблем в будущем (на всякий случай повторю — при прочих равных). Ведь в будущем вы просто переиспользуете готовый рабочий, возможно даже протестированный, механизм, не вникая во все его нюансы изнутри (потому что на это нет решительного никакого времени, читать эти тыщи строк кода). Примерно прикините: ну тут нечему тормозить, потому что оно под капотом должно делать А, B & C. А оно на самом деле делает (AA + BB) * C, потому что разработчику этого хватало на его "кошках" в дев-режиме. Что самое печальное, возможно и вам этого хватит. А вот конечный юзер уже взвоет. Его жалоба дойдёт до вас через полгода. Сколько денег за это время упустит бизнес?
И при всём при этом речь идёт об одной строке кода, необходимость которой, очевидно ещё до её написания. Нелепая ведь ситуация. Речь ведь не об "перемудрёной архитектуре" или "сложном алгоритме", который требует кучу времени на реализацию и поддержку. Просто… одна… строка… кода.
Живой пример. Есть такая библиотека для тестирования react-компонент — enzyme. Я использовал её для одного средних размеров проекта. В какой-то момент я понял что мои тесты непозволительно тормозят, там где этого ну категорически быть не должено. Там ведь тупо нечему тормозить. Оказалось ребята из airbnb (кажется) смогли сделать обход дерева в ширину за O(n^2) (или даже хуже). Я monkey-patch-ул метод простой наколеночной реализацией и всё залетало. С тех пор я опасаюсь пользоваться их npm-пакетами.
Я согласен с вами, что красивые примеры в статье таковы, что исправление квадрата в них не усложняет кода. Поэтому да, почему бы и не поправить их. И так же я согласен, что когда создаёшь библиотеку, все применения которой ты заранее не знаешь, то нужно постараться сделать адекватную асимптотику или по крайней мере задокументировать оценки производительности.
Но ведь в реальности обычно по-другому, и нет "белого" или "чёрного". Разработчик работает с километрами кодовой базы, в которой то тут, то там спрятаны квадраты. И какие-то поправить совсем легко, какие-то посложнее, а для каких-то потребуется уже отдельный мини-проект. Копья в code-review будут ломать как раз вокруг этого случая "посложнее", когда ускорение кода возможно путём некоторой потери читабельности или, скажем, расширяемости. Практический толк от каждой из таких оптимизаций будет, скорее всего, мизерным - до тех пор, пока в коде остаются другие квадраты.
какие-то посложнее, а для каких-то потребуется уже отдельный мини-проект
Всё так. Но данная статья про один (ну ок два) конкретных use-cases. Ни больше, ни меньше. Я не продвигаю тут идею, что за BigO надо стоять горой и слать всех коллег на три буквы. Всегда и везде есть конкретные обстоятельства, в которые нужно вникать.
Практический толк от каждой из таких оптимизаций будет, скорее всего, мизерным — до тех пор, пока в коде остаются другие квадраты.
Если продолжить эту идею то все наши решения это некий компромис. Всегда есть что-то на одной чаше весов, и что-то на другой. Я не ставил перед собой задачу дать рецепт на все случаи жизни. Я просто прошу перестать людей писать квадраты в очевидных местах, где эти квадраты ну нафиг не нужны и ничего не стоит их убрать. Вы сами заметили, что это не усложняет кода. Вот я именно об этих случаях, а не абстрактно обо всех возможных вообще.
Например я не призываю отказываться от регулярных выражений. Хотя если переписать вручную почти все места их использования в типовом приложении оно только выиграет по производительности. Но сильно проиграет по цене разработки. К тому же вполне вероятно эта победа по скорости никем не будет замечена. Скажем какой смысл писать руками сложный валидатор на имя пользователя, если это можно сделать одной строкой. У меня есть знакомые программисты, которые никогда не пишут регулярок, потому что "они медленные". Я их не понимаю. Каждому инструменту своё применение.
Регулярки регуляркам рознь. Некоторые работают за линейное время (от длины строки), без возвратов, и вряд ли можно заменить их на код более быстрый; а иные - за экспоненциальное время, если написать по-дурацки. Хотя тут опять же от движка зависит. Сафари меня удивил, он умеет плохие реги разрулить.
Плохие – это какие?
В смысле, это всё ещё регулярные выражения, просто "неудобные" для рекурсивного алгоритма (но нормально обрабатываемые Thompson's construction)? Или нечто с backreferences, что, вообще говоря, не является регулярным выражением, просто впихнуто в их синтаксис?
это всё ещё регулярные выражения, просто "неудобные" для рекурсивного алгоритма (но нормально обрабатываемые Thompson's construction)?
Скорее всего они самые.
Вот тут неплохо раскрыто: https://learn.javascript.ru/regexp-catastrophic-backtracking
до тех пор, пока в коде остаются другие квадраты.
Странный это был отдел. Лозунг у них был такой: «Познание бесконечности требует бесконечного времени». С этим я не спорил, но они делали из этого неожиданный вывод: «А потому работай не работай - все едино». И в интересах неувеличения энтропии Вселенной они не работали.
Оказалось ребята из airbnb (кажется) смогли сделать обход дерева в ширину за
O(n^2)(или даже хуже).
Пфффф, вообще фигня. Мы пару месяцев назад нарвались на багу, из-за которой coursier (он у нас в билд системе используется для выкачивания зависимостей) при билде падал в ООМ. Ему около 50 гигов оперативки стало требоваться для построения репорта в json формате. Как выяснилось там ребята как раз посчитали, что метод + у списка должен обновлять существующий список, а на деле он создавал новый. Как результат у них алгоритм обхода дерева в глубину начал обходить граф по всем возможным маршрутам в графе. А там уже что-то околоэкспоненциальное вылезает. При этом они там умудрились этот алгоритм еще и по нескольким местам раскопировать в коде.
Люди на собеседованиях не видят никакой проблемы в вызове .includes внутри .filter и подобных штуках.
Меня больше пугает, что есть люди, которые видят в этом какие-то проблемы. По-моему весьма глубокому опыту, проблемы с производительностью возникают из-за неверно выбранной архитектуры как софта, так и баз данных. Как показывает практика, один кривоватый запрос или неверная структура базы могут поставить жирнющий такой крест на всех JS-оптимизациях. Или еще хуже - пачка запросов в цикле, иногда скрытых в ORM. Именно это мне приходилось часто исправлять за многими разработчиками, причем некоторые были весьма опытные. И на собеседованиях я спрашиваю, как кандидат умеет оптимизировать софт по производительности, это многое показывает и рассказывает получше любых тестов. А если уж алгоритмы в JS начинают тормозить, то есть отличный вариант - вынести его в микросервис, написанный на чем-то быстром, либо вшить нативный/wasm кусок.
А если уж алгоритмы в JS начинают тормозить, то есть отличный вариант - вынести его в микросервис, написанный на чем-то быстром, либо вшить нативный/wasm кусок.
Сначала поправить асимптотику до оптимальной. А там, глядишь, и не надо будет возиться с нативщиной. Сабж о том, что незачем на ровном месте делать n^2 вместо n.
Судя по вашему комментарию вы про nodeJS backend (SQL, ORM, micro-services). Там своя специфика. Вы там не сталкиваетесь с описываемой мною проблемой, потому что на backend стороне никто не играет в immutability. Вот вам и кажется что проблема надуманная.
Вы там не сталкиваетесь с описываемой мною проблемой
Я бы так сказал - важность проблемы сильно преувеличена. Намного чаще встречаются на фронте другие ошибки в архитектуре, от которых производительность проседает весьма заметно. Как пример могу привести npm модуль react-dates от той же компании AirBnB. На всякий случай напомню, что это виджет с массой фич по выбору дат, периода дат, отображения календаря и т.д. Там постоянно народ жалуется, что виджет подтормаживает, например, вот. Проблем с производительностью там масса и корни разные, я даже изучал эту проблему внимательно, хороший кейс. Как Вы наверное догадались, проблемы не связаны с теми, которые Вы описали. Не буду раскрывать заранее карты и оставляю Вам возможность изучить реальные причины проблем с производительностью в React-проектах. Может напишете еще одну статью :).
Я бы так сказал — важность проблемы сильно преувеличена
Можно пример преувеличений с моей стороны?
от той же компании AirBnB
Похоже это уже не случайность, а закономерность
оставляю Вам возможность изучить реальные причины проблем с производительностью в React-проектах
Пройденный этап? Да я в состоянии написать цикл статьей про архитектурные проблемы React SPA. Но мне лень — это очень большой объём работ.
А теперь главное. О чём статья:
- есть проблема
- может быть критичной, может не быть
- очень широко распространена
- потому что огромный процент обучающих материалов повторяют эту ошибку
- она элементарно избегается ещё на стадии написании кода и не относится к preliminary optimizations
- ей подвержены разработчики самых разных уровней
- её лёгко продемонстрировать, её легко объяснить
Вышестоящего по вашему не достаточно для того чтобы привлечь к этому внимание?
Нет ну так то я могу написать и статью про "Обращение к Javascript сообществу: перестаньте выполнять сетевые запросы последовательно" и многие другие. Это как-то отменяет необходимость конкретно этой статьи?
P.S. мне стыдно за JS сообщество, что приходится объяснять что O(n^2) вместо O(n) это плохо, а когда разница заключается в одной строке, это прямо позорно.
JordanoBruno вопрос. Я тут подумал… А если я напишу статью про вредные последствия последовательных сетевых запросов вместо параллельных, вы не напишете что-нибудь вроде:
Меня больше пугает, что есть люди, которые видят в этом какие-то проблемы. Проблема сильно преувеличена. По-моему весьма глубокому опыту, проблемы с производительностью возникают из-за неверно выбранной архитектуры. В реальных SPA я встречал другие более серьёзные проблемы. Да и если у человека низкий сетевой latency, то он и не заметит никаких проблем.
Вы не будет отстаивать позицию, что сразу писать await Promise.all вместо серии await это предварительная оптимизация, а внимание стоит уделять более серьёзных архитектурным факапам?
Или если я напишу статью про "не запрашивайте записи из РСУБД по ID по одной, сделайте это в одном запросе", вы не скажете, что я перегибаю палку, т.к. существуют более серьёзные архитектурные проблемы, и если latency к СУБД меньше 2мс то никто не заметит разницы в производительности? И что вообще есть же кеширование, так что проблема не так ярко выражена, и лучше написать статьи про более серьёзные проблемы.
А если я напишу статью про "умоляю, начните валидировать данные пришедшие с клиента"? Не появятся комментарии про "ну безопасность надо гарантировать на всех слоях приложения, а не только на уровне валидации\санитации\whatever"?
Я просто всё никак не могу взять в толк, откуда такое яростное сопротивление (не только у вас), в очевидно косячном куске частотного кода, который сверх-тривиально фиксится и должен был быть так написан с самого начала.
А если я напишу статью..
Так Вы напишите сначала, потом будет видно, как я могу судить по тому, что не сделано? Есть масса случаев, когда те же последовательные запросы выгоднее параллельных. Вы опишите свой конкретный пример, я по критикую, если будет повод. Может Вы толково все распишите и я Вас только похвалю за аргументированность и точность в формулировках.
Я просто всё никак не могу взять в толк, откуда такое яростное сопротивление
Нет никакого яростного сопротивления, о чем Вы? Я лишь к тому, что описанная Вами проблема не критичная для большинства, да и проблемой не является вобщем. Это как красить двери у покосившегося дома.
Есть масса случаев, когда те же последовательные запросы выгоднее параллельных
Пример? Сразу даю вводную: браузер, latency=1000ms. Я весь во внимании. Любые примеры про пул-запросов отбрасываю (т.к. там есть параллельные запросы).
Это как красить двери у покосившегося дома.
Спасибо за пример. На нём хорошо видно в чём проблема. Итак, дано:
- покосившийся дом
- некрашеные обшарпанные двери
Правильное решение:
- срочно исправляем проблему с каркасом дома
- красим дверь, покрываем лаком
- При постройке новых домов — нанимаем адекватного архитектора, чтобы дом проблем с каркасом не возникло
- Малярам выдаём более качественную долговечную краску и не забываем про лак
Решение от JordanoBruno (то как я вижу вашу позицию):
- срочно исправляем проблему с каркасом дома
- дверь не красим, т.к. это не проблема. Нет ну правда. Вот покосившийся дом это проблема, да. А дверь… эх, вот дом вспомните, кривой какой был! Ух вот это была проблеееема. Да что вы пристали ко мне с этой дверью? Идите лучше ещё один дом постройте. А я вам потом отзыв оставлю.
Можно пример преувеличений с моей стороны?
Пожалуйста:
замедляет программу
Очень не значительно, по сравнению с другими ошибками в архитектуре
т.к. Javascript однопоточный - препятствует работе пользователя с UI
Чтобы препятстовать работе пользователя, это должны быть заметные лаги, то есть 0.2 сек. и более. Это ж какие алгоритмы и объем данных должны ворочаться? Вы так уверены, что большинство с таким сталкивается? Я что-то сомневаюсь.
тратит батарейку ноутбука или телефона на бесполезную работу
греет ваше устройство и заставляет работать кулер
Крайне незначительно по сравнению с тремя десятками открытых табов. И уж кулер точно не из-за "reduce" работает.
Но мне лень — это очень большой объём работ.
Никто ж не говорит, что нужно писать сразу про ВСЕ проблемы разработки в React. Выберите самую популярную причину тормозов БОЛЬШИНСТВА проектов React. Я думаю, это будет очень интересно всем разработчикам.
Нет ну так то я могу написать и статью про "Обращение к Javascript сообществу: перестаньте выполнять сетевые запросы последовательно" и многие другие. Это как-то отменяет необходимость конкретно этой статьи?
Не отменяет, Вы можете писать о чем хотите, это ж Хабр.
P.S. мне стыдно за JS сообщество, что приходится объяснять что O(n^2) вместо O(n) это плохо
Это весьма очевидные вещи, но практически никак не влияющие на конечный результат. Именно поэтому большинство разработчиков особо не парится по этому поводу.
Скажем так, когда-то давно я тоже уделял этому время и удивлялся, как это люди допускают такие неэффективные(по-моему мнению) конструкции, ведь можно писать более эффективно. Но потом со временем и опытом понимание пришло - влияние на результат крайне небольшое и большинству заказчиков вообще все равно, будет ли ПО работать в два раза быстрее или два раза медленнее. Потом я побывал на стороне заказчика и понял, что действительно, такие оптимизации особо не влияют на результат. Такая вот правда жизни.
Очень не значительно, по сравнению с другими ошибками в архитектуре
- Значительность зависит от конкретного кейса.
- Наличие ошибок в архитектуре не отменяет существования других ошибок
Выберите самую популярную причину тормозов БОЛЬШИНСТВА проектов React.
Я открыл ваш профиль и не вижу ни одной такой статьи. Что-то не сходится.
но практически никак не влияющие на конечный результат
Неправда. Это зависит от конкретного сценария. Асимптотические ошибки легко приводят к проблемам. Я уже неоднократно с этим сталкивался. Я даже привёл несколько примеров в этой теме. Причём для программиста они могут проявиться весьма неожиданно. Самое худшее — когда это приводит к финансовым потерям (поиск по слову Ikea).
Именно поэтому большинство разработчиков особо не парится по этому поводу.
С моей колокольни это не так: большинство разработчиков НЕ ЗНАЕТ как это работает. Мой опыт проведения собеседований прямое тому свидетельство.
Такая вот правда жизни.
А теперь я опишу как это выглядит с другой стороны: вы перестали воспринимать любые не фатальные проблемы, как проблемы. И кажется совсем (начисто) растеряли навык прогнозирования проблем.
P.S. у меня тоже богатый опыт. И вообще нас тут таких много (это ж хабр). Не стоит писать об этом в каждом 2-м комментарии ;)
Я открыл ваш профиль и не вижу ни одной такой статьи. Что-то не сходится.
Ну раз такие аргументы пошли в ход, то я даже не знаю, что ответить. Наверное пойду писать статьи по всем возможным проблемам в разработке ПО ).
Ну а что вы хотели? Я написал статью, которая будоражит мой мозг, которую я считаю очень важной для подрастающего поколения JS-разработчиков. Приходите вы с бинарными мышлением ("всё что приложение не убивает не существует") и с аргументами вида "лучше бы вы писали статью про что-нибудь важное" и "меня пугает что кто-то считает это важным". А когда я предположил что подобную критику я встречу, даже если напишу другие статьи (вроде последовательных api-запросов), я получил аргумент "ну ты напиши, а я, сделаю, так уж и быть, доброе дело, почитаю и покритикую". Вам не кажется что кто-то немного дерзит? ;) Кто-то с "глубоким опытом" и комментариями ментора.
Какое-то показное неуважение.
Ой, я пропустил кое чего.
Чтобы препятстовать работе пользователя, это должны быть заметные лаги, то есть 0.2 сек. и более
- Я регулярно вижу в консоли warning-и о том что какой-то код не уложился в кадр.
- Асимптотическим проблемам 0.2 сек вообще не рубеж. Проблемы с bigO это зачастую не конкретная строка, а сочетание нескольких методов (к примеру: медленный кусок кода прогоняется в цикле)
- Если это внутри анимации то 0.2 это очень много
Крайне незначительно по сравнению с тремя десятками открытых табов.
Chrome гасит неактивные вкладки, если это возможно. Поэтому десятки открытых табов это больше проблема памяти.
В целом я много раз натыкался на приложения которые соло выедают батарейку за кратчайшие сроки. Асимптотические проблемы, имхо, это один из главных кандидатов на эту роль. Но надо, конечно, разбирать каждый случай по отдельности. FAANG-и считают что это один из наиболее критичных навыков разработчика.
Дело в том, что влияние вышеуказанных методов на производительность весьма невелико и есть масса других, на порядки более влиятельных факторов. Именно поэтому данная проблема не является проблемой у большинства разработчиков. А преждевременная оптимизация - зло, как известно.
А преждевременная оптимизация — зло, как известно.Я не специалист по сабжу, но вы можете привести пример потенциальных проблем, вызываемых этой «оптимизацией»? Просто, по мне, она выглядит абсолютно бесплатной.
Дожили, разработчики уже не знают цитат классиков )).
Как писал в свое время Дональд Кнут:
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.
Речь скорее о его применимости к сабжу, и вот полная цитата тут как раз скорее против вас, тк ни какого «waste enormous amounts of time thinking about, or worrying» тут нет. Это настолько же является «оптимизацией», насколько ей являются правила типа «всегда оборачивать тело if скобками», «писать default в switch», всегда экранировать строки и тд и тд. Понимаю, что примеры не являются полными аналогиями, но тем не менее.
Вы немного неверно поняли как Кнутовское высказывание, так и его интерпретацию. Смотрите, вот тут полная его статья, откуда это высказывание, страница(268), почитайте, там весьма интересно:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6084&rep=rep1&type=pdf
Надо понимать, что в 1974-м году программы исполнялись на весьма медленных процессорах и памяти там было с гулькин нос(по нынешним меркам), поэтому тогда скорость программы играла намного более существенную роль, так же как и расход по памяти. Но даже в те времена Кнут рассказывает, почему важно сначала написать программу, а потом уже ее оптимизировать(если потребуется и захочется). Про «всегда оборачивать тело if скобками» я вообще не понял, это не имеет отношения ни к статье, ни к кнутовскому высказыванию, чисто code style rules.
Про «всегда оборачивать тело if скобками» я вообще не понял, это не имеет отношения ни к статье, ни к кнутовскому высказыванию, чисто code style rules.Это просто пример good practice аналогичный сабжу по трудоемкости. Ну то есть, написать лишнюю строчку из статьи не сильно труднее и не сильно дольше, чем нарисовать пару лишних скобок.
а потом уже ее оптимизироватьЯ пытаюсь указать вам на то, что конкретное решение изначально обходится дешевле чем не только «оптимизация потом» но даже дешевле, чем создание тикета «попозже глянуть производительность».
Вас послушать, так можно и обход массива по столбцам вместо строк делать — потом оптимизируем, если что.
Дожили, разработчики уже не знают цитат классиков
Да знаем мы её. И да она нам осточертела. Но не потому что плоха, а потому что, по нашему мнению, вы её не правильно трактуете. Вот из вашей же цитаты:
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 нагруженной части приложения? Легко. Просто поместите её туда как кусочек кода в цикле.
Замена O(n2) на O(n) — это как раз "good algorithm design".
Даже если на вашей машине разработчика это будет разница между 0.17мс и 0.2мс, то на машине пользователей вместо ваших тестовых десяти элементов легко может быть тысяча, и разница станет куда заметнее. Мой постулат состоит в том, что писать сразу более оптимальный алгоритм стоит куда меньше, чем переписывать готовый код когда он уже начал вызывать проблемы.
Для контекста. Самый большой репорт в моей памяти на данный момент составляет 35 тысяч строк, и каждая строка там тоже не из одного элемента. И нынешнее наше требование — поддерживать по 50 тысяч строк (с запасом чтобы). А по факту просто из-за хорошей гигиены, когда нам пришло обновлённое требование (цифра до этого была около 500), мы всего лишь нагенерировали нужное количество данных и убедились, что всё по-прежнему работает удовлетворительно. Код менять даже не пришлось.
Мой постулат состоит в том, что писать сразу более оптимальный алгоритм стоит куда меньше, чем переписывать готовый код когда он уже начал вызывать проблемы.
Кнут - дядька опытный, зря не будет телеги прогонять, я бы все же прислушался ).
Мысль его понятна - в сложной программе даже не всегда сразу понятно, где именно тормозит, нужно профайлить или как-то по-другому замерять скорость участков кода. Сложная - это, грубо, человеко-месяцы затрат, а не пример из статьи, где и оптимизировать-то особо нечего.
Мысль его понятна — в сложной программе даже не всегда сразу понятно, где именно тормозит, нужно профайлить или как-то по-другому замерять скорость участков кода.
Одно другому не мешает. Если у вас где-то сложный код и вы там сразу не нашли O(n2), то это простительно, бывает со всеми. Бывает и так, что O(n2) — это вообще лучшая асимптотика из возможных.
Сложная — это, грубо, человеко-месяцы затрат, а не пример из статьи, где и оптимизировать-то особо нечего.
Оптимизация таких мелких примеров, где весь код вообще на одной странице монитора — не попадает в моих глазах под критерии premature optimization. Эти вещи не нужно искать с профайлером, понимаете? Достаточно немного подумать и поменять буквально пару строк кода, всё. У меня такие случаи занимают дополнительно ну максимум минут десять, а success story этого подхода я выше уже приводил в пример.
Не могу не заметить, что Кнут жил в другое время, писал на других языках и пользовался другими инструментами. Не думаю, что современное понимание его слов соответствует тому, что он имел в виду.
Готов поспорить, что он был бы сейчас не стороне тех, кто против скобочек.
На сколько я помню, Кнут стремился чуть ли не к физическим обоснованиям эффективности алгоритмов. По сути, у него делается упор не на абстрактные алгоритмы и языки, а именно на их непосредственное исполнение в физическом мире. Его слова, наверное, можно трактовать как "минимальная форма частного, зачастую не является тем, что вам действительно нужно". Я не думаю, что эта проблема имеет какой-то временной характер. И действительно, если даже брать разбор с этими спреад операторами, то это легко можно оптимизировать во время интерпретации, при условии, конечно, что прототипы базовых классов не менялись, но это уже совсем другая проблема.
На сколько я помню, он говорил о том, что свои силы надо тратить эффективно. Среди примеров неэффективности был момент, когда разработчики правили код, который отвечал за ничего не делание.
Применительно к данной теме: Затраты на то, чтобы писать/не писать скобочки исчезающе малы, фактически отсутствуют. А профит есть и очевидный.
Не думаю, что в данном случае Кнута вообще стоит вспоминать, он писал совсем не о том.
Да зачастую flatMap решает половину проблем связанных с reduce ...spread, и только сокращает количество скобочек. Сам я, стараюсь как можно реже допускать неявное увеличение асимптотической сложности алгоритмов. Spread оператор, мной воспринимается исключительно как средство выразительности языка. Проблема в том, что всё, так или иначе относящееся к стилю кода, обычно имеет множество субъективных критериев оценки. Не в том смысле, что это какая-то прихоть, а в том, что различные измеряемые критерии, могут быть очень важными для одних, и совершенно ничего не значить для других.
Возможно, я сильно ошибаюсь, но по моим впечатлениям Кнут проводит грань между творческим подходом к решению проблем, и постоянным повторением устаревших однообразных практик. Второй подход, как правило, и приводят к зацикливанию внимания на незначительных мелочах, в условиях перегруженной системы.
http://elib.ict.nsc.ru/jspui/bitstream/ICT/882/3/knuth_1974.pdf
Поэтому, самое эффективное решение, в случае данной проблемы, я вижу, не в том, что бы определить как нужно, и как не нужно писать код в относительно редких случаях. А скорее, в устранении причин, которые нас подводят к составлению подобных правил. Либо в доказательстве того, что единого хорошего решения не существует, но в этом случае придется заменить экстраполяции, уходящие в бесконечность, на практические и ясные методы измерения пользы.
В остальном же, я согласен с автором на 90%. Просто потому что реальные инструменты далеки от идеальных, и сам произвожу подобные "оптимизации" практически на автомате.
Проблем нет. Ощутимой пользы, в подавляющем большинстве случаев, тоже.
А скрытых случаев недостаточно чтобы взять это за правило? Под скрытыми случаями понимаю те самые ситуации где предположения программиста оказались ошибочными (вместо 5 языков или стран в деве на проде подсунили 200, вместо 5 разных товаров, покупатель купил 20, вместо одной записи, потребовалось показать 250, и т.д.)?
Если чему меня опыт и научил, так это в первую очередь тому, что мы все регулярно ошибаемся в своих оценках.
Для того чтобы этой проблемы не было обязательно ждать таску в Jira? Вот эта строка кода стоит того?
потребовалось показать 250
Судя по бенчмаркам, 250 элементов обработаются достаточно быстро.
Для того чтобы этой проблемы не было обязательно ждать таску в Jira? Вот эта строка кода стоит того
Эта строка кода не гарантирует, что проблем не будет. Проблема не в том, что concat писали, а в том, что проектировали под список из 10-20 элементов. Ну будет вместо concat что-то более оптимизированное, а рендер не оптимизировали и UX неудобный т.к. изначально не предполагали больше 10 элементов в списке.
Судя по бенчмаркам, 250 элементов обработаются достаточно быстро
Повторюсь — это вопрос конкретных условий как и где эти 250 элементов обрабатываются. Вы не натыкались на то что неправильный полифил на Object.assign уничтожает производительность в старых бразуерах? Я натыкался. В IE8 (или IE7) календарики на форме инициализировались почти минуту. В Chrome такого поведения не было, т.к. полифил не применялся (да и v8 быстрее).
Эта строка кода не гарантирует, что проблем не будет.
Давайте я перефразирую ваше же предложение:
Эта строка кода гарантирует, что этой проблемы не будет.
ну как? :)
это вопрос конкретных условий как и где эти 250 элементов обрабатываются.
Согласен, всегда следует оттакливаться от контекста. Есть контексты, где это важная оптимизация, которая ускорит процесс. Но, по моим ощущениям, их очень мало. А в большинстве контекстов неважно, concat там будет или не concat
ну как? :)
Если честно, я не понял вашу мысль.
Если честно, я не понял вашу мысль.
Эта строка гарантирует что именно этой проблемы не будет. А это уже много стоит. Уж точно этой самой строки.
Есть контексты, где это важная оптимизация, которая ускорит процесс
Я вот сейчас понял… Я в принципе не воспринимаю эту штуку как оптимизацию. Это ведь никакая не оптимизация. Это код по-умолчанию.
Вы ведь не пишете:
source
.map(something)
.slice(5)а пишете:
source
.slice(5)
.map(something)Является ли 2-ая версия оптимизацией. На мой взгляд нет. Просто первая версия кривая.
Это ведь никакая не оптимизация
Смотря что понимать под оптимизацией. Но я не знаю определения, по которому код с pushменее оптимальный, чем код с concat
Это код по-умолчанию.
Просто первая версия кривая.
Это звучит очень субьективно
Это звучит очень субьективно
Если у вас 1-ая версия (где slice после map, а не наоборот) может пройти code-review, я рад что не работаю у вас :) На мой взгляд это уже настоящее разгильдяйство.
Если у вас 1-ая версия (где
sliceпослеmap, а не наоборот) может пройти code-review
Да, такой код может пройти code-review (как и код с concat), если учитывать контекст применения кода. Например, если нам достаточно, чтобы код корректно работал и выполнялся не дольше минуты.
я рад что не работаю у вас :) На мой взгляд это уже настоящее разгильдяйство
Стало еще более субьективно. А как же условия, контексты?
Предлагаю на этом сообщений завершить тред, т.к. от цифр мы пришли к обвинению в непрофессионализме, как в настоящем холиваре :)
Это звучит очень субьективно
-- Зубы нужно держать в порядке, чтобы изо рта не воняло и других проблем позже не возникло.
-- Это звучит очень субъективно. Достаточно, чтобы сегодня зубы не качались и жевали, всё остальное -- преждевременная оптимизация.
Это очень спекулятивная аналогия.
В статье и комментариях есть замеры - reduce + concat на массиве из 1000 элементов отрабатывает около 2мс.
При обработке 1000 элементов, скорее всего, не эта операция окажется узким местом.
Более близкой аналогия была бы, если предположить, что статья предлагает использовать ополаскиватель для рта. Это полезно и с этим никто не спорит, но неиспользование ополаскивателя не является ключевым фактором проблем с зубами.
Использование ополаскивателя требует действий сверх базовой гигиены. Использование линейного reduce+push или flatMap вместо квадратичного reduce+concat не требует ничего, кроме навыков базовой гигиены. Ну просто уже одно только знание, что concat создаёт новый массив, а reduce гоняет цикл, и мы одно вставляем в другое, должно вызвать органолептическую реакцию "фу, грязь" и позыв найти нормальный способ.
Я понимаю, если кто-то просто не знал/забыл про особенность concat -- это ок, со всяким бывает. Если же знает, но сознательно выбирает из двух равноценных вариантов более грязный -- и даже настаивает на этом! -- и при этом у него нет серьёзных причин для такого выбора, то это явно проблемы с гигиеной.
Здесь не мутирование абы какого массива, а мутирование внутреннего аккумулятора, специально для этого предназначенного. Чистота сохраняется, внешних эффектов нет, полная детерминированность. Сможете показать, как тут нарушена чистота?
Нарушена чистота внутренней функции, переданной в reduce. С внешней-то понятное дело что всё в порядке.
Это-то понятно, но это именно что внутренняя лямбда, оказывающая эффект исключительно на внутренний аккумулятор, который лежит прямо тут же, рядом. Продолжая аналогию с зубами, у нас нет цели держать зубы чистыми ежесекундно и чистить их после каждого откушенного куска булочки. Это уже будет другая крайность -- обсессивно-компульсивный синдром.
Причём тут вообще зубы?
Продолжая аналогию с зубами, у нас нет цели держать зубы чистыми ежесекундно и чистить их после каждого откушенного куска булочки. Это уже будет другая крайность — обсессивно-компульсивный синдром.Так ведь той же аналогией можно описать и избегание «квадратов» при обходе массива в 5 элементов.
Не всякое избегание — обессивное расстройство. Эдак вы дойдёте до идеи что "гигиена — это тоже ОКР, ритуальное избегание грязи". Нужно же учитывать диапазон последствий. Что отличает здоровую гигиену от обсессивного растройства?
- Гигиена: в худшем случае — бесполезна, в лучшем случае — может сильно помочь.
- Обсессивное расстройство: в лучшем случае — безвредно, а в худшем — может сильно навредить.
Случай в 5 элементов — это то где reduce+concat ещё безвреден, а reduce+push ещё бесполезен. Это то место, где гигиена и ОКР могут показаться неотличимыми, но это не значит, что их можно приравнивать.
А в где worst case у push? На каких даных он становится вреден? И в чём best case у concat, когда он становится полезен?
Если я правильно понял логику Вашего собеседника, речь не о данных, а о коде: чем компактнее и понятнее функция, тем более допустимым в ней может быть использование побочных эффектов, т.к. они все будут на виду. Другой вопрос - зачем вообще использовать в reduce что-то больше пяти-шести строк...
Ну в таком разрезе как бы да, если рассматривать независимые оси "код vs данные", то про push в маленькой функции можно сказать, что по оси "код" это "лучший случай ", а с ростом кода всё хуже. Но в процессе развития системы шанс случайно и непреднамеренно напороться на большие данные всё же выше, чем шанс случайно и непреднамеренно превратить двустрочник в функцию на пару экранов с кучей эффектов. Код ты сам контролируешь, а данные приходят в reduce извне, сегодня 5 элементов, а завтра 100500. Этот код какой-нибудь джун скопипастит не приходя в сознание, проблема вылезет у него -- а винить он будет того, у кого он код этот взял. Для общей кармы плохо :)
Этот код какой-нибудь джун скопипастит не приходя в сознание, проблема вылезет у него — а винить он будет того, у кого он код этот взял. Для общей кармы плохо :)Именно! Скопипастит и расширит, не следя за сайд-эффектами. Плюсы иммутабельно-функционального подхода же, в основном, как раз не в повышении производительности, а в упрощении контроля. А джун пусть лучше сначала пишет медленный, но гарантированно рабочий и модульный код, чем быстрый, но требующий вдумчивости в применении.
Chamie боюсь сложность "иммутабельно-функционального подхода" настолько велика, что junior-а к такому коду вообще подпускать страшно. А если FP запущен во взрослому, то ниже senior-а уже не вариант.
Скопипастит и расширит
P(скопипастит) > P(скопипастит)*P(расширит|скопипастит)
Ну и если закладываться на "расширит", то ничто ему не мешает до куба расширить :)
не следя за сайд-эффектами
Как уже говорилось, сайд-эффектов тут нет. Есть эффекты, изолированные внутри чистой функции, т.е. очищенные.
Ну и если закладываться на «расширит», то ничто ему не мешает до куба расширить :)Да просто передаст в качестве второго параметра не пустой массив, а какой-нибудь существующий.
Как уже говорилось, сайд-эффектов тут нет. Есть эффекты, изолированные внутри чистой функции, т.е. очищенные.Давайте определимся: где «тут»? Функция, в которой этот reduce используется? Функция-редьюсер? Метод reduce?
Главная функция у нас будет чистая только если мы за этим проследим (этакий unsafe-код) это и есть «следя за сайд-эффектами» (что они не просачиваются наружу), функция-редьюсер у нас точно не чистая, а метод reduce так и вообще просто вызывает её в цикле, никак не ограничивая её в мутировании см. тот же пример выше с передачей существующего массива в качестве стартового значения «аккумулятора» (мне о нём больше нравится думать как об объекте межитерационного обмена).
Давайте определимся: где «тут»?
Функция
(items) => items.reduce(
(acc, item) => {...},
[]) — является чистой что с concat, что с push вместо ....
Да просто передаст в качестве второго параметра не пустой массив, а какой-нибудь существующий.
Легко:
(items, init) => items.reduce(
(acc, item) => { acc.push(item); return acc; },
[...init])— сложность кода такая же, эффективность на месте, никаких эффектов наружу не просачивается.
Хотя не очень понятно зачем — если мы переиспользуем аккумулятор для межитерационного обмена, то ожидаем, что в нём будет накапливаться результат прогона нескольких редьюсеров, и нам важно конечное значение аккумулятора, а не промежуточные.
Функция, вызывающая грязную, не является чистой по определению.
Функция, вызывающая грязную, не является чистой по определению.
Только при условии, что грязная функция имеет такие side-effect-ы, которые являются side для вызывающей функции.
У чистой функции нет никаких сайд эффектов по определению. Соответственно и вызывать функции с сайд эффектами она не может.
Ну так о том и речь. Что не любой side-effect функции B рассматривается как side-effect функции A. Стало быть А может использовать "грязную" B и оставаться при этом чистой.
const pure = (value: number): number => {
let a: number = 0;
(() => { ++a; })();
return a + value;
}Здесь (() => { ++a; })(); это грязная функция. Её side-effect это ++a. Это не просто effect, это side-effect, т.к. a это переменная извне.
В то же время с точки зрения функции pure это эффект локальный. Она остаётся чистой.
К чистым функциям всего два требования:
- отсутствие side-effect-ов (у pure их нет)
- детерминированность (pure детерминирована)
Вышеописанное актуально, кажется, только для мультипарадигменных языков. В чистом FP языке, кажется, даже написать такое не получится.
В чистом FP языке, кажется, даже написать такое не получится.
Получится, runST в помощь.
Ну уж нет, именно такое и получится. Разумеется, скоуп для runST нужно выбрать правильно. Как-то так, если я ничего не напутал:
pure value = runST do
a <- newSTRef 0
inner
return a+value
where inner = modifySTRef a (+1)Вы тут не передаёте внутрь reduce существующий массив, вы создаёте новый.Да просто передаст в качестве второго параметра не пустой массив, а какой-нибудь существующий.Легко:— сложность кода такая же, эффективность на месте, никаких эффектов наружу не просачивается.(items, init) => items.reduce( (acc, item) => { acc.push(item); return acc; }, [...init])
Вы тут не передаёте внутрь reduce существующий массив, вы создаёте новый.
Да, это был пример того, как устранить сайд-эффект "изменение начального значения аккумулятора" и сделать функцию чистой, не прибегая к concat
Кстати, знаете, как сделать вот этот код...
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));
}
Согласен, описанные в статье практики могут выстрелить в ногу. Но они выстрелят в некоторых случаях. В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.
Поэтому стандартизированные общие практики в итоге позволяют экономить больше ресурсов, так как большинство кодеров в фронтенде не сталкивается с проблемой высоконагруженных систем.
Впрочем, тем, кто пишет серверный код - уже стоит призадуматься. Да, в серверном коде я бы не стал так яростно использовать цепочечные методы. На бэкенде и доли миллисекунды в итоге довольно быстро превращаются в большие выигрыши или большие потери.
В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.
И насколько у нас упала "читабельность"? Код стал непонятным? :) Really?
В большинстве остальных случаев читабельность важнее, так как огромное количество времени кодеров уходит на чтение и разбор чужого кода.
Поддержу тут.
большинство кодеров в фронтенде не сталкивается с проблемой высоконагруженных систем
И тут тоже. В основном надо писать быстро, так как сроки поджимают.
тем, кто пишет серверный код - уже стоит призадуматься
Там все перекроют потери если лишний раз сходишь в базу. Лучше там пооптимизировать.
Я бы не откидывал фронтенд так просто. Вот, пару лет назад писал большую статью об огромной полезности знаний алгоритмов и структур данных во фронтенде на dou, с примерами применения.
Сделал бенч на jsbench.me и выглядит, что чтобы не уложится в 16 мс, нужно пару сотен элементов в массиве.
Это я не к тому, что использовать concat в reduce - хорошая практика. Но из статьи выглядит, будто бы уже при 30 элементах в массиве будет проседать перформанс, однако это не так. Граница, когда все становится плохо, находится дальше и там, возможно, concat будет не самой большой проблемой
Пара сотен это не так много, как кажется. В 16 милисекунд нужно уложить не только обработку данных, но и модификацию DOM-дерева, и ещё оставить браузеру время на обработку изменений DOM-дерева, отрисовку интерфейса и обработку событий. На 5-летних устройствах всё это будет происходить раза в 2 медленнее. По-хорошему, обработка данных должна занимать не больше 1мс на железе разработчика.
Я так понимаю вы сделали следующие допущения:
- код запускается не в цикле (или циклах)
- код запускается всего один раз
- это единственный код который вообще запускается
В целом да. 30^2 операций не так много, чтобы соло создать performance bottleneck :) На моих примерах разница с линейной версией была всего в 4 раза.
Я повторил бенч из скриншотов из Firefox и Chrome. Там где сравниваются 2600 vs 30
Там по 3 примера: 1000, 100, 30. Ну просто для наглядности различий между O(n) и O(n^2). 2600:30 это не количество элементов, это количество миллисекунд. И такая большая разница была как раз при 1000 элементах. При 30 всего 16:3. Что полностью соответствует теории — чем выше N, тем больше дистанция. Чем ниже N, тем меньше дистанция.
Мне, при беглом прочтении статьи, показалось, что обработка 1000 элементов через concat занимает 2 секунды , а через push - 30 мс.
Но там делается 1000 прогонов по 1000 элементов и потом замеряется общее время. Получается, concat на 1000 элементов в среднем выполнялся за 2мс. Это, конечно, много и повлияет на рендер, но не прям драмматично.
Если нам нужно эти 1000 элементов еще и отрендерить, то полезнее будет заняться оптимизацией рендера, а не заменой concat
Это, конечно, много и повлияет на рендер, но не прям драмматично.
Да, всё зависит от обстоятельств. К примеру я не так давно долго ковырялся с 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 их не убирать надо. Их просто не надо писать. Всё просто. Не нужно с самого начала писать бредовый код.
Если нам нужно эти 1000 элементов еще и отрендерить
Кстати не факт, что нужно рендерить. Не все данные нужны для отображения.
Пример. Писал приложение для ручного формирования расписаний. Там были достаточно большие данные (почти все данные школы), чтобы ни в коем случае, нельзя было забивать на bigO, но выводилось их весьма ограниченное количество. Все проблемы с performance были на стороне объекто-дробилок (всякие фильтрации, вычисление подходящих окон для размещения урока, валидация и пр. и пр.). Вся эта объекто-вакханалия перевычислялась на лету при малейших изменениях.
Для примера стоило начать drag-n-drop-ать условный "Математика 2А класс Савельева Е.В." с панели "неразмеченных уроков" на "текущая проекция расписания" как нужно было за <16ms пересчитать все допустимые ячейки. Где-то у 2А уже урок, где-то нельзя, так как нормативы нагрузки перевыполнятся, где-то у учителя другой урок, где-то кабинет занят физиком, ну и т.д… Естественно это всё ещё и реактивное (иначе бы я вечность это писал).
Любые попытки написать это игнорируя квадратичную сложность на ровном месте просто уничтожили бы проект.
Немного рановато для таких статей. Вот через пару лет когда наступит Производительный Кризис и цена эффективного кода будет выше чем цена быстрописного, тогда и пригодятся этот и подобные тексты.
Порой у меня создается ощущение что программирование это не про здравый смысл, а про моду и стиль. Используются популярные решения, а не эффективные. (надеюсь кто то скажет мне что я не прав)
У меня был случай лет 15 назад, когда на вопрос к разработчику, почему так тормозят расчеты в программе (Delphi + MSSQL) был ответ - это не мои проблемы, томозит - купите сервер помощнее. Пришлось самому лезть разбираться (пока он был в отпуске), в итоге тормоза пропали после добавления пары хинтов в SQL-запрос. Когда ему показал, как я решил проблему, в ответ было - ну давай везде эти хинты навешаем.
К слову - человек к тому времени уже лет 5 занимался исключительно клепанием CRUD-двухзвенок на этой связке, а я только начал тогда изучать работу с БД.
К чему я это рассказываю - ничего не поменялось за эти годы. Если человек не видит потенциальной проблемы в том, что список покупок в корзине обновляется 40 секунд, или что документ по уникальному реквизиту в системе документооборота ищется 5 минут, и если за такое ему не бьют линейкой по пальцам, а послушно докупают более мощные серверы и терпят убытки из-за потерянных покупателей - ничего не поменяется. Если повезет, придет другой разработчик, который парится за производительность и вычистит из кода квадраты, кубы и прочие экспоненты, но это должно еще повезти.
Удивлён, что это вызвало такую большую дискуссию. Всегда был уверен, что переход от N к N2 – ну никак не незначительная потеря производительности. И классики говорили все же про оптимизации, изменяющие константу возле big O.
А уж если ради того, чтобы убрать одну строку кода на такое идут – что ж, теперь я понимаю, почему так много плохих сайтов в Интернете.
Удивляет как здравый смысл (не делать ненужных действий) многие называют преждевременной оптимизацией.
В следующий раз когда пойдете в магазин возьмите тележку. Когда захотите положить туда товар - вернитесь возьмите новую тележку, положите туда товар. Когда снова понадобится положить товар - опять вернитесь и возьмите новую тележку, переложите все товары в новую тележку и добавьте новый товар. И так повторяйте каждый раз с новым товаром. Интересно использование одной тележки вы будете называть оптимизацией или просто здравым смыслом?
P.S. А потом выйдет GC из подсобки и будет очень рад числу ненужных тележек, оставленных по всему магазину.
Справедливости ради, в случае массива, можно использовать flatMap:
В случае объекта, там обычно не бывает тысячи полей.
Всё как обычно: это зависит от обстоятельств. На моей практике было очень много примеров когда в массиве были сотни и тысячи полей. Просто словарик. Сейчас для таких целей завезли Map, и я предпочитаю использовать его. Но ImmutableMap у нас нет :)
Плюс я намеренно не стал сильно углубляться в объекты, сказав, что там всё сложно. Потому что в зависимости от реализации, любая операция с объектом может затребовать O(logN) действий (если он скажем сделан при помощи binary search tree). В общем и целом — объекты не массивы, они и сложнее и тяжелее.
В тайпскрипте есть ReadonlyMap.
Я же не про типы. Я про оптимизированную структуру данных, с которой можно работать иммутабельно, без больших пенальти по производительности.
Так объекты тут ничем не отличаются. Даже медленнее работают из-за жонглирования скрытыми классами.
Да, я знаю. Я не имел ввиду того, что Map хуже чем {}. Наверное слишком косноязычно написал. Просто пожаловался на отсутствие желаемого. Но нас ждут #{} и #[] с ними будет поинтереснее.
А вы же тут с самого начала обсуждаете пересоздание объектов? Не доступ по ключу? Доступ по ключу и у {}, и у Map всегда же будет O(1)?
Я видимо с утра сильно непонятно пишу. 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, но уже большего размера
Всё как обычно: это зависит от обстоятельств. На моей практике было очень много примеров когда в массиве были сотни и тысячи полей. Просто словарик. Сейчас для таких целей завезли
Map, и я предпочитаю использовать его. НоImmutableMapу нас нет :)
Всё так, только количество таких словарей мало, большинство объектов имеют мало полей.
Как вариант, для объектов вместо reduce можно использовать map + Object.fromEntries.
---
Немного переделал ваш тест, чтобы тестировать на объекты.
На firefox, ожидаемо занимает много времени: https://i.imgur.com/FUljbwl.png
Но интересно, что chrome смог это оптимизировать: https://i.imgur.com/IlA84PE.png
Как вариант, для объектов вместо reduce можно использовать map + Object.fromEntries
Да, можно. Страшненько получается правда, поэтому не совсем понятно зачем. ИМХО читаемость куда ниже.
Страшненько получается правда, поэтому не совсем понятно зачем
Когда мы поштучно добавляем новые поля в {}, меняются скрытые классы для него. Object.fromEntries, реализованный нативно, теоретически мог бы избежать этой проблемы. Хотя не знаю, как дело обстоит сейчас и что быстрее. Оно там внутри постоянно меняется.
Этот вариант может быть предпочтительнее, для тех кто хочет обходиться иммутабельними структурами.
Я не против мутировать accumulator, но например eslint пока не сможет везде запретить мутации кроме accumulator'a, поэтому приходиться либо запретить везде либо разрешить.
Если вы решили запретить мутабельные структуры, то такой вариант (Object.fromEntries) вам подходить, во всех остальных случаях мутация accumulator'а предпочтительнее.
---
Читаемость можно улучшить с помощью вспомогательных функций, например:
pipe(
source,
array.map(n => [n, n]),
dict.fromEntries,
);
Либо в будущем так:
source
|> %.map(n => [n, n])
|> Object.fromEntries(%)В случае объекта, там обычно не бывает тысячи полей.
Недавно на ruSO был вопрос как обойти ограничение браузера на (кажется) 48 миллионов(!) полей в объекте… O_o
Может ли кто-либо, пожалуйста, привести пример неудачного includes внутри .filter? И пример оптимизации. Не уверен, что понял. Заранее благодарю!
.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 равны, скажем, четырём, то сидеть колупать код резона нет :)
На преобразование тоже уйдёт время и память.
O(n logN)в случае tree.
Откуда там logN? Дерево занимает O(n) памяти
upd: а, это время
Подскажите, что лучше использовать в данной ситуации? Есть массив строк и поле для ввода. По мере ввода пользователя нужно фильтровать этот массив строк - в выборку должны попадать лишь те, что содержат введённую строку.
Когда массив строк не очень велик, вариант arr.filter(str => str.includes(value)) работает без тормозов, да. Когда нужно было это сделать на большом массиве строк (если правильно помню, 5000 строк), то использовал arr.filter(str => str.match(value)). На Includes были заметны тормоза, на match - летало.
Есть много алгоритмов поиска подстроки в строке. Суть сводится к тому, что "в лоб" эту задачу быстро не решить. Но если изначально подготовить оптимальную структуру данных, перегнать в неё исходные данные, то потом по ним можно искать быстрее. Какой конкретно подойдёт лучше я не знаю, потому что ни разу не сталкивался с такой задачей. Точнее с самой задачей сталкивался, но всегда были крошечные объёмы, где код можно было писать ногами. Вот тут есть описания и сам список.
Ещё добавлю, что в рамках такой задачи не помешает предварительно:
- trim-ать строки
- str.normalize — нормализовывать
- приводить к одному case-у (например lower)
Ещё можно дробить поисковый запрос на слова и искать отдельно по каждому слову. Частенько это лучше покрывает желания пользователя, чем просто поиск в лоб.
Как вариант, сохранять и переиспользовать предыдущие выборки. Наиболее типовой сценарий здесь - когда в текстовом поле набивается слово, и с каждой новой буквой делается поиск. И, допустим, имея на руках выборку для "abc", которая существенно меньше исходного полного набора слов, из неё очень быстро сделаем выборку для "abcd", ничего не потеряв. В общем, для некоторой введённой строки S ищем среди предыдущих запросов запрос для наиболее длинной подстроки S, и выбираем из него.
Ну а если бы поиск делался не по вхождению, а по началу строки, то там можно с помощью префиксного дерева без проблем окучивать сотни тыщ строк
Если строки должны начинаться со ввода, то отличный вариант — построить бор из фильтруемых строк, при вводе пользователя спускаться по этому бору и потом при поиске обходить бор с этой вершины и выводить все строки в этом поддереве.
Если запрос пользователя должен входить как подстрока, то можно разбить все строки на 3-граммы (3 подряд идущих символа), для каждого набора построить список из всех строк, которые его содержат (отсортированные по id). Потом при запросе эти списки мерджить и искать только в этих строках.
Еще, я не знаю, что там у String.includes под капотом, но может ручная реализация какого-нибудь KMP будет быстрее.
Самый быстрый и сложный в реализации метод будет таким: построить суффиксные деревья для всех строк, потом объединить их в одно дерево. Потом в каждой вершине сохранить Set всех строк, кончающихся в поддереве. Чтобы быстро строить и не занимать очень много памяти, надо каждый Set хранить в виде персистентного бинарного сбалансированного дерева. Тогда построить это счастье можно за O(L log n) и памяти оно столько же занимать будет. Тут L — суммарная длина всех строк, n — их количество. Зато время поиска будет O(1) на каждый введенный символ и вывод всех строк будет за O(k), где k — длина ответа. Быстрее вообще никак. Но этот метод будет проигрывать совсем наивным на маленьких размерах из-за оверхеда и по настоящему засияет только при больших наборах данных. Но бонусом тут можно дерево предпостроить на сервере и выдать сразу его на клиент.
Но никакие эти структуры, естественно, не встроены никуда, а на js наверно даже не реализованы нигде ни разу.
Из простых решений можно чуть доработать ваше: соединяем все строки через перевод строки, после чего через match натравливаем на неё регулярку. Например:
'foo bar\nbar\nfoo'.match( /^.*bar.*$/migu ) // ['foo bar', 'bar']Предположу, что вы делали не просто match по строке, а по заранее подготовленному регулярному выражению. В таком случае ничего удивительного нет — ведь includes тоже делает подготовку, пусть и более простую — зато каждый раз.
Из более оптимальных способов тут можно разве что заранее сокращенное суффиксное дерево построить для всего массива строк, это заставит поиск "летать", но вы замаетесь его строить.
Синтаксис { ...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 всего несколько миллисекунд.
Если количество элементов source равно количеству свойств у newObject
Просто замените .reduce на .map.
Для себя сделал "правило" стараться не расширять объекты вот так: obj[property] = valueЧестно говоря я рекомендую вам провести замеры. Есть немалая вероятность что экономии нет, или она крошечная. Вы исходите из того, что Object.fromEntries очень мощно оптимизирован. Может быть оно так и есть. А может быть и нет. А ещё может быть что потери на игры с ненужным массивом перебивают любую выгоду от финта ушами с Object.fromEntries. В общем я рекомендую вначале прогнать простые тесты на нужных вам платформах. А то может быть вы зря мучаетесь :)
Ну и стоит отметить, что асимптотической разницы там быть не должно. И если речь не про высоконагруженный участок кода какой-нибудь числодробилки то едва ли игра стоит свеч.
Просто замените
.reduceна.map.
Действительно, что-то я увлёкся редьюсом)
Честно говоря я рекомендую вам провести замеры.
Я проверил. Object.fromEntries() работает намного быстрее, чем { ...acc, props val }, но обычное добавление свойства всё же быстрее. Если оценивать сложность то она одинаковая: O(n) (простое добавление) против O(2n) (Object.fromEntries), а вот в абсолютном времени простое добавление свойства побыстрее.
На всякий случай уточню O(n) это ровно тоже самое что O(100500 * N). Т.е. O(n) === O(2n). То о чём вы говорите (2) это константа. Время, которое тратится на отдельно взятую операцию. У разных алгоритмов она, разумеется, разная. Поэтому когда мы говорим об bigO мы в первую очередь говорим о больших объёмах данных, т.к. чем больше данные, тем меньше влияния константы при разных bigO. Даже если у одного алгоритма константа в 20 раз выше, чем у другого, если тот другой имеет bigO(n!), а первый O(n), то роль этих "в 20 раз" уже не важна на объёмах. 20х алгоритм будет настолько ультимативно быстрее, что ...
В отдельно взятых ситуациях берут в рассчёт уже и константы. И прочие обстоятельства. К примеру есть много вариаций binary search tree. У большинства из них (или всех, не знаю) одни и те же bigO. Но разница в константе (и прочих нюансах непокрытых bigO) заставляет применять разные деревья. Понятное дело это касается нагруженных участков кода.
Это, правда, по опыту backend. Смею предположить, что оператор "..." может быть попросту неудачен и не должен быть добавлен в язык именно потому, что он в 99% случаев ведёт к O(N) вместо O(1), что неизбежно приведёт к O(N^x) системах с бОльшей цикломатической сложностью, которую вовсе не всегда можно удержать в голове. Или, как минимум, к лишнему множителю o(xN). По-моему, ЯП не должен проектироваться с таким подходом, когда сахар замедляет программу в типичном случае без убер-оптимизатора, пусть якобы немного в этом типичном случае.
На самом деле, оператор "..." вполне удачен, потому что у него есть куча применений когда без него совсем плохо.
Например, вызов функции с передачей произвольного числа аргументов: fn(foo, bar, ...baz) без этого оператора выглядел бы так: fn.apply(null, [foo, bar].concat(baz)). И да, у нормальных функций никогда не бывает слишком много аргументов.
Например, вызов функции с передачей произвольного числа аргументов: fn(foo, bar, ...baz)Пример так себе, потому что в этом случае можно обойтись
fn(foo, bar, baz), объявив функцию соответствующим образом. Заодно ничего никуда копироваться не будет. Я думаю, функции с произвольным числом аргументов — это не пример отличного дизайна. Оператор для неудачного дизайна — не лучшая идея.Про кучу применений я как раз не в курсе. Чисто логически я вижу, что этот оператор поощряет неудачный дизайн кода, когда можно или нужно использовать другие пути — при разработке и развитии ЯП хотелось бы таких решений избегать.
Если это декоратор — то надо работать с тем что есть. И с чего вы вообще взяли, что у функции переменное число аргументов?
Если это декоратор — то надо работать с тем что есть.Не совсем понимаю, но специальный оператор для работы «с тем что есть» — такое себе.
И с чего вы вообще взяли, что у функции переменное число аргументов?А зачем ещё код вроде
fn(foo, bar, ...baz)? Если функция имеет фиксированные аргументы, и в массиве эти аргументы, то это даже ещё хуже. Аргументы к функциям должны быть явными, а не разворачиваться из массива, потому что в массиве может быть что угодно.
Я прекрасно понимаю алгоритмичесую сложность, но мутировать в что-то лишний раз, тем более в reduce, не буду:
Это плохой пример другим. Товарищи решат, что так можно везде, и начнут, например, удалять элементы из массива по которому проходят. А потом товарищи перейдут на бакенд, который многопоточный. И про "memory model" не прочитают. Оптимизировать безопасный код проще, чем вылавливать плохо повтояемые баги.
Итак, у меня 1000 элементов, для которых описанная оптимизация имеет значение. А они точно нужны на клиенте? Может, в качестве первой оптимизации, их не присылать, а взять только те 20, которые пользователь видит.
Ну хорошо, в этот раз у меня канвас на UHD и элементов правда нужно много. А использовать библиотеку с дополнительными структурами данных не разрешили. Я ведь могу написать свой минимальный "util.js", в котором внутри всё будет в стиле "for(;;)" и "let", а снаружи чисто.
Есть линтеры, которые заставляют помечать небозопасные конструкции. Возможно есть/будет и для js такой инструмент. И я стараюсь писать код так, чтобы легко интегрировать его в будущем.
Смешались в кучу люди кони… И не-JS backend с многопоточностю, и мутация итерируемых коллекций, и канвас. Ух. Но я и не настаиваю на .reduce. Если согласно вашим правилам, принятым в команде, мутации в .reduce это большой грех, то:
- используйте вместо него
.flatMap, там где это возможно - не используйте
.reduce, там где получаетсяO(n^2)на пустом месте. Есть множество способов сделать тоже самое, без него
Главное не ставьте аргументы из п1. выше чем bigO. Над нами уже весь IT мир потешается.
Печально отметить, что MDN тоже предлагает использовать concat https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce#flatten_an_array_of_arrays
Обращение к Javascript-сообществу: перестаньте писать квадраты