Если вы пытаетесь выбрать k отдельных элементов из списка из n, приведенные выше методы будут O (n) или O (kn), потому что удаление элемента из вектора приведет к сдвигу массива элементы вниз.
Поскольку вы запрашиваете наилучший способ, это зависит от того, что вам разрешено делать с вашим списком ввода.
Если допустимо изменить список ввода, как в ваших примерах, то вы можете просто поменять k случайных элементов в начале списка и вернуть их за O (k) время следующим образом:
public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
Random r = new Random();
int inputSize = input.size();
for (int i = 0; i < subsetSize; i++)
{
int indexToSwap = i + r.nextInt(inputSize - i);
T temp = input.get(i);
input.set(i, input.get(indexToSwap));
input.set(indexToSwap, temp);
}
return input.subList(0, subsetSize);
}
Если список должен заканчиваться в том же состоянии, в котором он был создан, вы можете отслеживать позиции, которые вы поменяли местами, а затем вернуть копию в исходное состояние после копирования выбранного вами подсписка. Это все еще решение O (k).
Если, однако, вы не можете изменить список ввода вообще, а k намного меньше n (например, 5 из 100), было бы намного лучше не удалять выбранные элементы каждый раз, а просто выбирать каждый элемент, и если Вы когда-либо получаете дубликат, выбрасываете его и повторно выбираете. Это даст вам O (kn / (n-k)), который все еще близок к O (k), когда n доминирует над k. (Например, если k меньше n / 2, то оно уменьшается до O (k)).
Если в k не доминирует n, и вы не можете изменить список, вы также можете скопировать свой исходный список и использовать свое первое решение, потому что O (n) будет так же хорошо, как O (k).
Как уже отмечали другие, если вы зависите от сильной случайности, где возможен (и беспристрастен) каждый подсписок, вам определенно понадобится что-то более сильное, чем java.util.Random. Смотри java.security.SecureRandom.