如何从集合中随机选取一个元素? 我特别感兴趣的是从a中随机选取一个元素 Java中的HashSet或LinkedHashSet。 也欢迎其他语言的解决方案。
当前回答
对于番石榴,我们可以做得比霍斯的答案更好一点:
public static E random(Set<E> set) {
int index = random.nextInt(set.size();
if (set instanceof ImmutableSet) {
// ImmutableSet.asList() is O(1), as is .get() on the returned list
return set.asList().get(index);
}
return Iterables.get(set, index);
}
其他回答
Clojure的解决方案:
(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
if (i == item)
return obj;
i++;
}
你能不能得到集合/数组的大小/长度,生成一个介于0和大小/长度之间的随机数,然后调用索引与该数字匹配的元素?HashSet有一个.size()方法,我很确定。
在伪代码中-
function randFromSet(target){
var targetLength:uint = target.length()
var randomIndex:uint = random(0,targetLength);
return target[randomIndex];
}
如果你不介意第三方库,Utils库有一个IterableUtils,它有一个randomFrom(Iterable Iterable)方法,该方法将接受一个Set并从中返回一个随机元素
Set<Object> set = new HashSet<>();
set.add(...);
...
Object random = IterableUtils.randomFrom(set);
它在Maven中央存储库中:
<dependency>
<groupId>com.github.rkumsher</groupId>
<artifactId>utils</artifactId>
<version>1.3</version>
</dependency>
不幸的是,这在任何标准库集合容器中都不能有效地完成(比O(n)更好)。
这很奇怪,因为向哈希集和二进制集添加随机选择函数是非常容易的。在一个非稀疏散列集中,你可以尝试随机的条目,直到你得到一个命中。对于二叉树,您可以在左子树或右子树之间随机选择,最多有O(log2)步。我已经实现了后面的演示如下:
import random
class Node:
def __init__(self, object):
self.object = object
self.value = hash(object)
self.size = 1
self.a = self.b = None
class RandomSet:
def __init__(self):
self.top = None
def add(self, object):
""" Add any hashable object to the set.
Notice: In this simple implementation you shouldn't add two
identical items. """
new = Node(object)
if not self.top: self.top = new
else: self._recursiveAdd(self.top, new)
def _recursiveAdd(self, top, new):
top.size += 1
if new.value < top.value:
if not top.a: top.a = new
else: self._recursiveAdd(top.a, new)
else:
if not top.b: top.b = new
else: self._recursiveAdd(top.b, new)
def pickRandom(self):
""" Pick a random item in O(log2) time.
Does a maximum of O(log2) calls to random as well. """
return self._recursivePickRandom(self.top)
def _recursivePickRandom(self, top):
r = random.randrange(top.size)
if r == 0: return top.object
elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
return self._recursivePickRandom(top.b)
if __name__ == '__main__':
s = RandomSet()
for i in [5,3,7,1,4,6,9,2,8,0]:
s.add(i)
dists = [0]*10
for i in xrange(10000):
dists[s.pickRandom()] += 1
print dists
我得到[995,975,971,995,1057,1004,966,1052,984,1001]作为输出,所以分布很好。
我自己也遇到过同样的问题,但我还不确定这种更有效的选择所带来的性能收益是否值得使用基于python的集合。当然,我可以将其提炼并翻译成C语言,但这对我来说工作量太大了:)
推荐文章
- Android Studio无法找到有效的Jvm(与MAC OS相关)
- 为什么一个组合器需要减少方法转换类型在java 8
- CountDownLatch是如何在Java多线程中使用的?
- 如果我同步了同一个类上的两个方法,它们能同时运行吗?
- 分治算法与动态规划的区别
- 如何减去X天从一个日期对象在Java?
- Java标识符中的“连接字符”是什么?
- 如何JSON序列化集?
- 一对多、多对一、多对多的区别?
- 从枚举中选择一个随机值?
- 如何从URL获取参数与JSP
- 如何在Eclipse中生成Javadoc注释?
- 我如何在c++中创建一个随机的字母数字字符串?
- 找到java类从哪里加载
- 从集合中随机选取一个元素