当前位置:

首页 > 编程开发 > 高效计算任意时间点未平仓股份数量:基于扫描线与二分查找的优化方案

高效计算任意时间点未平仓股份数量:基于扫描线与二分查找的优化方案

采用扫描线思想,将订单生命周期拆分为起始与终止事件,排序后计算前缀累积,结合二分查找实现任意时刻未平仓股份数的高效查询,复杂度从O(m×n)降至O(nlogn+mlogn)。

本文目录
    今天聊一个在金融高频场景中很常见的需求:如何快速计算任意时刻的未平仓股份数量?通过事件点预处理 + 前缀累积 + 二分查找,可以把复杂度从 O(m×n) 降到 O(n log n + m log n),轻松应对批量查询。

    在高频交易、订单簿快照或实时风控等场景中,经常需要问这样一个问题:某个时刻,还有多少订单处于“活跃”状态(即已创建但尚未取消或成交)?这些订单对应的总股份数是多少?

    如果直接遍历所有订单,对每个查询都判断时间区间是否包含该时刻——即暴力解法——复杂度是 O(m×n)。订单量 n 一上来,查询量 m 一多,性能立刻崩盘。

    更好的解法其实源自一个经典思想:扫描线(Sweep Line)。把每个订单的生命周期拆成两个事件:

    • 起始事件:在 created_at 时刻,+shares(新增未平仓股份);
    • 终止事件:在 cancelled_or_executed_at 时刻,−shares(移除未平仓股份)。

    注意:这里的区间定义为 [created_at, cancelled_or_executed_at) —— 左闭右开。也就是说,在终止事件发生的那个时刻,该订单已经不再活跃,所以减法操作应该在这个时间点生效。

    然后,把所有事件按时间戳升序排序,计算时间轴上的累积未平仓股份前缀和。这实际上会形成一个非递减的分段常数函数(step function)。对于任意查询时间 q,只需要找到它左侧最近的事件点,就能拿到该时刻的实时未平仓总量。

    下面是用 Python 的 bisect 模块实现的版本,查询部分只需 O(log n):

    from bisect import bisect
    
    def calculate_outstanding_shares(orders, queries):
        # Step 1: 构建事件列表 (timestamp, delta_shares)
        events = []
        for order in orders:
            _, shares, _, _, created_at, executed_at = order
            events.append((created_at, shares))
            events.append((executed_at, -shares))
    
        # Step 2: 按时间戳排序(时间相同时,按 delta 排序可保证逻辑一致;此处默认 -shares 在 +shares 后不影响结果)
        events.sort(key=lambda x: (x[0], x[1]))
    
        # Step 3: 构造前缀累积数组:[(t0, s0), (t1, s1), ..., (tk, sk)]
        # 其中 si 表示在时间 ti(含)之后、ti+1(不含)之前的未平仓总量
        cum_shares = []
        curr = 0
        for t, delta in events:
            curr += delta
            cum_shares.append((t, curr))
    
        # Step 4: 对每个 query_time,二分查找最后一个 ≤ query_time 的事件点
        result = {}
        for q in queries:
            # bisect 返回插入位置,减1即为最右匹配索引
            idx = bisect(cum_shares, (q, float('inf'))) - 1
            if idx < 0:
                result[q] = 0  # 查询时间早于所有事件
            else:
                result[q] = cum_shares[idx][1]
        return result
    
    # 示例验证
    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, 1500, 2500, 3500, 5500]
    print(calculate_outstanding_shares(orders, queries))
    # 输出:{500: 10, 1500: 30, 2500: 45, 3500: 50, 5500: 25}

    这招的核心优势在哪里?

    • 预处理 O(n log n):一次排序加一次线性扫描,搞定。
    • 单次查询 O(log n):用 bisect 在有序事件数组中快速定位,效率极高。
    • 空间 O(n):只存 2n 个事件及其累积值,内存友好。
    • 支持离线批量查询:日终批量快照、回测分析等场景,批量丢进去,一把出结果。

    实际使用中需要注意几点:

    • 如果存在同一时刻多个事件(比如多个订单同时创建或结束),上面排序时 key=(t, delta) 可以保证先加后减的逻辑正确(因为 +shares 数值上大于 −shares)。更严谨的做法是显式规定:创建事件优先于终止事件,比如用 (t, 0) 和 (t, 1) 区分。
    • 生产环境中建议封装成类,支持增量更新,比如流式订单接入时能动态维护。
    • C++ 里可以用 std::vector> + std::sort + std::upper_bound 实现完全相同的效果。

    这个方法本质上把“区间覆盖求和”问题,转化成了“事件驱动的阶梯函数建模”。它不仅是计算几何里的经典技巧,在日志分析、金融系统中也属于一类非常实用的优化范式。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    悟空浏览器怎么彻底清理浏览器配置文件
    悟空浏览器怎么彻底清理浏览器配置文件

    彻底清理悟空浏览器的数据,通常有三个路径:通过手机系统设置能一次性清除所有配置和用户信息;利用浏览器内置功能,可以只清理缓存而保留个性化设置;最彻底的则是卸载重装,让应用回到初始状态。 悟空浏览器用久了,是不是偶尔会感觉变慢,或者出现一些难以解释的小毛病?有时候,与其一个个排查问题,不如来一次彻底的

    漫蛙漫画官网首页登录入口
    漫蛙漫画官网首页登录入口

    漫蛙漫画首页登录入口https://www.manwamh.top/:一触即达的漫画世界核心枢纽 对于漫画迷而言,找到那个可靠的资源门户至关重要。漫蛙漫画的首页登录入口,正是这样一个核心渠道。通过它,你可以直接跳转到漫蛙2漫画APP的下载页面,轻松几步完成安装,马上就能投入到精彩纷呈的漫画之旅中。 漫蛙漫画首页登录入口: 官方入口地址已经为你备好

    漫蛙漫画官方入口
    漫蛙漫画官方入口

    漫蛙漫画官方入口与核心功能解析 寻找一个稳定、资源丰富的漫画在线阅读平台,是许多漫画爱好者的共同需求。其中,漫蛙漫画官方入口及其免费全集服务,受到了不少关注。那么,这个平台究竟如何?下面,我们就来深入了解一下它的具体信息与特色功能。 平台的官方访问地址是:https://www.manwa123.c

    漫蛙动漫APP最新版本下载
    漫蛙动漫APP最新版本下载

    对于动漫爱好者而言,找到一个资源全、体验佳的追番平台,常常是件头疼事。漫蛙动漫APP的定位很明确:就是要打造一个聚合全球正版动漫资源的专属乐园。无论是当季火爆的日漫新番、值得回味的经典国创,还是那些小众却精彩的优质动画,在这里基本都能一网打尽。平台底层采用了智能缓冲技术,最大程度保证了播放的流畅度,

    漫蛙官网入口免费下载最新版
    漫蛙官网入口免费下载最新版

    想要获取正版manwa漫蛙APP?官方指定下载渠道就是漫蛙官网入口。 对于漫画迷而言,找到一款心仪的阅读神器至关重要。漫蛙APP正是这样一款专为全球漫画爱好者打造的平台,它汇聚了从日韩人气连载到本土原创精品的海量资源。说它“应有尽有”毫不为过。更重要的是,其界面设计清爽直观,搭配智能检索功能,能让用

    漫蛙漫画在线观看入口
    漫蛙漫画在线观看入口

    想要畅享海量正版漫画资源?漫蛙漫画平台不容错过 对于漫画迷来说,找到一个资源丰富、体验流畅的正版平台实属幸事。漫蛙漫画凭借其优质的在线阅读服务,已经成为了许多资深读者的心头好。今天,我们就来详细拆解一下平台的访问方法与实用技巧,助你轻松开启漫画之旅。 漫蛙漫画网页入口页面指南 想立刻体验?官方在线观

    漫蛙如何下载最新版本
    漫蛙如何下载最新版本

    漫蛙漫画网APP官方下载方法全解析 对于资深漫画迷来说,找到一个资源全、更新快、体验佳的阅读平台,就像淘到了宝藏。漫蛙漫画网APP,正是这样一个专为爱好者打造的精品集散地。它汇聚了全球优质的正版漫画,从火爆的日漫连载到崛起的国创佳作,平台都能做到实时同步更新。当然,第一步得先把它装到设备上。接下来,

    漫蛙漫画APP最新版本下载
    漫蛙漫画APP最新版本下载

    漫蛙漫画APP:专业漫画阅读工具的全面革新 作为一款专业的漫画阅读工具,漫蛙漫画APP整合了全球优质漫画资源,其升级版漫蛙2在功能与体验上可谓全面革新。这款应用不仅囊括日漫经典与国漫新作,更通过简洁直观的界面设计和流畅操作,为用户打造沉浸式阅读环境,充分满足各类漫画爱好者的多样化需求。 漫蛙漫画特色

    卖茶叶妈妈3d漫蛙安卓版下载
    卖茶叶妈妈3d漫蛙安卓版下载

    当下动漫圈热议的卖茶叶妈妈3d漫蛙下载,凭借其突破性的3D视觉技术成为焦点 最近动漫爱好者们都在讨论一个现象级产品——卖茶叶妈妈3d漫蛙下载。这款由漫蛙漫画平台倾力打造的3D作品专区,用立体建模与动态分镜彻底颠覆了传统二维漫画的阅读模式。你猜怎么着?现在只需通过专区提供的便捷下载通道,无论是热血冒险

    漫蛙下载最新版本
    漫蛙下载最新版本

    漫蛙APP:资深漫画迷的移动图书馆与阅读利器 对于漫画爱好者来说,找到一个资源全、体验好的阅读平台,从来都不是件容易的事。而漫蛙APP,恰恰就是为这个需求而生的。它凭借海量的正版漫画库和极其便捷的离线下载功能,在圈内积累了相当不错的口碑。更重要的是,从经典的日本热血漫到新兴的国产原创作品,它几乎一网

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。