Звучит это очень загадочно, как и ваши примеры кода.

Извините, но это буквально уже невежливо.

Ваша статья строится на том, что вы изменили сложность алгоритма с квадратичной на линейную. Это основное утверждение которое вы сформулировали в своей статье. Я утверждаю что у вас НЕ изменилась сложность алгоритма т.к. он как был линейным так и остался (если считать за N число файлов).

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

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

Вот в википедии написано:

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

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

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

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

Касательно замены push на concat я совершил ошибку что об этом написал. Не потому что то что я сказал неправильно просто теперь вы всё время пытаетесь увести разговор на это, вместо то чтобы обсуждать что в статье допущена ошибка. Если мы придём к согласию относительно статьи я могу разобрать с вами смысл замены push на concat и объяснить почему это может или не может приводить к изменению скорости исполнения (с учётом реализации в v8), но сейчас давайте оставим этот вопрос за скобками, т.к. в реальных условиях вклад этого изменения врятли будет заметен измерением. Либо вы можете разобраться в этом сами если посмотрите первые две лекции курса ссылку на который я отправил выше. При том что ваше изменение вклада не имеет вообще потому что это буквально тот же код.

Кроме того я провёл измерение следующим способом:

git pull https://github.com/coderaiser/putout.git

# коммит с оптимизацией
git checkout 07ced670d1ff03c768844b114f63e70117b15be3
npm i

# Первый прогон отбрасываем чтобы прогрелись все кэши
time npm run lint:fresh

# Делаем три прогона и усредняем
time npm run lint:fresh
time npm run lint:fresh
time npm run lint:fresh

# откатываем коммит с оптимизацией
git revert 07ced670d1ff03c768844b114f63e70117b15be3
npm i

# Первый прогон отбрасываем чтобы прогрелись все кэши
time npm run lint:fresh

# Делаем три прогона и усредняем
time npm run lint:fresh
time npm run lint:fresh
time npm run lint:fresh

Я получил такие результаты.

С оптимизацей
Executed in 36.76 secs
Executed in 37.00 secs
Executed in 36.51 secs
Среднее 36.76

Без оптимизации
Executed in 36.93 secs
Executed in 36.88 secs
Executed in 36.79 secs
Среднее 36.87

Разница 0.11s или 0.3%. При том что разброс между отдельными измерениями вполне доходит до 0.5s я думаю что это можно списать на погрешность. Ни о каких 13% ускорения речи не идёт.

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

Смотрите пример. Вам надо обойти массив длиной N. Это можно сделать в цикле:

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

Кажется мы оба согласны что это алгоритм линейной сложности.

Дальше смотрите я сделаю так:

const half = arr.length / 2;
for (let i = 0; i < 2; i++) {
    for (let j = half * i; j < half * (i+1); j++) {
      something(arr[j]);
    };
}

Является ли второй пример квадратичным? Ведь в нем есть "цикл в цикле"! Нет там все также линейная сложность. Можно переписать это ещё раз и сделать "цикл в цикле в цикле". Кошмар! Должна быть кубическая! Но нет все ещё остаётся линейная.

Но почему? Количество операций которые мы выполняем не изменилось. Мы проходим по каждому элементу один раз. От того что циклов стало два не изменится ничего. Я даже предположу что современные компиляторы выдадут одинаковый результат для обоих кусков кода.

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

Что касается вашего предложения перепроверить ваши замеры, извините но делать этого я не буду. Ваше предложение похоже на чайник Рассела. Вы высказали некоторое утверждение, я указал вам на то что оно кажется неверным и привел некоторое разумное объяснение. Вы предлагаете мне потратить значительно большее количество времени чем то что вы потратили на написание этой статьи. Извините, но даже не понятно что измерять. Вы сначала сравниваете с мастером, теперь с 17.5.0. Что за проект вы анализировали, не указано. Как прогревали кэши и сколько раз проводили измерения — не указано.

Потом вы сами пишете что да, может стало быстрее из-за того что v8 лучше оптимизирует. А может не стало, а может не лучше.

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

Но в тексте написано прямо противоположное. "сколько данных — столько и операций" это линейная сложность.

Простейший пример линейной сложности — поиск в односвязном списке. Чтобы получить элемент с номером N вам надо пройти по N ссылкам. В худшем случае, при получении последнего элемента по всему списку. Т.е. "сколько элементов в массиве, столько и операций". Размер списка имеет значение.

Пример константной сложности — поиск в массиве. Чтобы получить элемент с номером N надо просто взять смещение по размеру элемента и обратиться к нужному месту в памяти. Поэтому размер массива не имеет значения.

О(1) это константная сложность.

В двух словах идея такая:
имеет горячий код с квадратической сложностью -> делаем замеры -> оптимизируем код до линейной сложности -> делаем замеры -> код стал быстрее и проще в поддержке -> PROFIT

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

Буду благодарен за изминение кода + замеры, а еще мне не до конца понятно использование concat + spread при том, что map возвращает новый массив, и это равнозначно следующему коду:

1. Это не идентично. Ваш вариант вернёт массив массивов, а мой плоский массив.
2. Идея в том, что добавляя элементы по одному вы можете попасть на квадратичную сложность. Операция может иметь линейную сложность и соответственно вы можете на каждом цикле попасть на копирование всего существующего массива. concat принимает сразу массивы и склеивает их, по крайней мере копирование будет одно.

Ну это же легко проверить, вот ченчлог к версии v17.5.1, в этом и идея, что менялся только описанный код.

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

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

Проблема в том, что не понятно из-за чего произошло изменение, это вызывает все вопросы. Совершенно не понятно при чём тут монорепозиторий.

Я прочитал пост несколько раз пытался понять откуда берётся ускорение.

Допустим у нас 5 раннеров и каждый раннер возвращает нам 10 файлов. В первом варианте каждый раннер будет вызван один раз, функция processFile будет вызвана для каждого файла, т.е. 50 раз.

Да тут есть цикл в цикле но это ничего не меняет. Каждый внутренний проходит только по тем файлам что вернул текущий раннер. Т.е. каждый раннер будет вызван один раз и processFile будет вызвана 50 раз.

function process() {
    const results = [];

    for (const run of runners) {
        const files = run();

        for (const file of files) {
            results.push(processFile(file));
        }

     return results;
}

Т.е. нет никакой разницы с

function process() {
    const results = [];

    for (const run of runners) {
        files.push(...run());
    }

    for (const file of files) {
        results.push(processFile(file));
    }
     return results;
}

Тут также каждый раннер вызывается один раз и потом для каждого файла (а их будет 50 штук) будет вызван processFile.

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

Это можно полечить например с помощью чего-то вроде [].concat(...runners.map(r => r()));, тогда хотя бы не будет добавления элементов по одному.

Но главный вопрос, почему же стало быстрее не давал мне покоя и кажется я нашёл ответ. Проводя контрольный замер автор сравнивает мастер+свой патч с некоторой версией v17.5.0. Рискну предположить что разница из-за какого-то другого изменения. А тактов стало меньше потому что автор разделил функцию на три и они просто между ними размазались.

Может быть я понял что-то не так?

Ну насколько я могу понять, по обрывочным комментариям ТС, в частности про golang выше, основных проблем он видит две:

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

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

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

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

https://new.crbug.com/