Получение n-го элемента набора несколько раз в Java

Question

Есть ли эффективный способ для получения n-го элемента набора в Java? Я знаю два способа сделать это: - Итерируя его до тех пор, пока не дойду до нужного элемента - Преобразуя его в ArrayList и получая элементы из этого массива ArrayList Вопрос в том, что есть какой-либо другой способ получить n-й элемент его быстро. Мне понадобилась бы такая функция для TreeSets.

EDIT: Например, если я хочу выбрать 1000 случайных элементов из длинного treemap или treeet размером 10 000 000 элементов, очень часто (т.е. каждые 2-3 секунды), а затем клонирование его арраисту все время очень неэффективен, и итерация через множество элементов также неэффективна.

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] 

Update

выше программа, однако, имеет один нюанс - поскольку сбор образцов в том, что один проход через множество производится по вероятности, возвращенный 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); 

Предотвращение передискретизации

В одной итерации населения, мы над образцом немного, , а затем в конце мы бросаем некоторые образцы, если у нас их слишком много.

Профилактика субсэмплирования

Следует также отметить, что даже при передискретизации, существует ненулевая вероятность , что, в конце одной итерации населения, мы до сих пор получить меньше образцов, чем хотелось бы , Если это произойдет (маловероятно), мы рекурсивно будем называть тем же методом, что и вторая попытка. (Это рекурсия имеет вероятность приближающуюся один прекратить, потому что это очень непохоже, что при повторном рекурсивные вызова в метод, мы последовательно получаем Undersampling.)

Следующий код реализует новый 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. Поскольку название подразумевает узлы в форме TreeSet, дерево и узлы, скорее всего, хранятся в любом месте в памяти. Из-за этого, чтобы получить n-й элемент, вам нужно будет начинать с первого узла и переходить от узла к узлу, пока не достигнете позиции n - что похоже на то, как вы это сделаете в LinkedList.

Если все, что вы хотите сделать, это выбрать случайный элемент существует несколько вариантов:

• Если набор не меняется (или не часто), вы можете создать массив соответствия или ArrayList и использовать произвольный доступ ,
• Итерации над множеством для случайного числа раз.
• Создайте случайный ключ и найдите следующий элемент выше/ниже, например. используя tailSet(randomKey) и получив первый элемент этого набора хвостов. Конечно, вам придется обрабатывать случайные ключи, находящиеся вне диапазона элементов. Таким образом, поиск будет в основном бинарным поиском.

HashSet

HashSets в основном состоит из 2-х вещей: массив ковшей и связанный списка или дерева для столкновений, то есть если 2 элементов будут отображаться в том же ведро. Получение случайного элемента может быть выполнено путем доступа к случайному ведру (это был бы произвольный доступ), а затем итерация по элементам в этом ведре случайным числом раз.