高效的从一个大List中获取一个随机子List

实现功能

从一个大List中随机取出N个值，并且同一值（指同一个下标）只会取一次。

JAVA代码

import java.util.*;

/**
 * 获取随机子列表
 * @Author: leven
 */
public class RandomLists {

    private static Random r;

    /**
     * 获取随机子列表
     * @param source 原列表
     * @param limit 子列表长度
     * @param <T> 列表原类型
     * @return 子列表
     */
    public static <T> List<T> newRandomList(List<T> source, int limit) {
        if(source == null || source.size() == 0 || source.size() <= limit){
            return source;
        }

        Set<Integer> set = createRandomSet(source.size(), limit);
        Integer[] array = set.toArray(new Integer[0]);
        return new RandomList<>(source, array);
    }

    /**
     * 创建一个随机的有序下标Set
     * @param listSize 原列表长度
     * @param limit 子列表长度
     * @return 随机的下标Set
     */
    private static Set<Integer> createRandomSet(int listSize, int limit) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random();

        Set<Integer> set = new HashSet<>(limit);
        for (int i = 0; i < limit; i++) {
            int value = rnd.nextInt(listSize);
            if (!add(set, value, listSize)) {
                return set;
            }
        }
        return set;
    }

    /**
     * 往Set中添加一个随机值，如果有冲突，则取随机值+1
     */
    private static boolean add(Set<Integer> set, int value, int size) {
        if (set.size() == size) {
            return false;
        }

        if (!set.contains(value)) {
            return set.add(value);
        }

        int nextValue = value + 1;
        if (nextValue == size) {
            nextValue = 0;
        }
        return add(set, nextValue, size);
    }

    private static class RandomList<T> extends AbstractList<T> {
        final List<T> list;
        final Integer[] indexs;

        RandomList(List<T> list, Integer[] indexs) {
            this.list = list;
            this.indexs = indexs;
        }

        @Override
        public T get(int index) {
            if(index < 0 || index >= indexs.length)
            throw new IndexOutOfBoundsException("The start index was out of bounds: "
                    + index + " >= " + indexs.length);
            int start = indexs[index];
            return list.get(start);
        }

        @Override
        public int size() {
            return indexs.length;
        }

        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    }
}

使用方法

List<Integer> list = Arrays.asList(0,1,2,3,4,5,6,7,8,9);
List<Integer> subList = RandomLists.newRandomList(list, 5);

测试用例

import org.openjdk.jmh.annotations.*;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: leven
 */

@State(Scope.Benchmark)
public class RandomListsBenchmarkTest {

    @Param({"10","100","500"})
    int limit;
    @Param({"1000","10000","100000"})
    int sourceSize = 10000;
    List<Integer> list = new LinkedList<>();
    @Setup
    public void before(){
        for (int i = 0; i < sourceSize; i++) {
            list.add(i);
        }
    }

    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5)
    @Threads(1)
    @Fork(1)
    @Benchmark
    public List<Integer> newRandomList() {
        return RandomLists.newRandomList(list, limit);
    }

    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5)
    @Threads(1)
    @Fork(1)
    @Benchmark
    public List<Integer> newRandomListV2() {
        Collections.shuffle(list);
        return list.subList(0, limit);
    }
}

测试结果

结果：无论大List有多大，性能表现都很稳定，随机取500个单线程每秒可以执行4万次。

//使用shuffle+sublist作为对照组B比较耗时
//测试了3*3个场景情况，报告很长直接看结论

Benchmark                                                         (limit)  (sourceSize)    Mode     Cnt        Score    Error  Units
RandomListsBenchmarkTest.newRandomList                                 10          1000   thrpt       2  2714506.228           ops/s
RandomListsBenchmarkTest.newRandomList                                 10         10000   thrpt       2  2976543.261           ops/s
RandomListsBenchmarkTest.newRandomList                                 10        100000   thrpt       2  2867262.991           ops/s
RandomListsBenchmarkTest.newRandomList                                100          1000   thrpt       2   236765.344           ops/s
RandomListsBenchmarkTest.newRandomList                                100         10000   thrpt       2   227964.888           ops/s
RandomListsBenchmarkTest.newRandomList                                100        100000   thrpt       2   226400.881           ops/s
RandomListsBenchmarkTest.newRandomList                                500          1000   thrpt       2    46274.951           ops/s
RandomListsBenchmarkTest.newRandomList                                500         10000   thrpt       2    43491.168           ops/s
RandomListsBenchmarkTest.newRandomList                                500        100000   thrpt       2    46246.838           ops/s
RandomListsBenchmarkTest.newRandomListV2                               10          1000   thrpt       2    71911.650           ops/s
RandomListsBenchmarkTest.newRandomListV2                               10         10000   thrpt       2     5900.953           ops/s
RandomListsBenchmarkTest.newRandomListV2                               10        100000   thrpt       2      541.457           ops/s
RandomListsBenchmarkTest.newRandomListV2                              100          1000   thrpt       2    71728.840           ops/s
RandomListsBenchmarkTest.newRandomListV2                              100         10000   thrpt       2     6015.386           ops/s
RandomListsBenchmarkTest.newRandomListV2                              100        100000   thrpt       2      540.522           ops/s
RandomListsBenchmarkTest.newRandomListV2                              500          1000   thrpt       2    71526.677           ops/s
RandomListsBenchmarkTest.newRandomListV2                              500         10000   thrpt       2     5884.802           ops/s
RandomListsBenchmarkTest.newRandomListV2                              500        100000   thrpt       2      540.895           ops/s