求高效实现英国资本利得税（CGT）计算算法的技术指引

我正在尝试根据英国税务海关总署（HMRC）的规则实现英国资本利得税（CGT）的计算算法（或伪代码），但一直没能设计出高效低循环的方案。已经多方搜索并尝试自行实现，都没成功。以下是详细需求：

交易数据示例 #

id  action  amount  per share  total  date
1   buy     2000    £1         £2000  2017-05-05 10:00
2   buy     1000    £1         £1000  2017-05-10 10:00
3   buy     1000    £1.5       £1500  2017-06-01 10:00
4   sell    2000    £2.5       £5000  2017-06-01 10:00
5   sell    1000    £2         £2000  2017-06-01 10:00
6   buy     1500    £0.5       £750   2017-06-20 10:00

HMRC匹配规则 #

需严格遵循以下优先级顺序匹配卖出股份：

• 卖出交易首先按FIFO匹配同日买入交易
• 其次按FIFO匹配卖出后30天内的买入交易（Bed and Breakfast规则）
• 最后匹配过往平均买入的Section 104持仓

手动计算结果 #

1. 交易1+2合并为Section 104持仓：总计3000股，总成本£3000（每股£1）
2. 交易3因同日存在卖出交易，暂不合并到Section 104持仓：
   • 卖出交易4的2000股中，1000股匹配同日买入交易3：
     • 成本：1000股@£1.5 = £1500，收益：1000*£2.5 - £1500 = £1000
   • 卖出交易4剩余1000股匹配卖出后30天内的买入交易6：
     • 成本：1000股@£0.5 = £500，收益：1000*£2.5 - £500 = £2000
   • 卖出交易4总应税收益：£1000 + £2000 = £3000
3. 卖出交易5无法匹配买入交易3（已耗尽）：
   • 卖出交易5的1000股中，500股匹配买入交易6剩余股份：
     • 成本：500股@£0.5 = £250，收益：500*£2 - £250 = £750
   • 剩余500股匹配合并持仓（交易1+2）：
     • 成本：500股@£1 = £500，收益：500*£2 - £500 = £500
   • 卖出交易5总应税收益：£750 + £500 = £1250

总应税收益：£3000 + £1250 = £4250
剩余持仓：2500股，总成本£2500

我的初步伪代码思路 #

- 按时间顺序遍历所有交易
- 如果是卖出交易：
  - 检查是否有同日买入交易可匹配
  - 检查卖出后30天内的买入交易（Bed and Breakfast）
  - 如果以上匹配不足，使用现有Section 104持仓填充
- 如果是买入交易：
  - 添加到"same_day"数组
  - 次日遍历"same_day"数组，合并到Section 104持仓
  - 用交易ID索引的字典保存每个交易，以便匹配时扣除股份

高效算法设计技术指引 #

你的思路已经有了核心框架，我们可以通过优化数据结构和处理流程来减少循环次数，实现高效计算：

1. 数据结构选型：避免全局遍历 #

• 按日期分组存储：提前将交易按日期（yyyy-mm-dd）分组，用字典<日期, 交易列表>存储，处理卖出时直接取同日买入组，无需全局遍历。
• Bed and Breakfast滑动池：维护一个按买入时间排序的队列，只保留当前卖出日期后30天内的买入交易。处理完每个卖出后，自动移除超过30天的交易到Section 104。
• Section 104极简维护：不用保存每笔历史买入，只维护总股数和总成本两个字段，平均成本直接通过总成本/总股数计算，所有操作都是O(1)。

2. 实时处理流程：一次遍历完成所有匹配 #

不用先预处理所有买入再处理卖出，而是按时间顺序实时处理每笔交易，同时维护三个核心状态：

• same_day_buys：当日未匹配的买入交易（FIFO顺序，保留剩余股数）
• bed_and_breakfast_pool：符合Bed and Breakfast规则的未匹配买入交易（按时间排序）
• section_104：总持仓（总股数、总成本）

优化后的伪代码

# 初始化状态
same_day_buys = []  # 元素：{"amount": int, "cost_per_share": float, "remaining": int, "date": str}
bed_and_breakfast_pool = []
section_104 = {"total_shares": 0, "total_cost": 0.0}
total_taxable_gain = 0.0

