整数が等しいかどうかを確認する: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(\log a)$ どこ $a$ 10 進数の入力値です。

したがって、Python でコードを分析している場合、2 つの整数を比較するたびに、驚くほど複雑な作業を開始することになります。 $O(\log n)$ いずれかの数値の 10 進数の値に関して。

私にとって、これはいくつかの疑問を引き起こします。

1. これは正しいです？Python がログ時間で int を比較すると主張している人を他に見たことがありません。
2. 面接の実施中、候補者がこのような電話をかけてきた場合に気づきますか、または気にしますか? $O(1)$?
3. 現実世界でこの違いに気づくべきでしょうか、それとも気にするべきでしょうか?

編集：Python が一定時間内に任意の大きな int を比較できないことは簡単に検証できます (そして直観的に)。したがって、上記の質問 1 を尋ねるより良い方法は、「このオペレーションを呼び出す正当な理由 (ある場合) は何ですか?」です。 $O(1)$?プラグマティックだから？従来の？RAM モデルによって暗示されますか?

Answer 1

tl; DR：Pythonの極端な場合に断続する $ o（1）$ としてこのタイプの操作を説明するというCS規則があります。これらのケースは非常に reamで、 $ o（1）$ の条約と壊れるように除去されています。この種のプラグマティズムは、大きい $ o $ では正常です。

この質問に非常に良い回答がたくさんあり、私はあなたにそれらを読むことを勧めます。しかし、私は彼らのうちの誰かが私の質問に完全に答えるとは思わない。だからここに合成があります。

これは正しいですか？ Pythonがログタイムでintsを比較していると主張していません。

これは驚くほど微妙です。 Pythonは $ o（\ log n）$ ランタイムで非常に大きなintを比較することは true です。しかし、この操作を $ o（\ log n）$ として記述するための訂正です。

最終的にはこれが@Tomvanderzandenから最も説得されています：

CまたはPythonのバージョンが $ o（1）$ であると言った場合、任意のインタビュアーは完全に幸せになるはずです。あなたが言ったなら（Python版） $ o（\ log n）$ 彼らはおそらく幸せになるでしょう、しかしあなたがしないかなり小説の人だと思いますt通常の規則に従ってください。

と

私がインタビュアーだったら、あなたがしていることの実世界の制限を知っていて、必要な場合にのみそれらを持ってくるのか、そしてあなたが適切な場合にのみそれらを上げているのかを知っているかどうかを知っているかどうかを気にかけます。

しかし私は最初の段落が現在誤解を招くようだと思うので、答えとしてそれを受け入れていません（変化が満足しています）。

最終的にこの引数は実用的です。 big $ o $ の厳密な定義によって、Python int比較はまだ検証可能です $ o（\ log n）$ 。しかし、それを扱うのは役に立ちません。大きな $ O $ について厳密になるように追加します.big $ o $ のポイントを見逃すことです。分析。

Answer 2

整数は単なるバイナリ文字列であり、平等を判断するために、両方の言語は文字列をビットごとに比較します。

全くない。 C intはマシンワードサイズで、単一のマシン命令と比較されます。 Python intsは、base $ 2 ^ {30} $ で表されます（例： https://rushter.com/blog/python-integer-implementation / を比較した。したがって、対数の関連ベースは $ 2 ^ {30} $ です。

の場合、 for fixed for の場合、の数が $ 2 ^ {30d} $ によって制限されることができます $ d $ 、比較は $ o（1）$ です（最初に数字を比較するため）、そしてできない場合は、他の操作は等価比較よりもはるかに懸念がある可能性があります。だから実際にはそれが問題になることは非常にありそうもないと言うでしょう（そしてそれが知っているのであれば（そしてhref="https://gmplib.org" real="noreferrer">のようなものではなく）あなたは知っていると言うでしょう。 CのGNU多重精度算術ライブラリー。

Answer 3

複雑度は計算モデルに対して定義されています。PおよびNPは、例えば、チューニングマシンに関して定義されている。

比較のために、Word RAMモデルを考慮してください。このモデルでは、メモリは単語に分割されます。単語は一定にアクセスでき、問題のサイズは $ o（1）$ 単語を使用して表すことができます。

