あなたのComputer Science Degreeは嘘である

Computer Science教育の基本的な柱であるbinary searchは、探索アルゴリズムの議論の余地のない王者として君臨しています。あらゆる入門コースやデータ構造の教科書がその優雅さと効率性を称賛し、ソートされた配列内で要素を見つけるための最適な方法として提示しています。開発者の精神に深く根付いたこのアルゴリズムは、探索パフォーマンスの理論的な頂点を表しています。

その理論的な完璧さは否定できず、羨望の的であるO(log N)の計算量（time complexity）を誇ります。アルゴリズム解析の基礎であるこのBig O notationは、探索を完了するのに必要な時間が入力（N）のサイズに対して対数的にしか増加しないことを意味します。これにより、binary searchは効率性のゴールドスタンダードとなり、膨大なデータセットであっても超高速なパフォーマンスを予測させます。しかし、その根底にある仮定は、すべてのメモリアクセスが同じコストであるというものであり、これはその数学的モデルに深く組み込まれた前提です。

しかし、これほどまでに綿密に教えられ、広く受け入れられてきたこの基礎理論が、現実世界のハードウェアという試練の中で揺らぐとしたらどうでしょうか？Computer scientistのProfessor Daniel Lemireは最近、現代のプロセッサでは、標準的なbinary searchが莫大なパフォーマンスを置き去りにしていることを証明するベンチマークを発表しました。この発見は、そのBig O complexityが自動的に優れた実用速度に変換されるという考えに直接異議を唱えるものです。

ボトルネックは、古典的な理論が示唆するように比較の数ではありません。代わりに、memory latencyが真のパフォーマンス阻害要因として浮上します。binary search中にコンピュータが大きな配列の中央にジャンプすると、CPUは何百サイクルも頻繁に停止します。この遅延は、RAMからのキャッシュミスが解決されるのを待つ間に発生し、O(log N)によって約束された理論的な利益を根本的に損ないます。

この重要な洞察は、私たちが学校で学んだパフォーマンス指標が、現代のコンピュータアーキテクチャ上での実際の実行とは大きく異なることが多いことを明らかにしています。すべてのメモリ操作を等しく扱う従来のモデルは、現代のメモリシステムの階層的な性質や、非連続的なデータアクセスに伴うペナルティを考慮していません。

このパラダイムシフトは、ハードウェアが高速化された世界で「パフォーマンス」が真に何を意味するのかを再評価することを強います。アルゴリズム効率に対する私たちの理解は、抽象的な数学的予測を超えて、基盤となるcomputerアーキテクチャが*実際に*どのように動作するかを統合しなければなりません。準備してください。最適な探索の定義は変わろうとしており、純粋な比較回数よりもハードウェアの並列性を優先する新しい戦略を示唆しています。

対数的な比較回数で長らく称賛されてきたbinary searchの理論的効率性は、現代のプロセッサでは崩壊します。実際のパフォーマンスボトルネックは、CPUが実行する比較の数ではなく、むしろそれらの比較を実行するためのデータの苦痛な待ち時間です。ハードウェアアーキテクチャにおけるこの根本的な変化は、均一なメモリアクセスコストを仮定するBig O notationを、現実世界のパフォーマンスにとって誤解を招く指標にしてしまいます。

現代のCPUは驚異的な速度で動作し、しばしば1秒あたり数十億の命令を実行します。しかし、その生の処理能力は、データを迅速にアクセスする能力をしばしば上回ります。決定的な原因はmemory latencyであり、CPUがすぐに利用できないデータを要求したときに発生する固有の遅延です。プロセッサが超高速のローカルキャッシュに存在しない情報を必要とすると、CPU stallが発生し、はるかに低速なメインメモリ（RAM）からフェッチしている間、数百サイクルアイドル状態になります。

ミシュランの星を獲得したシェフが複雑な料理を作っていると想像してください。シェフは電光石火の速さで作業し、信じられないほどの精度で材料を準備します。しかし、常に材料の供給を待たなければならない場合、その効率は急落します。シェフが特定の珍しいスパイスを必要としているのに、隣にある十分にストックされた冷蔵庫に手を伸ばす代わりに、町の向こうにある遠い倉庫にアシスタントを送らなければならないと想像してください。シェフの比類なきスキルにもかかわらず、その長く非生産的な待ち時間が真のボトルネックを定義します。

