CC++ & Algorithm

inner_product内积与adjacent_difference

较难2
语言版本：通用
概述：学习用C++计算两个向量的点积（内积）和相邻元素的差，并了解Python中的实现方式。

用内积和相邻差轻松处理序列运算

你有没有遇到过这样的场景：要计算一周内每种零食的销量收入，或者想知道每天零花钱的变化量？这些看似复杂的运算，其实只需要两个C++函数就能搞定——inner_product（内积）和adjacent_difference（相邻差）。它们都藏在<numeric>头文件中，专门用来处理序列间的对应运算。

从生活中的例子引入

内积就像算账：货架上有薯片（5元）、饼干（3元）、糖果（2元），今天卖出10包薯片、5包饼干、8包糖果。总收入就是每种价格乘以数量再相加：5×10 + 3×5 + 2×8 = 81元。这个“对应位置相乘再求和”的操作，数学上叫点积（或内积）。编程中，内积常用来计算加权总分（比如平时成绩×30% + 期末×70%），或者计算两个向量的相似度。

相邻差则像观察零花钱的变化：周一5元，周二3元，周三7元，周四2元。你想知道每天比前一天多（少）了多少？周二-周一 = -2（少了2元），周三-周二 = 4（多了4元），周四-周三 = -5（少了5元）。这种“后一个减前一个”的运算，就是相邻差。在数据分析中，相邻差可以快速得到变化量，比如温度变化、股价涨跌。

C++的<numeric>已经帮你封装好了这两个函数，你只需要提供数据，就能自动完成这些计算。

1. 内积（inner_product）详解

函数原型

#include <numeric>

// 基本形式
T inner_product(InputIt1 first1, InputIt1 last1, 
                InputIt2 first2, T init);

// 自定义操作形式
T inner_product(InputIt1 first1, InputIt1 last1, 
                InputIt2 first2, T init,
                BinaryOperation1 op1, BinaryOperation2 op2);

  • 参数说明

    • first1, last1：第一个序列的范围（左闭右开）。
    • first2：第二个序列的起始位置。函数会从first2开始依次取元素，直到第一个序列结束。
    • init：初始值，最终结果会加上这个数（通常设为0）。
    • 默认操作：先对每对元素做乘法（op2），再把所有乘积加起来（op1默认是加法）。
    • 自定义操作：你可以用op1替换加法（比如累加时用减法或求最大值），用op2替换乘法（比如计算差的平方）。

  • 返回值
    返回 init 加上所有 op2(a[i], b[i]) 的结果经 op1 累计后的值。

  • 时间复杂度：O(N)，N为第一个序列的长度。

更多例子

例子1：计算考试加权总分
小明的三门考试成绩：数学80、语文90、英语85。各科权重：数学占40%、语文占30%、英语占30%。加权总分 = 80×0.4 + 90×0.3 + 85×0.3 = 32 + 27 + 25.5 = 84.5分。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<double> scores = {80.0, 90.0, 85.0};        // 各科成绩
    std::vector<double> weights = {0.4, 0.3, 0.3};          // 各科权重
    double total = std::inner_product(scores.begin(), scores.end(),
                                      weights.begin(), 0.0);
    std::cout << "加权总分: " << total << std::endl;         // 输出84.5
    return 0;
}

例子2：计算对应元素差的平方和（欧氏距离平方）
在机器学习中，经常需要计算两个向量之间的欧氏距离平方。比如向量a=(1,2,3)，b=(4,5,6)，差的平方和为 (1-4)^2+(2-5)^2+(3-6)^2 = 9+9+9 = 27。

#include <iostream>
#include <vector>
#include <numeric>   // 需要 <numeric> 和 <functional>（std::plus）
#include <functional>

int main() {
    std::vector<double> a = {1.0, 2.0, 3.0};
    std::vector<double> b = {4.0, 5.0, 6.0};
    double dist_sq = std::inner_product(a.begin(), a.end(), b.begin(), 0.0,
                                        std::plus<double>(),          // op1: 累加
                                        [](double x, double y) {      // op2: 计算差的平方
                                            double diff = x - y;
                                            return diff * diff;
                                        });
    std::cout << "欧氏距离平方: " << dist_sq << std::endl; // 27
    return 0;
}

注意：自定义操作时，op1负责累计每个元素对的结果，op2负责计算每个元素对的值。初学者容易把op1和op2的顺序搞反，导致编译错误或结果异常。

2. 相邻差（adjacent_difference）详解

函数原型

#include <numeric>

// 基本形式
OutputIt adjacent_difference(InputIt first, InputIt last, 
                             OutputIt d_first);

