阅读 181

PHP实现文本快速查找:二分查找法

PHP实现文本快速查找:二分查找法

编程之家收集整理的这篇文章主要介绍了PHP实现文本快速查找:二分查找法,编程之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。


搜索热词


起因

先说说事情的起因,最近在分析数据时经常遇到一种场景,代码需要频繁的读某一张数据库的表,比如根据地区ID获取地区名称、根据网站分类ID获取分类名称、根据关键词ID获取关键词等。虽然以上需求都可以在原始建表时,通过冗余数据来解决。但仍有部分业务存的只是关联表的ID,数据分析时需要频繁的查表。

所读的表存在共同的特点

@H_403_6@

  • 数据几乎不会变更

  • 数据量适中,从一万到100多万,如果全加载到内存也不太合适。

  • 纠结的地方

    在做数据分析时,需要十分频繁的读这些表,每秒有可能需要读上万次。其实内部的数据库集群完全可以胜任,但会对线上业务稍有影响。(你懂得,小公司不可能为离线分析做一套完整的数据存储服务。大部分数据分析还要借助线上的数据集群)

    优化方案的思考

    有没有一种方式可以不增加线上的压力,同时提供更高效的查询方式?想过redis,但最终选择用文本存储。因为数据分析是一个独立的需求,不希望与现有的redis集群或者其它存储服务有交集。还有一个原因是每次分析的中间结果,对下一次分析并没有很大的实质作用,并不需要把结果持久存储,而且占的内存也会较多。最终使用文本存储,然后用二分来查找。特点,1,存储非常快,虽然redis等nosql服务虽然已经非常快,但仍无法与文本存储相提并论;2,查找的时候使用二分查找,百万条记录查询也可在0.1ms内完成(使用线上的普通硬盘,如果是ssd盘会更快)。

    实现步骤

    将数据库中需要的字段导出到文本        方法:使用MysqL的PHPmyadmin工具,执行sql语句查出主建id和相应字段  如以上的关键词表: select kid, keyword from keyword  然后使用PHPmyadmin的导出工具,可以快速把结果导出到文本中  操作截图:



    导出数据流程1




    导出数据流程2

    • 将导出的文本(已经按id进行过排序)转换格式重新存储

    • 程序读取转换后的格式

    文本存储格式

    说明 :需求中,文本每行有两列,第一列是主建ID(数字),第二列为文本。整个文本已经按第一列有序排列,两列之间用tab键分隔。
    之前有看过ip.dat的存储,本次仿照其存储格式:将文本中的内容每行转换为固定长度后,存储到新的文件。搜索时,使用文件操作函数fopen,fseek,fgets等函数按字节读取内容,并以二分查找法快速定位需要的内容。

    代码实现部分

    • 通用类,类似需求只需要提供符合标准的文本(每行两列,第一列为查找的ID,第二列为文本。同时文本已经按第一列有序排序)

    • 生成以上所提到的存储格式

    • 提供根据id查询接口

    代码片断

    • 重新生成新的存储格式


      1.  //读源文件,写入到新的索引文件

      2.   $readfd = fopen($this->filename, 'rb');

      3.   $writefd = fopen($this->formatFile.'_tmp', 'wb+');

      4.   if ($readfd === false || $writefd === false) {

      5.       return false;

      6.   }

      7.   echo "\n start reformat file $this->filename ..";

      8.   while (!feof($readfd)) {

      9.       $line = fgets($readfd, 8192);

      10.       fwrite($writefd, pack("a".$this->maxLength, $line));

      11.   }

      12.   echo "\n reformat ok\n";

      13.   fclose($readfd);

      14.   fclose($writefd);

      15.   rename($this->formatFile.'_tmp', $this->formatFile);

    • 二分查找的代码片断


      整个类库代码一共91行,具体可查看github的demo代码

      1.  /**

      2.   * 在索引文件中进行二分查找

      3.   * @param  int $id    进行二分查找的id

      4.   * @return [type]     [description]

      5.   */

      6.   public function search($key)

      7.   {

      8.       $filesize = filesize($this->formatFile);

      9.       $fd = fopen($this->formatFile, "rb");

      10.       $left = 0; //行号

      11.       $right = ($filesize / $this->maxLength) - 1; 

      12.       while ($left <= $right) {

      13.           $middle = intval(($right + $left)/2);

      14.           fseek($fd, ($middle) * $this->maxLength);

      15.           $info = unpack("a*", fread($fd, $this->maxLength))['1'];

      16.           $lineinfo = explode("\t", $info, 2);

      17.           if ($lineinfo['0'] > $key) {

      18.               $right = $middle - 1;

      19.           } elseif ($lineinfo['0'] < $key) {

      20.               $left = $middle + 1;

      21.           } else {

      22.               return $lineinfo['1'];

      23.           }

      24.       }

      25.       return false;

      26.   }

    运行截图



    运行截图

    以上拿100万的关键词进行测试,根据关键词id快速查找关键词,平均速度可以达到0.1毫秒。

    总结

    以上是编程之家为你收集整理的PHP实现文本快速查找:二分查找法全部内容,希望文章能够帮你解决PHP实现文本快速查找:二分查找法所遇到的程序开发问题。

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。


    本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。

    如您喜欢寻找一群志同道合、互帮互助的学习伙伴,可以点击下方链接加入:
    编程之家官方1群:1065694478(已满)
    编程之家官方2群:163560250(已满)
    编程之家官方3群:312128206(已满)
    编程之家官方4群:230427597

