实现功能
从一个大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
