정수의 동등성 확인:C에서는 O(1)이지만 Python 3에서는 O(log n)입니까?

Question

C와 Python 3에서 이와 동일한 기능을 고려하세요.대부분의 개발자는 즉시 둘 다 주장할 것입니다. $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

하지만 표면 아래에서 무슨 일이 일어나고 있는지 생각해 보세요.정수는 단지 이진 문자열이며, 동일한지 확인하기 위해 두 언어 모두 문자열을 비트 단위로 비교합니다.두 경우 모두 이 스캔은 $O(b)$ 어디 $b$ 비트 수입니다.C에서 정수는 비트 단위로 일정한 크기를 가지므로 이는 간단히 말해서 $O(1)$.

편집하다:C는 비트 단위로 비교하지 않습니다. 이 답변을 참조하세요

그러나 Python 3에서는 정수가 ~ 아니다 크기가 고정되어 있고 스캔이 유지됩니다. $O(b)$ 입력의 비트 수 또는 $O(\로그 a)$ 어디 $a$ 10진수의 입력 값입니다.

따라서 Python에서 코드를 분석하는 경우 두 정수를 비교할 때마다 놀랍도록 복잡한 여정을 시작하게 됩니다. $O(\로그n)$ 어느 숫자의 밑수 10 값과 관련하여.

나에게 이것은 몇 가지 질문을 제기합니다.

1. 이 올바른지?나는 Python이 로그 시간에 int를 비교한다고 주장하는 사람을 본 적이 없습니다.
2. 인터뷰를 진행하는 과정에서 후보자가 이렇게 부르는지 알아채거나 주의해야 합니까? $O(1)$?
3. 현실 세계에서 이러한 차이를 주목해야 할까요? 아니면 관심을 가져야 할까요?

편집하다:Python이 상수 시간에 임의로 큰 정수를 비교할 수 없다는 것은 쉽게 검증되고 직관적입니다.따라서 위의 질문 1을 묻는 더 좋은 방법은 "(있는 경우) 이 작업을 호출하는 정당성은 무엇입니까?"입니다. $O(1)$?실용적이기 때문에?전통적인?RAM 모델에 의해 암시됩니까?

Answer 1

TL; DR :이 유형의 동작을 $ o (1) $ 으로서 파이썬을 위해 극단적 인 경우가 해제되는 경우. 이러한 경우는 매우 드물게 $ o (1) $ 의 규칙과 부서지기 위해 부정적인 유틸리티가 있습니다. 이런 종류의 실용주의는 빅 $ o $

에서 정상적인 것입니다.

이 질문에 많은 답변이 많이 있습니다. 나는 그들을 읽는 것을 권장합니다. 그러나 나는 그들 중 하나가 내 질문에 완전히 대답하지 않는다고 생각하지 않습니다. 그래서 여기 합성이 있습니다.

이게 정확합니까? 나는 다른 사람이 로그 시간에 ints를 비교한다고 주장하는 다른 사람을 보지 못했습니다.

이것은 놀라 울 정도로 뉘앙스가 있습니다. 파이썬이 $ o (\ log n) $ 런타임에서 매우 큰 int를 비교하는 것은 true 입니다. 그러나 $ o (\ log n) $

로이 작업을 설명하는 정확한 이 정확합니다.

궁극적으로 이것은 @tomvanderzanden 에서이 테이크에서 가장 설득됩니다 :

C 또는 Python 버전이 $ o (1) $ 모든 면접관은 완벽하게 행복해야합니다. 당신이 그것이 (python 버전) $ o (\ log n) $ 은 아마도 행복 할 것입니다. 그러나 당신은 오히려 긍정적 인 사람이라고 생각합니다.  정상적인 규칙을 따르십시오.

및

인터뷰 자 였으면 적절한 경우에만 해당하는 경우에만 이론적 인 우려 사항을 알고있는 것의 실제 세계의 한계를 알고 있는지를 신경 쓸 것입니다.

그러나 첫 번째 단락이 현재 오도 된 것으로 생각하기 때문에 그런 것을 받아들이지 않습니다.

궁극적 으로이 논쟁은 실용적입니다. 큰 $ o $ 파이썬 int 비교는 여전히 $ o (\ log n) $ . 그러나 그런 식으로 취급하는 것이 유용하지 않습니다. 그래서 당신은해서는 안됩니다. 나는 그것이 큰 $ o $ 에 대한 엄격한 것으로 추가 할 것입니다. $ o $ 분석.

Answer 2

정수는 바이너리 문자열이며 평등을 결정하기 위해 두 언어는 문자열 비트를 비트를 비교합니다.

