繰り返しになりますが、私は自分が一連の間違った仮定に直面していることに気づきました。記事自体は、実証済みの最適なアルゴリズムを変更して仮想メモリを考慮することにより、パフォーマンスが 10 倍向上することについて説明しています。
いくつかのギガヘルツのクロック周波数で動作する最新のマルチイシュー CPU では、最悪の場合の損失は、VM ページ フォールトごとに約 1,000 万命令です。回転ディスクで実行している場合、その数は 1 億の命令に近くなります。
O(log2(n)) アルゴリズムは、これらの操作がページ フォールトやディスク操作の低速化を引き起こす場合、何の役に立つでしょうか? 最も関連性の高いデータセットでは、ページ フォールトを回避する O(n) または O(n^2) アルゴリズムでさえ、その周りを円で囲みます。
そのようなアルゴリズムはもっとありますか? 教育の基本的な構成要素をすべて再検討する必要がありますか? 自分で書くとき、他に何に注意する必要がありますか?
説明:
問題のアルゴリズムは、Big-O 表記に欠陥があるか無意味であるため、実証済みの最適なアルゴリズムよりも高速ではありません。実証済みの最適なアルゴリズムは、最新のハードウェア/OS では当てはまらない仮定、つまりすべてのメモリ アクセスが等しく交換可能であるという仮定に依存しているため、高速です。