面试问题：给你一个文本文件，里面存储了一亿个QQ号，请用程序将其由小到大排序，汗呀!..

Question

面试问题：给你一个文本文件，里面存储了一亿个QQ号，请用程序将其由小到大排序，汗呀!..
求高手讲解思路！
还有其它问题：
比如Memcache的运行机制，它的工作原理它有什么优缺点！
现有一个库存100件的产品要进行秒杀，在秒杀过程中的秒杀人数远远超过库存，请问你将如何处理，应该注意什么问题！
请谈谈你对Mysql的优化的见解，或者说如果让你设计一个数据库，你将怎样设计并优化!
有高手吗，今天面试都自己认为都答得不太理想，求指教，还有下面的面试！
小弟的刚刚被裁员，本来就冬天，真的好冷啊！

Answer 1

排序的问题想不出来什么好办法，有没有更具体的限制条件，比如运行时间和内存？
如果都不限制直接sort函数就行，里面是用的快速排序法(quicksort)，理论上的效率应该是最高的，况且人家是native code，怎么也比php代码里模拟一个排序算法快。memcache的运行机制是使用职守进程开辟一块内存空间用来保存key/value数据，所有的请求和应用都共用这些数据。优点是存取速度快，适合用来缓存频繁读写的数据。缺点是占用内存，同时只能通过key检索，无法进行关系查询(SQL等）。要保证原子操作，使用一定的锁机制防止多个请求同时操作一个数据造成效果与预期不符。mysql数据库优化主要是索引和分表，为了性能可以为所有需要排序和检索的字段建立索引，并通过水平或垂直分表方式提高效率。

Answer 2

排序的话，常用方法有很多。比较经典的几种：冒泡排序，插入排序，归并排序，快速排序，堆排序，二叉树排序，桶排序。效率不同，但效率最高的也需要o(nlogn)的复杂度，即如果有一亿个数，需要比较26亿次。一般来说在实际使用上比较常用的是快速排序。

Answer 3

我是觉得是堆排序
因为平均时间和快速排序归并排序一样是O（nlogn）辅助存储是O(1)如果你只是需要单纯地记录一个QQ号而不包含其用户信息的话

Answer 4

import到数据库。排序。保存数据集。

Answer 5

这么庞大的内容，一次性加载到内存是不现实的。
目前常用的排序算法都是以内存为载体的，既然不能全部加载，那么排序算法也就不能用了于是可选择 哈希表 与 文件操作
创建一个文件作为 QQ表的索引：
以 QQ 号（转换成长整形）为偏移，存放 1 个字节的标志创建完成后，顺次读取索引文件，每次一字节。如果标志置位则其偏移就是 QQ 号，写入新文件即可代码省略，请自行书写。
作为面试，有思路就可以的

Answer 6

10亿QQ号
光是那个文件就差不多1G了，全部载入内存似乎是不现实

Answer 7

目的肯定不是让你投机，导入数据库，建索引导出，不过可以提一下
遍历一遍，将号码按大小，写入合适的文件比如约定10万一个号码段比如10,000，写在第0个文件，100,000,001，属于第1K个文件里面排序每一个文件数据，拼接文件排序的时候，如果文件较大，这里根据文件大小，大概能估计号码数量级的。。如果号码量少，可选择快排，否则，创建一个10万的数组，再次遍历，arr[qqnum-i*100000]+1;遍历数组，依数组值，增量写入号码即可复杂度是O(n),O(nlogn)之间

Answer 8

1亿个QQ号大概900多MB的文件吧。按QQ号前三位归纳另至以QQ长度命名的文件夹。文件名同为QQ号前三位。for读各文件夹文件排好序写文件。for顺序读各文件夹的文件合并数据。

Answer 9

切分成细的也是一种办法！但也可能不入流！按楼的上，将里面的QQ号最高等切分！ 然后将每个文件读入数组sort. 最后合并文件。

Answer 10

BTREE,用数据库的方式最简单.
如果想研究算法及数据结构的可以去找找资料.

Answer 11

用linux的split命令先对文件分割，再逐个排序，再合并文件，就可以搞定。

Answer 12

秒杀是用memcache做。memcache缓存的缺点由于分配的是特定长度的内存，因此无法有效利用分配的内存mysql优化就是设计合理，索引合理优化，这些网上写的文章很多的

Answer 13

现有一个库存100件的产品要进行秒杀，在秒杀过程中的秒杀人数远远超过库存，请问你将如何处理，应该注意什么问题！
===============================================
请求直接推入队列,再开一个程序读取队列，一条条处理。linux下php可直接调用系统队列(msg_前缀)请谈谈你对Mysql的优化的见解，或者说如果让你设计一个数据库，你将怎样设计并优化!
==============================================================================
哥就会dbdesigner建模，测试环境打开slow query log,explain观察

Answer 14

这个算法与我的算法一样
不过这个代码在实现上有点问题，目前 QQ号已经到达10位了仅存储这个串就需要 1G 内存。

Answer 15

$s  = '0';//5-7位的
$s2 = '0';//7-10位的$s2{qq号 - 1000000} = 1;

Answer 16

现在QQ号是10位的
那么建一个10^11bit的文件(理论上内存也可以)，遍历保存有QQ号的文本文件，将每个QQ号对应的第n位bit置为1。然后顺序遍历这个文件，如果第n位为1则输出QQ号，理论上可以达到O(n)的复杂度。

Answer 17

老大意思是文件中存bit串？也是哦，32位机一个文件就可以支撑2G以下字节，10位qq不是问题。

Answer 18

是的你没错，是我没说清楚，前面有说到需要分段。
7 - 8位q一个文件，8 - 10位一个文件，然后每一位再加上每个文件bit位表示特定的偏移量。

Answer 19

是 10^10 - 1
0000000000 ~ 9999999999如果真到了 10G，其实只要到达 2G，34位系统就都无法处理了php 所谓整数是 有符号 logn 类型的， 正数的上限是 2G - 1
就打算你把它当做无符号整数处理（假定操作系统也支持），其上限也只是 4G - 1

Answer 20

呵呵,qq有5位的
你算的是纯二进制位，不能说错，但是实现起来可能比较麻烦，就好象一个整形数999999，把其二进制第x位设置为1，然后最终结果还是得转二进制，找里面的1的位置。
而我们上面讨论是直接用串来表示二进制位，即一个字节为表示1位，(9999999999-9999)/(1024*1024*1024)大概9G多。

Answer 21

排序的最笨的方法，用EXCEL打开文件夹排序。
编程的方法入库，用算法排

Answer 22

比如Memcache的运行机制，它的工作原理它有什么优缺点 内存现有一个库存100件的产品要进行秒杀，在秒杀过程中的秒杀人数远远超过库存，请问你将如何处理，应该注意什么问题！队列请谈谈你对Mysql的优化的见解，或者说如果让你设计一个数据库，你将怎样设计并优化!索引 去join化 读写分离

Answer 23

qq号那个用位排序吧， 10^9 /8 /1024 /1024 ,只要100M内存

Answer 24

貌似这个方法更好，我记得《编程珠玑》第一章有这个题：一个最多包含n个正整数的文件，每个数都小于n，n = 1000 0000。文件中的正整数没有重复的，请按升序排列这些整数。可用内存空间只有1MB左右，运行时间在10秒左右。
是用的位图

Answer 25

举个例子吧！ 会php的请尽量贴代码！

Answer 26

原理未变，只是将按字节操作改为按位操作$num = 数;
$n = $num >> 3;
$m = 1 << $n % 8;
$s{$n} |= $m;只不过 10^9 /8 /1024 /1024 ,只要100M内存 这样才 9 位号码，并不能覆盖所有的 QQ 号

Answer 27

http://download.csdn.net/detail/rollor_phoe/168036
又找了一下，这个免费http://download.csdn.net/download/xkjack/2096200从事计算机应用普及二十年，现已退休三年了

Answer 28

qq号这个用位图法即可，大约需要200M空间。不过要分段，6位一个图，7位1个图一共要分5个图，支持6-10位的qq号。分段后一个位图实际上就是一个1维数组，读到一个QQ号，按照它的位数，转成整形直接往相应数组的相应位置放就行了。放完后顺序读取这几个数组的内容，过滤掉0值，输出到新文件里面

Answer 29

嗯，实际不需要这么多，因为这个数组可以是布尔型，这样1位可以放32个，实际空间只需要6M。嗯嗯，把读到的号码对应的位标成true，读取时遇到值为true的输出其下标。

Answer 30

这边分段的意思是从文件中读取qq号（假如从6位开始好了），如果该qq号是6位的则置相应的位为1。如果不是6位则不做处理，寻找文件中的下一个qq号。直到读完文件然后把6位的结果存入目标文件里面。然后再一次循序读取源文件去取7位的。这里6位的话需要空间就是10^6-1-10^5位空间；7位就是10^7-1-10^6位空间。是这样吗？那这样要多顺序读取4次文件

Answer 31

QQ号每位都是0-9，可以分为0-9文件，1开头的进入文件1中，2开头的进入文件2中...这样避免了占用内存过大(一行一行的读文件)，如果认为1000w条数据依然过大，那么你可以接着再分下去，这样也许会好些，当然了，至于排序方法本身就没啥了，毕竟排序方法就那么几种，本体估计考的就是内存的管理方面

Answer 32

在项目做过数据导入，一个表6千万，100多个字段，至少需要5个小时，用的是IBM的机子（电信服务器。）

Answer 33

如果用位图，标记为1，那不是生成的新文件和旧文件不一样大了？旧文件可能有重复qq#，新文件里没有重复的了？
我觉得还是根据qq号hash到多个小文件里，然后对小文件里的号码快速排序，然后在多路归并排序好点。

Answer 34

一般这个前提是没有重复的qq号码，试试上应该也是如此吧。如果是有重复的QQ号码，可以再设置一个标识的变量，来标识哪个位置重复了多少次

Answer 35

xuanbg的意思应该是下面这贴，一个数组元素模拟32位，确实很巧妙。
http://archive.cnblogs.com/a/2217369/

Answer 36

$num = 数;
$n = $num >> 3;
$m = 1 << $n % 8;   这里应该是 $m % 8
$s{$n} |= $m;一个位的信息只能存2种状态，，，一般这种题，应该会说明数据并不会重复，或者如前面说的，只给你限定的内存如果数据有重复，还是要靠数组来解决吧，

Answer 37

我按子节算，一个字节 8 个二进制位
他按 long 算 一个 long 占 4 个字节，共 32 个二进制位
不是一样吗？

Answer 38

我从oracle角度说啊。
用sqlldr 在nologing的模式下导入，比较快。
过程中根据规则设定50个分区，每个平均200W记录，按分区顺序分别排序导出

Answer 39

其实24楼和77楼的方法都可行,不用编程......
不过这分别是sysadmin和DBA的方法, 其它回帖都属于程序员的方法啦.....

Answer 40

没有生成1亿个数字，直接在内存中操作没有分段处理。define('MAX_NUM',1000);//这里架设已经知道最大的数字和数据总数
define('TOTALS_NUMS',20);
define('NUM_START',500);

bitsort(randNum(MAX_NUM,NUM_START,TOTALS_NUMS)); 
function bitsort($data){
$len = strlen(MAX_NUM);
$n = ceil((10^$len-1)/32);//位标识数组长度
$a = array_fill(1,$n,0);//位标识数组
echo '<br><br><br>';
for($i=0;$i<TOTALS_NUMS;++$i){
$a[intval($data[$i]/32)+1] |=1<<($data[$i]-1);//将标识位置为1
}
for($i=1;$i<=MAX_NUM;++$i){
for($j=0;$j<32;++$j){
$tmp = (1<<$j);
if(($a[$i]&$tmp)!=0){
echo (($i-1)*32+$j).'--<br>';
}
}
}
}
//随机生成start-n中的k个不重复的数
function randNum($p_n,$p_start,$p_k){
if($p_start>=$p_n)
return false;
for($i = $p_start;$i<=$p_n;++$i){
$a[$i] = $i;
}
for($j = 1;$j<=$p_k;++$j){
$r = mt_rand($p_start+$j,$p_n);
$b[] = $a[$r];
            $a[$r] = $a[$p_start+$j]; 
}
return $b;
}

Answer 41

昨晚做了一下测试，结果发现所有的算法都是不可忍受的
这就是理论与实践的差别
也是小规模数据和大规模数据的差别
所以软件工程学中一再强调边界数据的测试我用set_time_limit(0);
$fn = 'qq.txt';
echo microtime(true);
$a = range(0, 19999);
$b = range(0, 99999);
shuffle($a);
shuffle($b);$fp = fopen($fn, 'w');
for($i=0; $i<count($a); $i++)
  for($j=0; $j<count($b); $j++)
    fprintf($fp, "%d%05d%s", $a[$i], $b[$j], PHP_EOL);
fclose;
echo PHP_EOL, microtime(true);创建一个测试数据文件
结果耗时近 6 个小时得到一个 21G 的文件机器参数
Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz
3.09 GHz 1.98 GB 内存
操作系统 XP于是我决定放弃了，这种无聊的工作不是 php 可干的

Answer 42

老大耍人呢……这么频繁写入肯定要缓冲下啊我测试了10001*10001的规模，当然主要被6小时吓到了缓冲一下再写入，能提高4-5倍的性能。。写入耗时，跟fgets逐行读取相近，一个量级附测试代码，最后得到的文件是1,089,128,902 字节我也认可php不适合处理这种事$fn = 'qq.txt';
echo microtime(true);$a = range(0, 10000);
$b = range(0, 10000);
shuffle($a);
shuffle($b);$buffer = '';$fp = fopen($fn, 'a+');
for($i=0,$n=count($a); $i<$n; ++$i)
  for($j=0,$m=count($b); $j<$m; ++$j){
    $buffer .= sprintf("%d%05d%s", $a[$i], $b[$j], PHP_EOL);
if($j === $m-1){
fwrite($fp, $buffer);
$buffer = '';
}
  }
fclose($fp);
echo PHP_EOL, microtime(true);

Answer 43

我弄成1000次写入足足一亿个QQ号码。
847 MB (888,330,999 字节)但这么大的文件php怎么读。纠结中。
什么都关了。给最大内存依然读不了文件。

Answer 44

按字节存储set_time_limit(0);
$t = microtime(true);
$s = ' ';
for($i=0; $i<100000000; $i++) {
  $s{$i} = 'a';
}
echo microtime(true) - $t;
18.607635974884按位存储
set_time_limit(0);
$t = microtime(true);
$s = ' ';
for($i=0; $i<100000000; $i++) {
  $p = $i >> 3;
  for($m=1; $m<=128; $m <<= 1)
    $s{$p} = chr(ord($s{$p}) | $m);
}
echo microtime(true) - $t;
583.47053003311

Answer 45

如果是处理10位的数字，会有溢出现象，况且php不支持无符号整形。

Answer 46

面试的时候碰到这样的面试题直接说用冒泡，估计面试官脸会变臭的。
而且真要实现什么的就不要想着用php了吧，直接底层c了，php是高级语言，内存管理对于php来说是透明的，同样是一个integer变量，对c和对php来说意义完全不一样的，php的变量值存储就是一个c的结构体(Zval),因为php是弱类型，Zval内部的value又是一个结构体，所以Zval实际占的字节数可就多的多了

Answer 47

第一个问题，我觉得应该用分区存储的方式，取QQ号码后5位作为区内序号，后5位前的部分作为分区的区号，
例如QQ号码：12345678，可以放到123区的第45678的位置，这样遍历一遍QQ号码后，所有的QQ号码就排好序了。