c++ 使用XOR或临时变量进行冒泡排序

tv6aics1  于 2023-01-28  发布在  其他
关注(0)|答案(1)|浏览(101)

在使用bubble sort算法对数组排序的场景中,哪种算法更有效:在嵌套循环中创建临时变量或使用XOR运算符:

#include <iostream>

int main()
{
    int array[5] = {7, 2, 5, 3, 4};

    /* 1: using a temporary variable

    for(int i(0); i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                int tmp  = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
    */

    // 2: using the XOR ^ swapper
    for(int i = 0; i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                array[i] ^= array[j];
                array[j] ^= array[i];
                array[i] ^= array[j];
            }
        }
    }

    for( i = 0; i < 5; i++)
        std::cout << array[i] << ", ";

    std::cout << std::endl;
    return 0;
}

我只想知道哪种方法更快,更强大,知道这两种方法都很好用。

ql3eal8s

ql3eal8s1#

正如其他人已经指出的那样,唯一确定的方法是测量它。
“我该如何衡量它?”如果这个问题是《堆栈溢出》的主题,那么它将是一个完全不同的问题。
谷歌是你的朋友,谷歌一下吧,搜索关键词,比如“基准”或“配置文件”,还有“C++”,也许还有你正在使用的IDE的名字。
除此之外,我可以给予你一些相当好的指示,哪一个将更快,只是检查的指示。
该指令序列

a ^= b;
  b ^= a;
  a ^= b;

转换为以下未优化指令:

load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference
  load  register from b            ;memory reference
  xor   register with a            ;memory reference
  store register to b              ;memory reference
  load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference

其可能可优化如下:

load  register1 from a           ;memory reference
  load  register2 from b           ;memory reference
  xor register1 with register2
  xor register2 with register1
  xor register1 with register2
  store register1 to a             ;memory reference
  store register2 to b             ;memory reference

该指令序列

int tmp  = a;
  a = b;
  b = tmp;

转换为以下未优化指令:

load  register from a            ;memory reference
  store register to tmp            ;memory reference
  load  register from b            ;memory reference
  store register to a              ;memory reference
  load  register from tmp          ;memory reference
  store register to b              ;memory reference

其可能可优化如下:

load register1 from a            ;memory reference
  load register2 from b            ;memory reference
  store register1 to b             ;memory reference
  store register2 to a             ;memory reference

正如您所看到的,两种优化的片段都只涉及四个内存引用,因此这两种方法大致相同,但是XOR方法涉及三个额外的指令,因此它不可能执行得更好。
不相信我?好吧,那就不要相信我的话!我甚至不确定你的编译器还能执行哪些额外的优化。所以,除了运行基准测试或分析代码之外,还可以尝试查看编译器为上述代码片段生成的程序集。(当然,要启用所有优化。)

相关问题