优化算法效率的思路，以均线为例 优化算法的方法

对于量化交易策略而言，交易所发布的实时行情数据是远远不够的。通常需要经过大量的计算，得到衍生因子指标，再进行逻辑判断，最后输出交易信号。

今天就以最常见的移动平均为例，讲一下优化算法的一个思路。

移动平均是最近N个数据的算数平均。随着新数据的产生，移动平均的区间起点也会随之移动，起点到最新位置共有N个数据。

通常，用到的是K线收盘价的移动平均。

K线收盘价是指的固定区间内最后一笔Tick的价格。交易所以固定的频率发布Tick数据，假设每秒发布2笔，则1分钟K线就包含120笔Tick数据。当1分钟结束时，最一笔Tick的价格就是这1分钟K线的收盘价。

如上图，Last是最新K线位置，盘中Tick更新时，Last的价格随之变化。直到K线结束，产生了一个新的K线Last'，旧的Last就变成了Last-1。

基于以上认知，可以写出常规的算法：

首先，把源数据存储到vector中，每120次追加一次新数据，如果不是新数据，则更新最后一个数据；

然后，对vector最后N个数据求和；

最后，除以参数N，就得到了移动平均。

void maJunior()
{
  std::cout << "===>>> " << "maJunior" << " <<<===" << std::endl;
  double dSumValue = 0;

  /// 均线参数，从10到500
  for (int nParameter = 10; nParameter <= 500; ++nParameter)
  {
    std::chrono::time_point<std::chrono::high_resolution_clock> tAnchor;
    time_t nElapse = 0;

    /// 随机数
    std::uniform_real_distribution<double> u(9000, 11000);
    std::default_random_engine e;

    /// 进行100次重复实验
    for (int ikk = 0; ikk < 100; ++ikk)
    {
      /// 存放均线计算结果
      std::vector<double> vJuniorResultVector;
      vJuniorResultVector.reserve(110000);
      
      /// 存放数据源
      std::vector<double> vSourceVector;
      vSourceVector.reserve(2000);
      std::vector<double>::iterator itVector;

      /// 初始化
      int nIndex = 0;
      for (; nIndex < nParameter; ++nIndex)
      {
        vSourceVector.push_back(u(e));
      }

      --nIndex;
      double dValue;
      bool bIsStart;
      double dJuniorValue;
      /// 按照顺序生成10万个数据，并计算移动平均
      for (int jkk = 0; jkk < 100000; ++jkk)
      {
        /// 随机生成源数据
        dValue = u(e);
        /// 每120个数据占据一个K线位置
        bIsStart = (((jkk) % 120) == 0);

        /// 计时
        tAnchor = std::chrono::high_resolution_clock::now();

        /// 存放源数据
        if (bIsStart)
        {
          /// 一个新K线位置
          vSourceVector.push_back(dValue);
          ++nIndex;
        }
        else
        {
          /// 更新当前K线位置数据
          vSourceVector[nIndex] = dValue;
        }

        /// 均值
        dJuniorValue = std::accumulate(vSourceVector.end() - nParameter, vSourceVector.end(), 0.0) / nParameter;

        /// 耗时
        nElapse += std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - tAnchor).count();

        vJuniorResultVector.push_back(dJuniorValue);
      }
      dSumValue += std::accumulate(vJuniorResultVector.begin(), vJuniorResultVector.end(), 0.0);
    }
    std::cout << "Parameter:" << nParameter << ",Elapse:" << nElapse / 100000 / 100 << ",SumValue:" << dSumValue << std::endl;
  }
  std::cout << "===>>>" << "<<<===" << std::endl;
}

因为，每次都需要对K线序列中最后N个数据求和，所以该常规算法的耗时会随着参数N的增加而增加。

现在，我们来思考优化这个算法。

当K线结束时，这个K线收盘价也就固定了。在K线序列中，除了最后一个位置的数据在实时变化，之前的数据都是不变的。

如果我们把N个数据的和拆解为N-1个固定数据（Inactive），和1个变化数据（Last）。每次更新Last，只需要计算一次加法，即Last+Inactive，就可以得到N个数据的和。

当新K线Last'产生时，只要更新Inactive，从Inactive中减去Last-N-1，再加上Last，成为新的Inactive'，再与新的Last'相加可以了。

这样一来，优化后的算法的耗时就与参数N就没有关系了。

在服务器上运行测试代码，耗时数据也印证了这一点。

常规算法耗时随着参数N增加而增加，计算参数为500的移动平均，单数据点耗时670纳秒左右。

优化后的算法耗时与参数N无关，单数据点耗时124纳秒左右。

除了简单移动平均之外，常用的加权平均、区间最大/小值、线性回归等，都可以基于这个思路，拆解出来不变的部分和变化的部分，从而设计出来耗时与参数无关的算法。