algorithm - 将优化什么数据结构来表示股票市场？

Question

各种股票的数据源源不断地来自各个证券交易所。哪种数据结构适合存储这些数据？

需要考虑的是:

a) 由于股票数据在交易时间内每秒或微秒发生变化，因此需要有效检索和更新数据。

I thought of using Heap as the number of stocks would be more or less constant and the most frequent used operations are retrieval and update so heap should perform well for this scenario.

b) 需要显示当前趋势的股票(如特定日期最活跃和最不活跃、高利润和亏损的股票卖出量)

我不确定如何解决这个问题。

c) 考虑到在特定时间交易的股票数量，使用任何编程语言存储到数据库都会有一些延迟，您如何持久存储所有交易数据？

Ps:这是摩根士丹利的面试题。

Answer 1

堆不支持高效的随机访问(即按索引查找)，也不支持在不删除元素的情况下获取前 k 个元素(这是不需要的)。

我的回答是这样的:

为此，数据库将是首选，因为通过适当的表结构和索引，可以高效地完成所有必需的操作。

所以我想这更多是一个关于理解数据结构的理论问题(与内存存储相关，而不是持久化)。

看起来多数据结构是可行的方法:

a) Effective retrieval and update of data is required as stock data changes per second or microsecond during trading time.

一张 map 对这个来说很有意义。 HashMap 或树映射允许快速查找。

b) How to show stocks which are currently trending (as in volume of shares being sold most active and least active, high profit and loss on a particular day)?

几乎任何排序的数据结构在这里似乎都有意义(上面的映射具有指向正确节点或指向同一节点的指针)。一种用于事件，一种用于盈利。

我可能会使用排序(双)链表。获取第一个或最后一个 n 项所需的时间最少。由于您有一个通过 map 指向元素的指针，因此更新需要的时间与 map 查找加上再次排序所需的该项目的移动次数(如果有的话)一样长。如果一个项目经常同时移动多个索引，那么链表不是是一个不错的选择(在这种情况下我可能会选择二叉搜索树)。

c) How can you store all the transactional data persistently?

我对这个问题的理解是 - 如果与数据库的连接丢失或数据库在任何时候出现故障，您如何确保没有数据损坏？如果不是这样，我会要求重新措辞。

几乎任何数据库类(class)都应该涵盖这一点。

据我所知 - 它与创建另一条记录、更新该记录以及仅在记录完全更新后才设置指向该记录的实际指针有关。在此之前，您可能还必须设置一个指向旧记录的指针，以便在将指针移开之后但在删除之前发生某些事情时，您可以检查它是否已被删除。

另一种选择是拥有一个事件事务表，您可以在启动事务时将其添加到该表中，并在事务完成时将其删除(它还存储回滚或恢复事务所需的所有详细信息)。因此，只要一切正常，您就可以检查此表并回滚或恢复任何尚未完成的事务。