Проверка равенства целых чисел:O (1) в C, но O (log n) в Python 3?
https://cs.stackexchange.com/questions/127939
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Рассмотрим эти эквивалентные функции в C и Python 3.Большинство разработчиков сразу заявили бы, что оба $О(1)$.
def is_equal(a: int, b: int) -> bool:
return a == b
int is_equal(int a, int b) {
return a == b;
}
Но подумайте о том, что происходит под поверхностью.Целые числа — это просто двоичные строки, и для определения равенства оба языка сравнивают строки побитно.В любом случае это сканирование $О(б)$ где $б$ это количество битов.Поскольку в C целые числа имеют постоянный размер в битах, это просто $О(1)$.
РЕДАКТИРОВАТЬ:C не сравнивает побитно см. этот ответ
Однако в Python 3 целые числа нет имеют фиксированный размер и скан остается $О(б)$ для количества бит на входе или $O(\log а)$ где $а$ — это значение входа в базе 10.
Итак, если вы анализируете код на Python, каждый раз, когда вы сравниваете два целых числа, вы отправляетесь в удивительно сложное путешествие. $O(\log n)$ относительно значения по основанию 10 любого числа.
Для меня это вызывает несколько вопросов:
- Это верно?Я не видел, чтобы кто-нибудь еще утверждал, что Python сравнивает целые числа во время журнала.
- В контексте проведения собеседования следует ли вам заметить или обратить внимание на то, что кандидат называет это $О(1)$?
- Стоит ли вам замечать это различие или обращать на него внимание в реальном мире?
РЕДАКТИРОВАТЬ:Легко проверить (и интуитивно понятно), что Python не может сравнивать произвольно большие целые числа за постоянное время.Поэтому лучший способ задать вопрос 1 выше: «Каково (если таковое имеется) обоснование вызова этой операции?» $О(1)$?Потому что это прагматично?Общепринятый?Подразумевается моделью оперативной памяти?
Решение 7
TL; DR: Существует CS-конвенция о описании этого типа операции как $ O (1) $ , который происходит, чтобы сломаться в крайних случаях для Python. Эти случаи являются чрезвычайно редкостью, поэтому сломать с Конвенцией о $ O (1) $ имеет отрицательную утилиту. Этот вид прагматизма нормальный в большом $ O $ .
Есть много очень хороших ответов на этот вопрос, и я призываю вас прочитать их. Но я не думаю, что кто-либо из них полностью ответит на мои вопросы. Так вот синтез.
Это правильно? Я не видел никого другого утверждения, что Python сравнивает INT в журнале времени.
Это удивительно нюансировано. Это strong> true , что python сравнивает очень большое значение в $ O (\ log n) $ Runtime. Но это правильно , чтобы описать эту операцию как $ O (\ log n) $ ?
В конечном итоге я наиболее убежден этим взять от @tomvanderzanden:
Если вы сказали, что версия C или Python была
$ O (1) $ Любой интервьюер должен быть идеально счастливым. Если вы сказали, что (версия Python) была $ O (\ log n) $ они, вероятно, все равно будут счастливы, но думают, что вы довольно педантично, который не делает T следуйте за обычными конвенциями.
и
Если я был интервьюером, я бы заботился, знаете ли вы реальные ограничения того, что вы делаете и знаете, какие теоретические проблемы имеют значение, когда и что вы приносите их, если и только в случае необходимости.
Однако я не принимаю это как ответ, потому что я думаю, что первый абзац вводит в заблуждение (счастливо изменить).
В конечном итоге этот аргумент является прагматичным. По стромным определению Big $ O $ o $ Сравнение Python INT все еще подтверждается $ O (\ log n) $ Но это не полезно относиться к этому так, чтобы вы не должны. Я бы добавил, что это строго о большом $ O $ - это пропустить точку большого $ o $ анализ.
Другие советы
Целые числа — это просто двоичные строки, и для определения равенства оба языка сравнивают строки побитно.
Не совсем.С ints имеют размер машинного слова и сравниваются с одной машинной инструкцией;Питон intпредставлены в базе $2^{30}$ (см., например, https://rushter.com/blog/python-integer-implementation/) и сравнили поразрядно в этой базе.Таким образом, соответствующее основание логарифма равно $2^{30}$.
Если хотя бы один чисел могут быть ограничены $2^{30д}$ для любой зафиксированный $д$, сравнение $О(1)$ (поскольку сначала сравнивается количество цифр), и если они не могут этого сделать, другие операции, вероятно, будут вызывать гораздо большее беспокойство, чем сравнение на равенство.Так что на практике я бы сказал, что это маловероятно, и если это имеет значение, вы узнаете (и будете использовать not intно что-то вроде Библиотека арифметики множественной точности GNU и в C тоже).
определяется относительно модели вычислений.P и NP, например, определены в терминах Turging Machines.
Для сравнения, рассмотрим слово Word Model.В этой модели память делится на слова, слова могут быть доступны в постоянном времени, и размер задачи можно представить с помощью $ O (1) $ слова.
Так, например, при анализе операции сортировки на основе сравнения мы предполагаем, что количество элементов $ n $ может быть сохранено в $ o (1) $ Слова, поэтому требуется постоянное время для чтения или записи номера между $ 1 $ и $ N $ .
Это правильно? Я не видел никого другого утверждения, что Python сравнивает INT в журнале времени.
Нет (и немного да). Рассмотрим следующее провоцируемое мысль (но не очень верно): компьютер может иметь конечное количество памяти (ограничено количеством атомов во вселенной), поэтому версия Python также $ O (1) $ .
Проблема в том, что мы пытаемся сделать заявление об асимптотике (относящиеся к тому, что происходит на бесконечности), о конечном-станке (компьютер). Когда мы анализируем сложность кода, мы на самом деле не анализируйте сам код, так как он будет работать на компьютере, мы анализируем некоторую идеализированную модель кода.
Предположим, что я попросил вас проанализировать алгоритм сортировки, написанный в C. Вы можете указать, что он использует INT, чтобы индексировать массив, поэтому он может только сортировать массив размера до
В контексте проведения собеседования вы должны заметить или заботиться, если кандидат вызывает это о (1)?
Обычно не. Предположим, что я проводлю интервью и прошу вас написать компьютерную программу C или Python, которая подсчитывает количество сотрудников женщин, появляющихся в базе данных сотрудников.
Это будет невероятно pedantic, если я пожаловался, что ваша программа C была неверной, потому что она может рассчитывать только на $ 2 ^ {31} -1 $ .
Мы обычно предполагаем, что цифры достаточно маленькие, чтобы они могли вписаться в одно слово / целое число. Мы предполагаем добавление (или любое другое другое число) можно сделать в $ o (1) $ , потому что было бы очень раздражает, чтобы написать
Если вы сказали, что версия C или Python была
Если вы заметите или заботитесь об этом различии в реальном мире?
Да! Это начинает иметь значение, когда цифры становятся такими большими предположения, они маленькие нарушены. Допустим, вы занимаетесь интервью для Google, и они попросили вас вычислить количество поисковых запросов, выполненных пользователей женщин в прошлом году. Интервьюер будет вполне оправдан, чтобы пожаловаться, если вы написали программу C, используя ints.
Вы можете переключиться на использование длинных и до сих пор быть оправданным при вызове его $ O (1) $ и аналогично, вызывая версию Python
Если я был интервьюером, я бы заботился, знаете ли вы реальные ограничения того, что вы делаете и знаете, какие теоретические проблемы имеют значение, когда и что вы приносите их, если и только в случае необходимости.
Когда вы должны заботиться?
До сих пор я был немного расплывчатым о «больших» и «маленьких» числах. В обычном использованном модели RAM вам разрешено предполагать, что целочисленные операции могут быть выполнены в $ O (1) $ на номерах, которые имеют максимально возможное «Математический контейнер»> $ O (\ log n) $ bits (где $ n $ - это длина ввода). Обоснование этого предположения заключается в том, что если у нас будет ввод длины $ n $ , указатели / индексы на нашем языке программирования должны быть достаточно долго, чтобы иметь возможность решать Все входное пространство. Итак, в модели RAM, если вход - это двоичное число $ n $ (двоичных) цифр, сложность проверки равенства составляет $ O (\ log n) $ < / span> биты в одном $ o (1) $ операция.
Хотя это может показаться тривиальным моментом, ваше первое предложение неверно. Эти функции не эквивалентны.Чтобы сделать их эквивалентными, функция C должна использовать GMP (или аналогичный) для реализации арифметики произвольной точности.Итак, причина, по которой это наблюдение не является тривиальным, заключается в том, что степень, в которой разумно сказать, что эти два понятия эквивалентны, - это именно та степень, в которой разумно сказать, что код Python является постоянным во времени!То есть, если мы собираемся игнорировать, что целые числа Python являются величинами, мы можем (и должны) последовательно рассматривать их как фиксированный размер.
Аналогично, рассмотрим функцию C int is_equal(char a, char b) { return a == b; } и функция Python def is_equal(a: str, b: str) -> bool: return a == b.Теперь более очевидно, что функции не эквивалентны, но причина этого точно такая же, как и причина, по которой ваши не эквивалентны.Мы просто ожидаем постоянно видеть массивные строки в Python, но на самом деле не ожидаем массивных целых чисел, хотя, конечно, мы знаем, что они возможны.Итак, большую часть времени мы игнорируем тот факт, что целые числа в Python большие, и анализируем так, как будто они фиксированного размера.В редких случаях, когда мы заботимся о сроках выполнения операций bignum, вы можете использовать "реальные" сложности.И, конечно же, также используйте GMP в своем C-коде.
Все это для того, чтобы сказать:хотя вы этого не осознавали, вы уже знаете ответ на свою пересмотренную версию вашего вопроса в конце, и ответ таков: "то же обоснование, с помощью которого вы описали эти функции как эквивалентные".Python необычен тем, что не имеет целочисленного типа фиксированного размера (ну, не того, который люди обычно используют:конечно, можно написать один из них, и он есть в numpy).Но из соображений прагматизма мы не хотим, чтобы это мешало нам проводить "обычный" анализ сложности алгоритмов, которые обрабатывают целые числа, и получать "обычные" ответы.Редко бывает необходимо указывать на то, что если мы передадим ему пару целых чисел объемом 10 ГБ, которые почти равны, то для их сравнения может потребоваться некоторое время.
В некоторых случаях вы могли бы формализовать это (если вам действительно нужно), сказав, что вы ограничиваете свой анализ небольшими целыми числами.Затем вы могли бы рассмотреть сложность некоторого алгоритма в терминах размера некоторого массива целых чисел, рассматривая все арифметические операции как O (1).Если вы рассматриваете алгоритмы, которые действительно линейны или хуже по величине целого числа, то вы могли бы формализовать это, сказав, что собираетесь игнорировать логарифмический коэффициент, поскольку все, что вас действительно волнует, это то, является ли сложность ближе к линейной или квадратичной, потому что O (n log n) так же хорош, как и linear для ваших целей.Однако почти всегда вам не нужно формализовывать сложность алгоритмов в Python.Если вы дошли до определения языка программирования, то на самом деле вы больше не занимаетесь абстрактной информатикой ;-)
В контексте проведения собеседования, должны ли вы заметить или позаботиться если кандидат называет это $O(1)$?
Я полагаю, зависит от того, для чего проводится собеседование, но как профессионал в области программного обеспечения, работающий в основном на Python последние 10 лет, я бы не спрашивал об этом на собеседовании.Если бы я задал вопрос, в котором была скрыта сложность целочисленного сравнения (например, я не знаю, "какова сложность этого алгоритма сортировки?"), то я бы принял ответ, который игнорировал всю проблему.Я бы также принял тот, который адресован этому вопросу.Я действительно думаю, что это стоит понимать и усложнять вычисления как часть практического программирования, я просто не считаю это настолько важным для программирования быть очень осторожным, формально заявляя, что вы говорите о целых числах разумного размера.
Я бы также никогда не задал вопрос, в котором я хотел бы, чтобы кандидат предоставил информацию о том, что целые числа Python имеют произвольную точность, когда по какой-то причине это явно не имеет отношения к вопросу, связанному с задействованными данными.Если вопрос подразумевает, что задействованные числа могут превышать 264 затем на собеседовании на C я бы хотел, чтобы кандидат заметил, что это проблема, с которой ему нужно справиться, а на собеседовании на Python я бы хотел, чтобы кандидат знал, что это не так, но я бы не ожидал, что они будут изо всех сил заявлять об этом.В интервью нет времени излагать каждый незначительный факт, который превращает что-то в проблему.
Если бы я хотел проверить понимание сложности в интервью, то, скорее всего, я бы начал с запроса некоторого кода для какой-нибудь проблемы, где есть действительно простое "наивное" решение с низкой сложностью и, по крайней мере, одно менее простое решение с приличной сложностью с использованием хорошо известных методов.Если кандидат предлагает наивное решение, то вы можете спросить, в чем сложность и как бы он изменил код, чтобы улучшить его.Если кандидат предлагает лучшее решение, вы можете описать наивное решение, указать, как мало в нем строк кода, и спросить, что в нем не так (возможно, спросив: "если бы вы просматривали чей-то код и они дали вам это, что бы вы сказали об этом"?).Для большинства практических целей все, о чем вы заботитесь, - это могут ли они определить разницу между линейными, квадратичными и хуже квадратичных.O (n log n) также появляется, но в основном из-за сортировки или структур данных, где вы говорите о сложности с точки зрения количества сравнений.Стоимость каждого сравнения обычно считается несущественной, поскольку разработчик алгоритма обычно не имеет над ней никакого контроля (она предоставляется пользователем алгоритма или структуры данных).
В удивительно маловероятном случае, если бы я был интервьюером на должность преподавателя CS, занимающегося арифметикой произвольной точности, то, конечно, я бы хотел, чтобы кандидаты знали сложности различных алгоритмов для различных операций и действительно были знакомы с современным уровнем техники для нетривиальных.
Это правильно? Я не видел никого другого утверждения, что Python сравнивает INT в журнале времени. Python действительно имеет произвольный точный целочисленный формат. Однако мы должны сделать справедливое сравнение здесь. Если мы рассмотрим подмножество целых чисел на границе $ [0,2 ^ {64}] $ , мы обнаруживаем, что операция Python - это постоянное время.
То, что вы видите, является одним из ограничений, что для измерения вычислительной сложности с использованием обозначения Big-Oh. Он описывает, что происходит как n подходит к бесконечности, но не обязательно делает хорошую работу по сравнению поведения для меньших чисел. Мы видим это отлично в Алгоритмы умножения матрицы . Есть несколько алгоритмов, которые более эффективны в смысле большого ой, но на самом деле на самом деле медленнее, пока не доберетесь до матриц Gargantuan.
В контексте проведения собеседования вы должны заметить или заботиться, если кандидат вызывает это о (1)?
зависит от того, что вы нанимаете их. Для подавляющего большинства рабочих мест, называющих его o (1), должно быть в порядке. Действительно, именно мы склонны участвовать в школе. Если вы хотели превратить его в полезную возможность узнать о своем кандидате, вы можете спросить их, почему они думают, что дополнение - это постоянное время (насколько ответ является тем, что модель, которую они использовали для определения Big-Oh Действительный ответ)
Если вы нанимаете кого-то, чтобы искать такие вещи, как эксплойтиты в вашем коде, вы можете толчок дальше. Bignum, создаваемый вашим собственным кодом, это одно, но пользователь позволяет вводить номер их собственного выбора? Если это так, они могут иметь возможность создавать временные атаки и DOSS, используя тот факт, что это дополнение может быть ужасно медленно. Обнаружение этого риска может быть частью их работы.
Если вы заметите или заботитесь об этом различии в реальном мире?
Практически говоря: нет. Не до тех пор, пока вы пострастно не запустите его, и исправьте проблему в отладке. Python делает участок о вещах, которые "вообще безопасны" и очень эффективны. Вот почему он занял один из самых популярных языков в мире.
Для эквивалентной ситуации: как быстро генеракодицетагкод в Python? Мы думаем об этом как о O (1), но там на самом деле есть хеш-нагляд. Этот Hash Lookup использует известный механизм зондирования, а полученный поиск на самом деле является O (n). Вы никогда не увидите это в обычном коде. Но в коде, где противник попадает, чтобы заполнить ваш словарь со своим собственным контентом, они могут намеренно редить ключевые ключи, которые сталкиваются таким образом.
Я никогда не сталкивался с текстом, который лечил «регулярные» целочисленные операции как все, помимо постоянного времени, с неявным предположением, что размер имел некоторую разумную конечную верхнюю границу (например, 64 бита).Возможно, было бы точнее, чтобы указать предположение, но для аудитории CS, я думаю, что это неявно.
делает это так, чтобы ввести много сложности в обсуждениях по существу не связанными темами.Реализации Bigint, как правило, не реализуются битром, но в базе - (размер слов машины), так что O (B)> O (1) проблема только для абсолютно больших чисел.
Лично во время интервью у кого-то, я могу оценить строгость и широту знаний, связанные с знанием целых чисел Python, были произвольными длиной, но что-то, кроме того, что касается предположения, что все математика - это О (1), будет чувствовать себя крайне педантичным.Если анализ начал становиться слишком далеко от темы арифметической, и впустую время, я бы считал этого плохого кандидата.
