首页 > 代码库 > 位图排序
位图排序
第一次听说位图排序是在上操作系统课的时候, 当时也没太在意, 就是觉得存储挺方便。 最近看《编程珠玑》开篇就将到位图排序, 那么有缘就来实现下。
以下代码将JDK提供的排序和位图排序做了下对比(分别在稠密集和稀疏集情况下):
package com.wenniuwuren.sort.bitmap; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; /** * 位图排序与普通排序的比较 * @author wenniuwuren * */ public class BitMapSort { private static final int COUNT = 10000000; // 辅助存储空间 private static int[] temp = new int[COUNT]; // 待处理的数据集 private static List<Integer> dataList = new ArrayList<Integer>(); // 计时 private static long start = 0l; private static long end = 0l; public static List<Integer> bitMapSort(final List<Integer> data) { BitMapSort.dataList.clear(); // 1. initial set to empty for (int i = 0; i < BitMapSort.temp.length; i++) { BitMapSort.temp[i] = 0; } // 2. insert present elements into set for (int i = 0; i < data.size(); i++) { BitMapSort.temp[data.get(i)] = 1; } // 3. write sorted output for (int i = 0; i < BitMapSort.temp.length; i++) { if (BitMapSort.temp[i] == 1) { BitMapSort.dataList.add(i); } } return BitMapSort.dataList; } public static void getStartTime() { start = System.nanoTime(); } public static void getEndTime(final String s) { end = System.nanoTime(); System.out.println(s + ": " + (end - start) + "ns"); } public static void main(final String[] args) { // dense set List<Integer> denseSet = new ArrayList<Integer>(); // sparse List<Integer> sparseSet = new ArrayList<Integer>(); Random random = new Random(); for (int i = 0; i < COUNT; i++) { denseSet.add(i); sparseSet.add(random.nextInt(COUNT)); } Collections.shuffle(denseSet); Collections.shuffle(sparseSet); getStartTime(); Collections.sort(sparseSet); getEndTime("Java sort sparse set run time"); getStartTime(); bitMapSort(sparseSet); getEndTime("BitMapSort sparse set run time"); System.out.println("-----------------------------------"); getStartTime(); Collections.sort(denseSet); getEndTime("Java sort dense set run time"); getStartTime(); bitMapSort(denseSet); getEndTime("BitMapSort dense set run time"); } }
Java sort sparse set run time: 25559066561ns
BitMapSort sparse set run time: 20466873163ns
-----------------------------------
Java sort dense set run time: 20786022181ns
BitMapSort dense set run time: 3490992530ns
从结果可以清楚看出位图排序的优势和劣势
优势: 在数据集集中分布的情况下, 运行时间比一般的排序快挺多。 是一个典型的空间换时间的算法。
劣势: 在数据集稀疏分布的情况下, 运行时间不会差太多。 而且得事先知道要处理的数据最大值, 才好定义辅助属性的大小。
位图排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。