1

我正在研究一个函数，该函数将 n×1 数组（称为“ts”）作为输入并创建一个 n×n 矩阵（称为“V”），其中 V 的每个元素都是 0 或 1 .

现在将“ts”想象成一个图：如果可以使用一条直线将任意点（例如 ts(5)）与另一个任意点（例如 ts(47)）连接起来而不与时间序列相交，那么矩阵元素 V( 5,47) 和 V(47,5) 应该为 1。如果两个点在不与时间序列相交的情况下无法连接，则矩阵中的相应元素应该为 0。应该对所有可能的对都执行此操作“ts”中的点数。

这是函数：它可以工作，但效率很低（尤其是因为三个嵌套循环）。有没有办法对这段代码进行矢量化？

function V = someFunction(ts)
len = length(ts);
V = zeros(len, len);
for a = 1:len,
   for b = 1:len,
       intersection = [];
       for c = min(a,b)+1 : max(a,b)-1,
           t_a = a;
           y_a = ts(a);
           t_b = b;
           y_b = ts(b);
           t_c = c;
           y_c = ts(c);

           if (y_c < y_b + (y_a - y_b) * ((t_b - t_c) / (t_b - t_a))),
               intersection = [intersection; 0];
           else
               intersection = [intersection; 1];
           end
       end
       if all(intersection==0),
           V(a,b) = 1;
       end
   end
end
end
4

1 回答 1

3

几件事：

  1. intersection当您点击您知道为零 的else子句时，无需创建数组。V(a,b)
  2. 由于V是对称的，因此您只能计算.5*n*(n-1)条目而不是n^2（相同的 O(n^2)，但仍然少得多）。
  3. Oleg的另一个观察是：“如果线段长度为 3 点，则不需要执行任何检查，在这种情况下，构造上不可能有任何交叉点”

新代码

V = ones(len,len); % default for all
for a = 1:(len-3),
   for b = (a+3):len,
      for c = min(a,b)+1 : max(a,b)-1,
          t_a = a;
          y_a = ts(a);
          t_b = b;
          y_b = ts(b);
          t_c = c;
          y_c = ts(c);

          if (y_c < y_b + (y_a - y_b) * ((t_b - t_c) / (t_b - t_a))),
              % do nothing
          else
              V(a,b) = 0; % intersect
              V(b,a) = 0;
              break; % stop the inner loop the moment an intersection was found
          end
      end
   end
end
于 2013-05-30T09:23:10.607 回答