先上结果,速度上秒掉各种排序:
1e4 Straight Insertion: 0.109916 Sec
1e4 Bitmap sorting : 0.000214 Sec
1e8 Bitmap sorting : 6.568575 Sec
前提条件是一般测试数据偏差不大,因此可以用bitmap来标记数据,标记完了自然就排序完成。比堆排序还要快一两个数量级。
缺点也很明显:占内存,只能使用不是特别多的数据排序。
内存评估:一字节8bit, 1M内存是8M bitmap, 1G内存可以排序偏差为8e9的数据,所以一般开发时如果内存够用可以快速出结果。上面1e8个随机数,生成的时候取值在1e9之内,所以内存占用125M.
实现:先扫描出最大最小值,然后分配bitmap内存,再扫描一次做标记,完工。复杂度应该是O(n)
参考:各种排序1万条随机数对比:https://wenku.baidu.com/view/65a02500168884868662d637.html
int *bitmap_sort(int *d, int n, int *r_min, int *r_count) {
//first scan find min and max
//create bitmap, size(max-min)
//2nd scan map existance of each number
int i;
int min = d[0];
int max = d[0];
for (i = 1; i < n; ++i) {
if (d[i] < min)
min = d[i];
else if (d[i] > max)
max = d[i];
}
int int_bits = sizeof(int) * 8;
*r_min = min;
*r_count = (max - min + 1) / int_bits + 1;
int *bitmap = (int *) calloc(int_bits, *r_count);
for (i = 0; i < n; ++i) {
int idx = d[i] - min;
bitmap[idx / int_bits] |= 1 << (idx % int_bits);
}
return bitmap;
}
void bitmap_dump(int min, int count, int* bitmap) {
int i, j, v;
int idx = 0;
for (i = 0; i < count; ++i) {
v = bitmap[i];
for (j = 0; j < sizeof(int) * 8; ++j) {
if (v & (1 << j)) {
if (idx % 50 == 49)
printf("\n");
printf("%d ", min + i * sizeof(int) * 8 + j);
idx++;
}
}
}
printf("\n");
}
void bitmap_sort_test(int n, int* d) {
clock_t start;
int min, count;
int* bitmap;
if (n < 1000)
bitmap_dump(min, count, bitmap);
start = clock();
bitmap = bitmap_sort(d, n, &min, &count);
printf("Bitmap Sort total time: %f\n",
(clock() - (double) start) / CLOCKS_PER_SEC);
if (n < 1000)
bitmap_dump(min, count, bitmap);
}
int main(int argc, char **argv) {
clock_t start;
// int d[] = { 2, 5, 9, 3, 4 };
// int n = sizeof(d) / sizeof(d[0]);
int n = 1e8;
int *d = (int *) malloc(n * sizeof(int));
if (!d) {
printf("not enough memory\n");
return -1;
}
make_random_data(d, n);
if (n <= 1e5) {
if (n < 1000)
dump_data(d, n, 0);
start = clock();
straight_insertion_sort(d, n);
printf("Straight Insertion total time: %f\n",
(clock() - (double) start) / CLOCKS_PER_SEC);
if (n < 1000)
dump_data(d, n, 1);
}
bitmap_sort_test(n, d);
return EXIT_SUCCESS;
}
分享到:
相关推荐
• 第六章 海量数据处理 o 6.0 本章导读 o 6.1 关联式容器 o 6.2 分而治之 o 6.3 simhash 算法 o 6.4 外排序 o 6.5 MapReduce o 6.6 多层划分 o 6.7 Bitmap o 6.8 Bloom filter o 6.9 Trie 树 o 6.10 数据库 o 6.11 ...
基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法,虽被广泛用于网络处理的多个领域(路由查找、网包分类等),却一直缺乏深入的分析。给出了Bitmap结构能提高算法空间性能的理论根据。总结了...
位图算法
主要介绍了c# 如何实现位图算法(BitMap),文中讲解非常细致,帮助大家更好的理解和学习,感兴趣的朋友可以了解下
3个bitmap文件,用于认识bitmap文件格式的本质
//Bitmap类,特点紧约型数据结构,GetPixel效率高,放弃调色板,自动支持4种色深,特有的12位颜色更接近人眼可识别颜色数目;有多种缩放,色深转换,拷贝,剪切,和hBitmap转换,显示等功能;支持串行化。支持1,12,...
使用Bitmap方式实现大数据查找,简洁的代码很直接的阐述了Bitmap的原理
一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具...
Bitmap 结构在高性能网络算法设计中的应用
Android中Bitmap缓存池(基于2Q算法),供大一起共同分享学习。
改成C#后效率一直不高(尝试过消除浮点运算 查表法等) 后看到MSDN上的转换公式 http: msdn microsoft com en us library aa917087 aspx 后编写了此转换类库 转换一个D1帧 704 576 大约只需60ms左右 压缩包为Vs2010...
一个DIB (位图)bitmap封装类 欢迎大家下载哈
android 把一个view视图转换成bitmap 保存到本地 可以用于分享的局部截屏
能通过任何一个节点找到其他所有的节点,将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环 常见操作 添加数据到链表中 遍历找到尾节点,插入即可(只要while(temp.next != null),...
处理bitmap内存溢出问题
软件开发网在此之前给大家介绍过图片加载框架Glide的基本用法介绍,大家可以先参考一下,本篇内容更加深入的分析了Glide获取图片Path、Bitmap用法,以及实现的代码分析。 1. 获取Bitmap: 1)在图片下载缓存好之后...
一个在VC中将Bitmap转换为Byte[]的小例子。