Использование алгоритма перемешивания в Java

复制代码代码如下:

/**
* Перемещает каждый элемент списка на случайную новую позицию в списке.
*
* список @param
* Список для перетасовки
*
* @throws UnsupportedOperationException
* при замене элемента в Списке не поддерживается
*/
public static void shuffle(List<?> list) {
перетасовать (список, новый случайный());
}

/**
* Перемещает каждый элемент списка на случайную новую позицию в списке.
* с использованием указанного генератора случайных чисел.
*
* список @param
* Список для перетасовки
* @param случайный
* генератор случайных чисел
*
* @throws UnsupportedOperationException
* при замене элемента в Списке не поддерживается
*/
@SuppressWarnings («не отмечено»)
public static void shuffle(List<?> list, Random random) {
if (!(список экземпляров RandomAccess)) {
Массив Object[] = list.toArray();
for (int i = array.length - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
если (индекс < 0) {
индекс = -индекс;
}
Температура объекта = массив[i];
массив[i] = массив[индекс];
массив [индекс] = температура;
}

интервал я = 0;
ListIterator<Object> it = (ListIterator<Object>) список
.listIterator();
в то время как (it.hasNext()) {
это.следующий();
it.set(массив[i++]);
}
} еще {
Список<Объект> rawList = (Список<Объект>) список;
for (int i = rawList.size() - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
если (индекс <0) {
индекс = -индекс;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
}

复制代码代码如下:

общественный класс javaShuffle {
общественный статический int temp = 0;
публичный статический длительный старт;
общедоступный статический длинный конец;

public static void main(final String args[]) {

Изменение объектаTemp;
List<Integer> numList = новый ArrayList<Integer>();
List<Integer> firstList = новый ArrayList<Integer>();
List<Integer> SecondList = новый ArrayList<Integer>();
List<Integer> ThirdList = новый ArrayList<Integer>();
List<Integer> fourList = новый ArrayList<Integer>();

for (int я = 1; я <= 100000; я++) {
numList.add (я);
firstList.add(я);
SecondList.add(я);
третийList.add(я);
четвёртыйList.add(я);
}

// первая перетасовка, используйте ChangeTemp
ПолучитьНачалоВремя();
интервал randInt = 0;
for (int i = 0, length = firstList.size(); i < length; i++) {
randInt = getRandom(i, firstList.size());
ChangeTemp = firstList.get(i);
firstList.set(i, firstList.get(randInt));
firstList.set(randInt, javaShuffle.temp);
}
getEndTime("Время первого перемешивания");

// вторая перетасовка, список обмена
ПолучитьНачалоВремя();
for (int i = 0, length = SecondList.size(); i < length; i++) {
randInt = getRandom(i, SecondList.size());
SecondList.set(i, SecondList.set(randInt, SecondList.get(i)));
}
getEndTime("Второе время тасования");

// третье перемешивание, изменение генерирует случайное целое число
ПолучитьНачалоВремя();
Object[] tempArray = ThirdList.toArray();
Случайный рандом = новый Random();
интервал j = 0;
for (int i = tempArray.length - 1; i > 0; i--) {
j = rand.nextInt(я + 1);
ThirdList.set(i, ThirdList.set(j, ThirdList.get(i)));
}

getEndTime("Третье время выполнения тасования");

// четвертое перемешивание, имитируем перетасовку Java
ПолучитьНачалоВремя();
Случайный случайный = новый случайный();
if (!(четвертый экземпляр RandomAccess)) {
Массив Object[] = fourList.toArray();
for (int i = array.length - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
если (индекс < 0) {
индекс = -индекс;
}
Температура объекта = массив[i];
массив[i] = массив[индекс];
массив [индекс] = температура;
}

интервал я = 0;
ListIterator<Integer> it = (ListIterator<Integer>) fourList.listIterator();
в то время как (it.hasNext()) {
это.следующий();
it.set((Целое число) массив[i++]);
}
} еще {
Список <Целое число> rawList = (Список <Целое число>) четвёртый список;
for (int i = rawList.size() - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
если (индекс <0) {
индекс = -индекс;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
getEndTime("время четвертого тасования");

// перетасовка Java
ПолучитьНачалоВремя();
Коллекции.shuffle(numList);
getEndTime("Время выполнения перетасовки Java");
}

public static void swap(int a, int b) {
javaShuffle.temp = а;
а = б;
б = javaShuffle.temp;
}

public static int getRandom(final int low, Final int high) {
return (int) (Math.random() * (высокий – низкий) + низкий);
}

public static void getStartTime() {
javaShuffle.start = System.nanoTime();
}

public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}

}

如果数值较小,例如100000级别,则输出大概是:

время первого тасования: 85029499нс
время второго тасования: 80909474нс
время выполнения третьего тасования: 71543926нс
время выполнения четвертого тасования: 76520595нс
Время выполнения Java Shuffle: 61027643ns

время первого тасования: 82326239нс
время второго тасования: 78575611нс
время выполнения третьего тасования: 95009632нс
время выполнения четвертого тасования: 105946897нс
Время выполнения Java Shuffle: 90849302ns

время первого тасования: 84539840 нс
время второго тасования: 85965575нс
время выполнения третьего тасования: 101814998нс
время выполнения четвертого тасования: 113309672нс
Время выполнения Java Shuffle: 35089693 нс

время первого тасования: 87679863нс
время второго тасования: 79991814нс
время выполнения третьего тасования: 73720515нс
время выполнения четвертого тасования: 78353061нс
Время выполнения Java Shuffle: 64146465 нс

время первого тасования: 84314386нс
время второго тасования: 80074803нс
время выполнения третьего тасования: 74001283нс
время четвертого тасования: 79931321нс
Время выполнения Java Shuffle: 86427540 нс

время первого тасования: 84315523нс
время второго тасования: 81468386нс
время выполнения третьего тасования: 75052284нс
время выполнения четвертого тасования: 79461407нс
Время выполнения Java Shuffle: 66607729ns