作为程序员一定要保持良好的睡眠，才能好编程

  2. 首页
  3. Php

百万级数据查找保存问题结合位图法详细说明

发布时间：2018-11-02

面试中经常会遇到一些面试官问 ，百万级别的数据中，如何快速查找到这个数是否存在？

如何来进行存储？



下面我们来做一个测试


首先创建一个150万的数据

bit2.png


data.txt 这是一个字符串数据，共计 150 万个数据，大小共计 10.3M


data.txt

bit1.png


那么我们先看看这么大的数据范围内，如何判断文件是否在数组中：


我这里提供了两种方法，是我自己想想的，请大家看看:

1、把数组进行val排序  sort($data) 然后 key、value 交换位置 ，最后适用isset（）判断数据是否存在

2、采用位图法，首先将数组进行bitmap 位图化，然后进行查找


先来看看第一种方法：


1、排序 进行数据判断是否存在


A、读取文件数据 并以逗号进行分割

B、sort进行数据排序

C、isset() 是否存在


代码如下：

ini_set('memory_limit', '1000M');

$findval = 1000004;
printf("开始内存使用情况:%s M\n", bcdiv(memory_get_usage(), 1024 * 1024, 3));
$starttime = microtime(true);

$data = explode(',', file_get_contents('data.txt'));

sort($data);
// $bitmap = bitmap($data);

$data = array_flip($data);

if (isset($data[$findval])) {
    printf("findVal:%s 存在\n", $findval);
}

$howtime = bcsub(microtime(true), $starttime, 3);

printf("总共耗时:%s \n", $howtime);

printf("内存使用情况:%s M\n", bcdiv(memory_get_usage(), 1024 * 1024, 3));


使用内存排序法，内存占用情况，及结果

bit7.png

有时，还极易出一内存溢出等问题：这是不能容忍的，所以使用这种方法，请设置内存大小

bit6.png


结论：

这样的方法 总共耗时 2.127 秒 内存使用情况是 56M




2、位图法


位图法，我这里提供了三张图，运行时间差不多，程序使用内存出现了极大的不同，

我们先来看看第一种方法：


bit5.png



bit9.png


改良后的内存使用情况：

bit8.png


发生了什么？为什么会内存适用情况会发生这么大的变化？

看上面的红字



使用2M内存

$bitmap = bitmap(explode(',', file_get_contents('data.txt')));


使用 86M 内存

$data = explode(',', file_get_contents('data.txt'));
$bitmap = bitmap($data);


以上功能是一样的，这也许就是高级程序员与初级程序员的区别吧




printf("开始内存使用情况:%s M\n", bcdiv(memory_get_usage(), 1024 * 1024, 3));
$starttime = microtime(true);

// $bitmap = bitmap(explode(',', file_get_contents('data.txt')));
$data = explode(',', file_get_contents('data.txt'));
$bitmap = bitmap($data);
$howtime = bcsub(microtime(true), $starttime, 3);

printf("是否包含1000004:%s \n", checkExists($bitmap, 1000004) ? '是' : '否');

printf("总共耗时:%s \n", $howtime);

printf("内存使用情况:%s M\n", bcdiv(memory_get_usage(), 1024 * 1024, 3));




结论：

以上的这两种判断方法还是很快的，

我推荐使用位图法  时间是 1.3秒 内存适用2M多，这对于服务器来说是很快的


排序查找法  时间是 2.1秒  内存适用情况是 56M多  ，足足慢了快1秒了   内存使用 是位图法的 28倍  ，由此可见 位图法  对于大数据存储与查找速度还是很快的。


总比 foreach 循环快多了吧！呵呵呵



保存成位图来说：





一个是10M多 一个是 600多K  还不到1M 

试问： 读取哪个文件快?



更多>> Php