Cで値を交換する最速の方法は何ですか?

番号 2 は、「賢い」方法であるとよく言われます。実際には、2 つの変数を交換するというプログラマーの明確な目的がわかりにくくなるため、処理速度が遅くなる可能性が高くなります。これは、コンパイラが実際のアセンブラ操作を使用してスワップするように最適化できないことを意味します。また、オブジェクトに対してビット単位の xor を実行できることも前提としています。

番号 1 に固執します。これは最も一般的で最も理解しやすいスワップであり、簡単にテンプレート化/一般化できます。

このウィキペディアのセクションでは、問題について非常によく説明しています:http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice


a と b が同じアドレスを指している場合、XOR メソッドは失敗します。最初の XOR は、両方の変数が指すメモリ アドレスのすべてのビットをクリアするため、初期値に関係なく、関数が (*a ==*b ==0) を返すと。

Wiki ページの詳細:XOR スワップ アルゴリズム

この問題が発生する可能性は低いですが、予期しない瞬間に失敗する巧妙な方法ではなく、動作が保証されている方法を常に使用することを好みます.


最新のプロセッサでは、大きな配列をソートするときに次を使用でき、速度に違いはありません:

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

あなたの質問の本当に重要な部分は、「なぜ？」です。部。さて、20 年前の 8086 日にさかのぼると、上記は真のパフォーマンス キラーでしたが、最新の Pentium では、あなたが投稿した 2 つに匹敵するスピードでした。

その理由は純粋にメモリの問題であり、CPU とは関係ありません。

メモリ速度と比較して、CPU 速度は天文学的に上昇しています。メモリへのアクセスは、アプリケーション パフォーマンスの主要なボトルネックになっています。すべてのスワップ アルゴリズムは、データがメモリからフェッチされるのを待つことにほとんどの時間を費やします。最新の OS は、最大 5 レベルのメモリを持つことができます:

  • キャッシュ レベル 1 - CPU と同じ速度で実行され、アクセス時間はごくわずかですが、小さい
  • キャッシュ レベル 2 - L1 よりも少し低速で実行されますが、サイズが大きく、アクセスのオーバーヘッドが大きくなります (通常、データは最初に L1 に移動する必要があります)
  • キャッシュ レベル 3 - (常に存在するとは限りません) 多くの場合、CPU の外部にあり、L2 よりも低速で大きい
  • RAM - メイン システム メモリ。通常はパイプラインを実装するため、読み取りリクエストにレイテンシが発生します（CPU がデータをリクエストし、メッセージが RAM に送信され、RAM がデータを取得し、RAM がデータを CPU に送信します）
  • ハードディスク - 十分な RAM がない場合、データは HD にページングされますが、これは非常に遅く、CPU の制御下にありません。

並べ替えアルゴリズムは、通常非常に順不同の方法でメモリにアクセスするため、メモリ アクセスを悪化させ、L2、RAM、または HD からデータを取得する非効率的なオーバーヘッドが発生します。

そのため、swap メソッドの最適化は本当に無意味です。数回しか呼び出されない場合は、呼び出し回数が少ないために非効率性が隠され、頻繁に呼び出された場合は、キャッシュ ミスの数が原因で非効率性が隠されます (ここで、 CPU は、L2 (1 サイクル)、L3 (10 サイクル)、RAM (100 サイクル)、HD (!) からデータを取得する必要があります。

実際に行う必要があるのは、swap メソッドを呼び出すアルゴリズムを調べることです。これは簡単な演習ではありません。 Big-O 表記は便利ですが、n が小さい場合、O(n) は O(log n) よりも大幅に高速になる可能性があります。 (これについては CodingHorror の記事があると思います。) また、多くのアルゴリズムには、コードが必要以上のことを行う縮退のケースがあります (ほぼ順序付けられたデータで qsort を使用すると、アーリーアウト チェックを使用したバブル ソートよりも遅くなる可能性があります)。したがって、アルゴリズムとそれが使用しているデータを分析する必要があります。

これは、コードを分析する方法につながります。プロファイラーは便利ですが、結果を解釈する方法を知る必要があります。結果を収集するために 1 回の実行を使用しないでください。常に多くの実行で結果を平均してください。これは、テスト アプリケーションが途中で OS によってハード ディスクにページングされた可能性があるためです。常にリリース、最適化されたビルドをプロファイリングし、デバッグ コードをプロファイリングすることは無意味です。

元の質問について - どちらが速いですか? - ウィング ミラーのサイズと形状を見て、フェラーリがランブルジーニよりも速いかどうかを判断しようとするようなものです。