だから、比較ベースのソート操作を分析するときは、 $ n $ の数が $ O（1）$ ワードなど、 $ 1 $ と $ n $ 。

Answer 4

これは正しいですか？ Pythonがログタイムでintsを比較していると主張していません。

いいえ（そして少しはい）。次の考えを誘発する（しかし実際には本当ではない）請求項を検討してください：コンピュータは、有限量のメモリ（ユニバース内の原子数によって制限されています）のみ、Pythonバージョンも $ o（1）$ 。

問題は、有限状態機械（コンピュータ）について、漸近治療法についての声明を（無限大で何が起こるかに関連している）についての声明をしようとしていることです。コードの複雑さを分析しているときは、コンピュータ上で実行されるため、実際にコード自体を分析していません。

C.に書かれたソートアルゴリズムを分析するように依頼したとします。intsを使用して配列を索引付けすることができるので、 $ 2のサイズの配列を並べ替えることができます。 ^ {31} -1 $ 。それでも、このようなコードを分析すると、任意の大きなアレイを処理できるふりをします。明らかに、C整数比較は $ o（1）$ ではありません。は32ビット数のみを処理できます。

インタビューを実施するという文脈では、候補者がこのO（1）を呼び出す場合に気にかけたり気にしたりする必要がありますか？

通常はそうではありません。私がインタビューを行っているとし、従業員データベースに現れる女性の従業員の数を数えるCまたはPythonのコンピュータプログラムを書くように依頼します。

になるだろう Peditint In Prodrentが正しくない場合は、 $ 2 ^ {31} -1 $ 。

一般的に、数字が1ワード/整数に収まるように数字が小さいと仮定します。 $ o（1）$ で行うことができます。 $ \ log n $ であっても、math-container "> $ o（\ log n）$ 、それはすべてを読み取り不可能にするだけです。とにかく本当に関係ありません。

CまたはPythonのバージョンが $ o（1）$ であると言った場合、任意のインタビュアーは完全に幸せになるはずです。あなたが言ったなら（Python版） $ o（\ log n）$ 彼らはおそらく幸せになるでしょう、しかしあなたがしないかなり小説の人だと思いますt通常の規則に従ってください。

現実の世界でこの区別を気付いたり気にかけたりしてください。

はい！数字が大きくなると、それらが小さい仮定が違反しているときに問題が発生し始めます。あなたがグーグルにインタビューしているとしましょうそして彼らはあなたに過去1年間で女性ユーザーによって行われた検索クエリの数を計算するように頼みました。インタビュアーは、intsを使用してCプログラムを書いた場合に不平を言うことが正当化されます。

Longsを使って切り替えることができ、それでも $ o（1）$ 、そして同様に、Pythonバージョン $ o（1）$ も正当化されています。 $ o（1）$ v.s. $ o（\ log n）$ は、数字が非常に長くなったときにのみ起動します。たとえば、タスクが $ \ pi $ の桁を計算するプログラムを書くことである場合。このタスクのためにPythonプログラムを書いた場合、尋ねられたときに複雑さの特殊性を言及しなかった場合、インタビュアーは気にします。

私がインタビュアーだったら、あなたがしていることの実世界の制限を知っていて、必要な場合にのみそれらを持ってくるのか、そしてあなたが適切な場合にのみそれらを上げているのかを知っているかどうかを知っているかどうかを気にかけます。

あなたはいつ気にしていればいいですか？

これまでのところ、私は「大きい」と「小」の数について少し曖昧でした。一般的に使用されるRAMモデルでは、 $ o（1）$ で行うことができると仮定することができます。 "math-container"> $ O（\ log n）$ bits（ $ n $ は入力の長さです）。この仮定の正当化は、長さ $ n $ の入力を持っている場合、私たちのプログラミング言語のポインタ/インデックスはアドレスに対処できるのに十分な長さになる必要があります。入力スペース全体したがって、RAMモデルでは、入力が2進数の $ n $ （バイナリ）桁の数字の数字の数字では、平等をチェックする複雑さは $ O（\ frac {n} {\ log n}）$ $ o（\ log n）$ <$ << / SPAN> 1つの $ o（1）$ 操作。

