90w 条记录排序

benjiam

90w 条记录排序

需要接近25 分钟。 记录使用的是protobuff 写的。所以有个解压 压缩的过程。
用的是hash 分块 ，内存排序 再合并的方法做的。 因为hash 分块 是动态分的。
类似堆排序。  直到将块分到一定大小的时候 再内存里面排序 合并。

问题是 这个hash 分起来 一开始的效率很低的。 90w条记录 第一次hash 的结果可能是
40w 50w, 1w 2w 10w 这样的结果。 所以需要反复hash 这hash 一次就需要 将这40w 50w条记录
重新读一次， 感觉效率还是低。  

我现在不是保持在mysql 这样的数据库里面。 而是自己写了 所有的代码。

目前是单线的，如果多线，
40w 50w 这些记录 第二次分 就可以放在别的线程 或的别的机器上了。是不是 small bigtable啊！
不知道这种模型还有无可以提高的地方呢

修改了hash的步进速度 快了n多 n多

A.com

90w……还不到1M的排序应该很快的，楼主还是详细说下排什么序吧。。。我实在是看得一头雾水，不明白你在说什么

peidright

,吧数据拿放出来，大家比一比，谁写的排序快。。。。。。

benjiam

... 错了 看了一下 890w 条记录

是用protobuff 写的记录。380M


既然大家很有兴趣不如做个比较吧。

希望算法可以平行扩展， 也就是最好能多个pc 一起工作。 要求算法是稳定的。


文件在http://www.msn2web.com:8080/pb/alladdress.rar

20M 还算好


读取的接口和函数在这里

http://www.msn2web.com:8080/pb/src.rar

读取的方法， 和类是这样的

ReadProtoFile(std::string filename) 类用来建立一个读对象

template<typename a>
bool GetProject( a & ta )

读出一个我要排序的对象

我要排序的对象
LocalAddress





最后一点 你需要下载和安装一个google 的protobuff 的类库。否则 编译不过


protbuff 的原型文件如下

message LocalAddress {

  optional string name  = 1; // 请求名字
  
  optional int64  id  = 2;    // 唯一id 编号
  optional string QuHaoName = 3;// 区号名
  optional string quming = 4; // 小区名
  optional string street = 5; // 街道
  optional string clnt =6 ;  // 经度
  optional string clng  = 7;  // 维度
  optional  int64 xiaoquid  = 8;// 小区id编号
  optional string srcstreet = 9;// 原始路径

}


你可以自己编译出localaddress 类。

排序就是按照 name 这个字段进行排序. std::cmp 的方式。


希望能并向运行。



我在我的sl500 的本本上win2003 时间  比linux centos  p42.0 的时间要长30% 的时间

真是悲剧啊

学与思

为什么要排序，不能不排序吗？

benjiam

要去重， 而且排序是很多起他业务的基础，不排。速度慢n多。

而且可能按照不同的条件要排好几次

没本

要去重， 而且排序是很多起他业务的基础，不排。速度慢n多。

而且可能按照不同的条件要排好几次
benjiam 发表于 2010-05-04 10:15

去掉重复之后还排很多次，那索引拿来干什么？