5

Data for various stocks is coming from various stock exchange continuously. Which data structure is suitable to store these data?

things to consider are :

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

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) need 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)

I am nt sure about how to got about this.

c) as storing to database using any programming language has some latency considering the amount of stocks that will be traded during a particular time, how can u store all the transactional data persistently??

Ps: This is a interview question from Morgan Stanley.

4

3 回答 3

5

堆不支持有效的随机访问（即按索引查找），也不支持在不删除元素的情况下获取前 k 个元素（这是不希望的）。

我的答案是这样的：

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

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

似乎多个数据结构是要走的路：

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

一张地图对这个很有意义。哈希图或树图允许快速查找。

b) 如何显示当前趋势的股票（如在特定日期最活跃和最不活跃、高盈亏的股票数量）？

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

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

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

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

几乎任何数据库课程都应该涵盖这一点。

据我记得 - 它与创建另一条记录、更新这条记录以及只有在它完全更新后才设置指向这条记录的真实指针有关。在此之前，您可能还必须设置一个指向旧记录的指针，以便您可以检查它是否已被删除，如果在设置指针之后但在删除之前发生了某些事情。

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

于 2013-04-19T10:03:20.537 回答
2

如果我必须选择，我会选择Hash Table：

原因：它是同步和线程安全的，BigO(1)作为平均案例复杂度。

提供： 1.良好的哈希函数，避免碰撞。2. 高性能缓存。

于 2019-06-20T15:42:40.717 回答
0

虽然这是一个与语言无关的问题，但我突然想到了一些要求。例如：

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

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

需要显示当前趋势的股票（如在特定日期出售的最活跃和最不活跃的股票数量，高盈亏）

这是一个基于实现的问题。最好的办法是实现一个快速排序算法，比如QuickSortor Mergesort。

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

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

于 2013-04-18T10:04:56.913 回答