(As pointed out in Comment, there is some room for efficiency improvement.)
Comment of Hokuhoku no Imo This is the method I thought of for.
This section describes how to efficiently extract multiple elements randomly from the list without duplication. The "list" here is a variable-length, randomly accessible list [^ variable-length, randomly accessible list].
[^ Variable-length randomly accessible list]: java.util.ArrayList for Java, ʻArray for JavaScript, std: vector` for C ++
The explanation is given in Java, but the final code that has been functionalized for reuse is provided in Java, JavaScript, and Kotlin.
In the Java code example, suppose the following ʻimport` statement is declared at the beginning of the file.
Java
import java.util.*;
It's easy to randomly pick just one element from the list.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,List with 4 elements of D
int index = new Random().nextInt(list.size()); //Randomly selected integer greater than or equal to 0 and less than 4
Character result = list.get(index); //Randomly selected elements
System.out.println(result); //Output example> B
Retrieving all the elements in a random order is also easy if the standard library has such a function.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,List with 4 elements of D
List<Character> shuffled = new ArrayList<>(list); //A copy of the list that is then randomly sorted
Collections.shuffle(shuffled); //Randomly sort the elements of shuffled.
System.out.println(shuffled); //Output example> [C, A, D, B]
So how about retrieving multiple elements, not all elements, in a random order?
Java (Note: Inefficient)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,List with 4 elements of D
List<Character> shuffled = new ArrayList<>(list); //A copy of the list that is then randomly sorted
Collections.shuffle(shuffled); //Randomly sort the elements of shuffled.
List result = shuffled.subList(0, 2); //New list with two elements from the front of shuffled
System.out.println(result); //Output example> [C, B]
No, it's easy to write this, There is a lot of waste because all the elements are shuffled. If you shuffle 10,000 elements when you retrieve 100 elements from a list of 10,000 elements, 9900 elements will be wasted.
Then what do you do?
Randomly select only one element, remove the selected element from the list, and so on.
Java (Note: Inefficient)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,List with 4 elements of D
List<Character> result = new ArrayList<>(); //A list with randomly selected elements
List<Character> remaining = new ArrayList<>(list); //List of remaining elements
Random random = new Random(); //Random number generator
for (int i = 0; i < 2; i++) { //Repeat twice.
int remainingCount = remaining.size(); //Number of remaining elements
int index = random.nextInt(remainingCount); //Randomly selected index
Character element = remaining.remove(index); //Fetch randomly selected elements.
result.add(element); //Have Randomly Selected Elements Add a randomly selected element to the end of the list.
}
System.out.println(result); //Output example> [B, D]
There is no useless shuffle. However, this is also inefficient.
Randomly accessible lists internally use arrays to hold elements If you delete an element in the middle, the process of stuffing the elements after that will be performed.
|A|B|C|D| | | | |
↓ Delete B
|A|C|D| | | | | |
Therefore, the earlier the element to be deleted, the longer the processing time.
Then what should I do?
It's slow because it deletes the elements in the middle. Delete only the end. Let's replace the elements in the middle without deleting them.
When deleting B
|A|B|C|D| | | | |
↓ Delete the D at the end and
|A|B|C| | | | | |
↓ Replace B with D.
|A|D|C| | | | | |
The code looks like this:
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,List with 4 elements of D
List<Character> result = new ArrayList<>(); //A list with randomly selected elements
List<Character> remaining = new ArrayList<>(list); //List of remaining elements
Random random = new Random(); //Random number generator
for (int i = 0; i < 2; i++) { //Repeat twice.
int remainingCount = remaining.size(); //Number of remaining elements
int index = random.nextInt(remainingCount); //Randomly selected index
Character element = remaining.get(index); //Randomly selected elements
result.add(element); //Have Randomly Selected Elements Add a randomly selected element to the end of the list.
int lastIndex = remainingCount - 1; //Index at the end of the list of remaining elements
Character lastElement = remaining.remove(lastIndex); //Remove the end from the list of remaining elements.
if (index < lastIndex) { //If the randomly selected element is other than the end ...
remaining.set(index, lastElement); //Replace it with the last element.
}
}
System.out.println(result); //Output example> [D, A]
Let's easily measure the difference in processing speed. Compare the one that shuffles all the elements to get the first partial list with the last one that is the least wasteful.
If you set the number of elements in the list to 100,000 and randomly acquire 50,000 from it, Approximately 590ms for all element shuffle If there is no waste, it will be about 370ms.
Java
public class TakeAtRandom {
public static void main(String... args) {
//List size
final int LIST_SIZE = 10_000_000;
//Number of elements to get from the list
final int N = 5_000_000;
//Number of repetitions
final int REPETITION = 100;
final List<Integer> list = new ArrayList<>(LIST_SIZE);
for (int i = 0; i < LIST_SIZE; i++) {
list.add(i);
}
final Random random = new Random();
for (int i = 0; i < REPETITION; i++) {
{
final long startAt = System.currentTimeMillis();
takeFromShuffled(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format("Shuffle all elements: %,d ms", finishedAt - startAt));
}
{
final long startAt = System.currentTimeMillis();
takeAtRandom(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format("No waste: %,d ms", finishedAt - startAt));
}
System.out.println();
}
}
public static <T> List<T> takeFromShuffled(List<T> list, int n, Random random) {
final List<T> workList = new ArrayList<>(list);
Collections.shuffle(workList);
return workList.subList(0, n);
}
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
final List<T> taken = new ArrayList<>(n); //A list with randomly selected elements
final List<T> remaining = new ArrayList<>(list); //List of remaining elements
for (int i = 0; i < n; i++) { //Repeat n times.
final int remainingCount = remaining.size(); //Number of remaining elements
final int index = random.nextInt(remainingCount); //Randomly selected index
final T element = remaining.get(index); //Randomly selected elements
taken.add(element); //Add a randomly selected element to the end of the list of randomly selected elements.
final int lastIndex = remainingCount - 1; //Index at the end of the list of remaining elements
final T lastElement = remaining.remove(lastIndex); //Remove the end from the list of remaining elements.
if (index < lastIndex) { //If the randomly selected element is other than the end ...
remaining.set(index, lastElement); //Replace it with the last element.
}
}
return taken;
}
}
Output example
Shuffle all elements:608 ms no waste: 705 ms
Shuffle all elements:659 ms no waste: 1,985 ms
Shuffle all elements:585 ms no waste: 372 ms
Shuffle all elements:598 ms no waste: 378 ms
Shuffle all elements:598 ms no waste: 397 ms
Shuffle all elements:586 ms no waste: 451 ms
Shuffle all elements:583 ms no waste: 381 ms
Shuffle all elements:584 ms no waste: 391 ms
Shuffle all elements:580 ms no waste: 383 ms
Shuffle all elements:578 ms no waste: 383 ms
Shuffle all elements:584 ms no waste: 377 ms
Shuffle all elements:585 ms no waste: 378 ms
Shuffle all elements:598 ms no waste: 381 ms
Shuffle all elements:591 ms no waste: 359 ms
Shuffle all elements:605 ms no waste: 354 ms
Shuffle all elements:590 ms no waste: 373 ms
Shuffle all elements:584 ms no waste: 379 ms
Shuffle all elements:586 ms no waste: 359 ms
Shuffle all elements:603 ms no waste: 357 ms
Shuffle all elements:589 ms no waste: 376 ms
Shuffle all elements:579 ms no waste: 385 ms
Shuffle all elements:581 ms no waste: 352 ms
Shuffle all elements:610 ms no waste: 350 ms
Shuffle all elements:587 ms no waste: 372 ms
Shuffle all elements:603 ms no waste: 381 ms
Shuffle all elements:595 ms no waste: 353 ms
Shuffle all elements:606 ms no waste: 348 ms
Shuffle all elements:579 ms no waste: 376 ms
Shuffle all elements:576 ms no waste: 390 ms
Shuffle all elements:582 ms no waste: 359 ms
Shuffle all elements:602 ms no waste: 357 ms
Shuffle all elements:583 ms no waste: 375 ms
Shuffle all elements:585 ms no waste: 379 ms
Shuffle all elements:586 ms no waste: 353 ms
Shuffle all elements:603 ms no waste: 350 ms
Shuffle all elements:590 ms no waste: 370 ms
Shuffle all elements:587 ms no waste: 376 ms
Shuffle all elements:586 ms no waste: 351 ms
Shuffle all elements:600 ms no waste: 359 ms
Shuffle all elements:585 ms no waste: 379 ms
Shuffle all elements:579 ms no waste: 382 ms
Shuffle all elements:580 ms no waste: 352 ms
Shuffle all elements:605 ms no waste: 349 ms
Shuffle all elements:588 ms no waste: 372 ms
Shuffle all elements:586 ms no waste: 375 ms
Shuffle all elements:584 ms no waste: 351 ms
Shuffle all elements:598 ms no waste: 358 ms
Shuffle all elements:579 ms no waste: 376 ms
Shuffle all elements:579 ms no waste: 381 ms
Shuffle all elements:578 ms no waste: 357 ms
Shuffle all elements:601 ms no waste: 348 ms
Shuffle all elements:593 ms no waste: 371 ms
Shuffle all elements:585 ms no waste: 376 ms
Shuffle all elements:584 ms no waste: 352 ms
Shuffle all elements:602 ms no waste: 349 ms
Shuffle all elements:586 ms no waste: 372 ms
Shuffle all elements:586 ms no waste: 376 ms
Shuffle all elements:578 ms no waste: 359 ms
Shuffle all elements:598 ms no waste: 357 ms
Shuffle all elements:583 ms no waste: 379 ms
Shuffle all elements:578 ms no waste: 382 ms
Shuffle all elements:592 ms no waste: 356 ms
Shuffle all elements:605 ms no waste: 350 ms
Shuffle all elements:587 ms no waste: 374 ms
Shuffle all elements:586 ms no waste: 377 ms
Shuffle all elements:586 ms no waste: 353 ms
Shuffle all elements:600 ms no waste: 357 ms
Shuffle all elements:581 ms no waste: 380 ms
Shuffle all elements:580 ms no waste: 380 ms
Shuffle all elements:580 ms no waste: 352 ms
Shuffle all elements:605 ms no waste: 349 ms
Shuffle all elements:592 ms no waste: 373 ms
Shuffle all elements:585 ms no waste: 374 ms
Shuffle all elements:585 ms no waste: 352 ms
Shuffle all elements:598 ms no waste: 357 ms
Shuffle all elements:580 ms no waste: 377 ms
Shuffle all elements:582 ms no waste: 383 ms
Shuffle all elements:578 ms no waste: 362 ms
Shuffle all elements:611 ms no waste: 358 ms
Shuffle all elements:581 ms no waste: 375 ms
Shuffle all elements:594 ms no waste: 377 ms
Shuffle all elements:587 ms no waste: 362 ms
Shuffle all elements:603 ms no waste: 350 ms
Shuffle all elements:587 ms no waste: 373 ms
Shuffle all elements:585 ms no waste: 376 ms
Shuffle all elements:586 ms no waste: 353 ms
Shuffle all elements:601 ms no waste: 358 ms
Shuffle all elements:593 ms no waste: 378 ms
Shuffle all elements:580 ms no waste: 384 ms
Shuffle all elements:577 ms no waste: 351 ms
Shuffle all elements:606 ms no waste: 349 ms
Shuffle all elements:589 ms no waste: 380 ms
Shuffle all elements:590 ms no waste: 352 ms
Shuffle all elements:605 ms no waste: 348 ms
Shuffle all elements:590 ms no waste: 375 ms
Shuffle all elements:581 ms no waste: 359 ms
Shuffle all elements:599 ms no waste: 357 ms
Shuffle all elements:581 ms no waste: 381 ms
Shuffle all elements:579 ms no waste: 353 ms
Shuffle all elements:607 ms no waste: 349 ms
I made it a function so that it can be reused.
Java
Java
import java.util.*;
public class TakeAtRandom {
/**
*Randomly retrieves the specified number of elements from the list without duplication.
*
* @param list Extracts elements from this list. This list does not change.
* @param n Number of elements to retrieve.
* @param <T>Element type.
* @return A list with the retrieved elements.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n) {
return takeAtRandom(list, n, new Random());
}
/**
*Randomly retrieves the specified number of elements from the list without duplication.
*
* @param list Extracts elements from this list. This list does not change.
* @param n Number of elements to retrieve.
* @param random The random number generator to use.
* @param <T>Element type.
* @return A list with the retrieved elements.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
if (list == null) {
throw new IllegalArgumentException("The value of the argument list is null.");
}
if (n > list.size()) {
throw new IllegalArgumentException(
String.format("The value of the argument n%d is the size of the argument list%Greater than d.",
n, list.size()));
}
if (random == null) {
throw new IllegalArgumentException("The value of the argument random is null.");
}
final List<T> taken = new ArrayList<>(n); //A list with randomly selected elements
final List<T> remaining = new ArrayList<>(list); //List of remaining elements
for (int i = 0; i < n; i++) { //Repeat n times.
final int remainingCount = remaining.size(); //Number of remaining elements
final int index = random.nextInt(remainingCount); //Randomly selected index
final T element = remaining.get(index); //Randomly selected elements
taken.add(element); //Add a randomly selected element to the end of the list of randomly selected elements.
final int lastIndex = remainingCount - 1; //Index at the end of the list of remaining elements
final T lastElement = remaining.remove(lastIndex); //Remove the end from the list of remaining elements.
if (index < lastIndex) { //If the randomly selected element is other than the end ...
remaining.set(index, lastElement); //Replace it with the last element.
}
}
return taken;
}
}
JavaScript
JavaScript
/**
*Randomly retrieve the specified number of elements from the array without duplication.
*
* @param {Array}array Extracts elements from this array. This array does not change.
* @param {number}n Number of elements to retrieve.
* @return {Array}An array with the retrieved elements.
*/
function takeAtRandom(array, n) {
if (array == null) {
throw new Error("The value of the argument array is null or undefined.");
}
if (n > array.length) {
throw new Error(`The value of the argument n${n}Is the size of the argument array${array.length}Is larger.`);
}
const taken = [];
const remaining = array.concat();
for (let i = 0; i < n; i++) {
const remainingCount = remaining.length;
const index = Math.floor(Math.random() * remainingCount);
const element = remaining[index];
taken.push(element);
const lastIndex = remainingCount - 1;
const lastElement = remaining.pop(lastIndex);
if (index < lastIndex) {
remaining[index] = lastElement;
}
}
return taken;
}
JavaScript
/**
*Returns a generator that randomly picks elements from an array without duplication.
*
* @param {Array}array Extracts elements from this array. This array does not change.
*/
function* takeAtRandom(array) {
if (array == null) {
throw new Error("The value of the argument array is null or undefined.");
}
const remaining = array.concat();
while(true) {
const remainingCount = remaining.length;
if (remainingCount === 0) {
break;
}
const index = Math.floor(Math.random() * remainingCount);
yield remaining[index];
const lastIndex = remainingCount - 1;
const lastElement = remaining.pop();
if (index < lastIndex) {
remaining[index] = lastElement;
}
}
}
Kotlin
Kotlin
import kotlin.random.Random
/**
*Randomly retrieves the specified number of elements from the list without duplication.
*
* @receiver Extracts an element from this list.
* @param n Number of elements to retrieve.
* @param random The random number generator to use.
* @param <T>Element type.
* @return A list with the retrieved elements.
*/
fun <T> Collection<T>.takeAtRandom(n: Int, random: Random = Random): List<T> {
require(n <= size) { "The value of the argument n$n is the size of the receiver${size}Is larger." }
val taken = mutableListOf<T>() //A list with randomly selected elements
val remaining = toMutableList() //List of remaining elements
//Repeat n times.
repeat(n) {
val remainingCount = remaining.size //Number of remaining elements
val index = random.nextInt(remainingCount) //Randomly selected index
taken += remaining[index] //Randomly selected elements
val lastIndex = remainingCount - 1 //Index at the end of the list of remaining elements
val lastElement = remaining.removeAt(lastIndex) //Remove the end from the list of remaining elements.
if (index < lastIndex) { //If the randomly selected element is other than the end ...
remaining[index] = lastElement //Replace it with the last element.
}
}
return taken
}
Kotlin
import kotlin.random.Random
/**
*Returns a sequence that randomly retrieves the specified number of elements from the list without duplication.
*
* @receiver Extracts an element from this list.
* @param random The random number generator to use.
* @param <T>Element type.
* @return sequence.
*/
fun <T> Collection<T>.toRandomSequence(random: Random = Random): Sequence<T> = sequence {
val remaining = toMutableList() //List of remaining elements
while (true) {
val remainingCount = remaining.size //Number of remaining elements
.takeIf { it > 0 }
?: break
val index = random.nextInt(remainingCount) //Randomly selected index
remaining[index].also {
yield(it)
}
val lastIndex = remainingCount - 1 //Index at the end of the list of remaining elements
val lastElement = remaining.removeAt(lastIndex) //Remove the end from the list of remaining elements.
if (index < lastIndex) { //If the randomly selected element is other than the end ...
remaining[index] = lastElement //Replace it with the last element.
}
}
}
/that's all
Recommended Posts