Java中 shuffle 算法的使用_java

Fisher–Yates shuffle 基本思想(Knuth 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

多次运行结果可能都不一样,但是基本java自带 shuffle速度最快,第三种方式次之。而第一种方法耗时最久。

如果是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

可以看出,第一种方法速度最快,而第四种最慢。java自带 shuffle速度也不理想。

在进行大数据处理的时候,如果使用java库效率较低时,可以考虑使用其他方式。

 

时间: 2024-09-12 00:15:40

Java中 shuffle 算法的使用_java的相关文章

Java中递归原理实例分析_java

本文实例分析了Java中递归原理.分享给大家供大家参考.具体分析如下: 解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合.  递归的三个

java中lambda表达式语法说明_java

语法说明 一个lambda表达式由如下几个部分组成: 1. 在圆括号中以逗号分隔的形参列表.在CheckPerson.test方法中包含一个参数p,代表了一个Person类的实例.注意:lambda表达式中的参数的类型是可以省略的:此外,如果只有一个参数的话连括号也是可以省略的.比如上一节曾提到的代码: p -> p.getGender() == Person.Sex.MALE && p.getAge() >= 18 && p.getAge() <= 25

java中的正则操作方法总结_java

正则表达式在处理字符串的效率上是相当高的 关于正则表达式的使用,更多的是自己的经验,有兴趣可以参阅相关书籍 这里主要写一下java中的正则操作方法 实例1:匹配 复制代码 代码如下: import java.util.Scanner; class Demo {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        //获取输入        System.out

Java中的接口知识汇总_java

一.为什么要使用接口  假如有一个需求:要求实现防盗门的功能.门有"开"和"关"的功能,锁有"上锁"和"开锁"的功能. 分析:首先防盗门是一个门,门有开门和关门的功能,还有一把锁,锁有开锁和上锁,按照面向对象的编程的思想,我们会将门和锁都作为一个类而单独存在,但是,不能让防盗门继承自门的同时又继承自锁,防盗门不是锁,不符合继承中is a的关系,在java中支持单继承.那么我们如何来解决这一问题,这时就要用到接口.     二.

浅析Java中JSONObject和JSONArray使用_java

废话不多说,先给大家贴代码,具体代码如下所示: import net.sf.json.JSONArray; import net.sf.json.JSONObject; import java.util.*; public class JavaTest { public static void main(String[] args){ JSONObject obj=new JSONObject(); obj.put("derek","23"); obj.put(&q

谈谈Java中Volatile关键字的理解_java

volatile这个关键字可能很多朋友都听说过,或许也都用过.在Java 5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果.在Java 5之后,volatile关键字才得以重获生机.volatile关键字虽然从字面上理解起来比较简单,但是要用好不是一件容易的事情. 一.前言 JMM提供了volatile变量定义.final.synchronized块来保证可见性. 用volatile修饰的变量,线程在每次使用变量的时候,都会读取变量修改后的最的值.volatile很容

Java中的字符串用法小结_java

本文实例总结了Java中的字符串用法.分享给大家供大家参考.具体分析如下: 字符串的本质是char类型的数组,但在java中,所有用双引号""声明的字符串都是一个String类的对象.这也正体现了Java完全面向对象的语言特点. String 类 1.String类对象表示的是一个常量字符串.它是不可变长度的.也就是说,一旦创建了一个String类的实例,那么这个实例所表示的串是不可改变的.类似于 str = str + "Hello"; 这样的操作,实质上是将 s

Java中String.split()用法小结_java

在java.lang包中有String.split()方法,返回是一个数组 我在应用中用到一些,给大家总结一下,仅供大家参考: 1.如果用"."作为分隔的话,必须是如下写法,String.split("\\."),这样才能正确的分隔开,不能用String.split("."); 2.如果用"|"作为分隔的话,必须是如下写法,String.split("\\|"),这样才能正确的分隔开,不能用String.s

深入解析Java中的数据类型与变量_java

Java数据类型转换(自动转换和强制转换)数据类型的转换,分为自动转换和强制转换.自动转换是程序在执行过程中"悄然"进行的转换,不需要用户提前声明,一般是从位数低的类型向位数高的类型转换:强制类型转换则必须在代码中声明,转换顺序不受限制. 自动数据类型转换 自动转换按从低到高的顺序转换.不同类型数据间的优先关系如下:     低--------------------------------------------->高     byte,short,char-> int