桶排序算法及实际运用

2019-12-12

前言

首先说一下需求，由于公司项目中有一份日志是从solr中查询出来，其中有一个ip字段，需要在页面展示为ip对应的国家和省份。数据库中存在一份地域库数据（即各个ip网段对应的国家省份城市等信息），地域库数据一共42万条，也就是solr中查询出来的数据每一条数据中的ip要在42万个IP网段中找到他所在的位置。虽然数据并不多，但是如果每条数据去找地域得话会严重影响耗时。如果单条耗时1毫秒，一万条数据耗时就是10000毫秒，可见如果数据量大的话影响是非常大的。所以想到了利用分桶来进行查找。原理是将42万数据中，将每个ip网段的开始段转为数字，然后按照这个数字分桶。分为100个桶即每个桶平均有420000/100 = 4200条数据。每个桶中的数字按照从小到大的顺序排序，即每个桶中最小的数据-1便是前一个桶的结尾。然后在每条数据的ip查找网段时同样将它转为数字即可得到该数字应该在哪个桶，然后遍历使用二分法找到值在该桶中的位置。这样的话效率便会快了很多。

正文

1. 原理

如果不理解二分法的话，可以先看这篇文章学习。这里讲一下桶排序算法，桶排序是一种排序算法，它工作的原理是将数组分到有限数量的桶中，每个桶分别排序（这里每个桶排序也可能运用到别的排序算法，例如插入排序）。

2.代码

/**
 * @Author Harrison
 * @Date Created in 18:33 2019/12/4
 */
@Slf4j
@Component
public class IpSegment implements ApplicationRunner {

    // 用于记录数组中的最大值,来定义最大的桶的数
    private static long MAXLONG = Integer.MIN_VALUE;

    // 桶数据
    private static List<AddressMsg>[] bucketSort = null;

    @Resource(name = "baseDaoSupportImpl")
    private BaseDaoSupport baseDaoSupportImpl;

    @Override
    public void run(ApplicationArguments applicationArguments) throws Exception {

        long start = System.currentTimeMillis();

        // 用sql查询出ip段以及对应国家、省份、城市数据，利用concat函数将结果组装为'ip段开始-ip段结束_国家id-省份id-城市id'格式。
        String sql = "select CONCAT(IP_ADDRESS_START,'-',IP_ADDRESS_END,'_',IP_COUNTRYID,'-',IP_PROVINCEID,'-',IP_CITYID) as IP_ADDRESS_MSG FROM tb_ipblock";
        List<Map<String, Object>> ipBlockList = baseDaoSupportImpl.findListMapByNativeSql(sql);

        // 此处是先将所有的国家身份信息查出来并存储为key为国家-省份-城市的map。最终用于将id翻译为名称。
        List<Location> locationList = baseDaoSupportImpl.findAll(Location.class, null);
        Map<String, Location> locationMap = new HashMap<>();
        locationList.forEach(location -> {
            locationMap.put(String.format("%s-%-%s", location.getCountryId(), location.getProvinceId(), location.getCityId()), location);
        });

        /**
         * 此处有多个处理：
         *   1.计算每个ip段开始ip的值。放入AddressMsg中，同时计算出最大的值赋给定义好的变量MAXLONG。
         *   2.计算每个ip段结束ip的值。放入AddressMsg中。
         *   3.将ip段对应的国家省份信息的名称，放入AddressMsg中。
         * 即AddressMsg对象存放4个信息。 该ip段的开始结束值、国家信息、省份信息、城市信息。
         **/
        List<AddressMsg> addressList = ipBlockList.stream().map(ipBlock -> {

            AddressMsg addressMsg = new AddressMsg();

            String msg = ipBlock.get("IP_ADDRESS_MSG").toString();
            // ip段信息 格式：ip段开始-ip段结束
            String ip = msg.split("_")[0];
            // 国家省份信息 格式：国家id-省份id-城市id
            String mapKey = msg.split("_")[1];

            // 计算ip段开始与结束的值
            long ipStartLong = getIp2long(ip.split("-")[0]);
            long ipEndLong = getIp2long(ip.split("-")[1]);
            addressMsg.setIpEndLong(ipEndLong);
            addressMsg.setIpStartLong(ipStartLong);

            // 求最大开始值赋值给变量MAXLONG
            MAXLONG = max(MAXLONG, ipStartLong);

            // 在locationMap国家省份信息中获取到对应信息，将国家和省份的名称放入addressMsg
            Location location = locationMap.get(mapKey);
            if (location == null) {
                location = new Location();
            }
            addressMsg.setCountryName(location.getCountryName());
            addressMsg.setProvinceName(location.getProvinceName());

            return addressMsg;
        }).collect(toList());

        // 将ip段数据分桶存放
        bucketSort = bucketSort(addressList);
        log.info("加载ip网段地址信息耗时{}毫秒", (System.currentTimeMillis() - start));
    }

    // 将ip转换为long值
    public static long getIp2long(String ip) {

        String[] ips = ip.split("\\.");
        long ip2long = 0L;
        for (int i = 0; i < 4; ++i) {
            ip2long = ip2long << 8 | Integer.parseInt(ips[i]);
        }
        return ip2long;
    }

    // 求最大值
    public static long max (long max, long num){
        return max > num ? max : num;
    }

