如何从集合中随机选取一个元素? 我特别感兴趣的是从a中随机选取一个元素 Java中的HashSet或LinkedHashSet。 也欢迎其他语言的解决方案。
当前回答
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++;
}
其他回答
如果你不介意第三方库,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>
Java使用ArrayList和HashMap的快速解决方案:[element -> index]。
动机:我需要一组具有RandomAccess属性的项目,特别是从集合中选择一个随机项目(参见pollRandom方法)。在二叉树中随机导航是不准确的:树不是完全平衡的,这不会导致均匀分布。
public class RandomSet<E> extends AbstractSet<E> {
List<E> dta = new ArrayList<E>();
Map<E, Integer> idx = new HashMap<E, Integer>();
public RandomSet() {
}
public RandomSet(Collection<E> items) {
for (E item : items) {
idx.put(item, dta.size());
dta.add(item);
}
}
@Override
public boolean add(E item) {
if (idx.containsKey(item)) {
return false;
}
idx.put(item, dta.size());
dta.add(item);
return true;
}
/**
* Override element at position <code>id</code> with last element.
* @param id
*/
public E removeAt(int id) {
if (id >= dta.size()) {
return null;
}
E res = dta.get(id);
idx.remove(res);
E last = dta.remove(dta.size() - 1);
// skip filling the hole if last is removed
if (id < dta.size()) {
idx.put(last, id);
dta.set(id, last);
}
return res;
}
@Override
public boolean remove(Object item) {
@SuppressWarnings(value = "element-type-mismatch")
Integer id = idx.get(item);
if (id == null) {
return false;
}
removeAt(id);
return true;
}
public E get(int i) {
return dta.get(i);
}
public E pollRandom(Random rnd) {
if (dta.isEmpty()) {
return null;
}
int id = rnd.nextInt(dta.size());
return removeAt(id);
}
@Override
public int size() {
return dta.size();
}
@Override
public Iterator<E> iterator() {
return dta.iterator();
}
}
以霍斯的答案为起点的通用解决方案。
/**
* @param set a Set in which to look for a random element
* @param <T> generic type of the Set elements
* @return a random element in the Set or null if the set is empty
*/
public <T> T randomElement(Set<T> set) {
int size = set.size();
int item = random.nextInt(size);
int i = 0;
for (T obj : set) {
if (i == item) {
return obj;
}
i++;
}
return null;
}
不幸的是,这在任何标准库集合容器中都不能有效地完成(比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语言,但这对我来说工作量太大了:)
Javascript解决方案;)
function choose (set) {
return set[Math.floor(Math.random() * set.length)];
}
var set = [1, 2, 3, 4], rand = choose (set);
或者:
Array.prototype.choose = function () {
return this[Math.floor(Math.random() * this.length)];
};
[1, 2, 3, 4].choose();
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 如何在Ruby中生成a和b之间的随机数?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder