java 乱序(小汇)-阿里云开发者社区

开发者社区> 数据库> 正文
登录阅读全文

java 乱序(小汇)

简介:

/**
 *
 *问题或许可以是这样:产生m个随机正整数,要求范围是从1到n,平且它们互不相同。 
问题或许可以这样解决:

假设我们已经有了经过排序的(升序),且满足要求的k个正整数,我们继续: 
1、在从1到n-k的区间范围内,产生一个随机的正整数i1; 
2、统计在已有序列中比i1小的数,将其个数加到i1上,得到i2;再统计从i1到i2数的个数,得到i3;一直循环,直到i不变为止。然后,把i插入已有的序列。这个过程相当于从头数出i1个空白,以此来保证新的数是随机的。 
3、这时得到了k+1个满足要求的数,然后就循环吧。 
上面的方法适用于n很大,但是m很小的时候。

如果m和n都很大,并且希望一次性的产生,那么: 
1先产生有一定冗余的随机正整数,然后排序,然后去掉相同的数。 
如果,产生了超额的数,可以将数列再打乱顺序,然后,取出符合规定的数目的数。

当然,也可以两种方法相结合,就是: 
1、先产生超过需求的、有一定冗余的随机正整数,然后排序,然后去掉相同的数,并且保存下来。记录它的数目m1 >m; 
2、当要用时,在产生一个从1到m的随机数j,然后取出数据库中第j个数,输出,并且把它从数据库中删除到。
 *
 *
 *
 *
 *
 *
 *
 *
 *数据有点大,用了128m 
start_1   ();   是即时输出(因为用boolean数组,所以内存小得多) 
start_2   ();   是把数据存进数组,以便再处理(需要内存很大,不赞成使用) 
如果要处理数据,可以用   start_1   ();   把数据保存进文件,再从文件中读取数据进行处理。

 */
public class Main{
 
 public final int n = 10000000;
 
 public Main () {
        start_1();
        //start_2 ();
    }
    
    public static void main (String[] args) {
        new Main();
    }
    
    public void start_1() {
        //布朗型默认为 false
        boolean[] barr = new boolean[n];
        //
        java.util.Random r = new java.util.Random ();
        int j = 0, x;
        int m = n;
        while(j < m) {
            x = r.nextInt (n);
            if (! barr[x]) {
                j++;
                barr[x] = true;
                System.out.println (x);
            }
        }
    }
    
    public void start_2() {
        //整型默认为 0
        int[] iarr = new int[n];
        //
        java.util.Random r = new java.util.Random ();
        int j = 0, x;
        int m = n;
        //少循环一次,因为要生成 0
        while(j < m-1) {
            x = r.nextInt (n);
            if (iarr[x] == 0) {
                j++;
                iarr[x] = j;
            }
        }
    }
}
/*
 *上面的算法,没有优化,生成数据耗时间。 
下面的算法改进了一下。生成所有数据半分钟左右。 
+---------- 
|   0...999999 
|   . 
|   . 
|   . 
|   99

Java code 
public class Main {
    
    public Main () {
        start_1 ();
        start_2 ();
    }
    
    public static void main (String[] args) {
        new Main ();
    }
    
    ** void start_1 () {
        for (int i = 0; i < n; i++) {
            byte j = 0;
            while(j < m-1) {
                int x = r.nextInt (m);
                if (barr_1[x] == 0) {
                    j++;
                    barr_1[x] = j;
                }
            }
        }
    }
    
    ** void start_2 () {
        int j = 0;
        while(j < n) {
            int x = r.nextInt (n);
            int y = (int) barr_2[x];
            if (y < m) {
                j++;
                barr_2[x]++;
                int z = ((int) barr_1[x][y]) * n;
                //System.out.println (x + z);
            }
        }
    }
    
    ** final int s = 10000*10000;
    ** final int m = 100;
    ** final int n = s/m;
    ** byte[][] barr_1 = new byte[n][m];
    ** byte[] barr_2 = new byte[n];
    ** java.util.Random r = new java.util.Random ();
    
}
*/

/*
 *和一位仁兄在另一个帖子争论中,受到启发。 
终于悟出一种时间复杂度极低的算法。 
(可以证明,任意一个数   在   任意位置的概率   都为   1/n)

因为内存不够,所以改成了7个9来算。总时间2秒

Java code 
public class Main {
    
    public Main () {
        start ();
    }
    
    public static void main (String args[]) {
        new Main ();
    }
    
    ** void start () {
        java.util.Random r = new java.util.Random ();
        for (int i = 0; i < n; i++) {
            int x = r.nextInt (i+1);
            iarr = iarr[x];
            iarr[x] = i;
        }
        //
        int m = 10;
        for (int i = 0; i < m; i++) {
            System.out.print (iarr + " ");
        }
    }
    
    ** final int n = 1000*10000;
    ** int[] iarr = new int[n];
    
}
*/

本文转自博客园执着的笨蛋的博客,原文链接:java 乱序(小汇),如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章
最新文章
相关文章