아니야. C ints는 기계 - 단어 크기이며 단일 기계 명령어와 비교됩니다. Python ints는 기본 $ 2 ^ {30} $ (예 : https://rushter.com/blog/python-integer-implementation/ ) 및 비교 해당베이스의 숫자를 비교했습니다. 따라서 로그의 관련 기초는 $ 2 ^ {30} $

입니다. 숫자의 은 $ 2 ^ {30d} $ 에 의해 에 의해 에 의해 경계 될 수 있다면 $ D $ 비교는 $ o (1) $ (자리 수가 비교되기 때문에 ), 그리고 그들이 할 수없는 경우 다른 운영은 평등 비교보다 훨씬 더 중요 할 것입니다. 그래서 실제로 나는 그것이 중요하지 않을 것이라고 말하고, 당신이 알고있는 경우 (그리고 ints를 사용하지만 "noreferrer"> GNU 다중 정밀 산술 라이브러리 C라도).

Answer 3

복잡성은 계산 모델에 비해 정의됩니다.P 및 NP는 예를 들어 튜링 머신의 관점에서 정의됩니다.

비교를 위해 Word RAM 모델을 고려하십시오.이 모델에서는 메모리가 단어로 나뉩니다. 단어는 일정한 시간으로 액세스 할 수 있으며 $ o (1) $ 단어를 사용하여 문제의 크기를 표현할 수 있습니다.

예를 들어, 비교 기반 정렬 작업을 분석 할 때 $ n $ 은 $ o (1) $ 단어이므로 $ 1 $ 와 $ n $ .

Answer 4

이 올바른지?나는 Python이 로그 시간에 int를 비교한다고 주장하는 사람을 본 적이 없습니다.

아니요(약간 그렇습니다).다음과 같은 시사점을 주는(그러나 실제로는 사실이 아닌) 주장을 고려해 보십시오.컴퓨터는 유한한 양의 메모리만 가질 수 있으므로(우주의 원자 수에 따라 제한됨) Python 버전도 $O(1)$.

문제는 우리가 유한 상태 기계(컴퓨터)에 대한 점근론(무한대에서 일어나는 일과 관련된)에 대해 설명하려고 한다는 것입니다.코드의 복잡성을 분석할 때 컴퓨터에서 실행되는 코드 자체를 실제로 분석하는 것이 아니라 이상적인 코드 모델을 분석하는 것입니다.

내가 당신에게 C로 작성된 정렬 알고리즘을 분석하라고 요청했다고 가정해보자.int를 사용하여 배열을 인덱싱한다고 명시할 수 있으므로 최대 크기의 배열만 정렬할 수 있습니다. $2^{31}-1$.그러나 그러한 코드 조각을 분석할 때 우리는 그것이 임의로 큰 배열을 처리할 수 있다고 가정합니다.분명히 C 정수 비교가 다음과 같다고 말하는 것은 아닙니다. $O(1)$ 왜냐하면 32비트 숫자만 처리할 수 있습니다.

인터뷰를 진행하는 과정에서 후보자가 O(1)이라고 부르는지 주의해야 합니까?

일반적으로 그렇지 않습니다.내가 인터뷰를 진행하면서 직원 데이터베이스에 나타나는 여성 직원의 수를 세는 C 또는 Python 컴퓨터 프로그램을 작성하라고 요청한다고 가정해 보겠습니다.

그럴 것이다 엄청나게 내가 당신의 C 프로그램이 올바르지 않다고 불평한다면 현학적이다. $2^{31}-1$.

우리는 일반적으로 숫자가 한 단어/정수 내에 들어갈 수 있을 만큼 충분히 작다고 가정합니다.우리는 덧셈(또는 다른 숫자 연산)이 다음에서 수행될 수 있다고 가정합니다. $O(1)$, 왜냐면 글을 써야 한다는 건 매우 짜증나는 일이니까요 $O(\로그n)$ 모든 곳에서 그렇게 하면 모든 것을 읽을 수 없게 됩니다. $\logn$ 너무 작아서 어쨌든 상관 없습니다.

C 또는 Python 버전이 다음과 같다고 말하면 $O(1)$ 어떤 면접관이라도 완벽하게 행복할 것입니다.당신이 (Python 버전) 말했다면 $O(\로그n)$ 그들은 아마도 여전히 행복할 것이지만 당신이 일반적인 관습을 따르지 않는 다소 현학적인 사람이라고 생각합니다.

현실 세계에서 이러한 차이를 주목해야 할까요? 아니면 관심을 가져야 할까요?

예!숫자가 너무 커지면 숫자가 작다는 가정이 위반되는 것이 중요해지기 시작합니다.당신이 Google과의 인터뷰를 하고 있으며 그들이 작년에 여성 사용자가 수행한 검색어 수를 계산해 달라고 요청했다고 가정해 보겠습니다.int를 사용하여 C 프로그램을 작성했다면 면접관이 불평하는 것이 정당할 것입니다.

long을 사용하도록 전환하고 여전히 호출하는 것이 정당할 수 있습니다. $O(1)$, 마찬가지로 Python 버전을 호출합니다. $O(1)$ 또한 정당화됩니다.그만큼 $O(1)$ 대 $O(\로그n)$ 숫자가 매우 길어질 때만 문제가 시작됩니다.예를 들어, 당신의 작업이 다음의 숫자를 계산하는 프로그램을 작성하는 것이라면 $\pi$ 또는 이와 유사한 작업.이 작업을 위해 Python 프로그램을 작성하고 질문을 받았을 때 복잡성의 특징을 언급하지 않았다면 면접관은 관심을 가질 것입니다.

내가 면접관이라면 당신이 하고 있는 일의 실제 한계를 알고 있는지, 언제 어떤 이론적 우려가 중요한지, 적절한 경우에만 문제를 제기하는지 관심을 가질 것입니다.

언제 신경써야 할까요?

지금까지 나는 "큰" 숫자와 "작은" 숫자에 대해 다소 모호했습니다.일반적으로 사용되는 RAM 모델에서는 정수 연산이 다음과 같이 수행될 수 있다고 가정할 수 있습니다. $O(1)$ 최대 숫자에 대해 $O(\로그n)$ 비트(여기서 $n$ 입력 길이입니다.)이 가정에 대한 정당성은 길이 입력이 있는 경우 $n$, 프로그래밍 언어의 포인터/인덱스는 전체 입력 공간을 처리할 수 있을 만큼 길어야 합니다.따라서 RAM 모델에서 입력이 이진수인 경우 $n$ (이진) 숫자, 동등성을 확인하는 복잡성은 $O(\frac{n}{\log n})$ 왜냐하면 우리는 한 그룹의 동등성을 확인할 수 있기 때문입니다. $O(\로그n)$ 비트를 하나로 $O(1)$ 작업.

Answer 5

이것이 사소한 점처럼 보일 수도 있지만 첫 번째 문장이 올바르지 않습니다. 기능이 동일하지 않습니다..이를 동등하게 만들기 위해 C 함수는 GMP(또는 이와 유사한 것)를 사용하여 임의 정밀도 산술을 구현해야 합니다.이제, 이 관찰이 사소하지 않은 이유는 둘이 동일하다고 말하는 것이 합리적인 정도가 바로 Python 코드가 상수 시간이라고 말하는 것이 합리적인 정도이기 때문입니다!즉, Python의 정수가 큰 숫자라는 점을 무시한다면 이를 고정된 크기로 일관되게 처리할 수 있고 처리해야 합니다.

마찬가지로 C 함수를 고려해보세요. int is_equal(char a, char b) { return a == b; } 그리고 파이썬 함수 def is_equal(a: str, b: str) -> bool: return a == b.이제 기능이 동일하지 않다는 것이 더 분명해졌지만 그 이유는 귀하의 기능이 동일하지 않은 이유와 정확히 동일합니다.우리는 항상 Python에서 대규모 문자열을 볼 것으로 예상하지만, 물론 그것이 가능하다는 것을 알고 있음에도 불구하고 실제로 대규모 정수를 기대하지는 않습니다.그래서 대부분의 경우 우리는 Python의 정수가 크다는 사실을 무시하고 마치 고정된 크기인 것처럼 분석합니다.우리가 bignum 작업의 타이밍을 고려하는 드문 경우에는 "실제" 복잡성을 사용할 수 있습니다.물론 C 코드에도 GMP를 사용하세요.

이 모든 말은 다음과 같습니다.비록 당신이 그것을 깨닫지는 못했지만, 당신은 이미 마지막에 질문의 다시 언급된 버전에 대한 답을 알고 있으며, 대답은 "해당 기능을 동등하다고 설명하는 것과 동일한 정당성"입니다.Python은 고정 크기 정수 유형이 없다는 점에서 특이합니다(글쎄, 사람들이 일반적으로 사용하는 유형은 아닙니다:물론 하나를 쓸 수도 있고, 거기에 하나도 있어요 numpy).그러나 실용주의의 문제로, 이것이 정수를 처리하는 알고리즘의 "일반적인" 복잡성 분석을 수행하고 "일반적인" 답변을 얻는 것을 방해하는 것을 원하지 않습니다.거의 동일한 10GB 정수 두 개를 전달하면 비교하는 데 약간의 시간이 걸릴 수 있다는 경고를 제공할 필요가 거의 없습니다.

어떤 경우에는 분석을 작은 정수로 제한한다고 말함으로써 이를 공식화할 수 있습니다(정말 필요한 경우).그런 다음 모든 산술 연산을 O(1)로 처리하여 일부 정수 배열의 크기 측면에서 일부 알고리즘의 복잡성을 고려할 수 있습니다.실제로 선형이거나 정수의 크기가 더 나쁜 알고리즘을 고려하는 경우 로그 요소를 무시하겠다고 공식화할 수 있습니다. 왜냐하면 실제로 관심을 갖는 것은 복잡성이 다음과 같은지 여부뿐이기 때문입니다. 선형 또는 이차형입니다. 왜냐하면 O(n log n)은 귀하의 목적에 선형만큼 좋기 때문입니다.하지만 거의 항상 알고리즘의 복잡성을 공식화할 필요는 없습니다. 파이썬에서.프로그래밍 언어를 지정하는 지점에 도달했다면 더 이상 추상적인 컴퓨터 과학을 하고 있지 않은 것입니다 ;-)