Answer 5

これは些細な点のように見えるかもしれませんが、あなたの最初の文は正しくありません。 関数は等価ではありません。それらを同等にするために、C関数は警戒精度演算を実装するためにGMP（または類似）を使用する必要があります。今、この観察が些細ではない理由は、2つが同等であると妥当な範囲は、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で大規模な文字列を常に見ることを期待していますが、もちろん、私たちは可能であることを知っていますが、本当に大規模なintsを期待していません。だから、ほとんどの場合、Pythonの整数が大きいという事実を無視して、それらが固定サイズであるかのように分析します。 Bignum Operationsのタイミングを気にかけているまれな場合は、「本物の」複雑さを使用できます。そしてもちろん、CコードでGMPを使用しています。

これはすべて言うことができます。 "。 Pythonは固定サイズの整数型を持たないのは珍しいです（まあ、人々が一般的に使用するものではありません。もちろん、それを書くことは可能です）。しかし、実用主義の問題としては、整数をクランチするアルゴリズムの複雑さ分析を行い、「通常の」回答を得ることを防ぐことを望んでいません。ほぼ等しい数の10GBの整数を渡すと、それらを比較するのに少しかかるかもしれません。

場合によっては、分析を小さな整数に制限していると言って、これを正式にすることができます（本当に必要な場合）。次に、いくつかの整数の配列のサイズに関していくつかのアルゴリズムの複雑さを考慮して、すべての算術演算をO（1）として処理します。あなたが本当に線形または整数の大きさでより悪いアルゴリズムを検討しているなら、あなたは本当に気にかけているのは複雑さがより近いかどうかということなので、あなたはあなたがログファクタを無視することを言うことによってそれを形式化することができます。 O（n log n）はあなたの目的のために線形と同じくらい良いものであるため、線形または二次的です。ただし、ほぼ常に、Python でアルゴリズムの複雑さを正式にする必要はありません。プログラミング言語を指定するという点に到達した場合は、抽象的なコンピュータサイエンスをもう実行していません。 - ）

インタビューを実施するという文脈では、気にしたり気にしたりしてください。 候補者がこの $ o（1）$ を呼び出す場合は？

は、私が想定しているのに対してインタビューに依存していますが、過去10年間Pythonで働いているソフトウェアプロフェッショナルとして、インタビューではそれを尋ねないでしょう。 IT整数比較の複雑さを有する質問をした場合（私はDunno、「このソートアルゴリズムの複雑さは何ですか？」）、その後、問題全体を無視した答えを受け入れます。私はそれを扱ったものも受け入れたいです。私はそれが実用的なプログラミングの一環として理解しそして計算する価値があると思います、私はあなたが合理的にサイズについて話していることを正式に述べるために非常に注意を払うことをそれを考えることはできません。整数

私はまた、候補者にPython整数が恣意的に正確であるという情報を提供したいという質問をすることはありません。質問が含まれている数字が2 ^{64 より高いことを意味する場合、Cインタビューでは、これが彼らが対処する必要がある問題であり、Pythonインタビューでは候補者が気付いてほしいと思います。候補者がそうではないことを知ってほしいのですが、私は彼らがそれを述べるように彼らの方法から外れるとは思わないでしょう。何かが問題ないことをするすべてのほとんどの事実を述べるための面接には時間がない。}

インタビューの複雑さの理解をチェックしたい場合は、ほとんどの場合、複雑さが悪い本当に簡単な「ナイーブ」ソリューションがある場合にいくつかの問題を求めて、少なくとも1つの直接的な解決策があると思います。よく知られた技術を用いたまともな複雑さを有する。候補者が素朴なソリューションを提供している場合は、複雑さが何であるか、そしてそれを改善するためにコードをどのように変更するかを尋ねることができます。候補者がより良いソリューションを提供している場合、あなたはナイーブソリューションを記述することができ、それがどのように数行のコードであるかを指摘し、それが何が問題になっているのか（おそらく尋ねることで、誰かを見直していた場合）を指摘することができます。

