(Comme indiqué dans Comment, il est possible d'améliorer l'efficacité.)
Commentaire de Hokuhoku no Imo C'est la méthode à laquelle j'ai pensé.
Cette section décrit comment extraire efficacement plusieurs éléments d'une liste au hasard sans duplication. La "liste" ici est une liste de longueur variable accessible au hasard [^ liste de longueur variable accessible de manière aléatoire].
[^ Liste de longueur variable accessible aléatoirement]: java.util.ArrayList pour Java, ʻArray pour JavaScript, std: vector` pour C ++
L'explication est donnée en Java, mais le code final qui a été fonctionnalisé pour la réutilisation est fourni en Java, JavaScript et Kotlin.
Dans l'exemple de code Java, supposons que l'instruction ʻimport` suivante soit déclarée au début du fichier.
Java
import java.util.*;
Il est facile de choisir au hasard un seul élément de la liste.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste avec 4 éléments de D
int index = new Random().nextInt(list.size()); //Entier sélectionné au hasard supérieur ou égal à 0 et inférieur à 4
Character result = list.get(index); //Éléments sélectionnés au hasard
System.out.println(result); //Exemple de sortie> B
La récupération de tous les éléments dans un ordre aléatoire est également facile si la bibliothèque standard a une telle fonction.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste avec 4 éléments de D
List<Character> shuffled = new ArrayList<>(list); //Une copie de la liste qui est ensuite triée aléatoirement
Collections.shuffle(shuffled); //Triez au hasard les éléments de shuffled.
System.out.println(shuffled); //Exemple de sortie> [C, A, D, B]
Alors, que diriez-vous de récupérer plusieurs éléments, pas tous les éléments, dans un ordre aléatoire?
Java (Remarque: Inefficace)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste avec 4 éléments de D
List<Character> shuffled = new ArrayList<>(list); //Une copie de la liste qui est ensuite triée aléatoirement
Collections.shuffle(shuffled); //Triez au hasard les éléments de shuffled.
List result = shuffled.subList(0, 2); //Nouvelle liste avec deux éléments du début de la lecture aléatoire
System.out.println(result); //Exemple de sortie> [C, B]
Non, c'est facile d'écrire ça, Il y a beaucoup de gaspillage car tous les éléments sont mélangés. Si vous mélangez 10 000 éléments lorsque vous récupérez 100 éléments d'une liste de 10 000 éléments, 9900 éléments seront perdus.
Alors tu fais quoi?
Sélectionnez au hasard un seul élément, supprimez l'élément sélectionné de la liste, etc.
Java (Remarque: Inefficace)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste avec 4 éléments de D
List<Character> result = new ArrayList<>(); //Une liste avec des éléments sélectionnés au hasard
List<Character> remaining = new ArrayList<>(list); //Liste des éléments restants
Random random = new Random(); //Générateur aléatoire
for (int i = 0; i < 2; i++) { //Répétez deux fois.
int remainingCount = remaining.size(); //Nombre d'éléments restants
int index = random.nextInt(remainingCount); //Index sélectionné au hasard
Character element = remaining.remove(index); //Extrait des éléments sélectionnés au hasard.
result.add(element); //Avoir des éléments sélectionnés au hasard Ajoutez des éléments sélectionnés au hasard à la fin de la liste.
}
System.out.println(result); //Exemple de sortie> [B, D]
Il n'y a pas de mélange inutile. Cependant, cela est également inefficace.
Les listes accessibles au hasard utilisent des tableaux en interne pour contenir des éléments Si vous supprimez un élément au milieu, le processus de bourrage des éléments après cela sera effectué.
|A|B|C|D| | | | |
↓ Supprimer B
|A|C|D| | | | | |
Par conséquent, plus l'élément à supprimer est précoce, plus le traitement prend du temps.
Alors que dois-je faire?
C'est lent car cela supprime les éléments au milieu. Supprimez uniquement la fin. Remplaçons les éléments du milieu sans les supprimer.
Lors de la suppression de B
|A|B|C|D| | | | |
↓ Supprimez le D à la fin et
|A|B|C| | | | | |
↓ Remplacez B par D.
|A|D|C| | | | | |
Le code ressemble à ceci:
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste avec 4 éléments de D
List<Character> result = new ArrayList<>(); //Une liste avec des éléments sélectionnés au hasard
List<Character> remaining = new ArrayList<>(list); //Liste des éléments restants
Random random = new Random(); //Générateur aléatoire
for (int i = 0; i < 2; i++) { //Répétez deux fois.
int remainingCount = remaining.size(); //Nombre d'éléments restants
int index = random.nextInt(remainingCount); //Index sélectionné au hasard
Character element = remaining.get(index); //Éléments sélectionnés au hasard
result.add(element); //Avoir des éléments sélectionnés au hasard Ajoutez des éléments sélectionnés au hasard à la fin de la liste.
int lastIndex = remainingCount - 1; //Index à la fin de la liste des éléments restants
Character lastElement = remaining.remove(lastIndex); //Supprimez la fin de la liste des éléments restants.
if (index < lastIndex) { //Si l'élément sélectionné au hasard n'est pas la fin ...
remaining.set(index, lastElement); //Remplacez-le par le dernier élément.
}
}
System.out.println(result); //Exemple de sortie> [D, A]
Mesurons facilement la différence de vitesse de traitement. Comparez celui qui mélange tous les éléments pour obtenir la première liste partielle avec le dernier qui est le moins coûteux.
Si vous définissez le nombre d'éléments de la liste sur 100 000 et que vous en acquérez au hasard 50 000, Environ 590 ms pour la lecture aléatoire de tous les éléments S'il n'y a pas de déchets, ce sera environ 370 ms.
Java
public class TakeAtRandom {
public static void main(String... args) {
//Taille de la liste
final int LIST_SIZE = 10_000_000;
//Nombre d'éléments à extraire de la liste
final int N = 5_000_000;
//Nombre de répétitions
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("Mélanger tous les éléments: %,d ms", finishedAt - startAt));
}
{
final long startAt = System.currentTimeMillis();
takeAtRandom(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format("Pas de déchets: %,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); //Une liste avec des éléments sélectionnés au hasard
final List<T> remaining = new ArrayList<>(list); //Liste des éléments restants
for (int i = 0; i < n; i++) { //Répétez n fois.
final int remainingCount = remaining.size(); //Nombre d'éléments restants
final int index = random.nextInt(remainingCount); //Index sélectionné au hasard
final T element = remaining.get(index); //Éléments sélectionnés au hasard
taken.add(element); //Ajoutez des éléments sélectionnés au hasard à la fin de la liste des éléments sélectionnés au hasard.
final int lastIndex = remainingCount - 1; //Index à la fin de la liste des éléments restants
final T lastElement = remaining.remove(lastIndex); //Supprimez la fin de la liste des éléments restants.
if (index < lastIndex) { //Si l'élément sélectionné au hasard n'est pas la fin ...
remaining.set(index, lastElement); //Remplacez-le par le dernier élément.
}
}
return taken;
}
}
Exemple de sortie
Mélanger tous les éléments:608 ms pas de gaspillage: 705 ms
Mélanger tous les éléments:659 ms pas de gaspillage: 1,985 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 372 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 378 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 397 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 451 ms
Mélanger tous les éléments:583 ms pas de gaspillage: 381 ms
Mélanger tous les éléments:584 ms pas de gaspillage: 391 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 383 ms
Mélanger tous les éléments:578 ms pas de gaspillage: 383 ms
Mélanger tous les éléments:584 ms pas de gaspillage: 377 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 378 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 381 ms
Mélanger tous les éléments:591 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:605 ms pas de gaspillage: 354 ms
Mélanger tous les éléments:590 ms pas de gaspillage: 373 ms
Mélanger tous les éléments:584 ms pas de gaspillage: 379 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:603 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:589 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 385 ms
Mélanger tous les éléments:581 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:610 ms pas de gaspillage: 350 ms
Mélanger tous les éléments:587 ms pas de gaspillage: 372 ms
Mélanger tous les éléments:603 ms pas de gaspillage: 381 ms
Mélanger tous les éléments:595 ms pas de gaspillage: 353 ms
Mélanger tous les éléments:606 ms pas de gaspillage: 348 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:576 ms pas de gaspillage: 390 ms
Mélanger tous les éléments:582 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:602 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:583 ms pas de gaspillage: 375 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 379 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 353 ms
Mélanger tous les éléments:603 ms pas de gaspillage: 350 ms
Mélanger tous les éléments:590 ms pas de gaspillage: 370 ms
Mélanger tous les éléments:587 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 351 ms
Mélanger tous les éléments:600 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 379 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 382 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:605 ms pas de gaspillage: 349 ms
Mélanger tous les éléments:588 ms pas de gaspillage: 372 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 375 ms
Mélanger tous les éléments:584 ms pas de gaspillage: 351 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 358 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 381 ms
Mélanger tous les éléments:578 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:601 ms pas de gaspillage: 348 ms
Mélanger tous les éléments:593 ms pas de gaspillage: 371 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:584 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:602 ms pas de gaspillage: 349 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 372 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:578 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:583 ms pas de gaspillage: 379 ms
Mélanger tous les éléments:578 ms pas de gaspillage: 382 ms
Mélanger tous les éléments:592 ms pas de gaspillage: 356 ms
Mélanger tous les éléments:605 ms pas de gaspillage: 350 ms
Mélanger tous les éléments:587 ms pas de gaspillage: 374 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 377 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 353 ms
Mélanger tous les éléments:600 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:581 ms pas de gaspillage: 380 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 380 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:605 ms pas de gaspillage: 349 ms
Mélanger tous les éléments:592 ms pas de gaspillage: 373 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 374 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:598 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 377 ms
Mélanger tous les éléments:582 ms pas de gaspillage: 383 ms
Mélanger tous les éléments:578 ms pas de gaspillage: 362 ms
Mélanger tous les éléments:611 ms pas de gaspillage: 358 ms
Mélanger tous les éléments:581 ms pas de gaspillage: 375 ms
Mélanger tous les éléments:594 ms pas de gaspillage: 377 ms
Mélanger tous les éléments:587 ms pas de gaspillage: 362 ms
Mélanger tous les éléments:603 ms pas de gaspillage: 350 ms
Mélanger tous les éléments:587 ms pas de gaspillage: 373 ms
Mélanger tous les éléments:585 ms pas de gaspillage: 376 ms
Mélanger tous les éléments:586 ms pas de gaspillage: 353 ms
Mélanger tous les éléments:601 ms pas de gaspillage: 358 ms
Mélanger tous les éléments:593 ms pas de gaspillage: 378 ms
Mélanger tous les éléments:580 ms pas de gaspillage: 384 ms
Mélanger tous les éléments:577 ms pas de gaspillage: 351 ms
Mélanger tous les éléments:606 ms pas de gaspillage: 349 ms
Mélanger tous les éléments:589 ms pas de gaspillage: 380 ms
Mélanger tous les éléments:590 ms pas de gaspillage: 352 ms
Mélanger tous les éléments:605 ms pas de gaspillage: 348 ms
Mélanger tous les éléments:590 ms pas de gaspillage: 375 ms
Mélanger tous les éléments:581 ms pas de gaspillage: 359 ms
Mélanger tous les éléments:599 ms pas de gaspillage: 357 ms
Mélanger tous les éléments:581 ms pas de gaspillage: 381 ms
Mélanger tous les éléments:579 ms pas de gaspillage: 353 ms
Mélanger tous les éléments:607 ms pas de gaspillage: 349 ms
J'en ai fait une fonction pour qu'elle puisse être réutilisée.
Java
Java
import java.util.*;
public class TakeAtRandom {
/**
*Récupère de manière aléatoire le nombre spécifié d'éléments de la liste sans duplication.
*
* @param list Extraire les éléments de cette liste. Cette liste ne change pas.
* @param n Nombre d'éléments à récupérer.
* @param <T>Type d'élément.
* @return Une liste avec les éléments récupérés.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n) {
return takeAtRandom(list, n, new Random());
}
/**
*Récupère de manière aléatoire le nombre spécifié d'éléments de la liste sans duplication.
*
* @param list Extraire les éléments de cette liste. Cette liste ne change pas.
* @param n Nombre d'éléments à récupérer.
* @param générateur aléatoire aléatoire à utiliser.
* @param <T>Type d'élément.
* @return Une liste avec les éléments récupérés.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
if (list == null) {
throw new IllegalArgumentException("La valeur de la liste d'arguments est nulle.");
}
if (n > list.size()) {
throw new IllegalArgumentException(
String.format("Valeur de l'argument n%d est la taille de la liste d'arguments%Supérieur à d.",
n, list.size()));
}
if (random == null) {
throw new IllegalArgumentException("La valeur de l'argument random est nulle.");
}
final List<T> taken = new ArrayList<>(n); //Une liste avec des éléments sélectionnés au hasard
final List<T> remaining = new ArrayList<>(list); //Liste des éléments restants
for (int i = 0; i < n; i++) { //Répétez n fois.
final int remainingCount = remaining.size(); //Nombre d'éléments restants
final int index = random.nextInt(remainingCount); //Index sélectionné au hasard
final T element = remaining.get(index); //Éléments sélectionnés au hasard
taken.add(element); //Ajoutez des éléments sélectionnés au hasard à la fin de la liste des éléments sélectionnés au hasard.
final int lastIndex = remainingCount - 1; //Index à la fin de la liste des éléments restants
final T lastElement = remaining.remove(lastIndex); //Supprimez la fin de la liste des éléments restants.
if (index < lastIndex) { //Si l'élément sélectionné au hasard n'est pas la fin ...
remaining.set(index, lastElement); //Remplacez-le par le dernier élément.
}
}
return taken;
}
}
JavaScript
JavaScript
/**
*Récupérez au hasard le nombre spécifié d'éléments du tableau sans duplication.
*
* @param {Array}array Extrait des éléments de ce tableau. Ce tableau est inchangé.
* @param {number}n Nombre d'éléments à récupérer.
* @return {Array}Un tableau avec les éléments récupérés.
*/
function takeAtRandom(array, n) {
if (array == null) {
throw new Error("La valeur du tableau d'arguments est nulle ou non définie.");
}
if (n > array.length) {
throw new Error(`Valeur de l'argument n${n}Est la taille du tableau d'arguments${array.length}Est plus grand.`);
}
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
/**
*Renvoie un générateur qui récupère aléatoirement des éléments d'un tableau sans duplication.
*
* @param {Array}array Extrait des éléments de ce tableau. Ce tableau est inchangé.
*/
function* takeAtRandom(array) {
if (array == null) {
throw new Error("La valeur du tableau d'arguments est nulle ou non définie.");
}
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
/**
*Récupère de manière aléatoire le nombre spécifié d'éléments de la liste sans duplication.
*
* @receiver Extrait un élément de cette liste.
* @param n Nombre d'éléments à récupérer.
* @param générateur aléatoire aléatoire à utiliser.
* @param <T>Type d'élément.
* @return Une liste avec les éléments récupérés.
*/
fun <T> Collection<T>.takeAtRandom(n: Int, random: Random = Random): List<T> {
require(n <= size) { "Valeur de l'argument n$n est la taille du récepteur${size}Est plus grand." }
val taken = mutableListOf<T>() //Une liste avec des éléments sélectionnés au hasard
val remaining = toMutableList() //Liste des éléments restants
//Répétez n fois.
repeat(n) {
val remainingCount = remaining.size //Nombre d'éléments restants
val index = random.nextInt(remainingCount) //Index sélectionné au hasard
taken += remaining[index] //Éléments sélectionnés au hasard
val lastIndex = remainingCount - 1 //Index à la fin de la liste des éléments restants
val lastElement = remaining.removeAt(lastIndex) //Supprimez la fin de la liste des éléments restants.
if (index < lastIndex) { //Si l'élément sélectionné au hasard n'est pas la fin ...
remaining[index] = lastElement //Remplacez-le par le dernier élément.
}
}
return taken
}
Kotlin
import kotlin.random.Random
/**
*Renvoie une séquence qui récupère de manière aléatoire le nombre spécifié d'éléments de la liste sans duplication.
*
* @receiver Extrait un élément de cette liste.
* @param générateur aléatoire aléatoire à utiliser.
* @param <T>Type d'élément.
* @séquence de retour.
*/
fun <T> Collection<T>.toRandomSequence(random: Random = Random): Sequence<T> = sequence {
val remaining = toMutableList() //Liste des éléments restants
while (true) {
val remainingCount = remaining.size //Nombre d'éléments restants
.takeIf { it > 0 }
?: break
val index = random.nextInt(remainingCount) //Index sélectionné au hasard
remaining[index].also {
yield(it)
}
val lastIndex = remainingCount - 1 //Index à la fin de la liste des éléments restants
val lastElement = remaining.removeAt(lastIndex) //Supprimez la fin de la liste des éléments restants.
if (index < lastIndex) { //Si l'élément sélectionné au hasard n'est pas la fin ...
remaining[index] = lastElement //Remplacez-le par le dernier élément.
}
}
}
/c'est tout
Recommended Posts