// 自定义操作形式
OutputIt adjacent_difference(InputIt first, InputIt last, 
                             OutputIt d_first, 
                             BinaryOperation op);

  • 参数说明

    • first, last：输入序列的范围。
    • d_first：输出序列的起始位置。输出序列必须有足够空间（至少 last - first 个元素）。
    • 默认操作：第一个输出元素等于输入的第一个元素；后续输出元素等于 当前元素 - 前一个元素。
    • 自定义op：你可以用加法（计算相邻和）、乘法（计算相邻积）等。

  • 返回值
    指向输出序列末尾的迭代器。

  • 时间复杂度：O(N)。

更多例子

例子1：计算每日气温变化
一周的气温：周一22°C，周二20°C，周三25°C，周四23°C。相邻差：22（不变），20-22=-2，25-20=5，23-25=-2。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> temps = {22, 20, 25, 23};           // 每日气温
    std::vector<int> changes(temps.size());               // 存储变化量
    std::adjacent_difference(temps.begin(), temps.end(), changes.begin());
    std::cout << "气温变化: ";
    for (int c : changes) std::cout << c << " ";          // 输出22 -2 5 -2
    std::cout << std::endl;
    return 0;
}

例子2：计算相邻和（自定义加法）
有时你想知道连续两天的总和，比如相邻和：周一22，周一+周二=42，周二+周三=45，周三+周四=48。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> nums = {22, 20, 25, 23};
    std::vector<int> sum_adj(nums.size());
    std::adjacent_difference(nums.begin(), nums.end(), sum_adj.begin(),
                             [](int a, int b) { return a + b; });  // 自定义op为加法
    std::cout << "相邻和: ";
    for (int s : sum_adj) std::cout << s << " ";   // 输出22 42 45 48
    std::cout << std::endl;
    return 0;
}

注意：自定义op的参数顺序是 (当前元素, 前一个元素)。默认减法中，当前元素是被减数，前一个元素是减数。自定义加法时也一样：前一个 + 当前。这和直觉可能有点不同，写代码时要小心。

3. 新手容易犯的错误

  1. 第二个序列长度不足
    inner_product假设第二个序列至少有第一个序列那么长。如果第二个序列较短，会访问到未定义的内存，程序可能崩溃或给出错误结果。总是确保两个序列长度匹配。

  2. 输出区间空间不够
    adjacent_difference需要输出区间至少能存放N个元素。如果目标容器大小为0或小于N，会导致越界写入。先调用resize或直接初始化大小。

  3. 混淆op1和op2的顺序
    在自定义版inner_product中，op1（默认加法）是第一个二元操作，op2（默认乘法）是第二个。很多初学者把顺序写反，比如写成inner_product(..., op2, op1)，结果变成累加时用乘法，元素对操作时用加法，得到完全不同的值。

  4. 误解adjacent_difference的第一个元素
    默认情况下，第一个输出直接复制输入的第一个元素（不是差）。如果需要忽略第一个元素，可以手动跳过或使用其他方法（比如std::transform结合相邻迭代器）。

  5. 数据类型不一致导致精度丢失
    比如inner_product使用double的初始值，但序列是int，结果会升级为double。但若初始值为int，乘法结果可能被截断。通常建议用0.0而非0作为初始值。

4. 完整可运行的代码示例

下面是一个综合程序，演示内积和相邻差的各种用法，并附有详细注释。

#include <iostream>
#include <vector>
#include <numeric>   // inner_product, adjacent_difference
#include <functional> // std::plus

int main() {
    // -------------------- 内积示例 --------------------
    // 1. 基本用法：价格 * 数量
    std::vector<double> prices = {5.0, 3.0, 2.0};           // 零食价格
    std::vector<int> quantities = {10, 5, 8};               // 卖出数量
    double revenue = std::inner_product(prices.begin(), prices.end(),
                                         quantities.begin(), 0.0);
    std::cout << "总收入: " << revenue << " 元" << std::endl; // 81

    // 2. 自定义内积：计算欧氏距离平方
    std::vector<double> vecA = {1.0, 2.0, 3.0};
    std::vector<double> vecB = {4.0, 5.0, 6.0};
    double dist_sq = std::inner_product(vecA.begin(), vecA.end(), vecB.begin(), 0.0,
                                         std::plus<double>(),                       // 累加
                                         [](double x, double y) {                   // 计算差的平方
                                             double diff = x - y;
                                             return diff * diff;
                                         });
    std::cout << "欧氏距离平方: " << dist_sq << std::endl; // 27

    // -------------------- 相邻差示例 --------------------
    // 3. 基本用法：每日零花钱变化
    std::vector<int> daily_money = {5, 3, 7, 2};            // 每日零花钱
    std::vector<int> changes(daily_money.size());           // 准备输出数组
    std::adjacent_difference(daily_money.begin(), daily_money.end(), changes.begin());
    std::cout << "零花钱变化: ";
    for (int c : changes) std::cout << c << " ";            // 5 -2 4 -5
    std::cout << std::endl;

    // 4. 自定义相邻差：相邻和
    std::vector<int> sum_adj(daily_money.size());
    std::adjacent_difference(daily_money.begin(), daily_money.end(), sum_adj.begin(),
                             [](int a, int b) { return a + b; });   // 自定义加法
    std::cout << "相邻和: ";
    for (int s : sum_adj) std::cout << s << " ";             // 5 8 10 9
    std::cout << std::endl;

    return 0;
}

