기 임의의 요소 세트에서
-
02-07-2019 - |
문제
어떻게 선택하는 임의의 요소 세트에서?나는 특히 관심을 따기에 임의의 요소서 HashSet 또는 LinkedHashSet,Java.솔루션을 위해 다른 언어로도 환영합니다.
해결책
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++;
}
다른 팁
다소 관련된 것은 다음과 같습니다.
유용한 방법이 있습니다 java.util.Collections
전체 컬렉션을 셔플 링하려면 : Collections.shuffle(List<?>)
그리고 Collections.shuffle(List<?> list, Random rnd)
.
an을 사용하는 Java를위한 빠른 솔루션 ArrayList
그리고 a HashMap
: [요소 -> 색인].
동기 부여 : 나는 일련의 아이템이 필요했습니다 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();
}
}
이것은 허용 된 답변에서 각각의 고리보다 빠릅니다.
int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
for-each construct 호출 Iterator.hasNext()
모든 루프에서, 그러나 그 이후로 index < set.size()
, 그 수표는 불필요한 오버 헤드입니다. 나는 10-20%의 속도 향상을 보았지만 YMMV. (또한 추가 반환 명령문을 추가하지 않고도 컴파일됩니다.)
이 코드 (및 대부분의 다른 답변)는 설정이 아닌 컬렉션에 적용될 수 있습니다. 일반적인 방법 형식 :
public static <E> E choice(Collection<? extends E> coll, Random rand) {
if (coll.size() == 0) {
return null; // or throw IAE, if you prefer
}
int index = rand.nextInt(coll.size());
if (coll instanceof List) { // optimization
return ((List<? extends E>) coll).get(index);
} else {
Iterator<? extends E> iter = coll.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
}
}
Java로하려면 요소를 임의 액세스 컬렉션 (예 : Arraylist)에 복사하는 것을 고려해야합니다. 세트가 작지 않는 한, 선택한 요소에 액세스하는 것은 O (1) 대신 O (N)가 비싸다. [ED : 목록 사본도 O (N)입니다.
또는 요구 사항과 더 밀접하게 일치하는 다른 세트 구현을 찾을 수 있습니다. 그만큼 ListOrderedSet Commons에서 컬렉션은 유망 해 보입니다.
Java :
Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);
Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
System.out.println(setArray[rand.nextInt(set.size())]);
}
List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
Clojure 솔루션 :
(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
Perl 5
@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};
다음은이를 수행하는 한 가지 방법입니다.
C ++. 전체 세트를 반복하거나 정렬 할 필요가 없으므로 합리적으로 빠릅니다. 이것은 대부분의 최신 컴파일러로 상자 밖으로 작동해야합니다. TR1. 그렇지 않은 경우 부스트를 사용해야 할 수도 있습니다.
그만큼 문서를 부스트하십시오 부스트를 사용하지 않더라도 여기에서 도움이됩니다.
요령은 데이터가 버킷으로 나뉘어 졌다는 사실을 사용하고 무작위로 선택한 버킷 (적절한 확률)을 신속하게 식별하는 것입니다.
//#include <boost/unordered_set.hpp>
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;
int main() {
unordered_set<int> u;
u.max_load_factor(40);
for (int i=0; i<40; i++) {
u.insert(i);
cout << ' ' << i;
}
cout << endl;
cout << "Number of buckets: " << u.bucket_count() << endl;
for(size_t b=0; b<u.bucket_count(); b++)
cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;
for(size_t i=0; i<20; i++) {
size_t x = rand() % u.size();
cout << "we'll quickly get the " << x << "th item in the unordered set. ";
size_t b;
for(b=0; b<u.bucket_count(); b++) {
if(x < u.bucket_size(b)) {
break;
} else
x -= u.bucket_size(b);
}
cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
unordered_set<int>::const_local_iterator l = u.begin(b);
while(x>0) {
l++;
assert(l!=u.end(b));
x--;
}
cout << "random item is " << *l << ". ";
cout << endl;
}
}
위의 솔루션은 대기 시간 측면에서 말하지만 각 지수를 선택할 확률을 동일하게 보장하지는 않습니다.
그것이 고려되어야한다면 저수지 샘플링을 시도하십시오. http://en.wikipedia.org/wiki/reservoir_sampling.
Collections.shuffle () (몇 명이 제안한대로)는 그러한 알고리즘 중 하나를 사용합니다.
"다른 언어에 대한 솔루션도 환영받습니다"라고 말했기 때문에 Python의 버전은 다음과 같습니다.
>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
세트/배열의 크기/길이를 얻을 수없고 0과 크기/길이 사이에서 난수를 생성 한 다음 인덱스가 해당 숫자와 일치하는 요소를 호출 할 수 없습니까? Hashset에는 .size () 메소드가 있습니다. 확실합니다.
psuedocode에서 -
function randFromSet(target){
var targetLength:uint = target.length()
var randomIndex:uint = random(0,targetLength);
return target[randomIndex];
}
"세트"가 배열이라고 가정합니다.
$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];
Mersenne Twister 기능이 더 좋지만 PHP에는 MT와 동등한 MT가 없습니다.
상 설정 유형과 임의의 요소 연산자 인 unery "?"가 있습니다.
? set( [1, 2, 3, 4, 5] )
1과 5 사이의 난수를 생성합니다.
프로그램이 실행될 때 임의의 시드가 0으로 초기화되므로 각 실행에 따라 다른 결과를 생성합니다. randomize()
C#에서
Random random = new Random((int)DateTime.Now.Ticks);
OrderedDictionary od = new OrderedDictionary();
od.Add("abc", 1);
od.Add("def", 2);
od.Add("ghi", 3);
od.Add("jkl", 4);
int randomIndex = random.Next(od.Count);
Console.WriteLine(od[randomIndex]);
// Can access via index or key value:
Console.WriteLine(od[1]);
Console.WriteLine(od["def"]);
자바 스크립트 솔루션;)
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();
LISP에서
(defun pick-random (set)
(nth (random (length set)) set))
Mathematica에서 :
a = {1, 2, 3, 4, 5}
a[[ ⌈ Length[a] Random[] ⌉ ]]
또는 최근 버전에서 간단히 말합니다.
RandomChoice[a]
이것은 아마도 설명이 없기 때문에 다운 투표를 받았습니다. 여기에는 다음과 같습니다.
Random[]
0과 1 사이의 의사로드 플로트를 생성합니다. 이것은 목록의 길이를 곱한 다음 천장 함수는 다음 정수까지 반올림하는 데 사용됩니다. 이 지수는 추출됩니다 a
.
해시 테이블 기능은 Mathematica의 규칙으로 자주 수행되므로 규칙은 목록에 저장되므로 사용할 수 있습니다.
a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};
그냥 어때
public static <A> A getRandomElement(Collection<A> c, Random r) {
return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
이것은 동일하게 받아들이 대답(Khoth)지만,불필요한 size
고 i
변수가 제거됩니다.
int random = new Random().nextInt(myhashSet.size());
for(Object obj : myhashSet) {
if (random-- == 0) {
return obj;
}
}
하지만 일을 멀리 두 전술하는 변수를 위한 솔루션이 여전히 남아있 무작위기 때문에 우리는 우리에 의존 random(에서 시작으로 무작위로 선택된 인덱스)을 감소하는 자체적으로 0
각 반복이다.
불행히도, 이것은 표준 라이브러리 세트 컨테이너에서 효율적으로 (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]을 얻었으므로 분포 이음새가 양호했습니다.
나는 나 자신에게도 같은 문제로 어려움을 겪었지만 아직 날씨를 결정하지 않았다.이 더 효율적인 선택의 성능 이득은 파이썬 기반 컬렉션을 사용하는 오버 헤드의 가치가있다. 물론 나는 그것을 개선하고 그것을 C로 번역 할 수 있지만, 오늘은 너무 많은 일입니다. :)
Java 8 :
static <E> E getRandomSetElement(Set<E> set) {
return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
MT를 사용하여 PHP :
$items_array = array("alpha", "bravo", "charlie");
$last_pos = count($items_array) - 1;
$random_pos = mt_rand(0, $last_pos);
$random_item = $items_array[$random_pos];
재미를 위해 나는 거부 샘플링을 기반으로 Randomhashset을 썼습니다. Hashmap은 테이블에 직접 액세스 할 수 없지만 잘 작동해야합니다.
추가 메모리를 사용하지 않으며 조회 시간은 O (1) 상각됩니다. (Java Hashtable이 조밀하므로).
class RandomHashSet<V> extends AbstractSet<V> {
private Map<Object,V> map = new HashMap<>();
public boolean add(V v) {
return map.put(new WrapKey<V>(v),v) == null;
}
@Override
public Iterator<V> iterator() {
return new Iterator<V>() {
RandKey key = new RandKey();
@Override public boolean hasNext() {
return true;
}
@Override public V next() {
while (true) {
key.next();
V v = map.get(key);
if (v != null)
return v;
}
}
@Override public void remove() {
throw new NotImplementedException();
}
};
}
@Override
public int size() {
return map.size();
}
static class WrapKey<V> {
private V v;
WrapKey(V v) {
this.v = v;
}
@Override public int hashCode() {
return v.hashCode();
}
@Override public boolean equals(Object o) {
if (o instanceof RandKey)
return true;
return v.equals(o);
}
}
static class RandKey {
private Random rand = new Random();
int key = rand.nextInt();
public void next() {
key = rand.nextInt();
}
@Override public int hashCode() {
return key;
}
@Override public boolean equals(Object o) {
return true;
}
}
}
또한 세트를 배열 사용 배열로 전송할 수 있습니다.
Object[] arr = set.toArray();
int v = (int) arr[rnd.nextInt(arr.length)];
당신이 정말로 당신이 Set
, 무작위성에 대한 보장없이 가장 쉬운 것은 반복자가 처음으로 반환하는 것입니다.
Set<Integer> s = ...
Iterator<Integer> it = s.iterator();
if(it.hasNext()){
Integer i = it.next();
// i is a "random" object from set
}
Java 8에서 가장 쉬운 것은 다음과 같습니다.
outbound.stream().skip(n % outbound.size()).findFirst().get()
어디 n
임의의 정수입니다. 물론 그것은 그보다 성능이 적습니다. for(elem: Col)
Khoth의 답변을 시작점으로 사용하는 일반적인 솔루션.
/**
* @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;
}
세트 크기가 크지 않으면 배열을 사용하여이를 수행 할 수 있습니다.
int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];