Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.example.scrap;
- import java.util.Random;
- import java.util.function.Consumer;
- import java.util.stream.IntStream;
- public class Shuffle {
- private static final Random r = new Random();
- private static final int TRIALS = 100000;
- private static final int LEN = 3;
- private static void swap(int[] array, int i, int j) {
- int temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- public static void naive(int[] array) {
- for (int i = array.length - 1; i >= 0; i--) {
- swap(array, i, r.nextInt(array.length));
- }
- }
- public static void fisher_yates(int[] array) {
- for (int i = array.length - 1; i >= 1; i--) {
- swap(array, i, r.nextInt(i + 1));
- }
- }
- public static class Histo {
- final int len;
- final int[][] buckets;
- int total;
- public Histo(int len) {
- this.len = len;
- buckets = new int[len][];
- for (int i = 0; i < len; i++) {
- buckets[i] = new int[len];
- }
- }
- public void accept(int[] array) {
- assert array.length == len;
- for (int i = 0; i < len; i++) {
- buckets[i][array[i]]++;
- }
- total++;
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder(" ");
- for (int i = 0; i < len; i++) {
- sb.append(String.format("%6d", i));
- }
- sb.append('\n');
- for (int i = 0; i < len; i++) {
- sb.append(String.format("a[%d]", i));
- for (int j = 0; j < len; j++) {
- sb.append(String.format("%6.1f", 100. * buckets[i][j]/total));
- }
- sb.append('\n');
- }
- return sb.toString();
- }
- }
- public static void testDistriubtion(int length, Consumer<int[]> algo, String name) {
- int[] ref = IntStream.range(0, length).toArray(), array = new int[ref.length];
- Histo histo = new Histo(length);
- for (int i = 0; i < TRIALS; i++) {
- System.arraycopy(ref, 0, array, 0, ref.length);
- algo.accept(array);
- histo.accept(array);
- }
- System.out.println(name + ":\n" + histo);
- }
- public static void main(String[] args) {
- testDistriubtion(LEN, (a) -> fisher_yates(a), "fisher_yates");
- testDistriubtion(LEN, (a) -> naive(a), "naive");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement