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

この記事では、エディターが Java でのシャッフル アルゴリズムの使用方法を紹介します。必要な友人は参考にしてください。

フィッシャー – イェーツ シャッフル (クヌース シャッフル) の基本的な考え方:

配列 a をシャッフルするにはn 要素 (インデックス 0..n-1):
for i from n − 1 downto 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 の組み込みシャッフルが最も高速で、次に 3 番目の方法が続きます。最初の方法が最も時間がかかります。

レベル 10000000 の場合、おおよそ次のようになります:

first shuffle run time : 2115703288ns
second shuffle run time: 3114045871ns
third shuffle run time : 4664426798ns
fourth shuffle run time: 2962686695ns
java shuffle run time  : 3246883026ns first shuffle run time : 2165398466ns
second shuffle run time: 3129558913ns
third shuffle run time : 4147859664ns
fourth shuffle run time: 2911849942ns
java shuffle run time  : 4311703487ns first shuffle run time : 2227462247ns
second shuffle run time: 3279548770ns
third shuffle run time : 4704344954ns
fourth shuffle run time: 2942635980ns
java shuffle run time  : 3933172427ns first shuffle run time : 2200158789ns
second shuffle run time: 3172666791ns
third shuffle run time : 4715631517ns
fourth shuffle run time: 2950817535ns
java shuffle run time  : 3387417676ns first shuffle run time : 2201124449ns
second shuffle run time: 3203823874ns
third shuffle run time : 4179926278ns
fourth shuffle run time: 2913690411ns
java shuffle run time  : 3571313813ns first shuffle run time : 2163053190ns
second shuffle run time: 3073889926ns
third shuffle run time : 4493831518ns
fourth shuffle run time: 2852713887ns
java shuffle run time  : 3773602415ns

最初の方法が最も速く、4 番目の方法が最も遅いことがわかります。 Java の組み込みシャッフル速度も理想的ではありません。

ビッグデータを処理する場合、Java ライブラリの使用が非効率な場合は、他の方法の使用を検討できます。

以上がJava でのシャッフル アルゴリズムの使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。