# 按时间戳升序排序所有交易（确保同日交易顺序正确）
sorted_trades = sorted(all_trades, key=lambda t: t["date"])

from datetime import datetime, timedelta

def parse_date(date_str):
    return datetime.strptime(date_str, "%Y-%m-%d %H:%M")

for trade in sorted_trades:
    if trade["action"] == "buy":
        current_date = trade["date"].split(" ")[0]
        # 切换日期时，将前日未匹配的同日买入合并到Section 104
        if same_day_buys and same_day_buys[0]["date"].split(" ")[0] != current_date:
            for buy in same_day_buys:
                section_104["total_shares"] += buy["remaining"]
                section_104["total_cost"] += buy["remaining"] * buy["cost_per_share"]
            same_day_buys = []
        # 添加到同日买入列表
        same_day_buys.append({
            "amount": trade["amount"],
            "cost_per_share": float(trade["per_share"].replace("£", "")),
            "remaining": trade["amount"],
            "date": trade["date"]
        })
        # 添加到Bed and Breakfast池
        bed_and_breakfast_pool.append({
            "amount": trade["amount"],
            "cost_per_share": float(trade["per_share"].replace("£", "")),
            "remaining": trade["amount"],
            "date": trade["date"]
        })
        # 保持Bed and Breakfast池按时间排序
        bed_and_breakfast_pool.sort(key=lambda x: x["date"])
    
    else:  # sell交易
        sell_amount = trade["amount"]
        sell_price = float(trade["per_share"].replace("£", ""))
        sell_date_obj = parse_date(trade["date"])
        thirty_days_later = sell_date_obj + timedelta(days=30)

        # 第一步：匹配同日买入
        while sell_amount > 0 and same_day_buys:
            buy = same_day_buys[0]
            match_qty = min(sell_amount, buy["remaining"])
            # 计算收益
            gain = match_qty * (sell_price - buy["cost_per_share"])
            total_taxable_gain += gain
            # 更新剩余股数
            buy["remaining"] -= match_qty
            sell_amount -= match_qty
            # 移除已耗尽的买入交易
            if buy["remaining"] == 0:
                same_day_buys.pop(0)
        
        # 第二步：匹配Bed and Breakfast交易
        # 过滤出30天内的有效交易，按FIFO处理
        valid_bnb = [b for b in bed_and_breakfast_pool if parse_date(b["date"]) <= thirty_days_later]
        for buy in valid_bnb:
            if sell_amount <= 0:
                break
            match_qty = min(sell_amount, buy["remaining"])
            gain = match_qty * (sell_price - buy["cost_per_share"])
            total_taxable_gain += gain
            buy["remaining"] -= match_qty
            sell_amount -= match_qty
        
        # 清理Bed and Breakfast池：移除已耗尽或超过30天的交易
        bed_and_breakfast_pool = [
            b for b in bed_and_breakfast_pool 
            if b["remaining"] > 0 and parse_date(b["date"]) <= thirty_days_later
        ]
        
        # 第三步：匹配Section 104持仓
        if sell_amount > 0 and section_104["total_shares"] > 0:
            avg_cost = section_104["total_cost"] / section_104["total_shares"]
            gain = sell_amount * (sell_price - avg_cost)
            total_taxable_gain += gain
            # 更新Section 104持仓
            section_104["total_shares"] -= sell_amount
            section_104["total_cost"] -= sell_amount * avg_cost

# 处理最后一天的同日买入，合并到Section 104
if same_day_buys:
    for buy in same_day_buys:
        section_104["total_shares"] += buy["remaining"]
        section_104["total_cost"] += buy["remaining"] * buy["cost_per_share"]

# 输出结果
print(f"总应税收益: £{total_taxable_gain:.2f}")
print(f"剩余持仓: {section_104['total_shares']}股，总成本£{section_104['total_cost']:.2f}")

3. 关键效率提升点 #

• 线性时间复杂度：所有交易仅遍历一次，排序的时间复杂度为O(n log n)，其余操作均为O(1)或O(k)（k为当日/30天内的交易数，远小于n）。
• 避免无效循环：仅处理剩余股数>0的交易，无需反复遍历已耗尽的买入记录。
• Section 104极简操作：通过总股数和总成本直接计算平均成本，避免遍历所有历史买入交易。

内容的提问来源于stack exchange，提问作者sof2er