컬렉션에서 임의의 하위 집합을 선택하는 가장 좋은 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/136474

문제

벡터에 임의의 하위 집합을 선택하려는 개체 집합이 있습니다(예:100개의 항목이 다시 돌아옵니다.무작위로 5개를 선택하세요).첫 번째 (매우 성급한) 패스에서 나는 매우 간단하고 아마도 지나치게 영리한 솔루션을 수행했습니다.

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

이는 훌륭하고 단순하다는 장점이 있지만 확장성이 좋지 않을 것으로 생각됩니다.Collections.shuffle()은 최소한 O(n)이어야 합니다.나의 덜 영리한 대안은

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

컬렉션에서 임의의 하위 집합을 추출하는 더 나은 방법에 대한 제안이 있습니까?

도움이 되었습니까?

해결책

Jon Bentley는 이것을 '프로그래밍 진주'또는 '더 프로그래밍 진주'에서 논의합니다. N of M 선택 프로세스에주의를 기울여야하지만 표시된 코드가 올바르게 작동한다고 생각합니다. 모든 항목을 무작위로 셔플하는 대신, 임의의 셔플은 첫 번째 N 위치 만 셔플하는 것만 할 수 있습니다. 이는 n << M에 유용한 절약입니다.

Knuth는 또한 이러한 알고리즘에 대해 논의합니다. Vol 3 "정렬 및 검색"이라고 생각하지만, 내 세트는 집의 이동이 보류 중이므로 공식적으로 확인할 수 없습니다.

다른 팁

@홍옥,

나는 이것이 당신이 말하는 솔루션이라고 생각합니다.

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Jon Bentley의 프로그래밍 진주 127 페이지에 있으며 Knuth의 구현을 기반으로합니다.

편집 : 방금 129 페이지의 추가 수정을 보았습니다.

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

이것은 "... 우리는 첫 번째 셔플 만 셔플이 필요하다는 아이디어를 기반으로합니다. 중 배열의 요소 ... "

n 목록에서 k 개의 개별 요소를 선택하려는 경우 위에서 제공한 방법은 O(n) 또는 O(kn)이 됩니다. 왜냐하면 Vector에서 요소를 제거하면 arraycopy가 모든 요소를 ​​아래로 이동하게 되기 때문입니다. .

최선의 방법을 요구하고 있으므로 입력 목록으로 무엇을 할 수 있는지에 따라 다릅니다.

예제에서와 같이 입력 목록을 수정하는 것이 허용되는 경우 k 임의의 요소를 목록의 시작 부분으로 바꾸고 다음과 같이 O(k) 시간에 반환할 수 있습니다.

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

목록이 시작된 것과 동일한 상태로 끝나야 하는 경우, 교체한 위치를 추적한 다음 선택한 하위 목록을 복사한 후 목록을 원래 상태로 되돌릴 수 있습니다.이것은 여전히 ​​O(k) 솔루션입니다.

그러나 입력 목록을 전혀 수정할 수 없고 k가 n보다 훨씬 작은 경우(예: 100에서 5) 매번 선택한 요소를 제거하지 않고 간단히 각 요소를 선택하는 것이 훨씬 더 좋습니다. 중복된 것을 버리고 다시 선택하세요.이것은 n이 k를 지배할 때 여전히 O(k)에 가까운 O(kn / (n-k))를 제공합니다.(예를 들어 k가 n/2보다 작으면 O(k)로 줄어듭니다.)

k가 n의 지배를 받지 않고 목록을 수정할 수 없는 경우 O(n)이 O(k)만큼 좋기 때문에 원래 목록을 복사하고 첫 번째 솔루션을 사용할 수도 있습니다.

다른 사람들이 언급했듯이 모든 하위 목록이 가능하고 편견이 없는 강력한 무작위성에 의존하는 경우 다음보다 더 강력한 것이 필요합니다. java.util.Random.보다 java.security.SecureRandom.

나는 썼다 이것의 효율적인 구현 몇 주 전에. C#이지만 Java로 변환은 사소합니다 (본질적으로 동일한 코드). 플러스 측면은 완전히 편견이 없다는 것입니다 (기존 답변 중 일부는 그렇지 않은 것) - 여기에 테스트하는 방법.

그것은 Fisher-Yates Shuffle의 Durstenfeld 구현을 기반으로합니다.

그러나 임의의 요소를 선택하는 두 번째 솔루션은 소리가 들립니다.

