Боюсь, это всё также довольно легко осваивается "вчерашними студентами" и вообще не является мерилом "сеньористости" (что бы это не значило).
Просто есть люди, которым заходит инженерия (всякие обходы деревьев или нюансы устройства индексов в бд), а есть кому заходит бизнес (как фичи деливерить и пофиг что здесь квадрат). Обычно нужны и те и другие — дальше вопрос только в балансе как в количестве, так и в соотношении качеств отдельных индивидов. И вот баланс уже зависит от компании и её потребностей.
то флаш кэша занимающий 5мс очевидно ничтожен по сравнению с запросами в интернет занимающими в десятки и сотни раз больше;
В этом случае у нас просто линейный Put. Амортизация тут неприменима. И тогда выигрыша от реализации 2.5 никакого нет.
Но в любом случае, O(n) кеш штука изначально довольно специфичная. Предлагать её без дополнительных вводных — странно.
кэш в процессорах ARM вообще на рандомную стратегию переделали ...
Ну так там же кеш по бакетам(в каждом бакете независимое вытеснение). И размер одного бакета 4-32, емнип. Это как раз ситуация довольно специфичная.
всё правильно, тут всё таки демонстрационная реализация :) к сожалению устройство и возможности мэпы конкретно в Go делают её особенно неудобной для любого "продвинутого" применения
Кажется было бы хорошо вставить по этому поводу комментарий — для неискушённых читателей. Впрочем, печально, что нет доступа к продвинутым юзкейсам (хотя в целом понятно почему).
При самописной реализации хештаблицы выигрыш от альтерантивных схем становится меньше. Можно же спокойно хранить ноды в стиле linked hashmap — и тогда выигрыш по памяти становится слабым (+заменить указатели на 32-битные индексы чтобы ещё ближе к другим вариантам стать).
Ну и как правило LRU не прям хорошо работает. Поэтому достаточно часто нужны гибридные стратегии — и там обычно тяжело отказаться от связных списков.
Здесь вместо внятно аргументации заголовка, просто самописная реализация хештаблицы. Это, как минимум, предаёт ожидания.
Дальше, позиция "поиск в хештаблице за O(1*)" более полезна, чем "поиск за O(n)". Вопрос только в том, в каком именно смысле там O(1) (этому можно придать строгую формулировку). В статье с таким заголовком я бы ожидал именно разбора различных формулировок и следствий из них.
Ну и в целом, хештаблицы — это инженерный трюк. А потому, разбирать абстрактную хештаблицу в вакууме смысла мало. Если уж и разбирать, то нужно брать конкретные реализации и особенности их работы.
Например, если взять хештаблицу в яве, то там не будет поиска O(n) даже в присутствии колизий (если ключи какие-нибудь строки, или числа — что почти всегда так). Просто потому, что бакеты там устроены как деревья, а не связанные списки.
Или, если взять хештаблицу в C#/Rust, то там другой подход. Там используется достаточно хорошая хешфункция, что спровоцировать колизии достаточно сложно даже в режиме "злоумышленика".
Кажется вариант 2 ввиду амортизации неприменим на практике. Обычно же этот lru требуется в онлайн задачах. Крайне редко он нужен в оффлайн алгоритмах.
Ну и использование итерации по мапе в качестве семплирования — не очень хорошо. Сразу по нескольким причинам. Никто же не обещает порядка итерации по мапе — это не то же самое, что и случайный порядок. Ну и в принципе, такая итерация использует внешнюю случайность — то есть она зависит от данных. Это плохо, так как данные могут быть скорелированны. Для робастности нужно использовать внутреннюю случайность.
Почему? В смысле, с ним не больше боли, чем в самом тс.
P.S. ну понятное дело, что в идеале any должен значить unknown, а реальный any должен называться untyped/typehole. Но это отдельный разговор, т.к. на уровне самого кодгена несложно заменить any на unknown.
Понятное дело, что динамика медленная. Но в качестве фоллбэка вполне себе норм. Потому что просто выкинуть существенно часть языка — решение такое себе.
Не очень понятно, а какую цель преследовали, зачем именно отказываться от v8? Может лучше было сделать фреймворк для биндингов, чтобы можно было легко вызывать ts код. В v8, емнип, довольно хорошо эта история должна быть проработана.
Ну и вопрос сравнений перфа, наверное, тоже не осветили. Хотя набор бенчиакров здесь сложновато найти, конечно.
Почему не смогли поддержать any? Его же можно в условный AnyJsValue транслировать и использовать динамические возможности... Смотрели в эту сторону?
А там эти примеры без достаточных пояснений и раскрытия того что "между строк"
Я не знаю, в каких учебниках Вы смотрели, но когда я изучал рекурсию, там было вполне себе рассказано, что происходит между строк. Поэтому не могу согласиться с этим порывом.
Да, и что "рекурсия вредит читаемости кода/усложняет код" и то что рекурсия не просто бывает медленной, а может оказаться внезапно и трудно предсказуемо ресурсоёмкой (медленно лишь один из аспектов ресурсоёмкости), а это тоже про "вредит читаемости".
Так не пойдёт. Эти тезисы находятся в конфликте, поэтому не имеет смысла пытаться их доказывать одновременно - просто получите кашу из мнений. Читаемость важна в первую очередь в "желтой" и "зелёной" зоне проекта, а вот ресурсоёмкость становиться важна, в основном, в красной зоне проекта. Пытаться доказать их одновременно - это доказательство запутыванием (ввиду неясного контекста!).
Ассимтотически, по крайней мере в этих примерах, и рекурсия и цикл оба работают за линейное/логарифмическое время (в зависимости от примера). Поэтому ассимптотически они одинаково оптимальные, либо неоптимальны*.
А наличие лишнего прохода - это как раз про "такты". Потому что если мы не учитываем такты, то замедление алгоритма даже в 2-10 раз, зачастую не является принципиальным.
*: ну если придираться, то рекурсия в этих примерах использует линейную доп. память, против константного у циклов. Но это по большей части вызвано вырожденностью этих примеров.
А вот ваша версия ... звучит конечно короче, но у меня в голове укладывается плохо ;)
Всё очень просто. Если знать и активно применять динамическое программирование, то подход половинного деления абсолютно естественный и его проще придумать. Аналогично, если иметь много опыта с разделяй и властвуй. Если быть от этого далёким - то действительно может быть непривычно.
А вот подход с двоичным разложением существенно завязан на структуру задачи. Двоичное разложение редко когда применимо к задачам. И нужно быть достаточно сильно погружённым в домен, чтобы догадаться до такого инварианта как двоичное разложение. Иными словами, этот подход достаточно тяжело переносить на другие задачи.
Как аналогию можно сравить дерево отрезков и дерево фенвика. Дерево отрезков гораздо проще придумать и доказать. Также в дерево отрезков гораздо проще вносить всякие интересные вариации. С деревом фенвика это делать гораздо сложнее.
Ну и в целом, я, например, достаточно много трачу времени на то, чтобы устранить рекурсию. И это очень сложно (ну кроме банального эмулирования стека - но это медленно довольно таки). Поэтому всё же в общем случае рекурсия более общий механизм чем циклы. Рекурсию можно заменить на цикл только в очень ограниченном наборе юзкейсов - и лишь в части из них, это выглядит естественно.
Банально, попробуйте написать поиск в дереве отрезков без рекурсии и сложность кода.
Обычно, под "алгоритмической эффективностью" подразумевают что-то в стиле "оптимальная ассимптотика". Поэтому возможно стоит сменить термин.
В приведённых здесь примерах этого нет, но дальше такие примеры появятся.
Так может стоило начать именно с таких примеров? Потому что пока что приведённые примеры весьма нереалистичны (никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
А "не будет" относится к тому что не будет приписывать второй цикл, который выполняет исключительно бессмысленные действия.
Вообще, с эффективностью в плане "не делать лишнего".есть всякие неочевидные сложности. Например, можете ли Вы сказать, оптимален ли такой код (с точки зрение Вашей "алгоритмической эффективности"):
Скрытый текст
size_t bespoke_strlcpy(char *dst, const char *src, size_t size)
{
size_t len = 0;
for (; src[len] != '\0'; ++len) {} // strlen() loop
if (size > 0) {
size_t to_copy = len < size ? len : size - 1;
for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
dst[i] = src[i];
dst[to_copy] = '\0';
}
return len;
}
Первый проход здесь почти бесмысленный. Можно его легко совместить со вторым проходом.
Ответ
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
P.S. Я честно говоря, не до конца понимаю, какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно". Это, если что, разные тезисы, которые обычно могут быть важны в разных ситуациях (и чаще всего несовместимы!).
"Неправильно" - это я с методологической точки зрения. Не важно, есть там использование стека или нет, важно что дебаг-принты и отладчик нельзя использовать для анализа на уровне "тактов" - они просто рисуют фантазию на тему, а не реальное поведение.
А так, понятное дело, что оптимизации компиляторозависимы. Более того, эти оптимизации ещё могут отваливаться при любом обновлении компилятора. Но, как уже говорил, подсчёт тактов в целом компиляторозависим.
Здесь наглядно видно результат работы обоих псевдоциклов. Увидеть эти циклы можно и при пошаговой отладке программы. Но в программе с рекурсией (код 1.2) мы не видим никаких циклов, а значит у программиста нет возможности выкинуть лишний цикл. Это иллюстрация того что рекурсия неуправляема и плохо читаема (красивый лаконичный код рекурсии не соответствует реальному поведению программы и надо разбираться что там подразумевается между строк).
Вообще, Вы в этой статье смешиваете семантический уровень и уровень железа. Как там оно будет исполняться на железе - вопрос весьма нетривиальный, на который в общем случае ответить нельзя. Например в том же хаскеле рекурсия не тратит стек в принципе (и там вообще нет стека в привычном понимании).
Рекурсия захламляет стек не только последовательностью n-1, n-2, n-3, ..., а ещё и адресом возврата из функции, но здесь и далее разбор этих "накладных расходов" опущен, поскольку рекурсия здесь рассматривается с точки зрения алгоритмической эффективности.
А что именно в Вашем понимании "алгоритмическая эффективность"?
Edit:
здравомыслящий программист не станет писать громоздкий и нелогичный код 2.3 вместо простого и наглядного кода 2.1, но именно код 2.3 является наглядной демонстрацией алгоритма работы "простого и красивого" рекуррентного кода 2.2.
Явно писать код со стеком - конечно не будет. Но это не означает, что наличие этого стека как-то мешает. В тот момент, когда глубина стека, или наличие там лишних значений становиться проблемой - тогда уже не мыслят категориями "рекурсия"/"цикл". В таких ситуациях мыслят бенчмарками и асмом. А в типовом коде, рекурсию используют не потому что быстро - а потому что просто - и с этим, вроде, даже Вы согласны, что никаких проблем нет.
Определенно меньше, достаточно лишь проанализировать одну диспач функцию, чтобы всё встало на места.
Здесь не очень очевидно. Речь же, разумеется, идёт не о том, чтобы анализировать руками — речь об автоматическом анализе. И там в одном случае нужно хешмап разворачивать, а в другом следить за указателем в данных. Но не суть — что то, что другое решаются.
Этот подход создаёт не больше трудностей (а то и меньше), чем виртуализация. По идее, хороший анализ девиртуализации спокойно может отменить все подобные приседания. Поэтому такой подход не масштабируется.
Если его пытаться масштабировать, то получится что-то в стиле vmprotect. То есть просто сделать виртуальную машину и транслировать код под эту вм. При этом, одна инструкция этой вм может делать весьма много действий. А чтобы масштабировать защиту, вм генерируется при каждой компиляции новая.
Боюсь, это всё также довольно легко осваивается "вчерашними студентами" и вообще не является мерилом "сеньористости" (что бы это не значило).
Просто есть люди, которым заходит инженерия (всякие обходы деревьев или нюансы устройства индексов в бд), а есть кому заходит бизнес (как фичи деливерить и пофиг что здесь квадрат). Обычно нужны и те и другие — дальше вопрос только в балансе как в количестве, так и в соотношении качеств отдельных индивидов. И вот баланс уже зависит от компании и её потребностей.
В этом случае у нас просто линейный Put. Амортизация тут неприменима. И тогда выигрыша от реализации 2.5 никакого нет.
Но в любом случае, O(n) кеш штука изначально довольно специфичная. Предлагать её без дополнительных вводных — странно.
Ну так там же кеш по бакетам(в каждом бакете независимое вытеснение). И размер одного бакета 4-32, емнип. Это как раз ситуация довольно специфичная.
Кажется было бы хорошо вставить по этому поводу комментарий — для неискушённых читателей. Впрочем, печально, что нет доступа к продвинутым юзкейсам (хотя в целом понятно почему).
При самописной реализации хештаблицы выигрыш от альтерантивных схем становится меньше. Можно же спокойно хранить ноды в стиле linked hashmap — и тогда выигрыш по памяти становится слабым (+заменить указатели на 32-битные индексы чтобы ещё ближе к другим вариантам стать).
Ну и как правило LRU не прям хорошо работает. Поэтому достаточно часто нужны гибридные стратегии — и там обычно тяжело отказаться от связных списков.
P.S. не поймите неправильно, статья интересная
Здесь вместо внятно аргументации заголовка, просто самописная реализация хештаблицы. Это, как минимум, предаёт ожидания.
Дальше, позиция "поиск в хештаблице за O(1*)" более полезна, чем "поиск за O(n)". Вопрос только в том, в каком именно смысле там O(1) (этому можно придать строгую формулировку). В статье с таким заголовком я бы ожидал именно разбора различных формулировок и следствий из них.
Ну и в целом, хештаблицы — это инженерный трюк. А потому, разбирать абстрактную хештаблицу в вакууме смысла мало. Если уж и разбирать, то нужно брать конкретные реализации и особенности их работы.
Например, если взять хештаблицу в яве, то там не будет поиска O(n) даже в присутствии колизий (если ключи какие-нибудь строки, или числа — что почти всегда так). Просто потому, что бакеты там устроены как деревья, а не связанные списки.
Или, если взять хештаблицу в C#/Rust, то там другой подход. Там используется достаточно хорошая хешфункция, что спровоцировать колизии достаточно сложно даже в режиме "злоумышленика".
Поэтому разбор странный.
Кажется вариант 2 ввиду амортизации неприменим на практике. Обычно же этот lru требуется в онлайн задачах. Крайне редко он нужен в оффлайн алгоритмах.
Ну и использование итерации по мапе в качестве семплирования — не очень хорошо. Сразу по нескольким причинам. Никто же не обещает порядка итерации по мапе — это не то же самое, что и случайный порядок. Ну и в принципе, такая итерация использует внешнюю случайность — то есть она зависит от данных. Это плохо, так как данные могут быть скорелированны. Для робастности нужно использовать внутреннюю случайность.
Понятно, что пробовали писать приложение на смеси c++ и TS. Вопрос в том, почему взялись за компиляцию, а не за интеграцию условного v8?
Ну, bun или v8 не так уж и важно. Это в любом случае меньше работы, чем написать комплиятор
Почему? В смысле, с ним не больше боли, чем в самом тс.
P.S. ну понятное дело, что в идеале any должен значить unknown, а реальный any должен называться untyped/typehole. Но это отдельный разговор, т.к. на уровне самого кодгена несложно заменить any на unknown.
Как раз наоборот. Динамика обычно требует pro, чтобы работать не прям совсем медленно.
Понятное дело, что динамика медленная. Но в качестве фоллбэка вполне себе норм. Потому что просто выкинуть существенно часть языка — решение такое себе.
Не очень понятно, а какую цель преследовали, зачем именно отказываться от v8? Может лучше было сделать фреймворк для биндингов, чтобы можно было легко вызывать ts код. В v8, емнип, довольно хорошо эта история должна быть проработана.
Ну и вопрос сравнений перфа, наверное, тоже не осветили. Хотя набор бенчиакров здесь сложновато найти, конечно.
Почему не смогли поддержать any? Его же можно в условный AnyJsValue транслировать и использовать динамические возможности... Смотрели в эту сторону?
Справедливости ради, подсчёт чисел Фибоначчи через цикл - это и есть тот самый другой алгоритм :)
Я не знаю, в каких учебниках Вы смотрели, но когда я изучал рекурсию, там было вполне себе рассказано, что происходит между строк. Поэтому не могу согласиться с этим порывом.
Так не пойдёт. Эти тезисы находятся в конфликте, поэтому не имеет смысла пытаться их доказывать одновременно - просто получите кашу из мнений. Читаемость важна в первую очередь в "желтой" и "зелёной" зоне проекта, а вот ресурсоёмкость становиться важна, в основном, в красной зоне проекта. Пытаться доказать их одновременно - это доказательство запутыванием (ввиду неясного контекста!).
Ассимтотически, по крайней мере в этих примерах, и рекурсия и цикл оба работают за линейное/логарифмическое время (в зависимости от примера). Поэтому ассимптотически они одинаково оптимальные, либо неоптимальны*.
А наличие лишнего прохода - это как раз про "такты". Потому что если мы не учитываем такты, то замедление алгоритма даже в 2-10 раз, зачастую не является принципиальным.
*: ну если придираться, то рекурсия в этих примерах использует линейную доп. память, против константного у циклов. Но это по большей части вызвано вырожденностью этих примеров.
Не придирайтесь к словам. От того, что компьютеры представляют числа в двоичной системе, двоичное разложение никуда не делось.
Всё очень просто. Если знать и активно применять динамическое программирование, то подход половинного деления абсолютно естественный и его проще придумать. Аналогично, если иметь много опыта с разделяй и властвуй. Если быть от этого далёким - то действительно может быть непривычно.
А вот подход с двоичным разложением существенно завязан на структуру задачи. Двоичное разложение редко когда применимо к задачам. И нужно быть достаточно сильно погружённым в домен, чтобы догадаться до такого инварианта как двоичное разложение. Иными словами, этот подход достаточно тяжело переносить на другие задачи.
Как аналогию можно сравить дерево отрезков и дерево фенвика. Дерево отрезков гораздо проще придумать и доказать. Также в дерево отрезков гораздо проще вносить всякие интересные вариации. С деревом фенвика это делать гораздо сложнее.
Ну и в целом, я, например, достаточно много трачу времени на то, чтобы устранить рекурсию. И это очень сложно (ну кроме банального эмулирования стека - но это медленно довольно таки). Поэтому всё же в общем случае рекурсия более общий механизм чем циклы. Рекурсию можно заменить на цикл только в очень ограниченном наборе юзкейсов - и лишь в части из них, это выглядит естественно.
Банально, попробуйте написать поиск в дереве отрезков без рекурсии и сложность кода.
Обычно, под "алгоритмической эффективностью" подразумевают что-то в стиле "оптимальная ассимптотика". Поэтому возможно стоит сменить термин.
Так может стоило начать именно с таких примеров? Потому что пока что приведённые примеры весьма нереалистичны (никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
Вообще, с эффективностью в плане "не делать лишнего".есть всякие неочевидные сложности. Например, можете ли Вы сказать, оптимален ли такой код (с точки зрение Вашей "алгоритмической эффективности"):
Скрытый текст
Первый проход здесь почти бесмысленный. Можно его легко совместить со вторым проходом.
Ответ
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
P.S. Я честно говоря, не до конца понимаю, какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно". Это, если что, разные тезисы, которые обычно могут быть важны в разных ситуациях (и чаще всего несовместимы!).
"Неправильно" - это я с методологической точки зрения. Не важно, есть там использование стека или нет, важно что дебаг-принты и отладчик нельзя использовать для анализа на уровне "тактов" - они просто рисуют фантазию на тему, а не реальное поведение.
А так, понятное дело, что оптимизации компиляторозависимы. Более того, эти оптимизации ещё могут отваливаться при любом обновлении компилятора. Но, как уже говорил, подсчёт тактов в целом компиляторозависим.
Наглядно, но неправильно. Правильно смотреть вот здесь: https://godbolt.org/z/86nxErzxW - найдите 10 отличий.
Вообще, Вы в этой статье смешиваете семантический уровень и уровень железа. Как там оно будет исполняться на железе - вопрос весьма нетривиальный, на который в общем случае ответить нельзя. Например в том же хаскеле рекурсия не тратит стек в принципе (и там вообще нет стека в привычном понимании).
А что именно в Вашем понимании "алгоритмическая эффективность"?
Edit:
Явно писать код со стеком - конечно не будет. Но это не означает, что наличие этого стека как-то мешает. В тот момент, когда глубина стека, или наличие там лишних значений становиться проблемой - тогда уже не мыслят категориями "рекурсия"/"цикл". В таких ситуациях мыслят бенчмарками и асмом. А в типовом коде, рекурсию используют не потому что быстро - а потому что просто - и с этим, вроде, даже Вы согласны, что никаких проблем нет.
Здесь не очень очевидно. Речь же, разумеется, идёт не о том, чтобы анализировать руками — речь об автоматическом анализе. И там в одном случае нужно хешмап разворачивать, а в другом следить за указателем в данных. Но не суть — что то, что другое решаются.
Этот подход создаёт не больше трудностей (а то и меньше), чем виртуализация. По идее, хороший анализ девиртуализации спокойно может отменить все подобные приседания. Поэтому такой подход не масштабируется.
Если его пытаться масштабировать, то получится что-то в стиле vmprotect. То есть просто сделать виртуальную машину и транслировать код под эту вм. При этом, одна инструкция этой вм может делать весьма много действий. А чтобы масштабировать защиту, вм генерируется при каждой компиляции новая.