面试题中经常会遇到有百万级数量数据的两个文件 A、B 文件，
https://www.cnblogs.com/bymo/p/7571320.html
https://www.cnblogs.com/lxwphp/p/10020074.html
问题1、如何能够快速的找到B文件中的值在A文件中不存在呢？
方法1、采用redis中bitmap类型：
[root@localhost src]# ./redis-cli -v
redis-cli 5.0.4
为了生成bigfile.txt 特意写了一个sh脚本
#!/bin/bash root=`pwd` file=$root"/bigfile.txt" for((i=10000;i<1000000;i++)) do echo $i >> $file done
场景：
[root@localhost bigfile]# cat bigfile.txt |wc -l
990000
解决方案：
1、将文件A中所有的数据，每一行通过crc32 计算后，存入redis bitmap中
99万的数据，存储使用时间 是11秒 内存占用情况是 64bte
2、打开B文件，通过 循环每一行 值经过计算 crc32 后，使用gitbit 这样的方法去判断是否存在
如果不存在，存入$data 数组中。
read.php
function echo_memory_usage($mem_usage) {
// $mem_usage = memory_get_usage(true);
if ($mem_usage < 1024)
echo $mem_usage." bytes";
elseif ($mem_usage < 1048576)
echo round($mem_usage/1024,2)." kilobytes";
else
echo round($mem_usage/1048576,2)." megabytes";
echo "<br/>";
}
$startime=microtime(true);
$starmemory=memory_get_usage();
$redis=new redis();
if(!$redis){
exit("redis init error");
}
$flag=$redis->connect("127.0.0.1",6379);
if(!$flag){
exit('redis connect error ');
}
$file="bigfile.txt";
$handle=fopen($file,"r");
$file="bigfile.txt";
$handle=fopen($file,"r");
while(!feof($handle)){
$content=fgets($handle);
if(strlen($content)==0) continue;
$redis->setbit('bigfile',abs(crc32($content)),1);
}
fclose($handle);
$redis->close();
$endtime=microtime(true);
$endmemory=memory_get_usage();
echo "内存:".echo_memory_usage($endmemory-$starmemory)."\n";
echo "时间:".($endtime-$startime)."\n";chongfu.php
function echo_memory_usage($mem_usage) {
// $mem_usage = memory_get_usage(true);
if ($mem_usage < 1024)
echo $mem_usage." bytes";
elseif ($mem_usage < 1048576)
echo round($mem_usage/1024,2)." kilobytes";
else
echo round($mem_usage/1048576,2)." megabytes";
echo "<br/>";
}
$startime=microtime(true);
$starmemory=memory_get_usage();
$redis=new redis();
if(!$redis){
exit("redis init error");
}
$flag=$redis->connect("127.0.0.1",6379);
if(!$flag){
exit('redis connect error ');
}
$file="two.txt";
$handle=fopen($file,"r");
$data=[];
while(!feof($handle)){
$content=fgets($handle);
if(strlen($content)==0) continue;
if(!$redis->getbit('bigfile',abs(crc32($content)))){
$data[]=$content;
}
//$redis->setbit('bigfile',abs(crc32($content)),1);
}
fclose($handle);
$redis->close();
$endtime=microtime(true);
$endmemory=memory_get_usage();
echo "内存:".echo_memory_usage($endmemory-$starmemory)."\n";
echo "时间:".($endtime-$startime)."\n";
var_dump($data);程序运行
1、通过程序运行php read.php 查看插入redis的时间
文件原始大小：
通过程序代码，读取6.6M的文件，使用了296bytes 的大小。
2、bigfile.txt 是 99万条数据
3、存入到redis的结果是：
4、找到B文件中的值不存在A文件的结果：
我们看到内存使用了 640 bytes 时间是 42.838秒
==================把99万的数据存储在redis bitmap中，占用的内存是多少？========================
原始内存
127.0.0.1:6379> info memory # Memory used_memory:645576 used_memory_human:630.45K used_memory_rss:1794048 used_memory_rss_human:1.71M used_memory_peak:275310680 used_memory_peak_human:262.56M total_system_memory:1054937088 total_system_memory_human:1006.07M used_memory_lua:25600 used_memory_lua_human:25.00K maxmemory:3221225472 maxmemory_human:3.00G maxmemory_policy:noeviction mem_fragmentation_ratio:2.78 mem_allocator:jemalloc-4.0.3
从1万 到 100万中 这99万的数字 经过crc32 计算后 最大的数是：2147481675
根据bitmap公式大概计算得：
2147481675/8/1024/1024
占用内存大小：255.99976480007 M
127.0.0.1:6379> info memory # Memory used_memory:269081256 used_memory_human:256.62M used_memory_rss:270270464 used_memory_rss_human:257.75M used_memory_peak:275310680 used_memory_peak_human:262.56M total_system_memory:1054937088 total_system_memory_human:1006.07M used_memory_lua:25600 used_memory_lua_human:25.00K maxmemory:3221225472 maxmemory_human:3.00G maxmemory_policy:noeviction mem_fragmentation_ratio:1.00 mem_allocator:jemalloc-4.0.3
可以看到，现在使用的内存是 256M。这是不是有些浪费资源，我们之前说过 ，只要是超过百万级的用户，可以使用set集合存储，
那么放在集合中，会有多少内存占用？
127.0.0.1:6379> info memory # Memory used_memory:52323024 used_memory_human:49.90M used_memory_rss:54525952 used_memory_rss_human:52.00M used_memory_peak:275310680 used_memory_peak_human:262.56M total_system_memory:1054937088 total_system_memory_human:1006.07M used_memory_lua:25600 used_memory_lua_human:25.00K maxmemory:3221225472 maxmemory_human:3.00G maxmemory_policy:noeviction mem_fragmentation_ratio:1.04 mem_allocator:jemalloc-4.0.3
存储在bitmap中的占用空间是256M 存储在集合中set 占用空间 49.9M . 可见省去内存 205M
足见，数据类型选择的重要性
存储在结合中，效率对比
排查重复数据的方法：
redis 集合
1、集合中不能存在重复的数据
2、集合中有一个方法 sismember 检测集合中是否包含同样的数据，时间复杂度 o(1)
3、sadd 方法 添加数据到集合 时间复杂度 o(n)
==================把99万的数据存储在redis bitmap中，占用的内存是多少？========================
方法2、采用redis的布隆过滤器
布隆过滤器，在redis4.0以后，才可以使用。
布隆过滤器存在一定的误判率，存储的数值越大则误判的情况 会越严重、误判率不超过1%