세트의 n 번째 요소를 Java에서 여러 번 가져 오기

Question

Java에서 n 번째 요소를 가져 오는 효율적인 방법이 있습니까? 나는 그것을하는 2 가지 방법을 알고있다 : - 필요한 요소에 도달 할 때까지 반복을 통해 - ArrayList로 변환하고 그 ArrayList에서 요소를 가져옴 질문은 거기에 다른 방법으로 n 번째 그것의 요소. 주로 TreeSets과 같은 기능이 필요합니다.

EDIT : 예를 들어 10 만 000 개의 긴 트리 맵 또는 트리 세트에서 1000 개의 임의 요소를 매우 자주 (즉, 2-3 초마다) 선택하고 싶다면 arraylist에게 항상 복제하는 것이 좋습니다. 비효율적이며 너무 많은 요소를 반복하는 것은 비효율적입니다.

Answer 1

통계적 샘플링과 같은 종류의 임의 위치에서 n 개의 요소가 필요하다고 확신하는 경우 세트를 한 번 반복하여 샘플을 가져 와서 원하는대로 확률은입니다. 이 방법은 세트를 한 번만 반복 할 때보다 효율적입니다.이 프로그램의

import java.util.ArrayList; 
import java.util.Iterator; 
import java.util.List; 
import java.util.Random; 
import java.util.Set; 
import java.util.TreeSet; 

public class SamplingFromSet { 

    public static void main(String[] args) { 
     Set<String> population = new TreeSet<>(); 

     /* 
     * Populate the set 
     */ 
     final int popSize = 17; 
     for (int i=0; i<popSize; i++) { 
      population.add(getRandomString()); 
     } 

     List<String> sample 
      = sampleFromPopulation(population, 3 /*sampleSize */); 

     System.out.println("population is"); 
     System.out.println(population.toString()); 
     System.out.println("sample is"); 
     System.out.println(sample.toString()); 

    } 


    /** 
    * Pick some samples for a population 
    * @param population 
    * @param sampleSize - number of samples 
    * @return 
    */ 
    private static <T> 
    List<T> sampleFromPopulation(Set<T> population 
            , int sampleSize) { 
     float sampleProb = ((float) sampleSize)/population.size(); 
     List<T> sample = new ArrayList<>(); 
     Iterator<T> iter = population.iterator(); 
     while (iter.hasNext()) { 
      T element = iter.next(); 
      if (random.nextFloat()<sampleProb) { 
       /* 
       * Lucky Draw! 
       */ 
       sample.add(element); 
      } 
     } 
     return sample; 
    } 


    private static Random random = new Random();  

    private static String getRandomString() { 
     return String.valueOf(random.nextInt()); 
    } 
} 

출력 :

다음 프로그램이 아이디어를 보여줍니다

population is 
[-1488564139, -1510380623, -1980218182, -354029751, -564386445, -57285541, -753388655, -775519772, 1538266464, 2006248253, 287039585, 386398836, 435619764, 48109172, 580324150, 64275438, 860615531] 
sample is 
[-57285541, -753388655, 386398836] 

업데이트

위의 프로그램을하지만,주의를 가지고 - 이후 그 세트를 통해 걸어 다니는 샘플이 인 확률은 확률로입니다.210 반환 된 sample은 오늘의 행운에 따라 지정된 것보다 더 많거나 많은 샘플을 가지고 있습니다. 이 문제는, 그러나, 절차의 약간의 변화, 약간 다른 방법 서명 사용 으로 해결할 수 있습니다 오버 샘플링의

/** 
* Pick some samples from a population 
* @param population 
* @param sampleSize - number of samples 
* @param exactSize - a boolean to control whether or not 
* the returned sample list must be of the exact size as 
* specified. 
* @return 
*/ 
private static <T> 
List<T> sampleFromPopulation(Set<T> population 
           , int sampleSize 
           , boolean exactSize); 

방지를 인구를 통해 하나 개의 반복에서

, 우리 샘플 비트, 그리고 나서 우리가 너무 많은 것을 가지고 있다면 결국 샘플을 버립니다. 그

참고 또한 언더의

방지, 심지어 오버 샘플링과 인구를 통해 하나의 반복의 끝에서, 우리는 여전히 원하는 미만의 샘플을 얻을, 비 - 제로 확률 있다 . 그럴 경우 (있을 법하지 않음) 재귀 적으로 두 번째 시도와 동일한 방법으로 을 다시 호출합니다. (이 재귀는 매우 그와는 달리하기 때문에 하나의 이 방법으로 반복 순환 통화, 종료 접근 확률을 가지고, 우리는 지속적으로 언더를 얻을.)

