通过与 Jira 对比,让您更全面了解 PingCode

  • 首页
  • 需求与产品管理
  • 项目管理
  • 测试与缺陷管理
  • 知识管理
  • 效能度量
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案

25人以下免费

目录

需要存储行情的tick数据,什么样的数据结构查找起来比较快

需要存储行情的tick数据,查找起来比较快的数据结构有:1、哈希表;2、平衡树。哈希表是一种基于哈希函数实现的数据结构,使用哈希函数可以将数据映射到一个固定长度的数组中,从而实现常数时间内的查找、插入和删除操作。

一、需要存储行情的tick数据,查找起来比较快的数据结构

1、哈希表

哈希表是一种基于哈希函数实现的数据结构,使用哈希函数可以将数据映射到一个固定长度的数组中,从而实现常数时间内的查找、插入和删除操作。在存储行情tick数据时,可以将每个tick的时间戳作为键,将其余信息作为值进行存储。这样可以在需要查找某个时间点的tick数据时,通过时间戳快速定位到对应的tick数据。

哈希表的特点:

  • 访问速度很快:由于散列表有散列函数,可以将指定的 Key 都映射到一个地址上,所以在访问一个 Key(键)对应的 Value(值)时,根本不需要一个一个地进行查找,可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时,速度都很快。
  • 需要额外的空间:首先,散列表实际上是存不满的,如果一个散列表刚好能够存满,那么肯定是个巧合。而且当散列表中元素的使用率越来越高时,性能会下降,所以一般会选择扩容来解决这个问题。另外,如果有冲突的话,则也是需要额外的空间去存储的,比如链地址法,不但需要额外的空间,甚至需要使用其他数据结构。
  • 无序:散列表还有一个非常明显的特点,那就是无序。为了能够更快地访问元素,散列表是根据散列函数直接找到存储地址的,这样我们的访问速度就能够更快,但是对于有序访问却没有办法应对。
  • 可能会产生碰撞:没有完美的散列函数,无论如何总会产生冲突,这时就需要采用冲突解决方案,这也使散列表更加复杂。通常在不同的高级语言的实现中,对于冲突的解决方案不一定一样。

2、平衡树

平衡树包括红黑树、AVL树等,它们可以帮助我们保持数据的有序性。在存储tick数据时,可以按照时间戳为键进行排序,在需要查找某个时间段内的tick数据时,可以利用平衡树的查找时间为对数级别的特点,快速定位到对应的tick数据。

平衡二叉树的特点:

  • 非叶子节点非常多拥有两个子节点;
  • 非叶子节值大于左边子节点、小于右边子节点;
  • 树的左右两边的层级数相差不会大于1;
  • 没有值相等重复的节点。

二、tick数据简介

Tick Data本身并不神秘,就是交易所把每只股票(亦或是futures options)的active order book(你的委托还存在在交易所里面,但并且没有成交)里面的买、卖的单的情况发给你。Tick 一般是指 Best Bid/Offer 的变化,就是 Order Book 上优异的买单和卖单发生的变化。Tick 2 和 Tick 1 的不同就在于 Best Offer 的 size 变了(少了 25),所以产生了这一个 tick。当然这个不等于说 Tick 1 和 Tick 2 之间没有别的 Order Book 的变化,它可以在除了 Best Bid/Offer 之外的地方变化,只不过这些事情在 Tick Data 上被滤掉了而已。

这种所谓的 Tick Data 其实就是一种对 Order Book Events 的 Down Sample 而已,它的前提假设是 Best Bid/Offer 是最重要的信息,以丢弃其它相对不如这个重要的信息为代价,缩减数据规模,让数据处理变的更容易。而实际上,真正的 Limit Order Book Market 里,交易所发的原始数据是所有对 Order Book 的增、删、改+成交这四样,特别是改单一般都是占整体数据流的大部分。只不过要处理这种级别的数据,需要使用数据结构的操作,维护重建 Order Book。

优异质的tick包含两部分,一是orderbook每一笔订单的挂单、撤单;二是逐笔成交。一般交易所提供的深度都是快照,但也提供了每笔挂单数据,可以本地维护订单重建全深度。期货那种1s两次,也不提供逐笔成交的tick只是一个半残数据。下面提供一个简单的Bitmex深度更新推送重建orderbook的部分代码:

if event == 'orderBookL2':
    data = msg['data']
    symbol = data[0]['symbol'].lower()
    if msg['action'] == 'partial':
        _cache[symbol+'asks'] = {}
        _cache[symbol+'bids'] = {}
    for ele in data:
        if symbol == 'xbtusd':
            price = (1e8*88-int(ele['id']))*0.01
        else:
            price = (297*1e8-int(ele['id']))/20
        if ele['side'] == 'Buy':
            if msg['action'] == 'delete':
                del _cache[symbol+'bids'][price]
            else:
                _cache[symbol+'bids'][price] = float(ele['size'])
        else:
            if msg['action'] == 'delete':
                del _cache[symbol+'asks'][price]
            else:
                _cache[symbol+'asks'][price] = float(ele['size'])
    a = sorted([[k,v] for k,v in _cache[symbol+'asks'].items()])[:50]
    b = sorted([[k,v] for k,v in _cache[symbol+'bids'].items()], reverse=True)[:50]

三、数据结构简介

数据结构是一种计算机科学技术领域广泛使用的专业术语,在很多书籍以及博客中,对数据结构的解释为数据在计算机的存储方式,很容易让人误以为数据结构只是一种数据的物理存储方式,其实不然,数据结构可以理解为:数据 + 结构。数据是描述客观事物的符号,为程序操控,存储在计算机上,结构包括数据的逻辑结构和存储结构。

根据数据元素间关系的不同特性,通常有下列四类基本的结构:

  1. 集合结构:该结构的数据元素间的关系是“属于同一个集合”。
  2. 线性结构:该结构的数据元素之间存在着一对一的关系。
  3. 树型结构:该结构的数据元素之间存在着一对多的关系。
  4. 图形结构:该结构的数据元素之间存在着多对多的关系,也称网状结构。 从上面所介绍的数据结构的概念中可以知道,一个数据结构有两个要素。一个是数据元素的集合,另一个是关系的集合。在形式上,数据结构通常可以采用一个二元组来表示。

常见的数据结构:

  1. 栈(Stack):栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。
  2. 队列(Queue):队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。
  3. 数组(Array):数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。
  4. 链表(Linked List):链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。
  5. 树(Tree):树是典型的非线性结构,它是包括,2 个结点的有穷集合 K。
  6. 图(Graph):图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。
  7. 堆(Heap):堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。
  8. 散列表(Hash table):散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。

延伸阅读1:数据结构的常用运算

  • 检索:检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点。
  • 插入:往数据结构中增加新的节点。
  • 删除:把指定的结点从数据结构中去掉。
  • 更新:改变指定节点的一个或多个字段的值。
  • 排序:把节点按某种指定的顺序重新排列。例如递增或递减。
相关文章