인터뷰 수행의 맥락에서, 후보자가 이것을 전화하는지 알거나주의를 기울여야합니다. $O(1)$?

인터뷰에 따라 다르지만, 지난 10년 동안 주로 Python으로 작업한 소프트웨어 전문가로서 저는 인터뷰에서 그런 질문을 하지 않을 것입니다.내부에 정수 비교의 복잡성이 숨겨져 있는 질문(예: "이 정렬 알고리즘의 복잡성은 무엇입니까?")을 묻는 경우 전체 문제를 무시한 답변을 수락합니다.나는 또한 그것을 다루는 것을 받아들일 것입니다.나는 실용적인 프로그래밍의 일부로서 복잡성을 이해하고 계산할 가치가 있다고 생각하지만 그다지 중요하다고 생각하지 않습니다. 프로그래밍을 위해 합리적인 크기의 정수에 대해 이야기하고 있다고 공식적으로 언급하는 것은 매우 조심해야 합니다.

나는 또한 어떤 이유로 관련 데이터와 관련하여 질문과 분명히 관련이 없는 경우, Python 정수가 임의 정밀도라는 정보를 후보자에게 제공하기를 원하는 질문을 결코 묻지 않을 것입니다.질문에서 관련된 숫자가 2보다 높아질 수 있음을 암시하는 경우⁶⁴ 그런 다음 C 인터뷰에서는 후보자가 이것이 처리해야 할 문제라는 것을 알아차리기를 원하고 Python 인터뷰에서는 후보자가 그렇지 않다는 것을 알기를 원하지만 기대하지는 않습니다. 그것을 진술하기 위해 최선을 다합니다.인터뷰에서 무언가를 문제가 되지 않게 만드는 모든 작은 사실을 진술할 시간은 없습니다.