는

다음 코드는 새로운 sampleFromPopulation() 방법을 구현합니다

private static <T> 
List<T> sampleFromPopulation(Set<T> population 
           , int sampleSize 
           , boolean exactSize) { 
    int popSize = population.size(); 
    double sampleProb = ((double) sampleSize)/popSize; 

    final double OVER_SAMPLING_MULIT = 1.2; 
    if (exactSize) { 
     /* 
     * Oversampling to enhance of chance of getting enough 
     * samples (if we then have too many, we will drop them 
     * later) 
     */ 
     sampleProb = sampleProb * OVER_SAMPLING_MULIT; 
    } 
    List<T> sample = new LinkedList<>(); // linked list for fast removal 
    Iterator<T> iter = population.iterator(); 
    while (iter.hasNext()) { 
     T element = iter.next(); 
     if (random.nextFloat()<sampleProb) { 
      /* 
      * Lucky Draw! 
      */ 
      sample.add(element); 
     } 
    } 
    int samplesTooMany = sample.size() - sampleSize; 
    if (!exactSize || samplesTooMany==0) { 
     return sample; 
    } else if (samplesTooMany>0) { 
     Set<Integer> indexesToRemoveAsSet = new HashSet<>(); 
     for (int i=0; i<samplesTooMany;) { 
      int candidate = random.nextInt(sample.size()); 
      if (indexesToRemoveAsSet.add(candidate)) { 
       /* 
       * add() returns true if candidate was not 
       * previously in the set 
       */ 
       i++; // proceed to draw next index 
      } 
     } 
     List<Integer> indexesToRemoveAsList 
      = new ArrayList<>(indexesToRemoveAsSet); 
     Collections.sort(indexesToRemoveAsList 
       , (i1, i2) -> i2.intValue() - i1.intValue()); // desc order 
     /* 
     * Now we drop from the tail of the list 
     */ 
     for (Integer index : indexesToRemoveAsList) { 
      sample.remove((int) index); // remove by index (not by element) 
     } 
     return sample; 
    } else { 
     /* 
     * we were unluckly that we oversampling we still 
     * get less samples than specified, so here we call 
     * this very same method again recursively 
     */ 
     return sampleFromPopulation(population, sampleSize, exactSize); 
    } 
} 

을

Answer 2

귀하의 요구 사항이 거대한 세트에서 임의의 요소를 선택하는 것이라면 세트가 그 세트에 가장 적합한 지 스스로에게 물어야합니다.

내장 세트를 사용하려면 몇 가지 문제가 있습니다.

TreeSet의

TreeSet의가있는 당신은 n 번째 요소에 액세스 할 수 있도록 할 따라서 설정 주문하고. 그러나 ArrayList와 같은 임의 액세스를 허용하는 배열이 없기 때문에 n 위치로 반복해야합니다. 이름에서 알 수 있듯이 TreeSet의 노드는 트리를 형성하고 노드는 메모리의 어느 위치 에나 저장됩니다. 이 때문에 n 번째 요소를 얻으려면 첫 번째 노드에서 시작하여 노드에서 노드로 이동하여 n 위치에 도달해야합니다. 이는 LinkedList에서 수행하는 것과 유사합니다.

만약 당신이 몇 가지 옵션이 임의의 요소를 선택하기 만 원하는 모든 : 설정 변경 (또는하지 자주) 당신이 일치하는 배열을 만들 수 있습니다 또는 ArrayList를 및 랜덤 액세스를 사용하지 않는

• 경우 .
• 임의의 횟수만큼 집합을 반복합니다.
• 임의의 키를 생성하고 다음 상위/하위 요소를 조회합니다 (예 : tailSet(randomKey)을 사용하고 해당 꼬리 세트의 첫 번째 요소를 가져옵니다. 물론 요소의 범위를 벗어난 무작위 키를 처리해야합니다. 그렇게하면 조회는 기본적으로 2 진 검색이됩니다.

HashSets 기본적으로 2 가지로 구성 HashSet의 2 개 요소는 동일한 버킷에 매핑 될 경우, 버킷의 배열과의 충돌에 대한 링크 된리스트 또는 트리, 즉. 무작위 요소를 얻는 것은 랜덤 버킷에 접근하여 수행 할 수 있습니다 (랜덤 액세스). 그런 다음 임의의 시간 동안 해당 버킷의 요소를 반복합니다.