    /**
     * 获取数字对应桶的下标
     *
     * @param data
     * @return
     */
    public static int getBucketIndex(long data) {
        /**
         *	MAXLONG为最大值。 除以100是因为分了100个桶，表示将MAXLONG分为100份。
         * 	data为需要计算在哪个桶的值,data除以(MAXLONG/100)得到的结果，即表示所在的桶的位置。
         *  例如：
         *  	MAXLONG为1000，将MAXLONG分为100份。 即1000/100=10。
         *      1000分为100份，每份是10，可以想象为：
         *         	第一个桶为1-10,第二个桶11-20，第三个桶21-30..以此类推
         *		data为55, 55/10=5; 即桶的位置为5.因为数组下标是从0开始，所以5应该表示为第6个桶。
         *		按照上面的算法，第六个桶应该为51-60.即55放入第6个桶是正确的。
         **/
        Long index = data / (MAXLONG / 100);
        return index.intValue();
    }

    /**
     * 将数据分桶存放
     *
     * @param arr
     * @return
     */
    public static List<AddressMsg>[] bucketSort(List<AddressMsg> arr) {

        // 桶的数量
        int bucketSize = 100;

        // 桶集合
        List<AddressMsg> bucket[] = new ArrayList[bucketSize];
        for (int i = 0; i < arr.size(); i++) {

            // 计算每个ip段数据应该存放的桶的位置
            int index= getBucketIndex(arr.get(i).getIpStartLong());
            if(index >= 100){
                // 这里是因为是以ip段开始值的最大值计算的，所以当最后一个ip段计算时值可能会超出最大值
                index = 99;
            }
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<AddressMsg>();
            }
            bucket[index].add(arr.get(i));
        }
        // 对各个桶内的list中的元素进行排序
        for (int j = 0; j < bucketSize; j++) {
            Collections.sort(bucket[j], Comparator.comparing(AddressMsg::getIpStartLong));
        }
        return bucket;
    }


    /**
     * 二分法查找ip所在位置
     *
     * @param ip 需要查找的ip
     * @return
     */
    public static AddressMsg getAddressMsgDichotomy (String ip) {

        if(StringUtil.isEmpty(ip)){
            return null;
        }

        // 获取ip对应的long值
        long ipLong = getIp2long(ip.trim());
        // 计算该ip应该存在的桶的位置
        int bucketIndex = getBucketIndex(ipLong);
        // 获取到对应桶的数据
        List<AddressMsg> msgList = bucketSort[bucketIndex];

        // 二分法在桶数据中查找该ip对应ip段的具体信息
        return dichotomy(msgList, ipLong);
    }

    /**
     *	二分法查找ipLong在list中的位置
     **/
    public static AddressMsg dichotomy(List<AddressMsg> list, long ipLong) {

        int start = 0;
        int end = list.size() - 1;
        boolean isExist = false;
        int middle = 0;

        while (start <= end) {
            middle = (start + end) / 2;
            if (ipLong < list.get(middle).getIpStartLong()) {
                end = middle - 1;
            } else if (ipLong > list.get(middle).getIpEndLong()) {
                start = middle + 1;
            } else {
                isExist = true;
                break;
            }
        }
        if (isExist) {
            return list.get(middle);
        } else {
            return null;
        }
    }

    /**
     * 循环查找ip所在位置， 该方法为第二种查找方法，效率要比二分法查找慢。
     *
     * @param ip
     * @return
     */
    public static AddressMsg getAddressMsg (String ip) {

        if(StringUtil.isEmpty(ip)){
            return null;
        }
        long ipLong = getIp2long(ip.trim());
        int bucketIndex = getBucketIndex(ipLong);
        List<AddressMsg> msgList = bucketSort[bucketIndex];

        // 循环桶数据找到ip所在的位置，没有二分法快的原因就在这里。因为是循环集合中所有数据
        List<AddressMsg> filterList = msgList.stream()
                .filter(addressMsg -> addressMsg.getIpStartLong() <= ipLong && ipLong <= addressMsg.getIpEndLong())
                .collect(toList());
        if(CollectionUtils.isEmpty(filterList)){
            return null;
        }
        return filterList.get(0);
    }
}

3.测试结果

Random random = new Random();
String ip = null;
for (int i = 0; i < 10000; i++) {
    int ip1 = random.nextInt(255);
    int ip2 = random.nextInt(255);
    int ip3 = random.nextInt(255);
    int ip4 = random.nextInt(255);
    if(ip1 == 0){
        ip1 = 1;
    }
    if(ip1 > 223){
        ip1 = 223;
    }
    ip = String.format("%s.%s.%s.%s", ip1, ip2, ip3, ip4);


    long start = System.currentTimeMillis();
    AddressMsg addressMsg = IpSegment.getAddressMsg(ip);
    log.info("循环查找耗时{}毫秒,结果:{}", (System.currentTimeMillis() - start), JacksonUtil.obj2str(addressMsg));

    long s = System.currentTimeMillis();
    addressMsg = IpSegment.getAddressMsgDichotomy(ip);
    log.info("二分查找耗时{}毫秒,结果:{}", (System.currentTimeMillis() - s), 		JacksonUtil.obj2str(addressMsg));
}