吃饱喝足了，还发贴了。
拆开分成几千份进行排序再合并。
首先先创建一个1亿个QQ号的txt。
<?php// 创建一亿个QQ号的txt (大约需85~100秒)set_time_limit(0);$fn = 'qq.txt';$fp = fopen($fn, 'w');$st = microtime(true);$l = range(0,10000);shuffle($l);foreach ($l as $k=>$v){ $arr = range($v*10000+10000,10000*($v+1)+9999); shuffle($arr); fputs($fp,implode("\n", $arr)."\n"); unset($arr);}echo microtime(true)-$st;?> 稍等一两分钟1亿个随机QQ创建完成了。
QQ号码范围为>10000。文件大小大概有840MB。
下面就进行分类划分成几千份文件。
以QQ号码长度为文件夹，QQ号码前3位为文件名。
<?php// 长度号码分类 (大约需360~400秒)set_time_limit(0);$st = microtime(true);if(!is_dir('qq_no')) mkdir('qq_no');$file = fopen('qq.txt', 'r'); $i=0;$end_s = '';while(!feof($file)){ $g = 1042*1024; fseek($file,$g*$i); $s = fread($file, $g); $end = strrpos($s, "\n"); $arr_s = $end_s.substr($s, 0, $end); $end_s = substr($s, $end); $arr = explode("\n", $arr_s); foreach ($arr as $k=>$v) { if($v!='') { $tag = "$v[0]$v[1]$v[2]"; $text_arr[strlen($v)][$tag][] = $v; } } foreach ($text_arr as $k=>$v) { $n_dir = 'qq_no/'.$k; if (!is_dir($n_dir)) mkdir($n_dir); foreach ($v as $tag=>$val) { $n_tf = fopen($n_dir.'/'.$tag.'.txt', 'a+'); fputs($n_tf,implode("\n",$val)."\n"); } } unset($text_arr); ++$i;}echo microtime(true)-$st;?> 最后就要每个文件进行排序合并数据了。
<?php// 排序完成拉 (800~920秒)set_time_limit(0);$st = microtime(true);$qq_done = fopen('qq_done.txt', 'a+');$root = 'qq_no';$dir_array = scandir($root);foreach ($dir_array as $key=>$val){ if ($val != '.' && $val != '..') $dirs[$val] = scandir($root.'/'.$val);}foreach ($dirs as $key=>$val){ foreach ($val as $v) { if ($v != '.' && $v != '..') { $file = $root. '/' . $key . '/'. $v; $c = file_get_contents($file); $arr = explode("\n", $c); sort($arr); fputs($qq_done, implode("\n",$arr)); unlink($file); } } rmdir($root. '/' . $key);}rmdir($root);echo microtime(true)-$st;?> 总共大概花费了20多分钟。
虽然完成了，但方法很土鳖 0_0 ，坛里各位高手们改进改进啊。
回复讨论(解决方案)
没学过php 能不能用哈希散列分散去排列？
我去打酱油了。
这么晚还有人，
楼上两位吃吃瓜子吧。
强大的数组工程
交给数据裤吧
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分钟出结果
(可能还要短一点,因为我把它放后台了)
没学过php 能不能用哈希散列分散去排列？
我也没学过，我只会C和Java...哈希散列完全可以，QQ号码不重复的话可以完全映射
来个C版本的
#include#define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F#define N 100000000int a[1 + N/BITSPERWORD];void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK)); //i&MASK相当于1&(32-1)，即1%32}void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK));}int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK));}int main(){ int i; //初始化 for(i = 0; i < N; i++) clr(i); //读取文件，置位 while(scanf("%d", &i) != EOF) set(i); for(i = 0; i < N; i++) if(test(i)) printf("%d\n", i); return 0;}
请做好边界测试
1亿个QQ号码并不是1亿个1亿以内的数
10月份我一个朋友申请的QQ号已是 1450250164 了
千万别小瞧了那多出来的一位
先把数据存入数据库，然后在读，这样时间会不会快，这会不会死机？
这位同学请教一下，直接sort怎么弄啊?
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分钟出结果
(可能还要短一点,因为我把它放后台了)
这确实啊。。没考虑到这一点。
差一位就差很多了。
从容量统计上看就看出来差很多了。
大概。
6位QQ号的总7mb
7位QQ号的总70mb
8位QQ号的总700mb
...
请做好边界测试
1亿个QQ号码并不是1亿个1亿以内的数
10月份我一个朋友申请的QQ号已是 1450250164 了
千万别小瞧了那多出来的一位
c的方法还得学习学习。
用数据库来排序还在测试中...
还没成功。导入是个问题。
这位同学请教一下，直接sort怎么弄啊?
引用 6 楼 helloyou0 的回复:
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分钟出结果
(可能还要短一点,因为我把它放后台了)
就是unix的命令sort啊
改天我再试试大点的文件和mysql数据库
mysql我测好了。
引用 12 楼 ci1699 的回复:
这位同学请教一下，直接sort怎么弄啊?
引用 6 楼 helloyou0 的回复:
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分钟出结果
(可能还要短一点,因为我把它放后台了)
就是unix的命令sort啊
改天我再试试大点的文件和mysql数据库
用mysql来排序完成了。
入库排序导出最快也要10来分钟。
相对上面php来排快了些。
说话什么都要动动手。
不抓抓还真不知哪里疼哪里痒啊。
用mysql来排序首先要入库。
第一个要解决的问题，就是把1亿个QQ号入库。
总不能INSERT一亿次吧?
刚开始想直接把生成的QQ号码转成sql直接导入。
但生成sql后1G多啊。这么大，怎么耍?
想想还是分开了几个几百MB吧。
然后就分成了几百MB一个sql导入。
这一导upu、内存就开始狂飙了，滴答了大半天没反应。
关进程查表看情况怎样，但表还是空空如也。
又没报错又没信息看。莫非文件还太大?
继续分成几十MB试试。
又是等十多分钟，但是还是失败了。报max_allowed_packet错。
改max_allowed_packet继续导，依然报错。
最后没方法试了少量数据终于找到原因拉。
是SQL太长...(),(),()...的原因，那除了分下文件又得分sql了。
拆成1MB一条sql。
下面贴代码，各位朋友可以试试。
<?php// 生成sql (大约需70秒)set_time_limit(0);$st = microtime(true);$file = fopen('qq.txt', 'r'); $filesize = filesize('qq.txt');$i=0;while(!feof($file)){ $g = 1042*1024; fseek($file,$g*$i); $s = fread($file, $g); $end = strrpos($s, "\n") + 1; $_s = $end_s.substr($s, 0, $end); $end_s = substr($s, $end); $tag = 'sql_' . ceil(($i+1)/200); // 一个文件处理200MB if(!isset($$tag)) { $$tag = fopen($tag.'.txt', 'a+'); fputs($$tag,"INSERT INTO `test` (`qq`) VALUES ('"); } $_s = str_replace("\n", "'),\n ('", $_s); $next = 'sql_' . ceil(($i+2)/200); $add = (isset($$next) && $g*($i+1) <$filesize) ? "\nINSERT INTO `test` (`qq`) VALUES ('" : ''; // 1MB一条sql $_s = substr($_s, 0, strrpos($_s, ',')) . ';' . $add; fputs($$tag, $_s); ++$i;}echo microtime(true)-$st;?> 执行完成就生成5个sql文件。
进入mysql控制台，
use test;
分别source D:xxxx\sql_X.txt导入。
ok。亿条数据入库了。
最后排序导入txt。
顺利完成了。
这过程涉及到引擎与索引两个问题。
也分别做了测试。大家可以对比下。
CREATE TABLE IF NOT EXISTS `test` ( `qq` int(10) NOT NULL, KEY `qq` (`qq`)) ENGINE=MyISAM DEFAULT CHARSET=utf8;#MyISAM类型----------------------- #无索引------------ 导入亿条记录210秒左右。 导出txt SELECT * FROM `test` ORDER BY `qq` ASC INTO OUTFILE "ok1.txt"; 426.73秒 (另: 单独ORDER BY `qq`均 60秒，导出时写文件相当快。平均60MB一秒地写) 总花费636秒约10分钟。 #有索引------------ 导入亿条记录花费了1100.1秒。 导出txt SELECT * FROM `test` ORDER BY `qq` ASC INTO OUTFILE "ok2.txt"; 391.24秒 (另: 单独ORDER BY `qq`均 0.0003秒，相当的快，有点震惊。 不过不知为何导出时写文件这么慢。平均2、3MB一秒地写) 总花费1491秒约24分钟。#InnoDB类型----------------------- 无索引------------ 导入亿条记录1544秒左右。 有索引------------ 导入亿条记录>4200秒。(插到后面相对来说越来越慢) 太慢了。导出就不测了。
总结上面最佳方案就是使用MyISAM引擎并且无索引。
最后有几点疑问，INTO OUTFILE是怎么会事的呢?
一个索引一个无索引导出写文件速度差别这么多。
还有让人郁闷的是，怎么InnoDB这么慢，且慢这么多?
不可想象。不玩了，睡觉了。 0_0zzzz
太牛了
真强大啊，，无语了。
强大的数组工程
既然有现成的数据文件，就没有必要去构造插入串了
set_time_limit(0);$sql =<<< SQLCREATE TABLE IF NOT EXISTS qq1 ( `qq` int(10) NOT NULL, KEY `qq` (`qq`)) ENGINE=MyISAM DEFAULT CHARSET=utf8;SQL;mysql_connect('localhost', 'root', '');mysql_select_db('test');mysql_query($sql);$filename = str_replace('\\', '/', realpath('qq.txt'));$sql =<<< SQLLOAD DATA INFILE '$filename' INTO TABLE qq1SQL;check_speed(1);mysql_query($sql) or print(mysql_error());;check_speed();时间: 182,955,851 微秒 内存: 664
set_time_limit(0);mysql_connect('localhost', 'root', '');mysql_select_db('test');echo '升序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_1.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq1 ORDER BY qq ASC INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());check_speed();echo '降序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_2.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq1 ORDER BY qq DESC INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());check_speed();echo '主键可不排序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_0.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq1 INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());;check_speed(); 升序
时间: 46,308,538 微秒
内存: 520
降序
时间: 105,860,001 微秒
内存: 432
主键可不排序
时间: 38,615,022 微秒
内存: 432
还有让人郁闷的是，怎么InnoDB这么慢，且慢这么多?
所有 InnoDB 类型表的数据被存放在一个文件 ibdata1 中，依靠文件指针来定位数据
但由于他不要求有连续的磁盘空间（这点与 oracle 不同，oracle 需要在创建库时就创建好连续的磁盘空间作为表空间），因此 InnoDB 类型表的访问速度取决于你的硬盘碎片的程度。碎片越多，速度越慢
楼主求真相的精神真让我感动。这个问题我也仔细想过，如果只使用内存，感觉使用哈希是最好了。但如果使用硬盘，控制内存。大量的IO就成了主要矛盾，mysql就是这样
既然你已经有数据了，帮试下。重新建索引的时间是多少。如果超过10分钟就不用再试了。
建索引就生成了索引文件，是一个真正的排序过程。mysql是使用b+树结构，随着树的深度，以后定位数据花的时间会越来越多。因此索引文件生成会越来越慢。估计不太乐观。至于InnoDB的索引就不用考虑了。
InnoDB 表测试
set_time_limit(0);$sql =<<< SQLCREATE TABLE IF NOT EXISTS qq2 ( `qq` int(10) NOT NULL, KEY `qq` (`qq`)) ENGINE=InnoDB DEFAULT CHARSET=utf8;SQL;mysql_connect('localhost', 'root', '');mysql_select_db('test');mysql_query($sql);echo '导入
';$filename = str_replace('\\', '/', realpath('qq.txt'));$sql =<<< SQLLOAD DATA INFILE '$filename' INTO TABLE qq2SQL;check_speed(1);mysql_query($sql) or print(mysql_error());;check_speed();导入 时间: 3,286,588,777 微秒
内存: 664
导出
set_time_limit(0);mysql_connect('localhost', 'root', '');mysql_select_db('test');echo '升序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_1.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq2 ORDER BY qq ASC INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());check_speed();echo '降序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_2.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq2 ORDER BY qq DESC INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());check_speed();echo '主键不排序
';$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_0.txt');if(file_exists($filename)) unlink($filename);$sql =<<< SQLSELECT qq FROM qq2 INTO OUTFILE '$filename'SQL;check_speed(1);mysql_query($sql) or print(mysql_error());;check_speed();升序 时间: 367,638,625 微秒
内存: 520
降序
时间: 390,232,528 微秒
内存: 432
主键不排序
时间: 367,762,026 微秒
内存: 432
ok, 又试了全是11位的QQ号, 实际上100020001个,
sort一下, 22分钟
引用 12 楼 ci1699 的回复:
这位同学请教一下，直接sort怎么弄啊?
引用 6 楼 helloyou0 的回复:
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分钟出结果
(可能还要短一点,因为我把它放后台了)
就是unix的命令sort啊
改天我再试试大点的文件和mysql数据库
仅给出测试的时间是没有意义的，因为同一代码在不同的机器和操作系统中，执行的效果并不取决于算法和代码本身
不同的算法和代码在同一环境中运行，才能体现出优劣
原来还可以这么导啊。
我刚执行了下，
用了387.14144778252。
这下又导入又有索引了。
看样子还是用上索引哈。。
既然有现成的数据文件，就没有必要去构造插入串了
PHP code
set_time_limit(0);
$sql =<<< SQL
CREATE TABLE IF NOT EXISTS qq1 (
`qq` int(10) NOT NULL,
KEY `qq` (`qq`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
SQL;
mysql_connec……
同一个文件,mysql myisam表导入/建索引/导出
4+13.5+2=19.5分钟,比sort还快点
ok, 又试了全是11位的QQ号, 实际上100020001个,
sort一下, 22分钟
引用 16 楼 helloyou0 的回复:
引用 12 楼 ci1699 的回复:
这位同学请教一下，直接sort怎么弄啊?
引用 6 楼 helloyou0 的回复:
用你代码生成qq.txt,
然后直接sort,
在我的fedora(vmware)里18分……
学习了。我还一直认为用InnoDB写操作比MyISAM快呢。
看样子InnoDB优势只在事务其它方面啊。
引用 18 楼 ci1699 的回复:
还有让人郁闷的是，怎么InnoDB这么慢，且慢这么多?
所有 InnoDB 类型表的数据被存放在一个文件 ibdata1 中，依靠文件指针来定位数据
但由于他不要求有连续的磁盘空间（这点与 oracle 不同，oracle 需要在创建库时就创建好连续的磁盘空间作为表空间），因此 InnoDB 类型表的访问速度取决于你的硬盘碎片的程度。碎片越多，速……
还想试一下这里106楼的c程序看能有多快,
http://topic.csdn.net/u/20111213/20/269a86f6-640e-4921-b8b1-b65840a5ef63_2.html
不过刚试了个小文件有bug,需要调试下.
楼主求真相的精神真让我感动。这个问题我也仔细想过，如果只使用内存，感觉使用哈希是最好了。但如果使用硬盘，控制内存。大量的IO就成了主要矛盾，mysql就是这样
既然你已经有数据了，帮试下。重新建索引的时间是多少。如果超过10分钟就不用再试了。
建索引就生成了索引文件，是一个真正的排序过程。mysql是使用b+树结构，随着树的深度，以后定位数据花的时间会越来越多。因此索引文件生成会越来越慢……
同学，你也折腾拉。
还想试一下这里106楼的c程序看能有多快,
http://topic.csdn.net/u/20111213/20/269a86f6-640e-4921-b8b1-b65840a5ef63_2.html
不过刚试了个小文件有bug,需要调试下.
:) 呵呵
其实我想说的是,这样的题目做面试题挺无趣的....
这样的活,我觉得就目前的测试来说,用sort是最现实的,
因为显然这个活不会经常干,22分钟完全可以接受,而且远远超出我的想象(我是在我的台式机里的vm虚拟机里做的,虚拟机分配了1G内存而已),如果上server干显然会更快.而用sort一点不用动脑筋,一行命令而已....
顺便崇拜一下sort及其它unix工具的作者.....真正的牛啊....
同学，你也折腾拉。
引用 32 楼 helloyou0 的回复:
还想试一下这里106楼的c程序看能有多快,
http://topic.csdn.net/u/20111213/20/269a86f6-640e-4921-b8b1-b65840a5ef63_2.html
不过刚试了个小文件有bug,需要调试下.
c 肯定要比 php 快，毕竟 php 是解释执行的，最终执行的还是 c 程序
导入一亿条数据到数据库的时间不要算的吗？ 用数据库的方法绝对不可取！（当然数据本身在数据库中除外）
楼主强大。
呵呵。确实这活不会经常干，不差那十来几分钟，能用linux的直接sort就sort拉。也这么快。
不过不经过测试怎么知道呢，这样下次就有经验了。
:) 呵呵
其实我想说的是,这样的题目做面试题挺无趣的....
这样的活,我觉得就目前的测试来说,用sort是最现实的,
因为显然这个活不会经常干,22分钟完全可以接受,而且远远超出我的想象(我是在我的台式机里的vm虚拟机里做的,虚拟机分配了1G内存而已),如果上server干显然会更快.而用sort一点不用动脑筋,一行命令而已....
顺便崇拜一下sort及其它unix……
c 肯定要比 php 快，毕竟 php 是解释执行的，最终执行的还是 c 程序
我想自己码的c也不会快过直接linux的sort命令吧?
哪位同学写写c来测测
导入一亿条数据到数据库的时间不要算的吗？ 用数据库的方法绝对不可取！（当然数据本身在数据库中除外）
你不仔细看帖子。就目前上面测试，数据库的方法最快。
在下搞php半年有余，如今在一家互联网公司搞网站开放，感觉天天写自己会的代码学不到什么，敢问楼主学php多少年月了？
有几年。。我还是小菜鸟拉。
在下搞php半年有余，如今在一家互联网公司搞网站开放，感觉天天写自己会的代码学不到什么，敢问楼主学php多少年月了？
主贴的qq号默认最大是100009999,而目前可能的最大qq号却是9999999999,差好多个数量级呢，实际情况使用位排序就是 9999999999 /8 /1024 /1024 差不多1.1G内存。。。
用主贴生成的数据测试了下，机器比较烂，花了300多秒生成，用c实现的位排序法读，排，写，总共时间差不多1分10秒多，LZ可以拿去测试看看,对了，主贴中生成qq号我改成了1行一个qq，方便读。
fputs($fp,implode(PHP_EOL, $arr).PHP_EOL);
ubuntu linux下gcc编译
#include#include #define MAX 100009999 #define SHIFT 5 #define MASK 0x1F #define DIGITS 32 int a[1+MAX/DIGITS]; void set(int n) { a[n>>SHIFT]=a[n>>SHIFT]|(1<<(n&MASK)); } void clear(int n) { a[n>>SHIFT]=a[n>>SHIFT]&(~(1<<(n&MASK))); }int test(int n) { return a[n>>SHIFT] & (1<<(n&MASK)); }int main(int argc, char *argv[]){ int i; int tp; FILE *ip; FILE *op; for(i=1;i<=MAX;i++) { clear(i); } ip = fopen("qq_before_sort.txt","r"); while( !feof(ip) ) { fscanf(ip,"%d\n",&tp); set(tp); } fclose(ip); op = fopen("qq_after_sort.txt","w"); for(i=1;i<=MAX;i++) { if(test(i)){ fprintf(op, "%d\n",i); } } fclose(op); return 0;}
在次看过，忙完了，在来学习
C
程序快这么多
？？？？
主贴的qq号默认最大是100009999,而目前可能的最大qq号却是9999999999,差好多个数量级呢，实际情况使用位排序就是 9999999999 /8 /1024 /1024 差不多1.1G内存。。。
用主贴生成的数据测试了下，机器比较烂，花了300多秒生成，用c实现的位排序法读，排，写，总共时间差不多1分10秒多，LZ可以拿去测试看看,对了，主贴中生成qq号我改成了1行一个qq，方便……
为什么编译不过去。。
错误 qq.c 7: 数组太小
主贴的qq号默认最大是100009999,而目前可能的最大qq号却是9999999999,差好多个数量级呢，实际情况使用位排序就是 9999999999 /8 /1024 /1024 差不多1.1G内存。。。
用主贴生成的数据测试了下，机器比较烂，花了300多秒生成，用c实现的位排序法读，排，写，总共时间差不多1分10秒多，LZ可以拿去测试看看,对了，主贴中生成qq号我改成了1行一个qq，方便……