인터뷰에서 복잡성에 대한 이해를 확인하고 싶다면 복잡성이 낮고 매우 간단한 "순진한" 솔루션이 있는 문제에 대한 일부 코드를 요청하는 것부터 시작할 가능성이 높으며, 상당히 복잡하지만 덜 간단한 솔루션이 하나 이상 있습니다. 잘 알려진 기술을 사용합니다.후보자가 순진한 솔루션을 제안하는 경우 복잡성이 무엇인지, 이를 개선하기 위해 코드를 어떻게 수정하는지 물어볼 수 있습니다.후보자가 더 나은 솔루션을 제안하는 경우 순진한 솔루션을 설명하고 코드 줄이 몇 줄인지 지적한 다음 무엇이 문제인지 물어볼 수 있습니다. 그것에 대해 말해줄래?"대부분의 실제 목적에서 관심 있는 것은 선형, 2차, 2차보다 나쁜 것의 차이를 구분할 수 있는지 여부입니다.O(n log n)도 나타나지만 주로 비교 횟수 측면에서 복잡성을 말하는 정렬 또는 데이터 구조 때문입니다.각 비교 비용은 일반적으로 알고리즘 설계자가 이를 제어할 수 없기 때문에(알고리즘 또는 데이터 구조 사용자가 제공) 관련성이 없는 것으로 간주됩니다.

