이 기사에서는 편집자가 Java에서 셔플 알고리즘을 사용하는 방법을 소개합니다. 도움이 필요한 친구는
Fisher–Yates shuffle(Knuth shuffle)의 기본 아이디어:
를 참조하세요.n개 요소(인덱스 0..n-1)로 구성된 배열 a를 섞으려면:
for i를 n − 1에서 1로 아래로 do
j ← 0 ≤ j ≤ i를 갖는 임의의 정수
교환 a [j] 및 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
여러 실행의 결과는 다를 수 있지만 기본 Java의 내장 셔플이 가장 빠르며 그 다음은 세 번째 방법입니다. 첫 번째 방법이 가장 오래 걸립니다.
레벨이 10000000이라면 대략 다음과 같습니다.
rree첫 번째 방법이 가장 빠른 반면, 네 번째 방법이 가장 느린 것을 알 수 있습니다. Java에 내장된 셔플 속도도 이상적이지 않습니다.
빅데이터 처리 시 자바 라이브러리를 사용하는 것이 비효율적이라면 다른 방법을 고려해 볼 수 있습니다.
위 내용은 Java에서 셔플 알고리즘 사용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!