コンピュータでは、この「遠い倉庫」のシナリオはcache missです。従来の二分探索が大きな配列内で新しい、しばしば連続していない場所に「ジャンプ」するたびに、頻繁にキャッシュミスを引き起こします。その後、CPUは一時停止し、時には数百クロックサイクルにわたって、要求されたデータがメインRAMからローカルキャッシュに移動するのを待ち、次の比較に進むことができます。Daniel Lemire氏の最近のベンチマークは、これらの蓄積されたストールが、比較回数を最小限に抑えるという理論的な利点をはるかに上回ることを鮮やかに示しています。彼は、標準的な二分探索が、特に現在のx64およびARMハードウェアにおいて、最適化された代替手段よりも2倍以上遅くなる可能性があり、大幅なパフォーマンスを損なっていることを証明しました。

二分探索の基本的な操作である探索空間を繰り返し二等分することは、本質的に非シーケンシャルで、ほとんどランダムなメモリアクセスパターンを生成します。アルゴリズムは中間点のインデックスを計算し、そのメモリ位置にアクセスし、その後新しい中間点を再計算します。このプロセスは、連続するメモリ要求がしばしば遠く離れており、広大で予測不可能なメモリ領域を横断することを意味します。

現代のCPUは、より高速なキャッシュメモリにデータを予測してプリロードするように設計された洗練されたprefetchersというハードウェアコンポーネントを備えています。これらのプリフェッチャは、線形的でシーケンシャルなメモリアクセスパターンを認識し、活用することに優れています。コードが`array[0]`を読み込み、次に`array[1]`を読み込む場合、プリフェッチャは`array[2]`、`array[3]`、およびそれ以降の要素を迅速にキャッシュにロードし、すぐに使用できるようにします。これにより、メモリレイテンシが劇的に削減されます。

しかし、二分探索の「中央へのジャンプ」アプローチは、これらの最適化されたプリフェッチシステムを完全に無効にしてしまいます。不規則なメモリアクセスにより、プリフェッチャが次に必要なデータを確実に予測することは不可能です。アルゴリズムが次に`array[N/4]`にアクセスするのか、それとも`array[3N/4]`にアクセスするのか、ましてや特定のバイトにアクセスするのかを予測することはできません。

この失敗は、頻繁でコストのかかるcache missesに直結します。超高速のL1またはL2キャッシュでデータを見つける代わりに、CPUはしばしば実行を停止し、はるかに低速なメインRAMからデータを取得しなければなりません。このプロセスは、ミスごとに数百クロックサイクルのレイテンシを発生させ、二分探索の比較回数が少ないという理論的なアルゴリズム上の利点を完全に覆い隠してしまいます。

コンピュータ科学者 Daniel Lemire氏の最近のベンチマークは、この問題を鮮やかに示しており、従来の二分探索が現代のプロセッサで大幅なパフォーマンスを損なっていることを証明しています。彼は、ボトルネックが比較回数ではなく、メモリアクセスのレイテンシであることを示しています。これらのベンチマークとC++の実装についてさらに深く掘り下げるには、Daniel Lemire氏の画期的なブログ記事「You can beat the binary search」を参照してください。

これを単純なリニアスキャンと比較してください。アルゴリズム的にはO(N)の複雑さで遅いですが、リニアスキャンはメモリに完璧なシーケンシャル順序でアクセスします。このパターンはプリフェッチャにとって理想的であり、キャッシュライン全体を効率的にロードし、データがほぼ常に利用可能であることを保証します。

コンピュータ科学者であるダニエル・レミール教授は、基本的なアルゴリズム、特に二分探索の揺るぎない支配を取り巻く数十年にわたる従来の常識に直接異議を唱えています。彼は、シーケンシャル処理と均一なメモリアクセスという過ぎ去った時代の最適化された教科書的なアプローチが、現代のCPUに固有の膨大な並列処理と複雑なメモリ階層には根本的に不向きであると主張しています。

レミールは、比較回数を最小限に抑えるという伝統的な焦点は、数学的には優雅であるものの、現代のハードウェアの真のボトルネックであるメモリレイテンシを決定的に無視していると主張します。標準的な二分探索の「中央にジャンプする」戦略は、非常に非シーケンシャルなメモリアクセスパターンを生成し、頻繁で高価なキャッシュミスを引き起こします。これにより、CPUは何百サイクルも、はるかに遅いRAMからのデータを待機して停止する可能性があります。このランダムアクセスパターンは、現代のCPUのプリフェッチメカニズムに積極的に反します。

