数据结构选择随机元素？ [英] Data structure for choosing random elements?

问题描述

有谁知道，有效地支持了两个操作的数据结构？

Does anyone know of a data structure that supports the two operations efficiently?

1. 插入一个值的数据结构。
2. 出列，并返回从数据结构与均匀地随机概率的条目。

这是有点像经典的包弹珠总是出现在入门概率类。你可以把任意弹珠入袋，然后可以有效地随意取出的弹珠。

This is sort of like the canonical "bag of marbles" that always comes up in introductory probability classes. You can put arbitrary marbles into the bag, and can then efficiently remove the marbles at random.

最好的解决方案我有如下 - 使用平衡树（AVL，AA，红色/黑色等）来存储中的元素。这给了O（LG N）的插入时间。要删除一个随机元素，选择一个随机指数我，然后找到并从树中删除第i个元素。如果你已经增强了结构适当，这可在O（LG n）的运行时间为好。

The best solution I have is as follows - use a self-balancing binary search tree (AVL, AA, red/black, etc.) to store the elements. This gives O(lg n) insertion time. To remove a random element, pick a random index i, then locate and remove the ith element from the tree. If you've augmented the structure appropriately, this can be made to run in O(lg n) time as well.

这肯定运行不坏，但我是否有可能做的更好好奇 - 也许是O（1）插入和O（LG N）的出队？或许运行在什么的预期 O（1）插入和删除使用散列函数？或许更强的摊销约束？

This runtime certainly isn't bad, but I'm curious if it's possible to do better - perhaps O(1) for insertion and O(lg n) for dequeues? Or perhaps something that runs in expected O(1) insert and delete using hash functions? Or perhaps a stronger amortized bound?

有没有人对如何使这一渐近更快任何想法？

Does anyone have any ideas on how to make this asymptotically faster?

推荐答案

是的。使用向量。

要插入，简单地底，并增加大小。要删除，挑一个元素随意，交换的内容与最终值，然后弹出关终值（即返回终值和减少向量的大小）。

To insert, simply place at the end, and increment the size. To remove, pick an element at random, swap its contents with the end value, then pop off the end value (i.e., return the end value and decrement the vector's size).

这两种操作摊销O（1）。

Both operations are amortised O(1).

这篇关于数据结构选择随机元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！