运行结果：

总收入: 81 元
欧氏距离平方: 27
零花钱变化: 5 -2 4 -5
相邻和: 5 8 10 9

5. Python中如何实现这两个功能

Python没有内置的inner_product和adjacent_difference，但用列表推导式和zip可以轻松模拟。

# 内积：价格 * 数量
prices = [5.0, 3.0, 2.0]
quantities = [10, 5, 8]
revenue = sum(p * q for p, q in zip(prices, quantities))
print("总收入:", revenue, "元")  # 81.0

# 自定义内积：欧氏距离平方
a = [1.0, 2.0, 3.0]
b = [4.0, 5.0, 6.0]
dist_sq = sum((x - y) ** 2 for x, y in zip(a, b))
print("欧氏距离平方:", dist_sq)  # 27.0

# 相邻差：每日零花钱变化
daily = [5, 3, 7, 2]
# 保持第一个元素不变，后面计算差值
diff = [daily[0]] + [daily[i] - daily[i-1] for i in range(1, len(daily))]
print("零花钱变化:", diff)  # [5, -2, 4, -5]

# 相邻和（自定义）
sum_adj = [daily[0]] + [daily[i] + daily[i-1] for i in range(1, len(daily))]
print("相邻和:", sum_adj)  # [5, 8, 10, 9]

# 使用 Python 3.10+ 的 itertools.pairwise
# from itertools import pairwise
# diff2 = [daily[0]] + [cur - prev for prev, cur in pairwise(daily)]

6. 相关知识点指引

掌握了inner_product和adjacent_difference，你还可以学习更多STL数值算法：

  • std::accumulate：直接对序列求和（或自定义累积），是内积的简化版（只有第一个序列）。
  • std::partial_sum：计算前缀和，类似于adjacent_difference的逆操作（从第一个元素开始累加，每个位置放累加和）。
  • std::transform_reduce（C++17）：更通用的并行归约算法，可以代替inner_product并支持并行执行。
  • std::iota：生成递增序列，常用于测试数据。

这些算法都定义在<numeric>或<algorithm>中，了解它们能让你写代码更高效、更少出错。下次遇到“对应相乘再求和”或“相邻元素相减”的问题时，不妨直接用内积和相邻差函数吧！

例题精讲

1单选题

在C++标准库中，std::inner_product的自定义重载版本接受两个二元操作符，关于这两个操作符的角色，下列说法正确的是？

A第一个二元操作符用于元素相乘，第二个用于累加
B第一个二元操作符用于累加，第二个用于元素相乘
C两个操作符都用于元素相乘
D两个操作符都用于累加
2填空题
完成以下C++代码，使用std::inner_product计算向量a和b的内积，初始值为0，结果存入result。
#include <iostream>
#include <vector>
#include <numeric>
int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    int result = ___(a.begin(), a.end(), b.begin(), 0);
    std::cout << result;
    return 0;
}
3判断题

使用std::adjacent_difference对序列{1,2,3,4}计算相邻差，得到的结果序列的第一个元素是1。

4填空题
以下C++代码使用std::adjacent_difference计算向量v的相邻差，并将结果追加到diffs向量的末尾。请填空。
#include <iostream>
#include <vector>
#include <numeric>
int main() {
    std::vector<int> v = {5, 10, 15, 20};
    std::vector<int> diffs;
    std::adjacent_difference(v.begin(), v.end(), ___(diffs));
    for(int x : diffs) std::cout << x << " ";
    return 0;
}
5单选题

在Python中，计算两个列表a=[1,2,3]和b=[4,5,6]的内积（对应元素乘积之和），以下哪种方式不能正确得到结果？

Asum(a[i]*b[i] for i in range(len(a)))
Bsum(map(lambda x,y: x*y, a, b))
Cnp.dot(a, b) (假设已import numpy as np)
Dsum(a)*sum(b)