股票市场最优化的数据结构是什么？

Question

股票市场最优化的数据结构是什么？

algorithmdata-structures

6

各种股票的数据持续从各个证券交易所不断传输。哪种数据结构适合存储这些数据?

需要考虑以下几点:

a) 需要有效地检索和更新数据，因为在交易时间内，股票数据每秒或每微秒都在变化。

我想考虑使用堆，因为股票数量会更多或更少，并且最常用的操作是检索和更新，所以堆应该在这种情况下表现良好。

b) 需要显示当前流行的股票（例如，在某一天的交易中被卖出的股票数量最活跃和最不活跃，高利润和亏损）

我不确定如何去处理这个问题。

c) 由于使用任何编程语言将数据存储到数据库具有一定的延迟性，考虑到在特定时间内将交易的股票数量，如何持久地存储所有事务性数据？？

备注：这是摩根士丹利的面试问题。

- user1631651

6

听起来你做得不太好。 - duffymo

3个回答

2

如果我必须选择，我会选择哈希表： 原因：它是同步和线程安全的，平均情况下的复杂度为BigO(1)。 提供： 1.良好的哈希函数以避免冲突。 2.高性能缓存。

"最初的回答"

- Rahul Srivastava

0

虽然这是一个与语言无关的问题，但其中一些要求引起了我的注意。例如：

需要有效地检索和更新数据，因为股票数据在交易时间每秒或微秒都会发生变化。

Java类HashMap使用键值的哈希码快速访问其集合中的值。它实际上具有O(1)的运行时复杂度，这是理想的。

需要显示当前流行的股票（即以卖出股票数量最多和最少、某一天的高利润和亏损为标准）

这是一个基于实现的问题。您最好实现一个快速排序算法，如QuickSort或Mergesort。

由于在特定时间内将交易的股票数量考虑在内，使用任何编程语言存储到数据库都存在一定的延迟，那么如何持久地存储所有交易数据？

数据库应该是我的首选，但这取决于您的资源。

- christopher

2

纳斯达克使用SQL Server数据库，而且数量不少，据我所知。看起来是一个非常学术的问题。 - duffymo

1

如果您一直重新排序数据，那么您将无法取得进展。当然，这是一个基于实现的问题 - 这就是问题所在。第三个答案实际上只是一种屈服。 - Konrad Rudolph

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

一个堆不支持高效的随机访问（即通过索引查找）也不支持获取前k个元素而不删除元素（这是不希望发生的）。

我的答案可能是：

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

所以我想这更多地是关于数据结构的理解的理论问题（与内存存储相关，而不是持久性）。

似乎多个数据结构是正确的选择：

a）需要有效检索和更新数据，因为股票数据在交易时间内每秒或微秒变化。

对于这个问题，映射是有意义的。哈希映射或树映射允许快速查找。

b）如何显示当前流行的股票（即销售最活跃和最不活跃的股票量，在特定日期的高利润和损失）？

几乎任何排序的数据结构在这里都是有意义的（具有上述映射指向正确节点或指向同一节点）。一个用于活动，一个用于利润。

我可能会选择一个排序的（双）链表。它花费最少的时间来获取第一个或最后一个n项。由于您通过地图拥有元素的指针，所以更新所需的时间与地图查找加上将该项移动到其所需排序位置的次数相同（如果有）。如果一个项目经常同时移动多个索引，则链表不是一个好的选择（在这种情况下，我可能会选择二叉搜索树）。

c）如何持久地存储所有事务数据？

我理解这个问题是-如果在任何时候连接到数据库丢失或数据库关闭，如何确保没有数据损坏？如果不是这样，我会要求重新表述。

几乎任何数据库课程都应该涵盖此内容。

据我所记 - 它与创建另一个记录、更新此记录以及仅在完全更新此记录后将真实指针设置为此记录有关。在此之前，您可能还需要设置对旧记录的指针，以便在指针离开但在删除之前发生某些事情时检查是否已删除。

另一种选择是拥有一个活动事务表，在开始事务时添加并在事务完成时删除（它还存储了回滚或恢复事务所需的所有详细信息）。因此，每当一切正常时，您都会检查此表，并回滚或恢复尚未完成的任何事务。