Java でのシャッフル アルゴリズムの使用

/**
* リストのすべての要素をリスト内のランダムな新しい位置に移動します
* 指定された乱数発生器を使用します。
*
* @paramリスト
* シャッフルするリスト
* @paramランダム
* 乱数発生器
*
* @throws UnsupportedOperationException
* リスト内の要素の置換はサポートされていない場合
*/
@SuppressWarnings("未チェック")
public static void shuffle(List<?> list, Random ランダム) {
if (!(RandomAccess のインスタンスのリスト)) {
オブジェクト[] 配列 = list.toArray();
for (int i = array.length - 1; i > 0; i--) {
int インデックス = ランダム.nextInt(i + 1);
if (インデックス < 0) {
インデックス = -インデックス;
}
オブジェクトの一時値 = 配列[i];
配列[i] = 配列[インデックス];
配列[インデックス] = 一時;
}

int i = 0;
ListIterator<Object> it = (ListIterator<Object>) リスト
.listIterator();
while (it.hasNext()) {
it.next();
it.set(配列[i++]);
}
} それ以外 {
List<Object> rawList = (List<Object>) リスト;
for (int i = rawList.size() - 1; i > 0; i--) {
int インデックス = ランダム.nextInt(i + 1);
if (インデックス < 0) {
インデックス = -インデックス;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
}

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

オブジェクトの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> fourList = new ArrayList<Integer>();

for (int i = 1; i <= 100000; i++) {
numList.add(i);
firstList.add(i);
SecondList.add(i);
thirdList.add(i);
fourList.add(i);
}

// 最初にシャッフルし、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("最初のシャッフル実行時間");

// 2 番目のシャッフル、交換リスト
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("2 回目のシャッフル実行時間");

// 3 回目のシャッフル、ランダムな int の生成を変更します
getStartTime();
Object[] tempArray = thirdList.toArray();
ランダム ランド = 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("3 回目のシャッフル実行時間");

// 4 番目のシャッフル、Java シャッフルをシミュレートします
getStartTime();
ランダム ランダム = new Random();
if (!(RandomAccess の 4 番目のリストのインスタンス)) {
Object[] 配列 = fourList.toArray();
for (int i = array.length - 1; i > 0; i--) {
int インデックス = ランダム.nextInt(i + 1);
if (インデックス < 0) {
インデックス = -インデックス;
}
オブジェクトの一時値 = 配列[i];
配列[i] = 配列[インデックス];
配列[インデックス] = 一時;
}

int i = 0;
ListIterator<Integer> it = (ListIterator<Integer>) fourList.listIterator();
while (it.hasNext()) {
it.next();
it.set((整数) 配列[i++]);
}
} それ以外 {
List<Integer> rawList = (List<Integer>) fourList;
for (int i = rawList.size() - 1; i > 0; i--) {
int インデックス = ランダム.nextInt(i + 1);
if (インデックス < 0) {
インデックス = -インデックス;
}
rawList.set(index, rawList.set(i, rawList.get(index)));
}
}
getEndTime("4 回目のシャッフル実行時間");

// Java シャッフル
getStartTime();
Collections.shuffle(numList);
getEndTime("Java シャッフル ランタイム ");
}

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() * (高 - 低) + 低);
}

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 クラス）、出力サイズの目安は次のとおりです。

最初のシャッフル実行時間: 85029499ns
2 回目のシャッフル実行時間: 80909474ns
3 回目のシャッフル実行時間: 71543926ns
4 回目のシャッフル実行時間: 76520595ns
Javaシャッフル実行時間：61027643ns

最初のシャッフル実行時間: 82326239ns
2 回目のシャッフル実行時間: 78575611ns
3回目のシャッフル実行時間：95009632ns
4 回目のシャッフル実行時間: 105946897ns
Javaシャッフル実行時間：90849302ns

最初のシャッフル実行時間: 84539840ns
2 回目のシャッフル実行時間: 85965575ns
3 回目のシャッフル実行時間: 101814998ns
4 回目のシャッフル実行時間: 113309672ns
Javaシャッフル実行時間：35089693ns

最初のシャッフル実行時間: 87679863ns
2 回目のシャッフル実行時間: 79991814ns
3回目のシャッフル実行時間: 73720515ns
4 回目のシャッフル実行時間: 78353061ns
Javaシャッフル実行時間：64146465ns

最初のシャッフル実行時間: 84314386ns
2 回目のシャッフル実行時間: 80074803ns
3回目のシャッフル実行時間：74001283ns
4 回目のシャッフル実行時間: 79931321ns
Javaシャッフル実行時間：86427540ns

最初のシャッフル実行時間: 84315523ns
2 回目のシャッフル実行時間: 81468386ns
3 回目のシャッフル実行時間: 75052284ns
4 回目のシャッフル実行時間: 79461407ns
Javaシャッフル実行時間：66607729ns