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

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

---

벡터에 임의의 하위 집합을 선택하려는 개체 집합이 있습니다 (예 : 돌아 오는 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는 'Programming Pearls'또는 'More Programming Pearls'에서 이에 대해 설명합니다. N / M 선택 프로세스에주의해야하지만 표시된 코드가 올바르게 작동한다고 생각합니다. 모든 항목을 무작위로 셔플하는 대신 처음 N 개 위치 만 셔플 링하여 무작위 셔플을 수행 할 수 있습니다. 이는 N << M 일 때 유용한 절약입니다.

Knuth는 또한 이러한 알고리즘에 대해 논의합니다. Vol 3 "Sorting and Searching"이 될 것이라고 생각합니다.하지만 제 세트는 이사를 기다리고 있기 때문에 공식적으로 확인할 수 없습니다.

---

@홍옥,

나는 이것이 당신이 말하는 해결책이라고 믿습니다.

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의 Programming Pearls 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";
}

이것은 "... 배열 의 처음 m 개 요소 만 섞을 필요가 있습니다 ..."라는 아이디어에 기반을두고 있습니다.

---

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 / (nk))를 줄 것입니다. (예를 들어 k가 n / 2보다 작 으면 O (k)로 감소합니다).

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

다른 사람들이 언급했듯이 모든 하위 목록이 가능하고 편향되지 않은 강력한 무작위성에 의존하는 경우 java.util.Random. 을 참조하십시오 java.security.SecureRandom.

---

저는 몇 주 전에 이것을 효율적으로 구현했습니다 . C #이지만 Java 로의 번역은 사소합니다 (본질적으로 동일한 코드). 장점은 (기존 답변 중 일부는 그렇지 않은) 완전히 편견이 없다는 것입니다- 여기에있는 테스트 방법 입니다.

이는 Fisher-Yates 셔플의 Durstenfeld 구현을 기반으로합니다.

---

Random을 사용하여 요소를 선택하는 두 번째 솔루션은 소리가 나는 것처럼 보입니다.

• 데이터의 민감도에 따라 일종의 해싱 방법을 사용하여 난수 시드를 스크램블하는 것이 좋습니다. 좋은 사례 연구를 보려면 온라인 포커에서 속임수를 배우는 방법을 참조하십시오 (그러나이 링크는 2015-12-18 현재 404입니다). 대체 URL (큰 따옴표로 묶인 기사 제목에 대한 Google 검색을 통해 찾을 수 있음)은 다음과 같습니다.

  • How We Learned to Cheat at Online Poker — apparently the original publisher.
  • How We Learned to Cheat at Online Poker
  • How We Learned to Cheat at Online Poker
     

• Vector is synchronized. If possible, use ArrayList instead to improve performance.

---

How much does remove cost? Because if that needs to rewrite the array to a new chunk of memory, then you've done O(5n) operations in the second version, rather than the O(n) you wanted before.

You could create an array of booleans set to false, and then:

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;
}

This approach works if your subset is smaller than your total size by a significant margin. As those sizes get close to one another (ie, 1/4 the size or something), you'd get more collisions on that random number generator. In that case, I'd make a list of integers the size of your larger array, and then shuffle that list of integers, and pull off the first elements from that to get your (non-colliding) indeces. That way, you have the cost of O(n) in building the integer array, and another O(n) in the shuffle, but no collisions from an internal while checker and less than the potential O(5n) that remove may cost.

---

I'd personal opt for your initial implementation: very concise. Performance testing will show how well it scales. I've implemented a very similar block of code in a decently abused method and it scaled sufficiently. The particular code relied on arrays containing >10,000 items as well.

---

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

---

This is a very similar question on stackoverflow.

To summarize my favorite answers from that page (furst one from user Kyle):

• O(n) solution: Iterate through your list, and copy out an element (or reference thereto) with probability (#needed / #remaining). Example: if k = 5 and n = 100, then you take the first element with prob 5/100. If you copy that one, then you choose the next with prob 4/99; but if you didn't take the first one, the prob is 5/99.
• O(k log k) or O(k²): Build a sorted list of k indices (numbers in {0, 1, ..., n-1}) by randomly choosing a number < n, then randomly choosing a number < n-1, etc. At each step, you need to recallibrate your choice to avoid collisions and keep the probabilities even. As an example, if k=5 and n=100, and your first choice is 43, your next choice is in the range [0, 98], and if it's >=43, then you add 1 to it. So if your second choice is 50, then you add 1 to it, and you have {43, 51}. If your next choice is 51, you add 2 to it to get {43, 51, 53}.

Here is some pseudopython -

# 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 

I'm saying that the time complexity is O(k²) or O(k log k) because it depends on how quickly you can search and insert into your container for s. If s is a normal list, one of those operations is linear, and you get k^2. However, if you're willing to build s as a balanced binary tree, you can get out the O(k log k) time.

---

two solutions I don't think appear here - the corresponds is quite long, and contains some links, however, I don't think all of the posts relate to the problem of choosing a subst of K elemetns out of a set of N elements. [By "set", I refer to the mathematical term, i.e. all elements appear once, order is not important].

Sol 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--;
}

This looks similar to the answer daniel gave, but it actually is very different. It is of O(k) run time.

Another solution is to use some math: consider the array indexes as Z_n and so we can choose randomly 2 numbers, x which is co-prime to n, i.e. chhose gcd(x,n)=1, and another, a, which is "starting point" - then the series: a % n,a+x % n, a+2*x % n,...a+(k-1)*x%n is a sequence of distinct numbers (as long as k<=n).

참고URL : https://stackoverflow.com/questions/136474/best-way-to-pick-a-random-subset-from-a-collection