如何在10亿数中找出前1000大的数

1 分治

 

2 10亿的数据int 需要4G 但是只有2G的内存怎么办

 

3 多台机器同时算

 

4 只有一台机器 – 堆

/**
 * @author xiaoshi on 2018/10/14.
 */
public class TopN {

    // 父节点
    private int parent(int n) {
        return (n - 1) / 2;
    }

    // 左孩子
    private int left(int n) {
        return 2 * n + 1;
    }

    // 右孩子
    private int right(int n) {
        return 2 * n + 2;
    }

    // 构建堆
    private void buildHeap(int n, int[] data) {
        for(int i = 1; i < n; i++) {
            int t = i;
            // 调整堆
            while(t != 0 && data[parent(t)] > data[t]) {
                int temp = data[t];
                data[t] = data[parent(t)];
                data[parent(t)] = temp;
                t = parent(t);
            }
        }
    }

    // 调整data[i]
    private void adjust(int i, int n, int[] data) {
        if(data[i] <= data[0]) {
            return;
        }
        // 置换堆顶
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        // 调整堆顶
        int t = 0;
        while( (left(t) < n && data[t] > data[left(t)])
            || (right(t) < n && data[t] > data[right(t)]) ) {
            if(right(t) < n && data[right(t)] < data[left(t)]) {
                // 右孩子更小，置换右孩子
                temp = data[t];
                data[t] = data[right(t)];
                data[right(t)] = temp;
                t = right(t);
            } else {
                // 否则置换左孩子
                temp = data[t];
                data[t] = data[left(t)];
                data[left(t)] = temp;
                t = left(t);
            }
        }
    }

    // 寻找topN，该方法改变data，将topN排到最前面
    public void findTopN(int n, int[] data) {
        // 先构建n个数的小顶堆
        buildHeap(n, data);
        // n往后的数进行调整
        for(int i = n; i < data.length; i++) {
            adjust(i, n, data);
        }
    }

    // 打印数组
    public void print(int[] data) {
        for(int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

}


主函数
import java.util.Random;

/**
 * @author xiaoshi on 2018/10/14.
 */
public class Main {

    public static void main(String[] args) {

        TopN topN = new TopN();

        // 第一组测试
        int[] arr1 = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};

        System.out.println("原数组：");
        topN.print(arr1);
        topN.findTopN(5, arr1);
        System.out.println("调整后数组：");
        topN.print(arr1);

        // 第二组测试
        int[] arr2 = new int[1000];
        for(int i=0; i<arr2.length; i++) {
            arr2[i] = i + 1;
        }

        System.out.println("原数组：");
        topN.print(arr2);
        topN.findTopN(50, arr2);
        System.out.println("调整后数组：");
        topN.print(arr2);

        // 第三组测试
        Random random =new Random();
        int[] arr3 = new int[1000];
        for(int i=0; i<arr3.length; i++) {
            arr3[i] = random.nextInt();
        }

        System.out.println("原数组：");
        topN.print(arr3);
        topN.findTopN(50, arr3);
        System.out.println("调整后数组：");
        topN.print(arr3);
    }

}

 

运行结果：

原数组：
56 30 71 18 29 93 44 75 20 65 68 34 
调整后数组：
65 68 71 75 93 18 29 30 20 44 56 34 
原数组：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100  
调整后数组：
951 952 955 954 953 956 957 963 968 964 972 961 979 959 958 967 966 969 974 965 970 973 988 962 983 993 986 981 987 992 960 976 1000 982 978 977 975 985 984 990 971 997 996 991 989 999 998 980 994 995 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
原数组：
835636999 -90522479 -769818338 -1416245398 1041573706 1812203535 896607110 1789246766 1774883884 26722194 -418633859 1344767118 1570967674 1316806558 -1435502178 1473470755 -918439629 1869702742 2101404773 -1296472335 649689400 1153902366 -1052670714 498645159 -1530905537 -1159220094 -154125959 -868393434 -504505075 -1106082731 -494609447 -1406763201 -750828828 -342445539 -744595730 -1920006464 -1230413255 -1426324562 -1277878264 474935729 -2029054806 447026196 -1121975794 -1448358181 1957166126 1336854710 …… 
调整后数组：
1960093727 1964906931 1970688292 1975808864 1981745799 1991241336 2022661667 1981095418 1998580270 19881693

 

如何判断一个数是否在40亿个整数中？

 

够多的机器

从磁盘加载数据是磁盘io操作，是非常慢的，你每次都要加载这么大的数据，还要8次，我估计你找一个数的时间可以达到分钟甚至小时级了。

毫秒级的方法

解决办法

32位int的范围，总共就是2的32次方，大概42亿多点。所以你可以申请2的32次方个位。

1代表第一个位，2代表第二个位，2的32次方代表最后一个位。40亿个数中，存在的数就在相应的位置1，其他位就是0。

2的32次方个位，相当于2的29次方个字节，哇，才500MB，真 是节省了不少内存呢。

内存是按照bit位来计算的，硬盘存储才按照byte字节来算的。

1字节 = 8位；1KB = 1024字节；

这是一种非常有名的大数据算法，叫位图法，英文名叫bitmap。顾名思义，就是用位来表示状态，从而节省空间。

位图法

位图法就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

 

一、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

申请512M的内存

一个bit位代表一个unsigned int值

读入40亿个数，设置相应的bit位

读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在

二、使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。

位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到 5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。