6

纯粹作为一个实验，我在 MATLAB 中编写排序函数，然后通过 MATLAB 分析器运行这些函数。我发现最令人困惑的方面与交换元素有关。

我发现交换矩阵中两个元素的“官方”方式

self.Data([i1, i2]) = self.Data([i2, i1])

运行速度比用四行代码慢得多：

e1 = self.Data(i1);
e2 = self.Data(i2);
self.Data(i1) = e2;
self.Data(i2) = e1;

第二个示例所占用的总时间比第一个示例中的单行代码少12 倍。

有人会解释为什么吗？

4

5 回答 5

6

根据发布的建议，我进行了更多测试。当在分配的 LHS 和 RHS 中都引用相同的矩阵时，性能似乎会受到影响。

我的理论是 MATLAB 使用内部引用计数/写时复制机制，这会导致整个矩阵在被双方引用时在内部被复制。（这是一个猜测，因为我不知道 MATLAB 内部）。

这是调用函数 885548 次的结果。（这里的区别是 4 倍，而不是我最初发布的 12 倍。每个函数都有额外的函数包装开销，而在我最初的帖子中，我只是总结了各个行）。

交换 1：12.547 秒
 交换 2：14.301 秒
 交换 3：51.739 秒

这是代码：

 methods (Access = public)
     function swap(self, i1, i2)
        swap1(self, i1, i2);
        swap2(self, i1, i2);
        swap3(self, i1, i2);
        self.SwapCount = self.SwapCount + 1;
    end
 end

 methods (Access = private)
    %
    % swap1: stores values in temporary doubles
    %         This has the best performance
    %
    function swap1(self, i1, i2)
        e1 = self.Data(i1);
        e2 = self.Data(i2);
        self.Data(i1) = e2;
        self.Data(i2) = e1;
    end

    %
    % swap2: stores values in a temporary matrix
    %        Marginally slower than swap1
    %
    function swap2(self, i1, i2)
        m = self.Data([i1, i2]);
        self.Data([i2, i1]) = m;
    end

    %
    % swap3: does not use variables for storage.
    %        This has the worst performance
    %
    function swap3(self, i1, i2)
        self.Data([i1, i2]) = self.Data([i2, i1]);
    end


end
于 2009-02-03T00:31:44.930 回答
4

在第一种（慢速）方法中，RHS 值是一个矩阵，所以我认为 MATLAB 在创建一个新矩阵来存储这两个元素时会导致性能损失。第二种（快速）方法通过直接使用元素来避免这种情况。

查看 MathWorks 上的“提高性能的技巧”一文，了解改进 MATLAB 代码的方法。

于 2009-02-02T05:31:17.963 回答
2

你也可以这样做：

tmp = self.Data(i1);
self.Data(i1) = self.Data(i2);
self.Data(i2) = tmp;
于 2009-02-02T14:41:21.127 回答
2

Zach 可能是正确的，因为可以制作矩阵的临时副本来执行第一个操作，尽管我会冒险猜测 MATLAB 中有一些内部优化试图避免这种情况。它可能是您正在使用的 MATLAB 版本的函数。我在版本 7.1.0.246（几年前）中尝试了你的两个案例，只看到大约 2-2.5 的速度差异。

这可能是通过所谓的“循环展开”提高速度的一个例子。在进行向量运算时，在内部代码中的某个级别可能存在一个 FOR 循环，该循环遍历您正在交换的索引。通过在第二个示例中执行标量操作，您可以避免循环产生的任何开销。注意这两个（有点傻）的例子：

vec = [1 2 3 4];

%Example 1:
for i = 1:4,
  vec(i) = vec(i)+1;
end;

%Example 2:
vec(1) = vec(1)+1;
vec(2) = vec(2)+1;
vec(3) = vec(3)+1;
vec(4) = vec(4)+1;

诚然，简单地使用向量操作会容易得多，例如：

vec = vec+1;

但以上示例仅用于说明目的。当我多次重复每个示例并对其计时时，示例 2 实际上比示例 1 快一些。对于具有已知数字（在示例中只有 4）的小循环，放弃循环实际上可能更有效。当然，在这个特定的例子中，上面给出的向量运算实际上是最快的。

我通常遵循这个规则：尝试一些不同的事情，然后为你的具体问题选择最快的。

于 2009-02-02T15:25:01.070 回答
2

这篇文章值得更新，因为 JIT 编译器现在是一个东西（从 R2015b 开始），因此timeit（从 R2013b 开始）更可靠的功能时序。

下面是一个用于在大型数组中交换元素的简短基准测试函数。我已经使用术语“直接交换”和“使用临时变量”来分别描述问题中的两种方法。

结果非常惊人，与使用临时变量相比，使用直接交换 2 个元素的性能越来越差。

阴谋

function benchie()
    % Variables for plotting, loop to increase size of the arrays
    M = 15; D = zeros(1,M); W = zeros(1,M);
    for n = 1:M; 
        N = 2^n;
        % Create some random array of length N, and random indices to swap
        v = rand(N,1);
        x = randi([1, N], N, 1);
        y = randi([1, N], N, 1);
        % Time the functions
        D(n) = timeit(@()direct);
        W(n) = timeit(@()withtemp);
    end
    % Plotting
    plot(2.^(1:M), D, 2.^(1:M), W);
    legend('direct', 'with temp')
    xlabel('number of elements'); ylabel('time (s)')

    function direct()
    % Direct swapping of two elements
        for k = 1:N
            v([x(k) y(k)]) = v([y(k)  x(k)]);
        end
    end

    function withtemp()
    % Using an intermediate temporary variable
        for k = 1:N
            tmp = v(y(k));
            v(y(k)) = v(x(k));
            v(x(k)) = tmp;
        end
    end
end
于 2017-08-16T16:44:36.227 回答