제거 비용은 얼마입니까? 배열을 새로운 메모리 덩어리로 다시 작성 해야하는 경우, 이전에 원하는 O (n)가 아닌 두 번째 버전에서 O (5n) 작업을 수행했습니다.

거짓으로 설정된 부울 배열을 만들 수 있습니다.

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

이 접근법은 서브 세트가 총 크기보다 큰 마진으로 작아지면 작동합니다. 이러한 크기가 서로 가까워지면 (예 : 크기 또는 무언가의 1/4) 임의의 숫자 생성기에 대해 더 많은 충돌이 발생할 수 있습니다. 이 경우 정수 목록을 더 큰 배열의 크기로 만들고 해당 정수 목록을 셔플 한 다음 첫 번째 요소를 끌어내어 (콜링하지 않은) inces를 얻습니다. 이렇게하면 정수 배열을 구축하는 데 O (n)과 셔플에 다른 o (n) 비용이 들지만 내부에서 내부에서 충돌은없고 체커에서 충돌하지 않고 비용을 제거하는 잠재적 O (5N)보다 적습니다.

나는 당신의 초기 구현을 개인적으로 선택합니다 : 매우 간결합니다. 성능 테스트는 그것이 얼마나 잘 확장되는지를 보여줍니다. 나는 괜찮은 학대 방법으로 매우 유사한 코드 블록을 구현했으며 충분히 확장되었습니다. 특정 코드는> 10,000 개의 항목이 포함 된 배열에 의존했습니다.

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

이것 StackoverFlow에서 매우 유사한 질문입니다.

해당 페이지에서 내가 가장 좋아하는 답변을 요약하려면 (사용자 Kyle의 Furst One) :

  • O (n) 솔루션: 목록을 반복하고 확률 (#needed / #Remaining)과 함께 요소 (또는 참조)를 복사하십시오. 예 : K = 5 및 n = 100 인 경우, 첫 번째 요소를 프로브 5/100으로 취합니다. 당신이 그것을 복사하면, 당신은 Prob 4/99로 다음을 선택합니다. 그러나 첫 번째를 취하지 않았다면 프로브는 5/99입니다.
  • o (k log k) 또는 o (k2): 숫자 <n을 무작위로 선택한 다음 숫자 <n-1 등을 무작위로 선택하여 k 인덱스 ({0, 1, ..., n-1}의 숫자)의 정렬 된 목록을 작성하십시오. 충돌을 피하고 확률을 유지하기 위해 선택을 리콜해야합니다. 예를 들어, k = 5 및 n = 100이고 첫 번째 선택은 43이면 다음 선택은 [0, 98] 범위에 있으며> = 43 인 경우 1을 추가합니다. 따라서 두 번째 선택이 50이면 1을 추가하면 {43, 51}이 있습니다. 다음 선택이 51이면 추가합니다 2 {43, 51, 53}을 얻기 위해.

여기 몇 가지 의사가 있습니다.

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

시간 복잡성은 O (k2) 또는 o (k log k)는 s를 위해 컨테이너에 얼마나 빨리 검색하고 삽입 할 수 있는지에 따라 다릅니다. S가 일반 목록 인 경우 해당 작업 중 하나는 선형이며 K^2를 얻습니다. 그러나 균형 잡힌 이진 트리로 S를 기꺼이 구축하려는 경우 O (k log k) 시간을 꺼낼 수 있습니다.

내가 여기에 나타나지 않는 두 가지 솔루션 - 서명은 상당히 길고 일부 링크를 포함하지만 모든 게시물이 N 요소 세트에서 k elemetns를 선택하는 문제와 관련이 없다고 생각합니다. . [ "세트"에 의해, 나는 수학적 용어를 언급합니다. 즉, 모든 요소가 한 번 나타나고 순서가 중요하지 않습니다].

졸 1 :

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

이것은 다니엘이 준 대답과 비슷해 보이지만 실제로는 매우 다릅니다. O (k) 실행 시간입니다.

또 다른 해결책은 일부 수학을 사용하는 것입니다. 배열 인덱스를 Z_N으로 고려하고 무작위 2 숫자, X는 N, 즉 chhose gcd (x, n) = 1, a, a는 "시작점" - 시리즈 : A % N, A+X % N, A+2*X % N, ... A+(K -1)*X % N은 고유 한 숫자의 시퀀스입니다. k <= n).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top