三角套利¶
假设有三个交易对（交易对指两种资产按照一定比例互相交易的市场）。
第一个为A-B，交换比例为1:10（即1个A可以兑换为10个B，10个B可以兑换为1个A，下同）；
第二个为B-C，交换比例为1:100；
第三个为A-C，交换比例为1:1000。
假设我们手中有1个A资产，当Price(A,C)变为1:1100时，我们可以拿1个A通过第三个交易对，交换为1100个C，再通过第二个交易对将1100个C交换为11个B，再通过第一个交易对将11个B交换为1.1个A，从而实现0.1个A的盈利。
问题1: 当你收到的是Price(A,C)变为1:900时，是否可以盈利？如何操作？
问题2: 写一个函数，当监听到三个交易对中，任意一个交易对的交换比例发生变化时，判断是否有盈利机会，需如何操作。
问题3: 假设市场上有5万个类似的交易对，如何找到所有可以进行上述交易全部回环？
问题4: 设计一个数据结构，存储找到的所有回环，并写一个函数，当监听到5万个交易对中，任意一个交易对的交换比例发生变化时，使用该数据结构快速找到最盈利的那一条回环。
问题5: 如果我们用来交换的不是固定的1个A，而是0-1000个A，但由于冲击成本的存在，A的输入越大，收益率越低，但绝对收益可能在一定区间保持上升，如何设计算法去找到每条回环乃至所有回环的最大盈利。
统计套利策略（配对交易）
- 资产对筛选（代码逻辑）： 计算候选资产对的价格差平方和$ \sum_{t=1}^{T}\left(S_{i,t}-S_{j,t}\right)^{2} $，选择最小值对应的资产对（如同一行业股票）；
- 偏离判断（代码公式）： 计算价格差的均值$ E[\Delta S_t]=\frac{1}{T}\sum_{t=1}^T \Delta S_t \(、标准差\) \sigma[\Delta S_t]=\sqrt{\frac{1}{T-1}\sum_{t=1}^T (\Delta S_t-E[\Delta S_t])^2} $；
- 交易触发： 若 $ \Delta S_\tau > E[\Delta S_\tau] + 2\sigma[\Delta S_\tau] $，代码执行“卖i买j”； 若 $ \Delta S_\tau < E[\Delta S_\tau] - 2\sigma[\Delta S_\tau] $，执行“买i卖j”。
问题1解答
当Price(A,C)变为1:900时，可以盈利，操作路径为A→B→C→A，具体步骤如下：
- 1个A兑换10个B（利用A-B的1:10比例）；
- 10个B兑换1000个C（利用B-C的1:100比例，10×100=1000）；
- 1000个C兑换约1.111个A（利用A-C的1:900比例，1000/900≈1.111）。
最终盈利约0.111个A，存在套利机会。
问题2：套利检测函数实现
将资产间的兑换比例建模为有向图的汇率矩阵，通过检测“循环路径的汇率乘积是否大于1”判断套利机会。对于3个资产，需检测两种核心循环路径：A→B→C→A和A→C→B→A。
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
enum class Asset { A, B, C };
// 资产转字符串辅助函数
std::string assetStr(Asset a) {
switch (a) {
case Asset::A:
return "A";
case Asset::B:
return "B";
case Asset::C:
return "C";
default:
return "Unknown";
}
}
class ArbitrageChecker {
private:
// 汇率矩阵：rate[i][j]表示1单位资产i可兑换的资产j数量
double rate[3][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1}; // 初始化为单位矩阵
public:
// 初始化默认汇率
ArbitrageChecker() {
setRate(Asset::A, Asset::B, 1, 10); // A-B:1:10
setRate(Asset::B, Asset::C, 1, 100); // B-C:1:100
setRate(Asset::A, Asset::C, 1, 1000); // A-C:1:1000
}
// 更新交易对汇率（a单位x兑换b单位y）
void setRate(Asset x, Asset y, int a, int b) {
int xi = static_cast<int>(x);
int yi = static_cast<int>(y);
rate[xi][yi] = static_cast<double>(b) / a; // 1x换b/a y
rate[yi][xi] = static_cast<double>(a) / b; // 1y换a/b x
}
// 检测套利机会并返回操作步骤
std::vector<std::string> check() {
const double EPS = 1e-9;
std::vector<std::string> steps;
// 检测路径1：A→B→C→A
double prod1 = rate[0][1] * rate[1][2] * rate[2][0];
if (prod1 > 1.0 + EPS) {
steps.emplace_back("套利路径: A→B→C→A");
steps.emplace_back("盈利倍数: " + std::to_string(prod1 - 1.0));
steps.emplace_back("操作:");
steps.emplace_back("1. 1A → " + std::to_string(rate[0][1]) + "B");
steps.emplace_back("2. " + std::to_string(rate[0][1]) + "B → " +
std::to_string(rate[0][1] * rate[1][2]) + "C");
steps.emplace_back("3. " + std::to_string(rate[0][1] * rate[1][2]) +
"C → " + std::to_string(prod1) + "A");
return steps;
}
// 检测路径2：A→C→B→A
double prod2 = rate[0][2] * rate[2][1] * rate[1][0];
if (prod2 > 1.0 + EPS) {
steps.emplace_back("套利路径: A→C→B→A");
steps.emplace_back("盈利倍数: " + std::to_string(prod2 - 1.0));
steps.emplace_back("操作:");
steps.emplace_back("1. 1A → " + std::to_string(rate[0][2]) + "C");
steps.emplace_back("2. " + std::to_string(rate[0][2]) + "C → " +
std::to_string(rate[0][2] * rate[2][1]) + "B");
steps.emplace_back("3. " + std::to_string(rate[0][2] * rate[2][1]) +
"B → " + std::to_string(prod2) + "A");
return steps;
}
steps.emplace_back("无套利机会");
return steps;
}
};
// 测试问题1场景
int main() {
ArbitrageChecker checker;
checker.setRate(Asset::A, Asset::C, 1, 900); // 更新A-C为1:900
auto res = checker.check();
for (const auto& s : res) std::cout << s << "\n";
return 0;
}
问题3：海量交易对的回环检测
将交易对建模为有向图（节点为资产，边权重为汇率的对数），将“套利回环”转化为“正权环”检测问题（乘积>1等价于对数和>0）。由于长回环实际套利可能性低，限制回环长度（如≤5步），使用改良的贝尔曼-福特算法高效检测：
- 图建模：资产为节点，边
X→Y权重为ln(rate[X][Y])； - 短环检测：对每个节点，运行贝尔曼-福特算法检测≤5步的正权环（松弛操作次数限制为5）；
- 回环收集：记录所有检测到的正权环，去重后即为有效回环。
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
// 资产用整数ID表示
using AssetId = int;
// 有向边：from -> to，权重为ln(汇率)（方便将乘积转为求和）
struct Edge {
AssetId from;
AssetId to;
double weight; // ln(rate)，即1单位from可兑换rate单位to，weight=ln(rate)
};
// 回环结构：存储路径和盈利倍数（汇率乘积）
struct Loop {
vector<AssetId> path;
double profit_multiplier; // 路径汇率乘积（>1表示盈利）
// 用于去重的哈希函数
size_t hash() const {
size_t h = 0;
// 标准化路径：以最小资产ID为起点，顺时针排列
auto min_it = min_element(path.begin(),
path.end() - 1); // 排除最后一个（与第一个相同）
int shift = min_it - path.begin();
for (int i = 0; i < path.size() - 1; ++i) {
AssetId id = path[(shift + i) % (path.size() - 1)];
h ^= hash<AssetId>()(id) + 0x9e3779b9 + (h << 6) + (h >> 2);
}
return h;
}
// 用于去重的相等判断
bool operator==(const Loop& other) const {
if (path.size() != other.path.size()) return false;
// 检查是否为同一环的不同起点
auto find_pos = [&](AssetId id) {
for (int i = 0; i < other.path.size() - 1; ++i) {
if (other.path[i] == id) return i;
}
return -1;
};
int pos = find_pos(path[0]);
if (pos == -1) return false;
for (int i = 0; i < path.size() - 1; ++i) {
if (path[i] != other.path[(pos + i) % (other.path.size() - 1)]) {
return false;
}
}
return true;
}
};
// 为Loop提供哈希支持
namespace std {
template <>
struct hash<Loop> {
size_t operator()(const Loop& l) const { return l.hash(); }
};
} // namespace std
class ArbitrageLoopDetector {
private:
vector<Edge> edges;
unordered_set<AssetId> all_assets;
const int MAX_LOOP_LENGTH = 5; // 最大回环长度（实际套利中长环无意义）
const double EPS = 1e-8; // 浮点数精度
public:
// 添加交易对：a单位from兑换b单位to（即1单位from可兑换b/a单位to）
void addTradingPair(AssetId from, AssetId to, int a, int b) {
double rate = static_cast<double>(b) / a;
edges.push_back({from, to, log(rate)}); // 正向边权重
edges.push_back({to, from, log(static_cast<double>(a) / b)}); // 反向边权重
all_assets.insert(from);
all_assets.insert(to);
}
// 检测所有盈利回环
unordered_set<Loop> findAllLoops() {
unordered_set<Loop> loops;
// 对每个资产作为起点检测回环
for (AssetId start : all_assets) {
// 距离数组：dist[k][v]表示从start出发，经过k步到达v的最大权重和
vector<unordered_map<AssetId, double>> dist(MAX_LOOP_LENGTH + 1);
// 前驱数组：prev[k][v] = 到达v的前一个节点（用于回溯路径）
vector<unordered_map<AssetId, AssetId>> prev(MAX_LOOP_LENGTH + 1);
// 初始化：0步到达start，权重和为0
dist[0][start] = 0.0;
// 松弛操作：最多MAX_LOOP_LENGTH步
for (int k = 1; k <= MAX_LOOP_LENGTH; ++k) {
// 复制上一步的距离（不操作的情况）
dist[k] = dist[k - 1];
prev[k] = prev[k - 1];
// 遍历所有边，尝试松弛
for (const Edge& e : edges) {
AssetId u = e.from;
AssetId v = e.to;
// 如果上一步能到达u，尝试更新v
if (dist[k - 1].count(u)) {
double new_weight = dist[k - 1][u] + e.weight;
// 找到更优路径（权重和更大）
if (!dist[k].count(v) || new_weight > dist[k][v] + EPS) {
dist[k][v] = new_weight;
prev[k][v] = u;
}
}
}
// 检查是否形成回环（从start出发，k步回到start，且权重和>0）
if (dist[k].count(start) && dist[k][start] > EPS) {
// 回溯路径
vector<AssetId> path;
AssetId current = start;
int steps = k;
while (steps > 0) {
path.push_back(current);
current = prev[steps][current];
steps--;
}
path.push_back(start); // 闭合回环
reverse(path.begin(), path.end()); // 恢复正确顺序
// 计算盈利倍数（汇率乘积 = exp(权重和)）
double profit = exp(dist[k][start]);
loops.insert({path, profit});
}
}
}
return loops;
}
};
// 测试示例
int main() {
ArbitrageLoopDetector detector;
// 添加问题1中的3个交易对
detector.addTradingPair(0, 1, 1, 10); // A(0)-B(1):1:10
detector.addTradingPair(1, 2, 1, 100); // B(1)-C(2):1:100
detector.addTradingPair(0, 2, 1, 900); // A(0)-C(2):1:900（问题1场景）
// 检测回环
auto loops = detector.findAllLoops();
// 输出结果
cout << "找到" << loops.size() << "个盈利回环：" << endl;
for (const Loop& loop : loops) {
cout << "路径：";
for (AssetId id : loop.path) {
cout << (char)('A' + id) << " → ";
}
cout << "\b\b\b " << endl; // 移除最后一个" → "
cout << "盈利倍数：" << loop.profit_multiplier << "（盈利："
<< (loop.profit_multiplier - 1) << "）" << endl;
cout << "------------------------" << endl;
}
return 0;
}
问题4：高效回环存储与最大盈利查询
数据结构
- 回环结构体（Loop）：
struct Loop {
std::vector<Asset> path; // 回环路径（如[A,B,C,A]）
double profit; // 当前盈利倍数
std::vector<std::pair<Asset, Asset>> edges; // 依赖的交易对
};
-
索引结构：
-
edge_to_loops：哈希表（键为交易对(X,Y)，值为依赖该交易对的回环列表）； profit_set：有序集合（按profit降序，存储(profit, Loop*)，支持快速查询最大值）。
更新与查询流程
-
交易对更新时：
-
遍历
edge_to_loops中该交易对对应的所有回环； -
重新计算回环的
profit，并在profit_set中更新（删除旧值，插入新值）。 -
查询最大盈利：直接返回
profit_set的首个元素（O(1)复杂度）。
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// 基础类型定义
using AssetId = int; // 资产ID（整数表示，支持扩展）
using TradingPair = std::pair<AssetId, AssetId>; // 有向交易对（X→Y，区分方向）
// 资产ID转字符串
std::string assetToStr(AssetId id) { return std::string(1, 'A' + id); }
// 交易对转字符串
std::string pairToStr(const TradingPair& pair) {
return assetToStr(pair.first) + "→" + assetToStr(pair.second);
}
// 回环结构体：存储回环完整信息及依赖关系
struct Loop {
std::vector<AssetId> path; // 回环路径（如[A,B,C,A]，首尾需相同）
double profit_multiplier; // 盈利倍数（汇率乘积，>1表示盈利）
std::vector<TradingPair> edges; // 依赖的有向交易对（与path一一对应）
// 构造函数：传入路径，自动生成依赖的交易对
Loop(std::vector<AssetId> p) : path(std::move(p)) {
// 生成交易对（如路径[0,1,2,0]→[(0,1),(1,2),(2,0)]）
for (size_t i = 0; i < path.size() - 1; ++i) {
edges.emplace_back(path[i], path[i + 1]);
}
profit_multiplier = 0.0; // 初始值，后续通过汇率计算
}
// 打印回环信息（辅助调试与结果展示）
void print() const {
std::cout << "回环路径：";
for (size_t i = 0; i < path.size(); ++i) {
if (i > 0) std::cout << "→";
std::cout << assetToStr(path[i]);
}
std::cout << "\n依赖交易对：";
for (size_t i = 0; i < edges.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << pairToStr(edges[i]);
}
std::cout << "\n当前盈利倍数：" << profit_multiplier << "（盈利："
<< (profit_multiplier - 1) * 100 << "%）\n";
}
};
// 核心索引类：维护回环双索引，支持交易对更新与最大盈利查询
class ArbitrageIndex {
private:
// 1. 交易对→当前汇率（键：有向交易对，值：1单位from兑换to的数量）
std::unordered_map<TradingPair, double> rate_map;
// 2. 所有回环对象（管理内存，避免野指针）
std::vector<Loop> all_loops;
// 3. 交易对→依赖该交易对的回环指针（更新交易对时快速定位回环）
std::unordered_map<TradingPair, std::vector<Loop*>> edge_to_loops;
// 4. 盈利有序集合（按盈利倍数降序，支持O(1)查最大、O(logn)增删）
using ProfitEntry = std::pair<double, Loop*>;
std::multiset<ProfitEntry, std::greater<ProfitEntry>> profit_set;
const double EPS = 1e-8;
// 计算单个回环的当前盈利倍数（基于最新汇率）
double calculateLoopProfit(const Loop& loop) const {
double product = 1.0;
for (const auto& pair : loop.edges) {
// 若交易对未定义，返回0（标记为无效回环）
auto it = rate_map.find(pair);
if (it == rate_map.end()) return 0.0;
product *= it->second; // 汇率乘积（如A→B→C→A：rate1*rate2*rate3）
}
return product;
}
// 从profit_set中删除回环的旧盈利记录（匹配盈利倍数+回环指针）
void removeFromProfitSet(Loop* loop) {
auto it = profit_set.begin();
while (it != profit_set.end()) {
if (std::abs(it->first - loop->profit_multiplier) < EPS &&
it->second == loop) {
profit_set.erase(it);
return;
}
++it;
}
}
public:
~ArbitrageIndex() = default;
// 添加/更新有向交易对：a单位from兑换b单位to → 1单位from换b/a单位to
void updateTradingPair(AssetId from, AssetId to, int a, int b) {
TradingPair pair = {from, to};
double new_rate = static_cast<double>(b) / a;
// 情况1：首次添加交易对（仅更新汇率表，无回环依赖）
if (rate_map.find(pair) == rate_map.end()) {
rate_map[pair] = new_rate;
std::cout << "[更新交易对] " << pairToStr(pair) << "：1→" << new_rate
<< "\n";
return;
}
// 情况2：交易对已存在（更新汇率+联动更新依赖回环）
rate_map[pair] = new_rate;
std::cout << "[更新交易对] " << pairToStr(pair) << "：1→" << new_rate
<< "（触发回环盈利更新）\n";
// 找到依赖该交易对的所有回环，重新计算盈利
auto loop_it = edge_to_loops.find(pair);
if (loop_it == edge_to_loops.end()) return; // 无依赖回环，直接返回
for (Loop* loop : loop_it->second) {
removeFromProfitSet(loop); // 删除旧盈利记录
double new_profit = calculateLoopProfit(*loop); // 计算新盈利
loop->profit_multiplier = new_profit; // 更新回环盈利
profit_set.emplace(new_profit, loop); // 插入新盈利记录
std::cout << " - 回环更新：";
loop->print();
}
}
// 添加新回环：需传入合法路径（首尾相同、长度≥3）
void addLoop(const std::vector<AssetId>& path) {
// 验证路径合法性（排除[A,B,A]等无效路径）
if (path.size() < 3 || path.front() != path.back()) {
std::cerr << "[错误] 无效回环路径（需首尾相同且长度≥3）\n";
return;
}
// 1. 存储回环对象并获取指针
all_loops.emplace_back(path);
Loop* new_loop = &all_loops.back();
// 2. 计算初始盈利并维护双索引
double init_profit = calculateLoopProfit(*new_loop);
new_loop->profit_multiplier = init_profit;
// 3. 关联交易对与回环（更新edge_to_loops）
for (const auto& pair : new_loop->edges) {
edge_to_loops[pair].push_back(new_loop);
}
// 4. 加入盈利有序集合
profit_set.emplace(init_profit, new_loop);
std::cout << "[添加回环成功]：\n";
new_loop->print();
}
// 查询当前最大盈利回环（返回nullptr表示无有效盈利回环）
const Loop* getMaxProfitLoop() const {
if (profit_set.empty()) {
std::cout << "[查询结果] 无有效回环\n";
return nullptr;
}
// 取盈利最大的记录（profit_set按降序排列，首元素即最大）
const auto& max_entry = *profit_set.begin();
if (max_entry.first <= 1.0 + EPS) {
std::cout << "[查询结果] 无盈利回环（最大盈利倍数：" << max_entry.first
<< " ≤ 1）\n";
return nullptr;
}
std::cout << "[查询结果] 最大盈利回环：\n";
max_entry.second->print();
return max_entry.second;
}
// 打印所有回环当前状态（辅助调试）
void printAllLoops() const {
if (all_loops.empty()) {
std::cout << "[打印所有回环] 无回环\n";
return;
}
std::cout << "[打印所有回环] 共" << all_loops.size() << "个回环：\n";
for (const auto& loop : all_loops) {
loop.print();
std::cout << "------------------------\n";
}
}
};
// 模拟交易对更新、回环添加与最大盈利查询
int main() {
// 1. 初始化索引对象
ArbitrageIndex arbitrage_index;
std::cout << "=== 初始化完成 ===" << "\n\n";
// 2. 添加3个资产的基础交易对（A=0, B=1, C=2）
std::cout << "=== 步骤1：添加基础交易对 ===" << "\n";
arbitrage_index.updateTradingPair(0, 1, 1, 10); // A→B：1A换10B
arbitrage_index.updateTradingPair(1, 2, 1, 100); // B→C：1B换100C
arbitrage_index.updateTradingPair(2, 0, 1, 0.0012); // C→A：1C换0.0012A
std::cout << "\n";
// 3. 添加2个核心回环（A→B→C→A 和 A→C→B→A）
std::cout << "=== 步骤2：添加回环 ===" << "\n";
arbitrage_index.addLoop({0, 1, 2, 0}); // 回环1：A→B→C→A
arbitrage_index.addLoop({0, 2, 1, 0}); // 回环2：A→C→B→A
std::cout << "\n";
// 4. 查询初始最大盈利回环
std::cout << "=== 步骤3：查询初始最大盈利回环 ===" << "\n";
arbitrage_index.getMaxProfitLoop();
std::cout << "\n";
// 5. 更新交易对汇率（模拟市场波动，创造套利）
std::cout << "=== 步骤4：更新C→A汇率（1C换0.0013A） ===" << "\n";
arbitrage_index.updateTradingPair(2, 0, 1, 0.0013);
std::cout << "\n";
// 6. 再次查询最大盈利回环（此时回环1应盈利）
std::cout << "=== 步骤5：查询波动后的最大盈利回环 ===" << "\n";
arbitrage_index.getMaxProfitLoop();
std::cout << "\n";
// 7. 打印所有回环状态
std::cout << "=== 步骤6：打印所有回环当前状态 ===" << "\n";
arbitrage_index.printAllLoops();
return 0;
}
// 支持更多资产：只需扩展AssetId（如 3=D、4=E），无需修改核心逻辑。
// 支持更长回环：添加回环时只需传入更长的合法路径（如
// [A,B,C,D,A]），索引会自动适配。
// 性能优化：若资产和回环数量极大，profit_set使用boost::container::flat_set提升缓存效率，
// 或对edge_to_loops使用哈希表分段存储。
问题5：冲击成本下的最大盈利算法
冲击成本导致收益率随投入量递增而递减，但绝对收益可能呈单峰分布（先增后减）。通过三分法在投入区间[0,1000]内寻找最优投入量：
- 冲击成本建模：定义函数
f(X→Y, x)表示投入x单位X可获得的Y数量（边际递减）； - 绝对收益函数：对回环
X1→X2→...→Xk→X1，投入a单位X1的绝对收益为：
- 三分法优化：由于
R(a)为单峰函数，通过迭代缩小区间找到最大值点。
// 冲击成本函数（基础汇率*投入量/(1+冲击系数*投入量)）
double冲击成本(Asset from, Asset to, double x, double base_rate) {
const double k = 0.001; // 冲击系数
return base_rate * x / (1 + k * x);
}
// 计算回环绝对收益
double calcProfit(const Loop& loop, double a,
const std::vector<double>& base_rates) {
double current = a;
for (size_t i = 0; i < loop.path.size() - 1; ++i) {
current = 冲击成本(loop.path[i], loop.path[i + 1], current, base_rates[i]);
}
return current - a;
}
// 三分法寻找最大盈利
double findMaxProfit(const Loop& loop, const std::vector<double>& base_rates) {
double left = 0.0, right = 1000.0;
for (int i = 0; i < 100; ++i) { // 迭代精度控制
if (right - left < 1e-6) break;
double m1 = left + (right - left) / 3;
double m2 = right - (right - left) / 3;
double p1 = calcProfit(loop, m1, base_rates);
double p2 = calcProfit(loop, m2, base_rates);
if (p1 < p2)
left = m1;
else
right = m2;
}
return calcProfit(loop, (left + right) / 2, base_rates);
}