如何避免在低延遲環境中重新分配？

Question

在交易平臺（低延遲環境）的訂單中，您需要存儲每個訂單ID，至少要驗證每個訂單是唯一的。您在交易日可以獲得的訂單ID數量是無限的。除了使用歷史數據分析之外，沒有數字可以適當地「猜測」來預先分配數據結構。有什麼方案可以避免日間訂單ID容器重新分配？

Answer 1

在交易平臺（低延遲環境）的訂單中，您需要存儲每個訂單ID，至少要驗證每個訂單的唯一性。您在交易日可以獲得的訂單ID數量是無限的。除了使用歷史數據分析之外，沒有數字可以適當地「猜測」來預先分配數據結構。有什麼方案可以避免日間訂單ID容器重新分配？

好問題。一種解決方案是使用樹形數據結構，其中每個分支是獨立的堆分配。這就是大多數純功能數據結構（例如OCaml和F＃中的Set和Map）如何工作的原因，它使它們增量，因此插入和刪除總是O（最壞情況是O（日誌n））。