제가 임의 정밀도 산술을 다루는 CS 학자 자리의 면접관이었던 놀랍게도 가능성이 낮은 사건에서 저는 분명히 지원자들이 다양한 연산에 대한 다양한 알고리즘의 복잡성을 알고 실제로 기술의 상태를 알기를 원할 것입니다. 사소하지 않은 것.

Answer 6

이 올바른지?나는 Python이 로그 시간에 int를 비교한다고 주장하는 사람을 본 적이 없습니다.Python에는 실제로 임의의 정밀도 정수 형식이 있습니다.그러나 여기서는 공정한 비교를 해야 합니다.경계에 있는 정수의 부분 집합을 고려하면 $[0,2^{64}]$, 우리는 Python 연산이 상수 시간임을 알 수 있습니다.

당신이 보고 있는 것은 빅오 표기법을 사용하여 계산 복잡성을 측정하는 데 있어 한계 중 하나입니다.이는 n이 무한대에 접근할 때 어떤 일이 발생하는지 설명하지만 더 작은 숫자에 대한 동작을 비교하는 데 반드시 좋은 작업을 수행하는 것은 아닙니다.우리는 이것을 유명하게 봅니다. 행렬 곱셈 알고리즘.큰 의미에서 더 효율적인 일부 알고리즘이 있지만 실제로는 거대한 행렬에 도달할 때까지 실제로 더 느립니다.

인터뷰를 진행하는 과정에서 후보자가 O(1)이라고 부르는지 주의해야 합니까?

당신이 그들을 고용하는 이유에 따라 다릅니다.대부분의 작업에서는 O(1)이라고 부르는 것이 좋습니다.실제로 우리는 학교에서 그것을 가르치는 경향이 있습니다.후보자에 대해 배울 수 있는 유용한 기회로 바꾸고 싶다면 왜 덧셈이 일정한 시간이라고 생각하는지 물어볼 수 있습니다. 이에 대한 대답은 빅오를 결정하는 데 사용한 모델이 그것을 가정했다는 것입니다.유효한 답변입니다)

코드에서 익스플로잇과 같은 것을 찾기 위해 누군가를 고용하는 경우 더 나아가고 싶을 수도 있습니다.자신의 코드로 생성된 빅넘도 하나인데, 사용자가 자신이 선택한 숫자를 입력해도 되나요?그렇다면 그들은 이 추가가 매우 느릴 수 있다는 사실을 이용하여 타이밍 공격과 DOS를 생성할 수 있습니다.이러한 위험을 감지하는 것이 업무의 일부일 수 있습니다.

현실 세계에서 이러한 차이를 주목해야 할까요? 아니면 관심을 가져야 할까요?

실제로 말하면:아니요.실제로 문제가 발생하고 디버그에서 문제를 해결하기 전까지는 아닙니다.파이썬은 많은 "일반적으로 안전"하고 매우 효율적인 것입니다.이것이 바로 이 언어가 세계에서 가장 인기 있는 언어 중 하나로 자리매김한 이유입니다.

동등한 상황의 경우:얼마나 빠른지 x.y 파이썬에서?우리는 그것을 O(1)로 생각하지만 실제로는 해시 조회가 있습니다.해당 해시 조회는 알려진 검색 메커니즘을 사용하며 결과 조회는 실제로 O(n)입니다.일반 코드에서는 이 내용을 볼 수 없습니다.그러나 적이 자신의 콘텐츠로 사전을 채우는 코드에서는 이러한 방식으로 충돌하는 키를 의도적으로 만들 수 있습니다.

Answer 7

필자는 "정기적 인"정수 작업을 일정한 시간 외에 "규칙적인 크기가 합리적인 유한 상한 (예를 들어 64 비트)이 있음을 암묵적으로 가정하여 치료 한 텍스트를 결코 마주 쳤습니다.아마도 가정을 진술하는 것이 더 정확할 것입니다. 그러나 CS 청중은 그것이 암시 적이라고 생각합니다.

본질적으로 관련이없는 주제의 토론에 많은 복잡성을 도입 할 것입니다.BigInt 구현은 일반적으로 비트별로 구현되지 않고 기본 - (기계 단어 크기)에서는 O (b)> o (1) 문제가 멋지게 큰 숫자를 위해 걷어차집니다.

개인적으로 누군가를 인터뷰하면서 파이썬 정수를 아는 것과 관련된 지식의 엄격함과 폭이 임의의 길이 였지만 모든 수학이 o (1)가 o (1)가 o (1)가 극도로 나타납니다.분석이 산술로 너무 멀리 떨어져 있고 시간을 낭비하는 것으로 시작되면이 나쁜 후보자를 고려할 것입니다.