彼の研究は、二分探索の理論的なO(log N)効率を否定することを目的とするのではなく、現在および将来のアーキテクチャに合わせて進化させることを目的としています。レミールは、Single Instruction, Multiple Data (SIMD) 命令やメモリレベル並列処理のような現代的な機能を活用するために、検索アルゴリズムを再設計するハードウェアアウェアなアプローチを提唱しています。このパラダイムシフトは、単純な計算ステップ数よりもスループットと効率的なデータ移動を優先し、CPUの真のパフォーマンスドライバーを認識しています。

レミールの影響力のある2026年4月27日のブログ投稿「二分探索に勝てる」は、コンピュータ科学コミュニティ全体で大きな議論を巻き起こしました。Apple M4やIntel Emerald Rapidsプロセッサを含む現代のx64およびARMハードウェアで実施された彼の説得力のあるベンチマークは、困難なコールドキャッシュ条件下でも、従来の二分探索に対して2倍以上の高速化を一貫して示しました。この否定できないパフォーマンス向上は、抽象的な理論モデルのみに頼るのではなく、今日のハードウェアが実際にどのように動作するかを深く理解してアルゴリズムを設計することの極めて重要な必要性を強調しています。

レミールの「SIMD Quad」アルゴリズムは、検索を根本的に再考し、理論的な比較を超えて現代のコンピュータハードウェアの能力を取り入れています。これは洗練されたハイブリッド戦略を採用し、配列サイズに基づいてアプローチを適応させることで、効率を最大化し、メモリレイテンシを最小限に抑えます。この設計は、幅広いデータ規模で最適なパフォーマンスを保証します。

非常に小さな配列、具体的には16要素未満の配列の場合、アルゴリズムは直接的なリニアスキャンを選択します。この一見基本的なアプローチは意図的な最適化であり、より複雑なアルゴリズム設定に伴うオーバーヘッドを回避します。そのような小さなデータセットでは、これは逆効果となるでしょう。代わりに、単純なシーケンシャルチェックが最速の結果をもたらします。

より大きな配列を扱う場合、レミールの手法はデータを巧妙に管理しやすい16要素の固定ブロックに分割します。このブロックベースの構成が効率性の基盤となり、アルゴリズムは大規模なデータセットを単一の巨大な問題としてではなく、一連のより小さな並列処理可能なタスクとして処理できるようになります。このセグメンテーションは、現代のCPUアーキテクチャを活用するために不可欠です。

ターゲット値の特定は、多方向探索戦略を通じて進行します。このアルゴリズムは、四元基数4補間を実行し、ターゲット位置が最も存在する可能性が高い特定の16要素ブロックをインテリジェントに特定します。このステップにより、探索空間が大幅に狭まり、高価なキャッシュミスを引き起こすメモリアクセスの回数が減少します。

アルゴリズムが可能性のあるブロックを特定すると、SIMD (Single Instruction, Multiple Data) 命令の全能力を展開します。その特定のブロック内の16要素すべてが単一のCPUレジスタにロードされます。プロセッサはその後、1回の並列操作で各要素をターゲット値と同時に比較し、その局所化されたデータチャンク内で比類のない速度を実現します。

完全な16要素ブロックにきれいに収まらない要素は、迅速な局所線形探索を受けます。この包括的な戦略は、従来の二分探索を一貫して上回り、単純な比較回数よりもメモリレベルの並列処理を優先することで、Apple M4やIntel Emerald Rapidsプロセッサなどのプラットフォームを含む、最新のx64およびARMハードウェアで2倍以上の高速化を実現します。

Lemireの設計は、二分探索の厳密なデータ半減を超えて、探索を根本的に再考します。彼の方法は、ルックアップの初期段階を劇的に加速する洗練された技術である四元基数4補間探索を組み込んでいます。探索空間を二分する代わりに、このアプローチはそれを効果的に四分の一に分割し、ブロック境界に焦点を当てます。