PHP二分查找法实现实现实现实现快速查找文本文本文本

  • 上一篇:
    海外技术译文:10例糟糕的PHP代码下一篇:
    PHP 取 Windows 启动时间及计算已启

相关文章



猜你在找的PHP相关文章

PHP中的公共静态方法

PHP中的公共静态方法,如: public static function getParam($input){.......}使用static,表明该公共方法是一个公共的静态方法,可以不用实例化这个类,直接className::functionName()来进行调用;同时,静态方法都是存在缓存里面,运行速度快;而非静态公共方法,需要用new实例化之后,才能使用$class->funct

php中的echo print print_r的区别

php中的echo   print  print_r的区别    echo----可以输出一个或多个字符串;没有返回值;用法 echo  或者  echo()    print-----只允许输出一个字符串;不能输出对象或者数组; 返回值总为1;        用法print   或者print()    print-r------可以输出String  Float  Int  Arr


php中的cookie和session的用法与区别

php中的cookie和session的用法与区别区别:        session信息存放在sever端,但session id存放在ckient cookie里面        cookie是完全存放在client端的1、cookie的配置与应用     A、创建cookie:setcookie(string name, string value, int expire,

在php文件里面插入文件html

有的时候我们得在php文件里面引入html代码,或者在php文件的某个位置引入文件html,下面就介绍一下实现的方法。下面是recharge.php的代码:<?php require_once "../../config.php";?> 充值 var serviceChargePoint = ;


往数据库插入中文的时候,显示乱码

用php往数据库插入中文的时候,显示乱码的解决方法,就是在建立与数据库的连接之后,加上这一句话:mysqli_query($this->link,"set names 'utf8'");在php中,建立与数据库的连接的方法如下: /** * 连接数据库 */ private function conn() { //

php中的require require_once include incllude_once的区别

php中的require   require_once   include   incllude_once的区别1、include、require执行包含文件,不对包含文件进行判断,可能会出现重复包含情况;     include_once、require_once在包含文件的时候,会先判断文件是否已经包含过,如果包含,则不再包含。这样的方式可以节省资        源,避免重复定义的错误


PHP中的date_default_timezone_set ()

PHP中的函数date_default_timezone_set()的作用是:设定脚本中所有日期时间函数的默认时区格式:bool date_default_timezone_set ( string $timezone_identifier )输入值:$timezone_identifier失去标识符返回值:如果参数$timezone_identifier无效返回false,有效返回t

PHP里面的函数mkdir(),is_dir()

1、PHP里面的函数mkdir()的作用是:新建目录bool mkdir ( string $pathname [, int $mode = 0777 [, bool $recursive = false [, resource $context ]]] )参数:$pathname---目录的路径          $mode--------默认的mode是0777,意



分类导航

PHPJavaJava SEPythonNumPyC#C&C++RubyVBasp.NetGoPerlnettygRPCDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole


文章分类
后端
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