(Wie in [Kommentar] ausgeführt (https://qiita.com/sdkei/items/43d2902908efcfca7f25#comment-b5adc7209cd15444da9e), gibt es Raum für Effizienzverbesserungen.)
Kommentar von Hokuhoku no Imo Dies ist die Methode, an die ich gedacht habe.
In diesem Abschnitt wird beschrieben, wie Sie mehrere Elemente ohne Duplizierung nach dem Zufallsprinzip effizient aus einer Liste extrahieren können. Die "Liste" hier ist eine zufällig zugängliche Liste variabler Länge [^ zufällig zugängliche Liste variabler Länge].
[^ Zufällig zugängliche Liste variabler Länge]: java.util.ArrayList für Java, Array für JavaScript, std: vector für C ++
Die Erklärung wird in Java gegeben, aber der endgültige Code, der für die Wiederverwendung funktionalisiert wurde, wird in Java, JavaScript und Kotlin bereitgestellt.
Angenommen, im Java-Codebeispiel wird am Anfang der Datei die folgende "import" -Anweisung deklariert:
Java
import java.util.*;
Es ist einfach, nur ein Element zufällig aus der Liste auszuwählen.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste mit 4 Elementen von D.
int index = new Random().nextInt(list.size()); //Zufällig ausgewählte Ganzzahl größer oder gleich 0 und kleiner als 4
Character result = list.get(index); //Zufällig ausgewählte Elemente
System.out.println(result); //Ausgabebeispiel> B
Das Abrufen aller Elemente in zufälliger Reihenfolge ist auch dann einfach, wenn die Standardbibliothek über eine solche Funktion verfügt.
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste mit 4 Elementen von D.
List<Character> shuffled = new ArrayList<>(list); //Eine Kopie der Liste, die dann zufällig sortiert wird
Collections.shuffle(shuffled); //Sortieren Sie die Elemente nach dem Zufallsprinzip.
System.out.println(shuffled); //Ausgabebeispiel> [C, A, D, B]
Wie wäre es also damit, mehrere Elemente, nicht alle Elemente, in zufälliger Reihenfolge abzurufen?
Java (Hinweis: Ineffizient)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste mit 4 Elementen von D.
List<Character> shuffled = new ArrayList<>(list); //Eine Kopie der Liste, die dann zufällig sortiert wird
Collections.shuffle(shuffled); //Sortieren Sie die Elemente nach dem Zufallsprinzip.
List result = shuffled.subList(0, 2); //Neue Liste mit zwei Elementen von vorne gemischt
System.out.println(result); //Ausgabebeispiel> [C, B]
Nein, das ist einfach zu schreiben, Es gibt viel Abfall, weil alle Elemente gemischt werden. Wenn Sie 10.000 Elemente mischen, wenn Sie 100 Elemente aus einer Liste von 10.000 Elementen abrufen, werden 9900 Elemente verschwendet.
Was machst du dann?
Wählen Sie zufällig nur ein Element aus, entfernen Sie das ausgewählte Element aus der Liste usw.
Java (Hinweis: Ineffizient)
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste mit 4 Elementen von D.
List<Character> result = new ArrayList<>(); //Eine Liste mit zufällig ausgewählten Elementen
List<Character> remaining = new ArrayList<>(list); //Liste der verbleibenden Elemente
Random random = new Random(); //Zufallsgenerator
for (int i = 0; i < 2; i++) { //Wiederholen Sie zweimal.
int remainingCount = remaining.size(); //Anzahl der verbleibenden Elemente
int index = random.nextInt(remainingCount); //Zufällig ausgewählter Index
Character element = remaining.remove(index); //Extrahiert zufällig ausgewählte Elemente.
result.add(element); //Zufällig ausgewählte Elemente hinzufügen Fügen Sie am Ende der Liste zufällig ausgewählte Elemente hinzu.
}
System.out.println(result); //Ausgabebeispiel> [B, D]
Es gibt kein nutzloses Mischen. Dies ist jedoch auch ineffizient.
Zufällig zugängliche Listen verwenden intern Arrays, um Elemente zu speichern Wenn Sie ein Element in der Mitte löschen, wird der Vorgang des Füllens der Elemente danach ausgeführt.
|A|B|C|D| | | | |
↓ Löschen B.
|A|C|D| | | | | |
Je früher das zu löschende Element ist, desto länger dauert die Verarbeitung.
Was soll ich dann tun?
Es ist langsam, weil es die Elemente in der Mitte löscht. Löschen Sie nur das Ende. Ersetzen wir die Elemente in der Mitte, ohne sie zu löschen.
Beim Löschen B.
|A|B|C|D| | | | |
↓ Löschen Sie das D am Ende und
|A|B|C| | | | | |
↓ Ersetzen Sie B durch D.
|A|D|C| | | | | |
Der Code sieht folgendermaßen aus:
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C,Liste mit 4 Elementen von D.
List<Character> result = new ArrayList<>(); //Eine Liste mit zufällig ausgewählten Elementen
List<Character> remaining = new ArrayList<>(list); //Liste der verbleibenden Elemente
Random random = new Random(); //Zufallsgenerator
for (int i = 0; i < 2; i++) { //Wiederholen Sie zweimal.
int remainingCount = remaining.size(); //Anzahl der verbleibenden Elemente
int index = random.nextInt(remainingCount); //Zufällig ausgewählter Index
Character element = remaining.get(index); //Zufällig ausgewählte Elemente
result.add(element); //Zufällig ausgewählte Elemente hinzufügen Fügen Sie am Ende der Liste zufällig ausgewählte Elemente hinzu.
int lastIndex = remainingCount - 1; //Index am Ende der Liste der verbleibenden Elemente
Character lastElement = remaining.remove(lastIndex); //Entfernen Sie das Ende aus der Liste der verbleibenden Elemente.
if (index < lastIndex) { //Wenn das zufällig ausgewählte Element nicht das Ende ist ...
remaining.set(index, lastElement); //Ersetzen Sie es durch das letzte Element.
}
}
System.out.println(result); //Ausgabebeispiel> [D, A]
Lassen Sie uns den Unterschied in der Verarbeitungsgeschwindigkeit leicht messen. Vergleichen Sie diejenige, die alle Elemente mischt, um die erste Teilliste zu erhalten, mit der letzten, die am wenigsten verschwenderisch ist.
Wenn Sie die Anzahl der Elemente in der Liste auf 100.000 festlegen und zufällig 50.000 daraus erwerben, Ungefähr 590 ms für alle Elementmischungen Wenn es keinen Abfall gibt, sind es ungefähr 370 ms.
Java
public class TakeAtRandom {
public static void main(String... args) {
//Listengröße
final int LIST_SIZE = 10_000_000;
//Anzahl der Elemente, die aus der Liste abgerufen werden sollen
final int N = 5_000_000;
//Anzahl der Wiederholungen
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("Mische alle Elemente: %,d ms", finishedAt - startAt));
}
{
final long startAt = System.currentTimeMillis();
takeAtRandom(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format("Keine Verschwendung: %,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); //Eine Liste mit zufällig ausgewählten Elementen
final List<T> remaining = new ArrayList<>(list); //Liste der verbleibenden Elemente
for (int i = 0; i < n; i++) { //N-mal wiederholen.
final int remainingCount = remaining.size(); //Anzahl der verbleibenden Elemente
final int index = random.nextInt(remainingCount); //Zufällig ausgewählter Index
final T element = remaining.get(index); //Zufällig ausgewählte Elemente
taken.add(element); //Fügen Sie zufällig ausgewählte Elemente am Ende der Liste der zufällig ausgewählten Elemente hinzu.
final int lastIndex = remainingCount - 1; //Index am Ende der Liste der verbleibenden Elemente
final T lastElement = remaining.remove(lastIndex); //Entfernen Sie das Ende aus der Liste der verbleibenden Elemente.
if (index < lastIndex) { //Wenn das zufällig ausgewählte Element nicht das Ende ist ...
remaining.set(index, lastElement); //Ersetzen Sie es durch das letzte Element.
}
}
return taken;
}
}
Ausgabebeispiel
Mische alle Elemente:608 ms kein Abfall: 705 ms
Mische alle Elemente:659 ms kein Abfall: 1,985 ms
Mische alle Elemente:585 ms kein Abfall: 372 ms
Mische alle Elemente:598 ms kein Abfall: 378 ms
Mische alle Elemente:598 ms kein Abfall: 397 ms
Mische alle Elemente:586 ms kein Abfall: 451 ms
Mische alle Elemente:583 ms kein Abfall: 381 ms
Mische alle Elemente:584 ms kein Abfall: 391 ms
Mische alle Elemente:580 ms kein Abfall: 383 ms
Mische alle Elemente:578 ms kein Abfall: 383 ms
Mische alle Elemente:584 ms kein Abfall: 377 ms
Mische alle Elemente:585 ms kein Abfall: 378 ms
Mische alle Elemente:598 ms kein Abfall: 381 ms
Mische alle Elemente:591 ms kein Abfall: 359 ms
Mische alle Elemente:605 ms kein Abfall: 354 ms
Mische alle Elemente:590 ms kein Abfall: 373 ms
Mische alle Elemente:584 ms kein Abfall: 379 ms
Mische alle Elemente:586 ms kein Abfall: 359 ms
Mische alle Elemente:603 ms kein Abfall: 357 ms
Mische alle Elemente:589 ms kein Abfall: 376 ms
Mische alle Elemente:579 ms kein Abfall: 385 ms
Mische alle Elemente:581 ms kein Abfall: 352 ms
Mische alle Elemente:610 ms kein Abfall: 350 ms
Mische alle Elemente:587 ms kein Abfall: 372 ms
Mische alle Elemente:603 ms kein Abfall: 381 ms
Mische alle Elemente:595 ms kein Abfall: 353 ms
Mische alle Elemente:606 ms kein Abfall: 348 ms
Mische alle Elemente:579 ms kein Abfall: 376 ms
Mische alle Elemente:576 ms kein Abfall: 390 ms
Mische alle Elemente:582 ms kein Abfall: 359 ms
Mische alle Elemente:602 ms kein Abfall: 357 ms
Mische alle Elemente:583 ms kein Abfall: 375 ms
Mische alle Elemente:585 ms kein Abfall: 379 ms
Mische alle Elemente:586 ms kein Abfall: 353 ms
Mische alle Elemente:603 ms kein Abfall: 350 ms
Mische alle Elemente:590 ms kein Abfall: 370 ms
Mische alle Elemente:587 ms kein Abfall: 376 ms
Mische alle Elemente:586 ms kein Abfall: 351 ms
Mische alle Elemente:600 ms kein Abfall: 359 ms
Mische alle Elemente:585 ms kein Abfall: 379 ms
Mische alle Elemente:579 ms kein Abfall: 382 ms
Mische alle Elemente:580 ms kein Abfall: 352 ms
Mische alle Elemente:605 ms kein Abfall: 349 ms
Mische alle Elemente:588 ms kein Abfall: 372 ms
Mische alle Elemente:586 ms kein Abfall: 375 ms
Mische alle Elemente:584 ms kein Abfall: 351 ms
Mische alle Elemente:598 ms kein Abfall: 358 ms
Mische alle Elemente:579 ms kein Abfall: 376 ms
Mische alle Elemente:579 ms kein Abfall: 381 ms
Mische alle Elemente:578 ms kein Abfall: 357 ms
Mische alle Elemente:601 ms kein Abfall: 348 ms
Mische alle Elemente:593 ms kein Abfall: 371 ms
Mische alle Elemente:585 ms kein Abfall: 376 ms
Mische alle Elemente:584 ms kein Abfall: 352 ms
Mische alle Elemente:602 ms kein Abfall: 349 ms
Mische alle Elemente:586 ms kein Abfall: 372 ms
Mische alle Elemente:586 ms kein Abfall: 376 ms
Mische alle Elemente:578 ms kein Abfall: 359 ms
Mische alle Elemente:598 ms kein Abfall: 357 ms
Mische alle Elemente:583 ms kein Abfall: 379 ms
Mische alle Elemente:578 ms kein Abfall: 382 ms
Mische alle Elemente:592 ms kein Abfall: 356 ms
Mische alle Elemente:605 ms kein Abfall: 350 ms
Mische alle Elemente:587 ms kein Abfall: 374 ms
Mische alle Elemente:586 ms kein Abfall: 377 ms
Mische alle Elemente:586 ms kein Abfall: 353 ms
Mische alle Elemente:600 ms kein Abfall: 357 ms
Mische alle Elemente:581 ms kein Abfall: 380 ms
Mische alle Elemente:580 ms kein Abfall: 380 ms
Mische alle Elemente:580 ms kein Abfall: 352 ms
Mische alle Elemente:605 ms kein Abfall: 349 ms
Mische alle Elemente:592 ms kein Abfall: 373 ms
Mische alle Elemente:585 ms kein Abfall: 374 ms
Mische alle Elemente:585 ms kein Abfall: 352 ms
Mische alle Elemente:598 ms kein Abfall: 357 ms
Mische alle Elemente:580 ms kein Abfall: 377 ms
Mische alle Elemente:582 ms kein Abfall: 383 ms
Mische alle Elemente:578 ms kein Abfall: 362 ms
Mische alle Elemente:611 ms kein Abfall: 358 ms
Mische alle Elemente:581 ms kein Abfall: 375 ms
Mische alle Elemente:594 ms kein Abfall: 377 ms
Mische alle Elemente:587 ms kein Abfall: 362 ms
Mische alle Elemente:603 ms kein Abfall: 350 ms
Mische alle Elemente:587 ms kein Abfall: 373 ms
Mische alle Elemente:585 ms kein Abfall: 376 ms
Mische alle Elemente:586 ms kein Abfall: 353 ms
Mische alle Elemente:601 ms kein Abfall: 358 ms
Mische alle Elemente:593 ms kein Abfall: 378 ms
Mische alle Elemente:580 ms kein Abfall: 384 ms
Mische alle Elemente:577 ms kein Abfall: 351 ms
Mische alle Elemente:606 ms kein Abfall: 349 ms
Mische alle Elemente:589 ms kein Abfall: 380 ms
Mische alle Elemente:590 ms kein Abfall: 352 ms
Mische alle Elemente:605 ms kein Abfall: 348 ms
Mische alle Elemente:590 ms kein Abfall: 375 ms
Mische alle Elemente:581 ms kein Abfall: 359 ms
Mische alle Elemente:599 ms kein Abfall: 357 ms
Mische alle Elemente:581 ms kein Abfall: 381 ms
Mische alle Elemente:579 ms kein Abfall: 353 ms
Mische alle Elemente:607 ms kein Abfall: 349 ms
Ich habe es zu einer Funktion gemacht, damit es wiederverwendet werden kann.
Java
Java
import java.util.*;
public class TakeAtRandom {
/**
*Ruft die angegebene Anzahl von Elementen zufällig aus der Liste ab, ohne sie zu duplizieren.
*
* @Parameterliste Extrahieren Sie Elemente aus dieser Liste. Diese Liste ändert sich nicht.
* @param n Anzahl der abzurufenden Elemente.
* @param <T>Elementtyp.
* @return Eine Liste mit den abgerufenen Elementen.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n) {
return takeAtRandom(list, n, new Random());
}
/**
*Ruft die angegebene Anzahl von Elementen zufällig aus der Liste ab, ohne sie zu duplizieren.
*
* @Parameterliste Extrahieren Sie Elemente aus dieser Liste. Diese Liste ändert sich nicht.
* @param n Anzahl der abzurufenden Elemente.
* @param random Zufallsgenerator zu verwenden.
* @param <T>Elementtyp.
* @return Eine Liste mit den abgerufenen Elementen.
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
if (list == null) {
throw new IllegalArgumentException("Der Wert der Argumentliste ist null.");
}
if (n > list.size()) {
throw new IllegalArgumentException(
String.format("Wert des Arguments n%d ist die Größe der Argumentliste%Größer als d.",
n, list.size()));
}
if (random == null) {
throw new IllegalArgumentException("Der Wert des Arguments random ist null.");
}
final List<T> taken = new ArrayList<>(n); //Eine Liste mit zufällig ausgewählten Elementen
final List<T> remaining = new ArrayList<>(list); //Liste der verbleibenden Elemente
for (int i = 0; i < n; i++) { //N-mal wiederholen.
final int remainingCount = remaining.size(); //Anzahl der verbleibenden Elemente
final int index = random.nextInt(remainingCount); //Zufällig ausgewählter Index
final T element = remaining.get(index); //Zufällig ausgewählte Elemente
taken.add(element); //Fügen Sie zufällig ausgewählte Elemente am Ende der Liste der zufällig ausgewählten Elemente hinzu.
final int lastIndex = remainingCount - 1; //Index am Ende der Liste der verbleibenden Elemente
final T lastElement = remaining.remove(lastIndex); //Entfernen Sie das Ende aus der Liste der verbleibenden Elemente.
if (index < lastIndex) { //Wenn das zufällig ausgewählte Element nicht das Ende ist ...
remaining.set(index, lastElement); //Ersetzen Sie es durch das letzte Element.
}
}
return taken;
}
}
JavaScript
JavaScript
/**
*Ruft die angegebene Anzahl von Elementen nach dem Zufallsprinzip ohne Duplizierung aus dem Array ab.
*
* @param {Array}Array Extrahiert Elemente aus diesem Array. Dieses Array bleibt unverändert.
* @param {number}n Anzahl der abzurufenden Elemente.
* @return {Array}Ein Array mit den abgerufenen Elementen.
*/
function takeAtRandom(array, n) {
if (array == null) {
throw new Error("Der Wert des Argumentarrays ist null oder undefiniert.");
}
if (n > array.length) {
throw new Error(`Wert des Arguments n${n}Ist die Größe des Argumentarrays${array.length}Ist größer.`);
}
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
/**
*Gibt einen Generator zurück, der Elemente ohne Duplizierung zufällig aus einem Array abruft.
*
* @param {Array}Array Extrahiert Elemente aus diesem Array. Dieses Array bleibt unverändert.
*/
function* takeAtRandom(array) {
if (array == null) {
throw new Error("Der Wert des Argumentarrays ist null oder undefiniert.");
}
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
/**
*Ruft die angegebene Anzahl von Elementen zufällig aus der Liste ab, ohne sie zu duplizieren.
*
* @Empfänger Extrahiert ein Element aus dieser Liste.
* @param n Anzahl der abzurufenden Elemente.
* @param random Zufallsgenerator zu verwenden.
* @param <T>Elementtyp.
* @return Eine Liste mit den abgerufenen Elementen.
*/
fun <T> Collection<T>.takeAtRandom(n: Int, random: Random = Random): List<T> {
require(n <= size) { "Wert des Arguments n$n ist die Größe des Empfängers${size}Ist größer." }
val taken = mutableListOf<T>() //Eine Liste mit zufällig ausgewählten Elementen
val remaining = toMutableList() //Liste der verbleibenden Elemente
//N-mal wiederholen.
repeat(n) {
val remainingCount = remaining.size //Anzahl der verbleibenden Elemente
val index = random.nextInt(remainingCount) //Zufällig ausgewählter Index
taken += remaining[index] //Zufällig ausgewählte Elemente
val lastIndex = remainingCount - 1 //Index am Ende der Liste der verbleibenden Elemente
val lastElement = remaining.removeAt(lastIndex) //Entfernen Sie das Ende aus der Liste der verbleibenden Elemente.
if (index < lastIndex) { //Wenn das zufällig ausgewählte Element nicht das Ende ist ...
remaining[index] = lastElement //Ersetzen Sie es durch das letzte Element.
}
}
return taken
}
Kotlin
import kotlin.random.Random
/**
*Gibt eine Sequenz zurück, die die angegebene Anzahl von Elementen ohne Duplizierung zufällig aus der Liste abruft.
*
* @Empfänger Extrahiert ein Element aus dieser Liste.
* @param random Zufallsgenerator zu verwenden.
* @param <T>Elementtyp.
* @Rückgabesequenz.
*/
fun <T> Collection<T>.toRandomSequence(random: Random = Random): Sequence<T> = sequence {
val remaining = toMutableList() //Liste der verbleibenden Elemente
while (true) {
val remainingCount = remaining.size //Anzahl der verbleibenden Elemente
.takeIf { it > 0 }
?: break
val index = random.nextInt(remainingCount) //Zufällig ausgewählter Index
remaining[index].also {
yield(it)
}
val lastIndex = remainingCount - 1 //Index am Ende der Liste der verbleibenden Elemente
val lastElement = remaining.removeAt(lastIndex) //Entfernen Sie das Ende aus der Liste der verbleibenden Elemente.
if (index < lastIndex) { //Wenn das zufällig ausgewählte Element nicht das Ende ist ...
remaining[index] = lastElement //Ersetzen Sie es durch das letzte Element.
}
}
}
/das ist alles
Recommended Posts