php排序1亿个QQ号码

Question

没学过php  能不能用哈希散列分散去排列？

Answer 1

用你代码生成qq.txt,然后直接sort, 
在我的fedora(vmware)里18分钟出结果(可能还要短一点,因为我把它放后台了)

Answer 2

我也没学过，我只会C和Java...哈希散列完全可以，QQ号码不重复的话可以完全映射

Answer 3

来个C版本的#include <stdio.h>#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;
}

Answer 4

请做好边界测试1亿个QQ号码并不是1亿个1亿以内的数
10月份我一个朋友申请的QQ号已是 1450250164 了千万别小瞧了那多出来的一位

Answer 5

这位同学请教一下，直接sort怎么弄啊? 

Answer 6

这确实啊。。没考虑到这一点。
差一位就差很多了。从容量统计上看就看出来差很多了。
大概。
6位QQ号的总7mb
7位QQ号的总70mb
8位QQ号的总700mb...

Answer 7

就是unix的命令sort啊改天我再试试大点的文件和mysql数据库

Answer 8

用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

Answer 9

既然有现成的数据文件，就没有必要去构造插入串了
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_connect('localhost', 'root', '');
mysql_select_db('test');
mysql_query($sql);$filename = str_replace('\\', '/', realpath('qq.txt'));
$sql =<<< SQL
LOAD DATA INFILE '$filename' INTO TABLE qq1
SQL;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 '升序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_1.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT qq FROM  qq1 ORDER BY qq ASC INTO OUTFILE '$filename'
SQL;
check_speed(1);
mysql_query($sql) or print(mysql_error());
check_speed();echo '降序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_2.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT qq FROM  qq1 ORDER BY qq DESC INTO OUTFILE '$filename'
SQL;
check_speed(1);
mysql_query($sql) or print(mysql_error());
check_speed();echo '主键可不排序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_0.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT 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

Answer 10

所有 InnoDB 类型表的数据被存放在一个文件 ibdata1 中，依靠文件指针来定位数据
但由于他不要求有连续的磁盘空间（这点与 oracle 不同，oracle 需要在创建库时就创建好连续的磁盘空间作为表空间），因此 InnoDB 类型表的访问速度取决于你的硬盘碎片的程度。碎片越多，速度越慢

Answer 11

楼主求真相的精神真让我感动。这个问题我也仔细想过，如果只使用内存，感觉使用哈希是最好了。但如果使用硬盘，控制内存。大量的IO就成了主要矛盾，mysql就是这样既然你已经有数据了，帮试下。重新建索引的时间是多少。如果超过10分钟就不用再试了。
建索引就生成了索引文件，是一个真正的排序过程。mysql是使用b+树结构，随着树的深度，以后定位数据花的时间会越来越多。因此索引文件生成会越来越慢。估计不太乐观。至于InnoDB的索引就不用考虑了。

Answer 12

InnoDB 表测试
set_time_limit(0);
$sql =<<< SQL
CREATE 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 '导入<br />';
$filename = str_replace('\\', '/', realpath('qq.txt'));
$sql =<<< SQL
LOAD DATA INFILE '$filename' INTO TABLE qq2
SQL;
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 '升序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_1.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT qq FROM  qq2 ORDER BY qq ASC INTO OUTFILE '$filename'
SQL;
check_speed(1);
mysql_query($sql) or print(mysql_error());
check_speed();echo '降序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_2.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT qq FROM  qq2 ORDER BY qq DESC INTO OUTFILE '$filename'
SQL;
check_speed(1);
mysql_query($sql) or print(mysql_error());
check_speed();echo '主键不排序<br />';
$filename = str_replace('\\', '/', dirname(__FILE__) . '/qq_0.txt');
if(file_exists($filename)) unlink($filename);
$sql =<<< SQL
SELECT 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

Answer 13

ok, 又试了全是11位的QQ号, 实际上100020001个,
sort一下, 22分钟

Answer 14

同一个文件,mysql myisam表导入/建索引/导出4+13.5+2=19.5分钟,比sort还快点

Answer 15

学习了。我还一直认为用InnoDB写操作比MyISAM快呢。
看样子InnoDB优势只在事务其它方面啊。

Answer 16

还想试一下这里106楼的c程序看能有多快,
http://topic.csdn.net/u/20111213/20/269a86f6-640e-4921-b8b1-b65840a5ef63_2.html
不过刚试了个小文件有bug,需要调试下.

Answer 17

:) 呵呵其实我想说的是,这样的题目做面试题挺无趣的....这样的活,我觉得就目前的测试来说,用sort是最现实的,因为显然这个活不会经常干,22分钟完全可以接受,而且远远超出我的想象(我是在我的台式机里的vm虚拟机里做的,虚拟机分配了1G内存而已),如果上server干显然会更快.而用sort一点不用动脑筋,一行命令而已....顺便崇拜一下sort及其它unix工具的作者.....真正的牛啊....

Answer 18

c 肯定要比 php 快，毕竟 php 是解释执行的，最终执行的还是 c 程序

Answer 19

呵呵。确实这活不会经常干，不差那十来几分钟，能用linux的直接sort就sort拉。也这么快。
不过不经过测试怎么知道呢，这样下次就有经验了。

Answer 20

我想自己码的c也不会快过直接linux的sort命令吧? 
哪位同学写写c来测测
你不仔细看帖子。就目前上面测试，数据库的方法最快。

Answer 21

在下搞php半年有余，如今在一家互联网公司搞网站开放，感觉天天写自己会的代码学不到什么，敢问楼主学php多少年月了？

Answer 22

主贴的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 <stdio.h>             
#include <stdlib.h>            
#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;
}

Answer 23

为什么编译不过去。。
错误 qq.c 7: 数组太小