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

东方客主 等级 491 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毫秒。

收藏
评论区

相关推荐

php指的是什么?
PHP(全称:Hypertext Preprocessor,即“PHP:超文本预处理器”)是一种开源的通用计算机脚本语言,尤其适用于网络开发并可嵌入H
php怎么做页面静态化
页面静态化的好处 根据不同情况,有些需要生成静态页,有些实现伪静态即可,根据实际需求进行抉择。而静态化的好处,总结下来有以下几点: ● 提高访问速
PHP对时间轮算法的简单实现
什么是时间轮算法? 把任务放到它需要被执行的时刻,然后等待时针转到这个时刻,取出该时刻的任务,执行并将任务从该时刻删除(消费)。 解决了什么问题? 以商品为例,如何实现商品的过保质期自动失效? 1:我们可以每分钟执行一个定时任务,扫描全表过期时间大于当前时间的商品,进行失效处理。(当然,也可以将该任务细化成秒级的) 2:商品添加时,将该商品的
PHP程序员必须会的 45 个PHP 面试题(第二部分)
Q20: require\_once 和 require 在什么场景下使用? Topic: PHP Difficulty: ⭐⭐⭐ require\_once() 作用与 require() 的作用是一样的,都是引用或包含外部的一个 php 文件,require\_once() 引入文件时会检查文件是否已包含,如果已包含,不再包含 (requir
PHP程序员必须会的 45 个PHP 面试题(第一部分)
Q1: 和 之间有什么区别? 话题: PHP 困难: ⭐ 如果是两个不同的类型,运算符 则在两个不同的类型之间进行强制转换 操作符执行’_类型安全比较_‘ 这意味着只有当两个操作数具有相同的类型和相同的值时,它才会返回 TRUE。 1 1: true 1 1: true 1 "1
使用PHP生成网站Sitemap,Laravel风格
PHP生成网站Sitemap,包含默认、分类、文章、标签、profile等 <?php namespace AppLibs; use AppS
nginx安全配置
安全是一个重要的问题,必须引起注意。 1. nginx介绍 nginx本身不能处理PHP(http://www.ttlsa.com/php/ "php"),它只是个web服务器,当接收到请求后,如果是php请求,则发给php解释器处理,并把结果返回给客户端。nginx一般是把请求发fastcgi管理进程处理,fastcgi管理进程选择cgi子
为什么要从php 加入到 go 的潮流
为何我要说加入go开发是一种潮流,尤其是对于php开发人员,我加入了很多go的开发群或者爱好群,发现大部分人都是从php过来的,原本google开发golang是想让更多的c/c人员来使用。 PHP 语言作为当今最热门的网站程序开发语言,它也是我多年来一直使用的语言,它具有成本低、速度快、可移植性好、 内置丰富的函数库等优点,因此被越来越多的企业应用于网站
php操作redis哨兵模式,主从切换后自动获取master
本文将介绍如何使用PHP来连接redis哨兵模式。哨兵模式:大概的原理就是监听redis主库心跳包,如果心跳断开,则枚举一个从库推举成为新的主库,防止redis宕机不能使用。为了增强redis的性能,防止其挂掉,引用redis哨兵监控redis集群是个不错的选择。下面三步简单记录php连接redis哨兵。 第一步、获取哨兵模式连接redis句柄对象/
PHP 微信公众号消息加解密
公众号配置根据提示设置即可:【图中信息均为无意义数据,仅供参考。注意服务器地址需可接收 GET/POST 两种请求】 AESKey 直接点一下随机生成即可,Token 可以生成一个 UUID 再把 UUID 进行 MD5 一次即可。 接收关注事件消息示例 请求参数校验这一步根据项目情况,可供参考:(Lumen 框架)php$valida
macOS 下通过 pecl 命令安装 PHP 扩展 Solr 方法
还是有点小麻烦的,根据日志一步步弄出来编译成功,辛苦辛苦...需要安装的东西有:1. curl2. libxml23. openssl4. libidn25. brotli以上 5 个组件都可以通过 brew install 命令安装确认安装完毕后 先执行 下方命令:bashexport LDFLAGS"L/usr/local/opt
PHP实现文本快速查找 - 二分查找法
起因先说说事情的起因,最近在分析数据时经常遇到一种场景,代码需要频繁的读某一张数据库的表,比如根据地区ID获取地区名称、根据网站分类ID获取分类名称、根据关键词ID获取关键词等。虽然以上需求都可以在原始建表时,通过冗余数据来解决。但仍有部分业务存的只是关联表的ID,数据分析时需要频繁的查表。所读的表存在共同的特点 数据几乎不会变更 数据量适中,从一万
网络渗透测试实验三
写在前面 实验终于开始有意思起来了,Attack! 网络渗透测试实验三:XSS 和 SQL 注入 实验目的+ 了解什么是XSS+ 了解XSS攻击实施,理解防御XSS攻击的方法+ 了解SQL注入的基本原理+ 掌握PHP脚本访问MySQL数据库的基本方法+ 掌握程序设计中避免出现SQL注入漏洞的基本方法+ 掌握网站配置。 系统环境+ Kali Linux2、Wi
dubbo网关演进之路
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 背景随着公司业务的飞速发展,基于php的模块化架构难以支持未来业务的发展: php模块化架远远落后于行业主流架构(微服务–云原生),而php生态的服务治理开源组件匮乏,研发投入过大 杭州php人才匮乏,导致新鲜血液招聘困难 基于php的多进程架构难以支撑
为什么说Python是最伟大的语言?看图就知道了!
测试一下你的分析能力,直接上图,自己判断一下为什么Python是最好的语言?有图有真相 Java之父 James Goshling C++之父 Bjarne Stroustrup PHP之父 Rasmus Lerdorf Python之父 Guido van Rossum看到他们的亮点了吗? Java和C++是锃亮的电灯泡 PHP是一