memory-management - 在低延迟环境中如何避免重新分配？

Question

在交易平台（低延迟环境）的订单簿中，您需要存储每个订单 ID，至少要验证每个订单都是唯一的。您在一个交易日内可以收到的订单 ID 数量是无限的。除了使用历史数据分析之外，没有任何数字可以让您适当地“猜测”来预先分配您的数据结构。有哪些方案可以避免当日订单 ID 容器重新分配？

Answer 1

在交易平台（低延迟环境）的订单簿中，您需要存储每个订单 ID，至少要验证每个订单都是唯一的。您在一个交易日内可以收到的订单 ID 数量是无限的。除了使用历史数据分析之外，没有任何数字可以让您适当地“猜测”来预先分配您的数据结构。有哪些方案可以避免当日订单 ID 容器重新分配？

好问题。一种解决方案是使用树数据结构，其中每个分支都是单独的堆分配。这就是大多数纯函数式数据结构（例如Set，Map在 OCaml 和 F# 中）的工作方式，它使它们递增，因此插入和删除总是 O(log n ) 最坏的情况。