Я после прочтения статьи как-то нервно сглотнул, т.к. у меня тоже этот ноут... Но жалобы после активного и непрерывного использования с августа 2021 года - вышел из строя разъём наушников, стёрся немного Trackpoint и на экране в одном месте что-то типа пятна (в области яркость больше, чем должна быть, при этом с увеличением расстояния до центра пятна эффект сходит на нет). Всё. Оперативную память расширил до 16 Гб (8+8), дополнительный терабайтный SSD поставил, полёт нормальный.
Хмм... Автор писал, что О(1) означает, что время работы не зависит от размера входа... Т.е. какие входы мы не пробуем, у нас всегда получается одно и то же время. В моём примере просто нет явно проговоренного входа, но можно сказать, что в функцию отдаётся массив, а функция на него не смотрит.
Но можно и докрутить, чтобы была явная зависимость. У меня получился пример O(1), которая может работать за разное время в зависимости от случая. Тогда вместо монетки будем смотреть на чётность длины входа => выйдет функция, где имеется явная зависимость от длины входа.
Опять прогеры пытаются интуитивно понять о-большое, не заботав нужный раздел матеши...
Но важно помнить: O(1)не всегда означает «мгновенно». Это лишь означает, что время выполнения не зависит от размера входных данных.
Почему это? Легко и непринуждённо может зависеть. Возьмём функцию, которая "кидает монетку", а затем, в случае, если выпал "орёл", делает цикл из 1000 итераций, иначе делает цикл из 1000000 итераций. В каждой итерации, допустим, делаем одну и ту же арифметику какую-нибудь или пишем в stdout номер итерации.
Итак, что у нас получилось? Функция совершает либо 1K, либо 1M элементарных действий, при этом каждое элементарное действие не зависит от входа. Эта функция работает за O(1), но время исполнения раз на раз не приходится. Причём сильно.
А всё дело в том, что множество "O(1)" - это ограниченные функции, а не константы, как может интуитивно показаться. В частности, для f(n) = 2+cos(n) выполнено f(n) = O(1). Я сейчас не про вычматистские методы приближённого вычисления косинуса, а про то, что косинус мажорируется по модулю единичкой, так что по определению получается здесь именно такое о-большое.
Все формулы, кстати, доказываются вполне строго - почему не пишем константы, почему не пишем основание логарифмов, почему оставляем только самую старшую степень в многочленах, etc... Но люди продолжают пытаться это на пальцах как-то объяснить.
Трафик Matrix - HTTP(S) с JSON под капотом. А что там внутри где-то встречаются base64 от зашифрованных мегольмом сообщений/файлов/signalling-сообщений уже не важно. А звонки (по крайней мере, согласно спекам матрикса) идут по WebRTC.
Удивил фрагмент N4. В цикле делается раз за разом malloc, результат сохраняется каждый раз в одну и ту же переменную... Это вы вырезали фрагменты, но не пометили многоточием?
Ни о чём статья. Таких я видел уже дофига, но вот почему-то до сути не доходит никто. У меня есть знакомый, дал я как-то ему задачу на префиксные суммы - научиться быстро вычислять суммы на подотрезках массива, если к массиву не делаются запросы на модификацию. Он написал на каждый запрос лобовое суммирование за линию. Я говорю ему, что надо бы побыстрее, так он стал в цикле в сумму докидывать сразу i'ый и N-i'ый элементы, мол, O(n/2). К чему я это - тема алгоритмической сложности довольно неочевидна, тут ботать надо плотно. Ни разу в научпопе не видел, чтобы объясняли, почему мы не пишем константы.
Кстати, о константах. Автор, вы бы как предпочли проверять на простоту: "до корня", т.е. за экспоненту, или за O(N^6)? Алгоритм АКС как раз за полином работает, берём его?
Декартово!
Ох, напомнило увуфикатор...
Я после прочтения статьи как-то нервно сглотнул, т.к. у меня тоже этот ноут... Но жалобы после активного и непрерывного использования с августа 2021 года - вышел из строя разъём наушников, стёрся немного Trackpoint и на экране в одном месте что-то типа пятна (в области яркость больше, чем должна быть, при этом с увеличением расстояния до центра пятна эффект сходит на нет). Всё. Оперативную память расширил до 16 Гб (8+8), дополнительный терабайтный SSD поставил, полёт нормальный.
Интересно, в какой такой я корпорации работаю...
Жесть, там не было detect it easy??? Это же очень полезный сканнер файлов... Он даже крипто-константы находит в бинарниках!
Но это добавляет слой индирекции, т.е. мало просто разыменовать, надо ещё и найти этот адрес по дескриптору.
Какой-какой версии? Боитесь, что больше версий не будет, что ли?
Хмм... Автор писал, что О(1) означает, что время работы не зависит от размера входа... Т.е. какие входы мы не пробуем, у нас всегда получается одно и то же время. В моём примере просто нет явно проговоренного входа, но можно сказать, что в функцию отдаётся массив, а функция на него не смотрит.
Но можно и докрутить, чтобы была явная зависимость. У меня получился пример O(1), которая может работать за разное время в зависимости от случая. Тогда вместо монетки будем смотреть на чётность длины входа => выйдет функция, где имеется явная зависимость от длины входа.
Опять прогеры пытаются интуитивно понять о-большое, не заботав нужный раздел матеши...
Почему это? Легко и непринуждённо может зависеть. Возьмём функцию, которая "кидает монетку", а затем, в случае, если выпал "орёл", делает цикл из 1000 итераций, иначе делает цикл из 1000000 итераций. В каждой итерации, допустим, делаем одну и ту же арифметику какую-нибудь или пишем в stdout номер итерации.
Итак, что у нас получилось? Функция совершает либо 1K, либо 1M элементарных действий, при этом каждое элементарное действие не зависит от входа. Эта функция работает за O(1), но время исполнения раз на раз не приходится. Причём сильно.
А всё дело в том, что множество "O(1)" - это ограниченные функции, а не константы, как может интуитивно показаться. В частности, для
f(n) = 2+cos(n)выполненоf(n) = O(1). Я сейчас не про вычматистские методы приближённого вычисления косинуса, а про то, что косинус мажорируется по модулю единичкой, так что по определению получается здесь именно такое о-большое.Все формулы, кстати, доказываются вполне строго - почему не пишем константы, почему не пишем основание логарифмов, почему оставляем только самую старшую степень в многочленах, etc... Но люди продолжают пытаться это на пальцах как-то объяснить.
Полжены?
Я в этот момент решил, что статья - перевод без тега "перевод".
Трафик Matrix - HTTP(S) с JSON под капотом. А что там внутри где-то встречаются base64 от зашифрованных мегольмом сообщений/файлов/signalling-сообщений уже не важно. А звонки (по крайней мере, согласно спекам матрикса) идут по WebRTC.
Городские и внутри МКАДа остались.
А мне тайпхинтов не хватает...
Наверное, "работал" == "денежные услуги оказывал". В этом смысле, а не в смысле РКН.
Удивил фрагмент N4. В цикле делается раз за разом
malloc, результат сохраняется каждый раз в одну и ту же переменную... Это вы вырезали фрагменты, но не пометили многоточием?От этого текста пахнет LLM.
Что...? Это кому это сломали https? Когда, как, кто? Звучит, как дичь.
SWL pog
Ни о чём статья. Таких я видел уже дофига, но вот почему-то до сути не доходит никто. У меня есть знакомый, дал я как-то ему задачу на префиксные суммы - научиться быстро вычислять суммы на подотрезках массива, если к массиву не делаются запросы на модификацию. Он написал на каждый запрос лобовое суммирование за линию. Я говорю ему, что надо бы побыстрее, так он стал в цикле в сумму докидывать сразу i'ый и N-i'ый элементы, мол, O(n/2). К чему я это - тема алгоритмической сложности довольно неочевидна, тут ботать надо плотно. Ни разу в научпопе не видел, чтобы объясняли, почему мы не пишем константы.
Кстати, о константах. Автор, вы бы как предпочли проверять на простоту: "до корня", т.е. за экспоненту, или за O(N^6)? Алгоритм АКС как раз за полином работает, берём его?