c++ - 数据结构 : insert(id, 值)、delete(id) 和 getMax()

Question

我必须设计一个订单簿 数据结构，允许我查询已插入但尚未删除的订单的最高价格。插入和删除操作在文件中预先给出，其中每个操作看起来像以下两个操作之一:

• TIMESTAMP insert ID PRICE
• TIMESTAMP 删除 ID

其中 ID 是一个顺序的整数标识符，时间戳始终按递增顺序排列，每个 ID 恰好出现两次:一次在插入操作中，一次在删除操作中，按此顺序。

从这个操作列表中，我需要输出最高价格的时间加权平均值。

---

例如，假设我们有以下输入:
10 I 1 10
20 I 2 13
22 I 3 13
24 E 2
25 E 3
40 E 1
我们可以说在ith之后操作，最大是 10, 13, 13, 13, 10时间加权平均值是 10*(20-10) + 13*(22-20) + 13*(24-22)+13*(25-24)+10*(40-25) = 10.5因为10是时间戳 [10-20] 之间的最高价格和 [25,40]其余 13 人。

我正在考虑使用 unordered_map<ID,price>和一个 multiset<price>支持:

• 插入 O(log(n))
• 删除 O(log(n))
• getMax 在 O(1)

这是我想出的一个例子:

struct order {
  int timestamp, id;
  char type;
  double price;
};

unordered_map<uint, order> M;
multiset<double> maxPrices;
double totaltime = 0;
double avg = 0;
double lastTS = 0;

double getHighest() {
  return !maxPrices.empty() ? *maxPrices.rbegin()
                            : std::numeric_limits<double>::quiet_NaN();
}

void update(const uint timestamp) {
  const double timeLeg = timestamp - lastTS;
  totaltime += timeLeg;
  avg += timeLeg * getHighest();
  lastTS = timestamp;
}

void insertOrder(const order& ord) {
  if (!maxPrices.empty()) {
    if (ord.price >= getHighest()) {
      // we have a new maxPrice
      update(ord.timestamp);
    }

  } else  // if there are not orders this is the mex for sure
    lastTS = ord.timestamp;

  M[ord.id] = ord;
  maxPrices.insert(ord.price);
}

void deleteOrder(
    const uint timestamp,
    const uint id_ord) {  // id_ord is assumed to exists in both M and maxPrices
  order ord = M[id_ord];
  if (ord.price >= getHighest()) {
    update(timestamp);
  }
  auto it = maxPrices.find(ord.price);
  maxPrices.erase(it);
  M.erase(id_ord);
}

这种方法的复杂度为 nlogn其中 n是活跃订单数。

有没有更快的渐近和/或更优雅的方法来解决这个问题？

Answer 1

我建议您采用数据库 方法。

将所有记录放入 std::vector .

创建索引表，std::map</* key type */, size_t> ，它将包含一个键值和 vector 中记录的索引。如果您希望键按降序排序，还需要提供一个比较仿函数。

此策略允许您创建许多索引表而无需重新排序所有数据。该 map 将为您的 key 提供良好的搜索时间。您还可以遍历映射以按顺序列出所有键。

注意:对于现代计算机，您可能需要大量数据才能在二分搜索( map )和线性搜索( vector )之间提供显着的时间改进。