従来の二分探索は一度推測し、その後待ちます。しかし、Lemireのアルゴリズムは多方向戦略を採用しています。より大きな配列の場合、まずデータを16要素の固定ブロックに分割します。その後、四元探索はこれらのブロック境界、特に各ブロックの最後の要素に対して動作し、ターゲット値を含む可能性が最も高いブロックを迅速に特定します。これは、より広範で効率的な初期探索を可能にするため、重要な違いです。

決定的に重要なのは、この多方向分岐により、コンピュータのCPUが複数のメモリー要求を並行して発行できることです。最大4つの潜在的なブロック末端位置を同時に評価することで、アルゴリズムはより情報に基づいた、より深いジャンプを行います。最新のプロセッサは、メモリレベル並列処理として知られる機能である、複数の未処理のデータフェッチの処理に優れています。これらの要求をオーバーラップさせることで、Lemireのアルゴリズムはメインメモリへのアクセスに内在するレイテンシを戦略的に隠蔽します。コンピュータはアイドル状態になりません。

対照的に、二分探索は厳密な逐次依存性で動作します。次の潜在的な中間点を計算する前に、単一の「中央へのジャンプ」メモリーフェッチの結果を待つ必要があります。その最初のフェッチがキャッシュミスを引き起こした場合、CPUは何百サイクルも停止し、パフォーマンスの重大なボトルネックとなります。その後の比較はすべて、その先行する、しばしば遅いメモリー操作に完全に依存し、依存関係の直列チェーンを作成します。

この逐次的な制限は、比較ではなくレイテンシが実行時間を支配する最新のハードウェアにおいて、二分探索を機能不全に陥らせます。Lemireの四元アプローチは、複数の潜在的な次のステップのためにデータを積極的にフェッチすることでこれを回避し、遠隔メモリを待っている間もプロセッサが作業できるようにします。単一の依存的なメモリアクセスから複数の並列要求の発行への移行は、ボトルネックをCPUの停止から並列実行の機会へと変えます。ハードウェアを意識したアルゴリズム設計に関するさらなる洞察については、Better Stackのようなリソースを探索することを検討してください。この革新的なアプローチは、最新のハードウェアが実際にどのように動作するかについて深い理解を示しています。

真のハードウェア並列性を解き放つことが、Lemireのパフォーマンス優位性の核です。彼の「SIMD Quad」アルゴリズムは、並列処理のために設計された現代のCPUの基本的な機能であるSIMD (Single Instruction, Multiple Data)を活用します。一度に1つのデータ項目に対して操作を実行する代わりに、SIMDは単一のCPU命令で複数のデータポイントを同時に操作することを可能にし、逐次的な作業を並行した活動のバーストへと変えます。

現代のプロセッサは、SIMD操作専用の命令セットを備えています。x64 architectureでは、SSE2、AVX、AVX2のような拡張機能が含まれ、ARMベースのチップはNEONを利用します。これらの命令セットは、複数のより小さなデータ型を保持できる、しばしば128ビットまたは256ビット幅の特殊なレジスタを提供します。例えば、128ビットレジスタは、16個の8ビット整数、8個の16ビット整数、または4個の32ビット整数を効率的に格納できます。

Lemireのアルゴリズムはこの能力を見事に活用します。四進数基数4の補間探索がターゲットブロックを特定すると、スカラー比較に進みません。代わりに、アルゴリズムはその特定されたブロックの16個の要素すべてを単一のワイドなSIMD registerにロードします。この単一のメモリ操作は連続したデータチャンクをフェッチするため、キャッシュに非常に優しく、従来のbinary searchを悩ませるランダムアクセスによるペナルティを回避します。

次に真の魔法が展開されます。16個の要素すべてが1つのレジスタに格納されている状態で、単一のSIMD instructionが16回の比較を同時に実行します。これは、通常、各要素を個別に比較するために16回の別々のサイクルを必要とするCPUが、わずか1サイクルで同じ結果を達成できることを意味します。この劇的な効率向上、ブロック内の比較フェーズでほぼ16倍の高速化は、全体の処理時間を大幅に短縮します。これはmemory bottleneckへの直接的な攻撃であり、コンピュータのシリコンに内在する、活用されていない生の並列能力を活用しています。Lemireは、ハードウェアの能力を理解することが、アルゴリズムの最高のパフォーマンスを達成するために最も重要であることを証明しています。

