c++ - 卷积 : the last element in the convolution is never right

Question

我正在用以下函数编写卷积的 C++ 实现

vector<double> Conv(vector<double> a, vector<double> b)
{
    // a and b are the same size
    int n = a.size() * 2 - 1;
    vector<double> c;
    for (int i = 0; i < n; i++) {
        c.push_back(0);
        for (int j = 0; j <= i; j++) {
            c[i] += a[j] * b[i - j];
        }
    }
    return c;
}

问题是除了最后一个以外，所有的卷积值都是正确的。我使用在网上找到的卷积计算器进行了检查。

示例输入:

Vector a = <0.961232, 0.00685581, 0.905588, 0.914544>

Vector b = <0.719889, 0.675933, 0.0571511, 0.148412>

Returned vector = <0.691981, 0.654664, 0.711493, 1.41354, 0.670944, 0.186668, 0.653971>

Expected = <0.691980343248, 0.65466385166109, 0.71149237410793, 1.413537159886891, 0.67094330437252, 0.1866673218544, 0.135729304128>

返回 vector 中 float 的准确性很好，但最后的结果不匹配。

Answer 1

根据其他社区成员的评论，我认为您的算法不太正确。我没有调试，而是决定通过 google 找到一个正确的。

这两个链接给了我线索:

• Convolution of Vectors (Mlmode)

• Convolution of two vectors in R

我使用这些链接用 C++ 制作了一个小示例:

#include <iostream>
#include <vector>

template <typename VALUE>
void convolve(
  std::vector<VALUE> &c, // out
  const std::vector<VALUE> &a, const std::vector<VALUE> &b) // in
{
  const size_t nA = a.size(), nB = b.size();
  const size_t nC = nA + nB - 1;
  c.clear(); c.resize(nC, (VALUE)0);
  for (size_t i = 0; i < nA; ++i) {
    for (size_t j = 0; j < nB; ++j) {
      c[i + j] += a[i] * b[j];
    }
  }
}

template <typename VALUE>
inline std::vector<VALUE> convolve(
  const std::vector<VALUE> &a, const std::vector<VALUE> &b)
{
  std::vector<VALUE> c; convolve(c, a, b); return c;
}

template <typename VALUE>
void print(
  std::ostream &out, const char *label, const std::vector<VALUE> &vec)
{
  out << label << '[' << vec.size() << "]: {";
  const char *sep = " ";
  for (const VALUE &v : vec) {
    out << sep << v;
    sep = ", ";
  }
  out << " }" << std::endl;
}

int main()
{
  // test 1
  // http://www.omatrix.com/manual/mlmode_conv.htm
  { std::cout << "Test 1:" << std::endl;
    const std::vector<int> a = {
      1, 1, 1, 1, 1
    };
    std::vector<int> c;
    convolve(c, a, a);
    print(std::cout, "a", a);
    std::cout << "Convolution of a and a:" << std::endl;
    print(std::cout, "c", c);
  }
  // test 2
  { std::cout << "Test 2:" << std::endl;
    const std::vector<float> a = {
      0.961232f, 0.00685581f, 0.905588f, 0.914544f
    };
    const std::vector<float> b = {
      0.719889f, 0.675933f, 0.0571511f, 0.148412f
    };
    std::vector<float> c;
    convolve(c, a, b);
    print(std::cout, "a", a);
    print(std::cout, "b", b);
    std::cout << "Convolution of a and b:" << std::endl;
    print(std::cout, "c", c);
  }
  // done
  return 0;
}

注意事项:

1. 复制 vector (如在 return 中所做的那样)对于大型 vector 来说可能代价高昂。因此，我通过引用提供结果 vector 。 (对于那些喜欢 return 的人，我写了一个 inline 包装器，但我没有使用它。)

2. 我使用了 vector::resize()，而不是 vector::push_back()。一次分配通常成本较低(特别是如果从一开始就知道大小)。 vector::resize() 也用于初始化。要丢弃可能的先前值，请先执行 vector::clear()。 (vector::clear() 是一种廉价方法，因为它不会释放存储空间，而只是重置内部元素数量。)

3. 我制作了convolve 模板。这使得使用更加灵活。

我在 Windows 10(64 位)的 cygwin 中用 g++ 编译并测试了它:

$ g++ -std=c++11 -o vector-convolution vector-convolution.cc 

$ ./vector-convolution.exe 
Test 1:
a[5]: { 1, 1, 1, 1, 1 }
Convolution of a and a:
c[9]: { 1, 2, 3, 4, 5, 4, 3, 2, 1 }
Test 2:
a[4]: { 0.961232, 0.00685581, 0.905588, 0.914544 }
b[4]: { 0.719889, 0.675933, 0.0571511, 0.148412 }
Convolution of a and b:
c[7]: { 0.69198, 0.654664, 0.711492, 1.41354, 0.670943, 0.186667, 0.135729 }

$

这看起来不错:

• 测试 1 符合 Convolution of Vectors (Mlmode) 的预期值.

• 检验 2 符​​合您问题的预期值。