每次查询已发行股票数量

Question

我遇到了这个问题，我能够解决它，但效率低下。我的解决方案是一个简单的 o(m*n)，其中 m 是查询数量，n 是订单数量。

您将获得我们交易发送的订单日志（std：向量） 系统一天多。每个订单都具有以下属性：

• order_token：标识订单的唯一整数
• 股票：买入或卖出的股票数量
• 价格：买入或卖出每股的价格
• 侧：假=卖出，真=买入
• 创建时间：订单创建时的时间戳
• cancelled_or_executed_at: 下单时的时间戳 被取消或执行（已填）

该时段内订单已生效 [创建时间、取消时间或执行时间）。也就是说，创建于 包含且cancelled_or_execulated_at 是排除的。时间戳是 表示为整数，例如自午夜以来的毫秒数。您可以 假设每个订单都被取消或全部执行。

除了 订单时，您还会获得一个查询向量。每个查询都有一个 字段：query_time，时间戳。查询的答案是总数 所有订单中已发行的股票数量 查询时间。已发行股票无论时间如何都会汇总，例如 实时未平仓订单买入 10 股和卖出 10 股总计 20 股。

我想知道是否有人有更好的方法来使用任何数据结构或算法来优化我的解决方案。我确信有。这是一个 C++ 问题，但为了方便我用 python 做了我的解决方案

def calculate_outstanding_shares(orders, queries):
    result = {}

    for query in queries:
        live_trades = 0
        for order in orders:
            if query > order[4] and query < order[5]:
                live_trades += order[1]
                
        result[query] = live_trades

    return result


# Example usage
orders = [
    [3, 15, 200, True, 2000, 4000],
    [1,10,100,True,0,5000],
    [4, 25, 250, False, 2500, 6000],
    [2,20,150,False,1000,3000],
]

queries = [
    500,  # Before any order
    1500,  # Inside the duration of the first buy order
    2500,  # Inside the duration of both buy orders and the start of the second sell order
    3500,  # Inside the duration of the second sell order and after the first sell order ends
    5500  # After all orders have ended
]

result = calculate_outstanding_shares(orders, queries)
print(result)

Answer 1

您可以预处理

orders

列表，并在每个时间点（开始/结束）计算实际已发行股票数量。

然后对于每个查询，使用

bisect

模块搜索正确的时间位置。这样您只需执行

m

*

log n

查询。

from bisect import bisect


def calculate(orders, queries):
    outstanding_shares = []

    for a, b, c, d, e, f in orders:
        outstanding_shares.append((e, b))
        outstanding_shares.append((f, -b))

    outstanding_shares.sort()

    c = 0
    outstanding_shares = [(t, (c := c + amt)) for t, amt in outstanding_shares]

    return {
        q: outstanding_shares[bisect(outstanding_shares, (q,)) - 1][1] for q in queries
    }


# Example usage
orders = [
    [3, 15, 200, True, 2000, 4000],
    [1, 10, 100, True, 0, 5000],
    [4, 25, 250, False, 2500, 6000],
    [2, 20, 150, False, 1000, 3000],
]

queries = [
    500,  # Before any order
    1500,  # Inside the duration of the first buy order
    2500,  # Inside the duration of both buy orders and the start of the second sell order
    3500,  # Inside the duration of the second sell order and after the first sell order ends
    5500,  # After all orders have ended
]

print(calculate(orders, queries))

打印：

{500: 10, 1500: 30, 2500: 45, 3500: 50, 5500: 25}

Answer 2

我认为在 Ruby 中添加一个答案可能会很有用，它可以被视为伪代码并且可以轻松适应任何语言。

orders = [
  [3, 15, 200,  'True', 2000, 4000],
  [1, 10, 100,  'True',    0, 5000],
  [4, 25, 250, 'False', 2500, 6000],
  [2, 20, 150, 'False', 1000, 3000],
]

第1步：保存起始余额并创建一个散列，其键是地点日期或清除日期，其值是关联的股票数量

balance = 0
epochs = {}
orders.each do |_, shares, _, _, place_date, clear_date|
  if place_date == 0
    balance = shares
  else
    add_to_epochs(epochs, place_date, shares)
  end
  add_to_epochs(epochs, clear_date, -shares)
end

balance
  #=> 10
epochs
  #=> {2000=> 15, 4000=>-15, 5000=>-10, 2500=>25,
  #    6000=>-25, 1000=> 20, 3000=>-20}

步骤 2 创建一个排序日期数组，并将

epoch

值转换为该纪元内的实时订单数

sorted_dates = epochs.keys.sort
  #=> [1000, 2000, 2500, 3000, 4000, 5000, 6000]

sorted_dates.map do |d|
  new_balance = balance + epochs[d]
  epochs[d] = balance
  balance = new_balance
end

epochs
  #=> {2000=>30, 4000=>50, 5000=>35, 2500=>45, 6000=>25, 1000=>10, 3000=>70}

步骤 3 对于每个查询，使用二分搜索来计算相关期间的结束日期，并返回该日期的

epoch

值

例如，如果查询是

3500

，二分查找将返回

d

的最小值

sorted_dates

，使得

d >= 3500

:

sorted_dates.bsearch { |d| d >= 3500 }
  #=> 4000
epochs[4000]
  #=> 50 live orders at time 3500

大多数每种语言都有一种执行二分搜索的方法或函数，并且无论如何编写一个方法或函数都很简单。二分查找的时间效率是 (log n)。

我们现在可以计算

queries

每个元素的实时订单数量：

queries.each do |q|
  alive = epochs[sorted_dates.bsearch { |d| d >= q }]
  puts "#{q}:  #{alive}"
end

显示以下内容。

 500:  10
1500:  30
2500:  45
3500:  50
5500:  25