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

东方客主 等级 1020 0 0

起因

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

所读的表存在共同的特点

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

纠结的地方

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

优化方案的思考

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

实现步骤

  • 将数据库中需要的字段导出到文本

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

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

导出数据流程1


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

导出数据流程2

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

文本存储格式

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

代码实现部分

  • 通用类,类似需求只需要提供符合标准的文本(每行两列,第一列为查找的ID,第二列为文本。同时文本已经按第一列有序排序)
  • 生成以上所提到的存储格式
  • 提供根据id查询接口

代码片断

  • 重新生成新的存储格式

     //读源文件,写入到新的索引文件
      $readfd = fopen($this->filename, 'rb');
      $writefd = fopen($this->formatFile.'_tmp', 'wb+');
      if ($readfd === false || $writefd === false) {
          return false;
      }
      echo "\n start reformat file $this->filename ..";
      while (!feof($readfd)) {
          $line = fgets($readfd, 8192);
          fwrite($writefd, pack("a".$this->maxLength, $line));
      }
      echo "\n reformat ok\n";
      fclose($readfd);
      fclose($writefd);
      rename($this->formatFile.'_tmp', $this->formatFile); 
  • 二分查找的代码片断

     /**
      * 在索引文件中进行二分查找
      * @param  int $id    进行二分查找的id
      * @return [type]     [description]
      */
      public function search($key)
      {
          $filesize = filesize($this->formatFile);
          $fd = fopen($this->formatFile, "rb");
          $left = 0; //行号
          $right = ($filesize / $this->maxLength) - 1; 
          while ($left <= $right) {
              $middle = intval(($right + $left)/2);
              fseek($fd, ($middle) * $this->maxLength);
              $info = unpack("a*", fread($fd, $this->maxLength))['1'];
              $lineinfo = explode("\t", $info, 2);
              if ($lineinfo['0'] > $key) {
                  $right = $middle - 1;
              } elseif ($lineinfo['0'] < $key) {
                  $left = $middle + 1;
              } else {
                  return $lineinfo['1'];
              }
          }
          return false;
      } 
  • 整个类库代码一共91行,具体可查看github的demo代码

运行截图

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

运行截图

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

收藏
评论区

相关推荐

