Java에서 shuffle 알고리즘 사용
To shuffle an array a of n elements (indices 0..n-1): for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] and a[i]
JDK 소스 코드는 다음과 같습니다
/**
* Moves every element of the List to a random new position in the list.
*
* @param list
* the List to shuffle
*
* @throws UnsupportedOperationException
* when replacing an element in the List is not supported
*/
public static void shuffle(List<?> list) {
shuffle(list, new Random());
}
/**
* Moves every element of the List to a random new position in the list
* using the specified random number generator.
*
* @param list
* the List to shuffle
* @param random
* the random number generator
*
* @throws UnsupportedOperationException
* when replacing an element in the List is not supported
*/
@SuppressWarnings("unchecked")
public static void shuffle(List<?> list, Random random) {
if (!(list instanceof RandomAccess)) {
Object[] array = list.toArray();
for (int i = array.length - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
if (index < 0) {
index = -index;
}
Object temp = array[i];
array[i] = array[index];
array[index] = temp;
}
int i = 0;
ListIterator<Object> it = (ListIterator<Object>) list
.listIterator();
while (it.hasNext()) {
it.next();
it.set(array[i++]);
}
} else {
List<Object> rawList = (List<Object>) list;
for (int i = rawList.size() - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
if (index < 0) {
index = -index;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
}
public class javaShuffle {
public static int temp = 0;
public static long start;
public static long end;
public static void main(final String args[]) {
Object changeTemp;
List<Integer> numList = new ArrayList<Integer>();
List<Integer> firstList = new ArrayList<Integer>();
List<Integer> secondList = new ArrayList<Integer>();
List<Integer> thirdList = new ArrayList<Integer>();
List<Integer> fourthList = new ArrayList<Integer>();
for (int i = 1; i <= 100000; i++) {
numList.add(i);
firstList.add(i);
secondList.add(i);
thirdList.add(i);
fourthList.add(i);
}
// first shuffle,use changeTemp
getStartTime();
int 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("first shuffle run time ");
// second shuffle,exchange list
getStartTime();
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("second shuffle run time");
// third shuffle, change generate random int
getStartTime();
Object[] tempArray = thirdList.toArray();
Random rand = new Random();
int j = 0;
for (int i = tempArray.length - 1; i > 0; i--) {
j = rand.nextInt(i + 1);
thirdList.set(i, thirdList.set(j, thirdList.get(i)));
}
getEndTime("third shuffle run time ");
// fourth shuffle, simulate java shuffle
getStartTime();
Random random = new Random();
if (!(fourthList instanceof RandomAccess)) {
Object[] array = fourthList.toArray();
for (int i = array.length - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
if (index < 0) {
index = -index;
}
Object temp = array[i];
array[i] = array[index];
array[index] = temp;
}
int i = 0;
ListIterator<Integer> it = (ListIterator<Integer>) fourthList.listIterator();
while (it.hasNext()) {
it.next();
it.set((Integer) array[i++]);
}
} else {
List<Integer> rawList = (List<Integer>) fourthList;
for (int i = rawList.size() - 1; i > 0; i--) {
int index = random.nextInt(i + 1);
if (index < 0) {
index = -index;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
getEndTime("fourth shuffle run time");
// java shuffle
getStartTime();
Collections.shuffle(numList);
getEndTime("java shuffle run time ");
}
public static void swap(int a, int b) {
javaShuffle.temp = a;
a = b;
b = javaShuffle.temp;
}
public static int getRandom(final int low, final int high) {
return (int) (Math.random() * (high - low) + low);
}
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 ， ：
first shuffle run time : 85029499ns
second shuffle run time: 80909474ns
third shuffle run time : 71543926ns
fourth shuffle run time: 76520595ns
java shuffle run time : 61027643ns
first shuffle run time : 82326239ns
second shuffle run time: 78575611ns
third shuffle run time : 95009632ns
fourth shuffle run time: 105946897ns
java shuffle run time : 90849302ns
first shuffle run time : 84539840ns
second shuffle run time: 85965575ns
third shuffle run time : 101814998ns
fourth shuffle run time: 113309672ns
java shuffle run time : 35089693ns
first shuffle run time : 87679863ns
second shuffle run time: 79991814ns
third shuffle run time : 73720515ns
fourth shuffle run time: 78353061ns
java shuffle run time : 64146465ns
first shuffle run time : 84314386ns
second shuffle run time: 80074803ns
third shuffle run time : 74001283ns
fourth shuffle run time: 79931321ns
java shuffle run time : 86427540ns
first shuffle run time : 84315523ns
second shuffle run time: 81468386ns
third shuffle run time : 75052284ns
fourth shuffle run time: 79461407ns
java shuffle run time : 66607729ns
10000000 레벨이면 다음과 같습니다.
first shuffle run time : 2115703288nssecond shuffle run time: 3114045871nsthird shuffle run time : 4664426798nsfourth shuffle run time: 2962686695nsjava shuffle run time : 3246883026ns first shuffle run time : 2165398466nssecond shuffle run time: 3129558913nsthird shuffle run time : 4147859664nsfourth shuffle run time: 2911849942nsjava shuffle run time : 4311703487ns first shuffle run time : 2227462247nssecond shuffle run time: 3279548770nsthird shuffle run time : 4704344954nsfourth shuffle run time: 2942635980nsjava shuffle run time : 3933172427ns first shuffle run time : 2200158789nssecond shuffle run time: 3172666791nsthird shuffle run time : 4715631517nsfourth shuffle run time: 2950817535nsjava shuffle run time : 3387417676ns first shuffle run time : 2201124449nssecond shuffle run time: 3203823874nsthird shuffle run time : 4179926278nsfourth shuffle run time: 2913690411nsjava shuffle run time : 3571313813ns first shuffle run time : 2163053190nssecond shuffle run time: 3073889926nsthird shuffle run time : 4493831518nsfourth shuffle run time: 2852713887nsjava shuffle run time : 3773602415ns
첫 번째 방법은 속도가 가장 빠르고 네 번째 방법은 가장 느리다는 것을 알 수 있다.자바 자체 셔플 속도도 이상적이지 않아요.
빅데이터 처리를 할 때 자바 라이브러리를 사용하면 효율이 낮을 때 다른 방식을 고려할 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