Lemireの研究は、否定できない証拠を提供しています。彼のSIMD-accelerated multi-way search algorithmは、現代のプロセッサにおいて従来のbinary searchを根本的に上回ります。AppleのM4 chipやIntelのEmerald Rapids processorsを含む最先端のハードウェアで実施されたベンチマークは、従来の常識に対する厳しい現実を明らかにしています。今日の高性能コンピューティングを代表するこれらの現代的なプラットフォームは、この再評価の試金石となりました。

数多くのテストを通じて、Lemireの手法は標準的なbinary searchの実装と比較して、一貫して2x speedup以上を達成しました。これはわずかな改善ではありません。探索効率における深遠な世代的飛躍を表しており、数十年にわたるコンピュータ科学の教育法に直接異議を唱えるものです。結果は、多様なデータセットと配列サイズにわたって堅牢かつ再現可能であり、ハードウェアを意識した設計原則を裏付けています。

決定的に重要なのは、これらの劇的な性能向上が最適な条件に依存していなかったことです。コンピュータのCPUがより遅いRAMから直接データを頻繁にフェッチする最悪のシナリオであるcold cacheであっても、Lemire’s algorithmはその顕著なリードを維持しました。これは、従来のbinary searchを機能不全に陥れるメモリレイテンシのボトルネックに対するその回復力を示しており、予測不可能なメモリアクセスパターンに直面してもその有効性を証明しています。

パフォーマンスはウォームキャッシュによってさらに向上しました。ここでは、頻繁にアクセスされるデータがより高速なCPUメモリに存在し、アルゴリズムがそのメモリレベル並列性とSIMD命令を最大限に活用できるようになります。例えば、ウォームキャッシュを備えたIntel Emerald Rapidsプラットフォームでは、新しいアルゴリズムは従来のアルゴリズムの半分以下の時間で完了しました。ARMベースのApple M4やx64 Intel Emerald Rapidsといった多様な最新アーキテクチャ全体での一貫性は、アルゴリズムの根本的な利点を強調し、理論的なベンチマークを超えて実際のアプリケーションでの優位性を証明しています。

Lemireの画期的な研究は、単一の検索関数を最適化するはるか先を行くものであり、ソフトウェア開発者やコンピュータ科学者がパフォーマンスにどのようにアプローチするかについて、根本的な再評価を求めています。何十年もの間、Big O notationは最高の地位を占め、洗練された理論的な複雑さの保証を提供してきました。しかし、現代のプロセッサでは、この数学的抽象化は実際の測定されたパフォーマンスからますます乖離しています。Big O分析の中心である、すべてのメモリアクセスが同じコストであるという仮定は、特に大規模なデータセットを扱う場合、全くの神話です。

ハードウェアアーキテクチャの理解は、パフォーマンスが重要な作業にとって、もはやオプションの贅沢ではなく、中核的な要件です。CPUはランダムなメモリジャンプを著しくペナルティとして課します。これは、従来のバイナリサーチの「中央へのジャンプ」アプローチがまさに生み出すものです。これらの非シーケンシャルなアクセスパターンは、頻繁に高価なキャッシュミスを引き起こし、より遅いRAMからのデータを待つ間、CPUを数百サイクル停止させます。このメモリレイテンシこそが、比較回数ではなく、実際のアプリケーションにおける主要なボトルネックとして浮上しています。

理論的な効率性と実際の実行との間のこの乖離の拡大は、業界全体で新しい考え方を義務付けています。開発者は純粋に論理的なアルゴリズム設計を超え、ハードウェアアウェアなアルゴリズム設計を受け入れる必要があります。このパラダイムは、データがメモリにどのように細心の注意を払って配置されるか、どのようにアクセスされるか、そしてCPU固有の並列処理能力（Single Instruction, Multiple Data (SIMD) 命令など）がどれほど効率的に活用できるかを優先します。Daniel Lemireの「SIMD Quad」アルゴリズムは、この哲学が実際に機能している主要な例として役立ちます。

