java - 在 Java 中多次获取集合的第 n 个元素

Question

在Java中是否有任何有效的方法来获取集合的第n个元素？ 我知道有两种方法: - 迭代它直到到达所需的元素 - 通过将其转换为 ArrayList 并从该 ArrayList 获取元素 问题是有没有其他方法可以快速得到它的第n个元素。我主要需要像 TreeSets 这样的功能。

编辑: 例如，如果我想从 10 000 000 个元素长的 TreeMap 或树集中非常频繁地(即每 2-3 秒)选择 1000 个随机元素，那么一直将其克隆到数组列表的效率非常低，并且迭代这么多elements 的效率也很低。

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]

更新

然而，上述程序有一个警告——因为 通过概率完成一次遍历集合的样本数， 返回的样本可能取决于您当天的运气， 样本数量少于或超过指定数量。 然而，这个问题可以通过稍微改变程序来解决， 它使用稍微不同的方法签名:

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