有关各种库存数据从不同的证券交易所不断到来。其中数据结构是适合于存储这些数据？

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

需要考虑的事情是：

一）有效的检索和数据的更新是必需的在交易时间每秒或微秒库存数据的变化。

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)

我NT肯定如何得到这一点。

I am nt sure about how to got about this.

c）根据使用任何编程语言，存储到数据库中有一些延迟考虑，将在特定时间内交易的股票的金额，如何ü可以存储所有的交易数据持续??

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.

推荐答案

一个堆不支持高效的随机存取（即查找同比指数），也获得前k个元素，而删除元素（这是不希望）。

A heap doesn't support efficient random access (i.e. look-up by index) nor getting the top k elements without removing elements (which is not desired).

我的答案是这样的：

一个数据库将是pferred选择此，作为$ P $，用适当的表结构和索引，所有必需的操作可以有效地进行。

A database would be the preferred choice for this, as, with a proper table structure and indexing, all of the required operations can be done efficiently.

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

So I suppose this is more a theoretical question about understanding of data structures (related to in-memory storage, rather than persistent).

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

It seems multiple data structures is the way to go:

a）有效检索和数据更新过程中的交易时间，需要每秒或微秒库存数据的变化。

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

一个地图将是有意义的这一个。哈希地图或树状图支持快速查询。

A map would make sense for this one. Hash-map or tree-map allows for fast look-up.

二）如何显示其股票目前的趋势（如股票成交量出售最活跃和最不活跃的，高利润和损失在某一天）？

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

几乎任何排序的数据结构似乎很有意义这里（具有上述地图指针到正确的节点，或指向同一节点）。其中的活动，一个以盈利为目的。

Just about any sorted data structure seems to make sense here (with the above map having pointers to the correct node, or pointing to the same node). One for activity and one for profit.

我可能会去一个排序（双）链表。这需要最短的时间内拿到的第一个或最后一个n项。因为你有一个指针通过地图的元件，更新的用只要地图查找加上得到它​​再次排序（如果有的话）所需的该项目的移动次数。如果一个项目往往运行多个索引一次，一个链表会的不可以是一个不错的选择（在这种情况下，我可能会去一个二叉搜索树）。

I'd probably go with a sorted (double) linked-list. It takes minimal time to get the first or last n items. Since you have a pointer to the element through the map, updating takes as long as the map lookup plus the number of moves of that item required to get it sorted again (if any). If an item often moves many indices at once, a linked-list would not be a good option (in which case I'd probably go for a Binary Search Tree).

C）你怎么能存储所有的交易数据持续？

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

我理解这个问题的 - 如果连接到数据库丢失或数据库出现故障，在任何时候，你如何保证不存在数据损坏？如果不是的话，我会一直问了重新表述。

I understand this question as - if the connection to the database is lost or the database goes down at any point, how do you ensure there is no data corruption? If this is not it, I would've asked for a rephrase.

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

Just about any database course should cover this.

至于我记得 - 它必须与创造另一个纪录，更新这个纪录，只有真正的指针设置为这个记录一旦被全面更新。在此之前，你可能还需要一个指针设置为旧的记录，这样就可以检查它是否被删除，如果设置指针离开后有事，但删除了。

As far as I remember - it has to do with creating another record, updating this record, and only setting the real pointer to this record once it has been fully updated. Before this you might also have to set a pointer to the old record so you can check if it's been deleted if something happens after setting the pointer away, but before deletion.

另一种选择是有其中添加启动事务时和当交易完成后删除（这还存储所需全部信息提交或回滚恢复交易）一个活跃的事务表。因此，只要一切都还好再次，检查此表和回滚或恢复尚未完成任何交易。

Another option is having a active transaction table which you add to when starting a transaction and remove from when a transaction completes (which also stores all required details to roll back or resume the transaction). Thus, whenever everything is okay again, you check this table and roll back or resume any transactions that have not yet completed.