PHP は 1 億個の QQ 番号をソートします
- WBOYオリジナル
- 2016-06-23 14:03:11912ブラウズ
食べたり飲んだりした後も投稿しました。
数千の部分に分割し、並べ替えて再度結合します。
まず、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 ～ 2 分待つと、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 を学習していないのですが、分散と配置にハッシュを使用できますか?
醤油作りに行ってきました。
こんな遅い時間にも人がいるよ、
２階でメロンの種を食べよう。
強力な配列エンジニアリング
Datapants にお任せください
コードを使用して qq.txt を生成し、
それから直接並べ替えます
結果は私の Fedora (vmware) で 18 分以内に表示されます
(少し短いかもしれません 、バックグラウンドに置いているので)
PHP を学習していないのですが、ハッシュを使用して並べ替えることはできますか?
私も習っていません、C と Java しか知りません... ハッシュは全く問題ありません。QQ 番号は繰り返されていなければ完全にマッピングできます
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;} 境界テストを行ってください
1 数億の QQ 番号は 1 億、1 億以内の数字ではありません
私の友人が 10 月に申請した QQ 番号はすでに 1450250164 です
余分な 1 を過小評価しないでください
まず、データをデータベース、では、読んでいる間に時間は早くなりますか？
このクラスメートは、直接ソートを行うにはどうすればよいですか?
コードを使用して qq.txt を生成し、
それから直接ソートしてください、
私の Fedora (vmware) では、結果は 18 分で得られます
(背景に入れているので少し短いかもしれません)
これは本当です。 。これは考慮されていませんでした。
たった一桁違うだけでも大きな違いです。
容量の統計から判断すると、大きな違いがあることがわかります。
たぶん。
6桁のQQ番号の合計は7mbです
7桁のQQ番号の合計は70mbです
8桁のQQ番号の合計は700mbです
...
境界テストを行ってください
1億QQ番号は1億以内ではありません 1億 番号
私の友人が10月に申請したQQ番号はすでに1450250164です
余分な人を過小評価しないでください
Cメソッドはまだ学習する必要があります。
データベースを使用した並べ替えはまだテスト中です...
まだ成功していません。輸入が問題です。
直接並べ替える方法を教えてください
6 階の helloyou0 からの引用:
コードを使用して qq.txt を生成し、
直接並べ替えます。私の Fedora (vmware) では、結果は次のようになります。 18 分で完了します
(バックグラウンドに置いているので、もしかしたらもっと短いかもしれません)
UNIX コマンドの sort です
別の日に大きなファイルと mysql データベースを試してみます
12 階の ci1699 から引用:
直接並べ替える方法を教えてください
6 階の helloyou0 から引用:
コードを使用して qq.txt を生成し、
直接並べ替えます。この場合、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 '升序<br />';$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 '降序<br />';$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 '主键可不排序<br />';$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 '导入<br />';$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 '升序<br />';$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 '降序<br />';$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 '主键不排序<br />';$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、
並べ替え、22 分です
12 階の ci1699 からの引用:
このクラスメートが聞きたいのですが、直接並べ替えを行うにはどうすればよいですか?
6 階の helloyou0 からの返信を引用します:
コードを使用して qq.txt を生成し、
そして直接並べ替えます。
私の Fedora (vmware) では 18 分で結果が得られます
(おそらく少し短いかもしれません) 、私がそれを置いたので バックグラウンドに置きます)
それは UNIX コマンドのソートです
大きなファイルと mysql データベースは別の日に試してみます
テスト時間を与えるだけでは意味がありません、同じだからですコードは異なるマシンやオペレーティングシステムで実行され、実行効果はアルゴリズムやコード自体には依存しません
異なるアルゴリズムやコードが同じ環境で実行された場合にのみ、利点と欠点が反映されます
このように導かれました。
実行したところ、
387.14144778252 が使用されました。
これで、再度インポートされ、インデックスが作成されました。
まだインデックスを使用する必要があるようです。 。
既製のデータ ファイルがあるため、挿入文字列を作成する必要はありません
PHP コード
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;
mysql_connec...
4+13.5+2=19.5 分、並べ替えよりも速い
OK、11 桁すべての QQ 番号を試してみました、実際には 100020001、
並べ替え、22 分
16 階の helloyou0 から引用 返信:
12 階の ci1699 からの引用:
直接並べ替える方法を教えてください
6 階の helloyou0 からの引用:
コードを使用して qq.txt を生成し、
直接並べ替えます。 Fedora (vmware) で 18 ポイント…
学びました。私は常々、InnoDB を使用した書き込み操作の方が MyISAM よりも速いと考えていました。
18 階の ci1699 からの返信を引用します:
また、気が滅入るのは、なぜ InnoDB がこんなにも遅いのかということです
InnoDB タイプのテーブル内のすべてのデータはファイル ibdata1 に保存され、データの検索にはファイル ポインターが使用されます。
ただし、連続ディスク領域を必要としないため (これは、ライブラリの作成時にテーブル領域として連続ディスク領域を作成する必要がある Oracle とは異なります)、InnoDB タイプのテーブルのアクセス速度は、ハードウェアの断片化の程度に依存します。ディスク。フラグメントが多ければ多いほど、速くなります...
また、ここの 106 階で C プログラムを試して、どれくらい高速になるかを試してみたいと思います。
しかし、私が試した小さなファイルにはバグがあり、デバッグする必要があります
を求める投稿者の精神には本当に感動します。真実。私もこの問題をよく考えて、メモリのみを使用する場合は、ハッシュを使用するのが最適であると感じています。ただし、ハードディスクを使用する場合は、メモリを制御してください。大量のIOが主な矛盾となっており、mysqlはこんな感じです
データは既にあるので試してみましょう。インデックスを再作成するのにどれくらい時間がかかりますか。 10 分以上かかる場合は、再試行する必要はありません。
インデックスを作成すると、インデックス ファイルが生成されます。これが実際の並べ替えプロセスです。 MySQL は b+ ツリー構造を使用しており、ツリーが深くなると、今後データを見つけるのにさらに時間がかかるようになります。そのため、インデックスファイルの生成はどんどん遅くなっていきます…
クラスメイト、あなたも苦労しています。
ここの 106 階の C プログラムも試して、どれくらい速いかを確認したいと思います。
http://topic.csdn.net/u/20111213/20/269a86f6-640e-4921-b8b1-b65840a5ef63_2.html
しかし、私はそれを試してみました。小さなファイルにデバッグが必要なバグがあります
。
:) 呵呵
其实我想说的是,这样的题目做面试题挺无趣的....
这样的活,我觉得就目前的测试来说,用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 <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;} 在次看过，忙完了，在来学习
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，方便……