[java] 세트에서 임의의 요소 선택

세트에서 임의의 요소를 어떻게 선택합니까? 특히 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++;
}

답변

다소 관련이 있습니까?

java.util.Collections전체 컬렉션을 섞는 데 유용한 방법이 있습니다 : Collections.shuffle(List<?>)및 Collections.shuffle(List<?> list, Random rnd).

답변

ArrayListand HashMap: [element-> index]를 사용하는 Java 용 빠른 솔루션 .

동기 부여 : 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();
    }
}

답변

이것은 허용 된 답변의 for-each 루프보다 빠릅니다.

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 구문은 Iterator.hasNext()모든 루프를 호출 하지만 이후 index < set.size()로이 검사는 불필요한 오버 헤드입니다. 속도가 10-20 % 향상되었지만 YMMV가 나타났습니다. 또한 여분의 return 문을 추가하지 않고도 컴파일됩니다.

이 코드 (및 대부분의 다른 답변)는 Set뿐만 아니라 모든 Collection에 적용 할 수 있습니다. 일반적인 방법 양식에서 :

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)입니다]

또는 요구 사항과 더 일치하는 다른 Set 구현을 찾을 수 있습니다. Commons Collections 의 ListOrderedSet 은 유망한 것으로 보입니다.

답변

자바 8 :

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

답변

자바에서 :

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())]);
}