Java和PHP在Web开发方面的比较
比较PHP和JSP这两个Web开发技术,在目前的情况是其实是比较PHP和Java的Web开发。以下是我就几个主要方面进行的比较: **一、 语言比较**     PHP是解释执行的服务器脚本语言,首先php有简单容易上手的特点。语法和c语言比较象,所以学过c语言的程序员可以很快的熟悉php的开发。而java需要先学好java的语法和熟悉一些核心的
PHP FFI详解——一种全新的PHP扩展方法
![](https://www.sixstaredu.com/files/default/2020/03-30/1659528b8fa2524354.jpg) 随着PHP7.4而来的有一个我认为非常有用的一个扩展:PHP FFI(Foreign Function interface),引用一段PHP FFI RFC中的一段描述: > 对于PHP,FFI提
PHP如何快速读取大文件
PHP如何快速读取大文件 在PHP中,对于文件的读取时,最快捷的方式莫过于使用一些诸如file、file\_get\_contents之类的函数,简简单单的几行代码就能 很漂亮的完成我们所需要的功能。但当所操作的文件是一个比较大的文件时,这些函数可能就显的力不从心, 下面将从一个需求入手来说明对于读取大文件时,常用的操作方法。 需求需求 有一个
PHP底层的运行机制与原理
PHP是一种适用于web开发的动态语言。具体点说,就是一个用C语言实现包含大量**组件模块**的软件框架。是一个强大的UI框架。 简言之;PHP动态语言执行过程:拿到一段代码后,经过词法解析、语法解析等阶段后,源程序会被翻译成一个个指令(opcodes),然后ZEND虚拟机顺次执行这些指令完成操作。PHP本身是用C实现的,因此最终调用的也是C的函数,实际上
PHP教程
PHP教程-php读取输出其他文件方法 人们往往想到出现一些关于访问很缓慢,有白页现象,要是测试环境你也就重启一下PHP的php-fpm进程发现又好了,隔一段时间又出类似的问题,本期我们邀请到了 兄弟连PHP教育[www.lampbrother.net](https://www.oschina.net/action/GoToLink?url=http%3A
PHP的性能优化方法总结
![](https://six.club/image/show/attachments-2020-10-rwbBlasg5f9b6ed2994d9.png) 什么情况之下,会遇到PHP性能问题? 1:PHP语法使用不恰当。 2:使用PHP语言做了它不擅长的事情。 3:使用PHP语言连接的服务不给力。 4:PHP自身的短板(PHP自身做不了的事情)。
Ubuntu 下 Apache2 和 PHP 服务器环境配置
Ubuntu 下 Apache2 和 PHP 服务器环境配置 ============================== 1、简介 ---- 本文主要是 Ubuntu 下 Apache2 和 PHP 服务器环境配置方法,同样适用于 Debian 系统:Ubuntu 20.0.4 注意:文中运行的命令基本上需要管理员权限 2、安装 Apache
LNMP架构之php
本文索引: * php-fpm的进程pool设置 * php-fpm慢执行日志 * open\_basedir参数设置 * php-fpm进程管理 * * * ### php-fpm的pool php-fpm.conf可以设置多个pool,在其中一个pool资源耗尽,会导致其他站点无法访问资源,报502错误。有必要把站点进行分离,分别
Netbeans 8.2将支持PHP 7
首先,将PHP项目的PHP版本设置为PHP 7.0。 ![](http://static.oschina.net/uploads/img/201607/04202546_9GSt.png) PHP 7其中一项新特性是返回类型声明,即PHP的函数和方法可以声明指定类型的返回值: ![](http://static.oschina.net/uploads/
PHP fastcgi_finish_request 方法
https://www.jianshu.com/p/bf55c803b70b http://www.laruence.com/2011/04/13/1991.html 本文介绍,PHP运行在FastCGI模式时,FPM提供的方法:fastcgi\_finish\_request。 在说这个方法之前,我们先了解PHP有哪些常用的运行模式? > PHP运
PHPcpp 变量和类型
    用PHPCPP来开发PHP扩展是非常容易的,最主要的就是变量类型和PHP中的变量类型一毛一样,最重要的是写法也是一毛一样。     在PHP中,变量默认是没有类型的,我们赋给他整数,他就是整形,赋给他字符串他就是string,也就是说PHP中的变量类型是随着值来定义的。PHPCPP在这里也是做了很大的优化,实现了类型随值的类型来定义。 P
PHP代码静态分析工具PHPStan
<blockquote>最近发现自己写的PHP代码运行结果总跟自己预想的不一样,排查时发现大多是语法错误,在运行之前错误已经种下。可能是自己粗心大意,或者说<code>php -l</code>检测太简单,不过的确是有一些语法错误埋藏得太深(毕竟PHP是动态语言),那么有没有办法,在代码代码正式运行之前,把语法错误全找出来呢?</blockquote> <p
PHP实现Byte转换为KB、MB、GB、TB的方法
本文实例讲述了PHP实现字节数Byte转换为KB、MB、GB、TB的方法。分享给大家,具体如下: <?php 运行结果如下图: ![](https://oscimg.oschina.net/oscnet/82e10fe140d2962bc8ea3d3ce425117736a.png) 本文分享自微信公众号 - PM吃瓜(wu\_lia
PHP自动测试框架Top 10
对于很多PHP开发新手来说,测试自己编写的代码是一个非常棘手的问题。如果出现问题,他们将不知道下一步该怎么做。花费很长的时间调试PHP代码是一个非常不明智的选择,最好的方法就是在编写应用程序代码之前就写好测试代码。自动化测试可以极大的缓解并改善PHP开发的工作流程,它能帮助开发人员管理大部分任务,使其更专注于开发逻辑的测试代码。本文将为大家介绍PHP自动测试
PHP配置优化:php
> PHP-FPM是一个PHP FastCGI管理器,php-fpm.conf配置文件用于控制PHP-FPM管理进程的相关参数,比如工作子进程的数量、运行权限、监听端口、慢请求等等。 我们在编译安装PHP的时,在./configure的时候带 –enable-fpm参数即可开启PHP-FPM。PHP-FPM配置文件为 php-fpm.conf,其语法类似 p