その深遠な実践的意味合いを考えてみましょう：キャッシュライン、メモリ配置、およびベクトル処理ユニットの特定の特性を明示的に考慮したアルゴリズムを設計することです。抽象的な操作を単に数えるのではなく、エンジニアは今や戦略的にキャッシュミスを最小限に抑え、メモリレベル並列性を最大化しなければなりません。Lemireの説得力のあるベンチマークは、彼の方法が現代のx64またはARMハードウェアで従来のバイナリサーチよりも一貫して2倍高速であることを示しており、この必要性の否定できない証拠を提供します。このパラダイムシフトは、高レベルのロジックからシリコンに至るまで、コンピュータシステム全体に対するより深く、より統合された理解を要求し、コンピュータサイエンスの教え方と実践方法を根本的に再構築します。

並列性の活用は、ソフトウェアにおける次のレベルのパフォーマンスを解き放つための揺るぎない鍵となります。Daniel Lemireの「SIMD Quad」アルゴリズムは、現代のx64およびARMハードウェアで従来のバイナリサーチを2倍以上上回り、比較回数を最小限に抑えるのではなく、並行操作を最大化することが真の効率を決定することを力強く証明しています。重要なボトルネックに対するシーケンシャル思考の時代は明確に終わりを告げました。未来は、利用可能なハードウェア並列性のあらゆる部分を活用するアルゴリズムを要求します。

このハードウェアを意識した設計思想は、検索だけに留まりません。ソート、ハッシュ、さらにはデータ圧縮といった基本的なアルゴリズムも、同様の抜本的な見直しが求められています。将来のソートルーチンは、スワップの最適化だけでなく、ベクトルユニットを使用して複数のデータチャンクを同時に処理したり、均一なメモリアクセスコストに関する古い仮定に頼るのではなく、キャッシュミスを回避し、最新のCPU設計に内在するメモリレベルの並列性を活用するために綿密に作成されたハッシュ関数を想像してみてください。

私たちは、「万能」アルゴリズムの終焉を目の当たりにしています。これは、より単純なコンピューティング時代の遺物です。特定のプロセッサアーキテクチャのニュアンスに合わせてカスタム設計された、共同設計されたハードウェア/ソフトウェアソリューションが、特定の課題に対する理想的な解決策としてますます重要になるでしょう。このパラダイムシフトは、抽象的な Big O notation を超え、キャッシュ階層やパイプラインストールといった具体的なハードウェアの現実に目を向け、現代のコンピューターが実際に命令を実行し、メモリを管理する方法についてより深い理解を求めています。

したがって、開発者はパフォーマンスに対して、より積極的で情報に基づいたアプローチを採用する必要があります。まず、コードを厳密にプロファイリングして、比較に費やされるCPUサイクルだけでなく、メモリアクセスパターンやキャッシュ動作に起因することが多い真のパフォーマンスボトルネックを特定します。次に、SIMD命令（ARM上の NEON や x64 上の SSE2/AVX など）のようなハードウェア固有の組み込み関数を直接使用して、これらの重要なセクションをベクトル化および並列化することを検討します。基盤となるコンピューターを深く理解した上で構築されたこのターゲットを絞った最適化は、今後数十年間で真に高速なソフトウェアを実現するための最も直接的な道筋となります。

なぜ二分探索は現代のCPUで遅いと見なされるのですか？

二分探索が遅いのは、比較のためではなく、そのランダムなメモリアクセスパターンが頻繁な「キャッシュミス」を引き起こすためです。これにより、高速なCPUは、はるかに遅いRAMからのデータを待つ間、数百サイクルにわたってストールすることを余儀なくされます。

Daniel Lemire 教授による二分探索のより高速な代替案は何ですか？

Daniel Lemire 教授は「SIMD Quad」アルゴリズムを開発しました。これは、補間を使用して可能性のあるデータブロックを見つけ、そのブロックを特殊なレジスタにロードし、SIMD 命令を使用してそのすべての要素を同時に比較する多方向探索です。

SIMD とは何ですか、そしてどのように検索を高速化しますか？

SIMD は「Single Instruction, Multiple Data」の略です。これは、1つの命令で複数のデータポイントに対して同じ操作を一度に実行できるCPU機能です。この場合、16個の数値のブロック全体を単一の操作でターゲット値と比較し、比較時間を劇的に短縮します。

これは Big O notation が役に立たないという意味ですか？

いいえ、Big O notation はアルゴリズムのスケーラビリティを理解するための依然として重要なツールです。しかし、この研究は、メモリレイテンシや並列性といった実際のハードウェア要因を考慮しておらず、これらがパフォーマンスを支配する可能性があるため、不完全であることを示しています。