'Sコードと彼らはこれを与えました、あなたはそれについて何について言いますか。n）は、比較数の観点から複雑さについて話すソートやデータ構造のためにも現れます。アルゴリズムデザイナは通常それを制御していないため、各比較のコストは無関係であると考えられます（それはアルゴリズムまたはデータ構造のユーザーによって提供されます。

驚くべきことに、私が恣意的精度の算術をカバーするCS学術としての地位のインタビュアーであることから、確かに私は候補者がさまざまな業務のためのさまざまなアルゴリズムの複雑さを知ることを求めて、そして確かにの状態を知るようになるでしょう。独立していないもののための技術。

Answer 6

これは正しいです？Python がログ時間で int を比較すると主張している人を他に見たことがありません。確かに、Python には任意精度の整数形式があります。ただし、ここでは公正な比較を行う必要があります。境界上の整数のサブセットを考慮すると、 $[0,2^{64}]$, とすると、Python の演算は定数時間であることがわかります。

あなたが見ているのは、big-oh 表記法を使用して計算の複雑さを測定する際の限界の 1 つです。これは、n が無限大に近づくと何が起こるかを説明しますが、より小さい数の動作を比較するのに必ずしも適切に機能するとは限りません。これは有名なところで見られます 行列乗算アルゴリズム. 。大きな意味ではより効率的でも、実際には巨大な行列に到達するまでは遅くなるアルゴリズムがいくつかあります。

面接を行う場合、候補者がこれを O(1) と呼ぶかどうかに注意する必要がありますか?

何のために彼らを雇用しているかによって異なります。ほとんどのジョブでは、O(1) と呼ぶのが問題ありません。実際、私たちは学校でそれを教える傾向があります。これを候補者について学ぶ有益な機会にしたい場合は、なぜ足し算が定数だと考えるのかを尋ねるとよいでしょう (答えは、ビッグオーを決定するために使用したモデルがそれを想定しているからです...それは有効な答えです）

コード内のエクスプロイトなどを探すために誰かを雇っている場合は、さらに作業を進めたくなるかもしれません。独自のコードで生成された bignum は別のことですが、ユーザーは自分で選択した数値を入力することができますか?そうであれば、この追加が非常に遅いという事実を利用して、タイミング攻撃や DOS を作成できる可能性があります。このリスクを検出することも彼らの仕事の一部かもしれません。

現実世界でこの違いに気づくべきでしょうか、それとも気にするべきでしょうか?

実際的に言えば:いいえ。実際に問題に遭遇し、デバッグで問題を修正するまでは。Python は次のことを行います 多く 「一般的に安全」で非常に効率的なもの。これが、世界で最も人気のある言語の 1 つとして定着した理由です。

同等の状況の場合:どのくらい速いですか x.y Pythonで？私たちはそれを O(1) と考えていますが、実際にはそこにハッシュ ルックアップがあります。このハッシュ ルックアップでは既知のプローブ メカニズムが使用されており、結果のルックアップは実際には O(n) になります。通常のコードではこれを見ることはありません。しかし、攻撃者が独自のコンテンツを辞書に埋め込むコードでは、このように衝突するキーを意図的に作成することができます。

Answer 7

私は、サイズが妥当な有限上限（例えば64ビット）を持ち、絶え間ない仮定を絶えず扱った「通常の」整数操作を扱ったテキストに遭遇しました。おそらくそれは仮定を述べるのがより正確になるでしょうが、CSの聴衆にとって、私はそれが暗黙のうと思います。

は、本質的に無関係なトピックの議論に多くの複雑さを紹介します。BigINT実装は通常、ビットごとに実装されていませんが、Base（Machine Word Size）では、O（B）> O（1）問題はFubulualyに大きな数のためにキックでキックをキックします。

個人的に誰かにインタビューしながら、Python整数を知ることに関連する知識の厳しさと幅を認識するかもしれませんが、すべての数学がO（1）であるという仮定を述べることを超えたものは非常に小児を感じるでしょう。分析が算術演算であまりにもずっと離れて時間を浪費し始めた場合は、これが悪い候補者を検討します。