关于黑白名单的实现

发布者：phpor 于关于黑白名单的实现留下评论

就在不经意的时候，我们可能会把一个大的黑白名单直接写在PHP的数组中，然后使用in_array判断指定的值是否在名单内，这样每次查一个值是否存在则都需要将所有的名单值构造成一个数组，然后遍历这个数组来查找，相当于我们要遍历两次名单而且其中一次是需要字符串比较的。

首先补充一点知识：PHP数组的构造是通过执行字节码来完成的，如arr.php：

  1. <?php
  2. $arr = array(
  3.         "a" => "AAA",
  4.         "a1" => array( "AAA","MMM"),
  5.         "b" => "BBB",
  6.         );

编译后生成的字节码如下：

  1. # php -dvld.active=1 d.php
  2. Finding entry points
  3. Branch analysis from position: 0
  4. Return found
  5. filename:       arr.php
  6. function name:  (null)
  7. number of ops:  7
  8. compiled vars:  !0 = $arr
  9. line     # *  op                           fetch          ext  return  operands
  10. ———————————————————————————
  11.    3     0  >   INIT_ARRAY                                       ~0      ‘AAA’, ‘a’
  12.    4     1      INIT_ARRAY                                       ~1      ‘AAA’
  13.          2      ADD_ARRAY_ELEMENT                                ~1      ‘MMM’
  14.          3      ADD_ARRAY_ELEMENT                                ~0      ~1, ‘a1’
  15.    5     4      ADD_ARRAY_ELEMENT                                ~0      ‘BBB’, ‘b’
  16.    6     5      ASSIGN                                                   !0, ~0
  17.    7     6    > RETURN                                                   1
  19. branch: #  0; line:     3-    7; sop:     0; eop:     6
  20. path #1: 0,

下面我们测试一下构造一个数组的效率，测试方法：
实验1. 在函数中构造一个大的数组，第一次执行之前做编译的工作，后续的执行则不需要编译，这样的话，我们调用函数1000次，则我们认为时间基本上是消耗在数组的构造上的；为了测试构造数组的时间，函数中最后return true， 而不是 return in_array($key, $arr);
实现2. 改造程序，将数组定义成static的，则数组只构造一次，其它和实验1相同
总结： (实验1的时间 – 实验2的时间) / 1000 则基本是构造一次数组需要的时间

测试代码test.php如下：

  1. <?php
  2. $s = microtime(1);
  3. for($i = 0 ; $i < 1000; $i++) {
  4.     check($i);
  5. }
  6. echo microtime(1) – $s;
  7. echo "\n";
  9. function check($key) {
  10. $arr = array(  // 一个很大的数组，1万个值的数组
  11. ‘value1’,
  12. ‘value2’,
  13. …
  14. );
  15. return true;
        
  16. }

$ php test.php
5.1018438339233

执行时间6s

给 $arr 添加static 关键字，代码如下：

  1. <?php
  2. $s = microtime(1);
  3. for($i = 0 ; $i < 1000; $i++) {
  4.     check($i);
  5. }
  6. echo microtime(1) – $s;
  7. echo "\n";
  9. function check($key) {
  10. static $arr = array(  // 一个很大的数组，1万个值的数组
  11. ‘value1’,
  12. ‘value2’,
  13. …
  14. );
  15. return true;
  16. }
        

执行时间：
#php test.php
0.0016131401062012

总结，根据实验的步骤中的公式来计算，可以知道初始化字节码执行时间约： 5s/1000 = 5ms ; 时间是比较长的

或许你会说如果将value当做key出现，则，可以使用 isset($arr[$key]) 而不是 in_array($key, $arr) 会更快些，应为in_array会遍历数组，而isset则是一个简单的hash就能判断。 但是问题是，如果将value当做key出现，则构造数组的时候，每个value都要做一个hash，这样构造数组的速度会更慢，如果每次构造能使用n次，则不失为一个好的办法，如果每次构造只使用一次，就有些不合算了。

下面对初始化1万个key的数组和1万个value的数组做一个比较：

1. 我们上面已近知道初始化1000次value的数组时间为5.1018438339233s
2. 下面我们通过如下函数测试初始化1000次key的数组的时间：

  1. function check2($key) {
  2.     $arr = array(
  3. "value1" => true,
  4. "value2" => true,
  5. …
  6. );
  7. return true;
  8. }

#php test.php
4.8184480667114

这里和我预想的不一样了，虽然每个key都要做hash，但是，初始化数组耗费的时间反而更少（虽然差别不大），稍后再研究一下初始化数组的内部逻辑

下面看一下如下代码的字节码：

 
  1. <?php
  2. $arr = array(
  3.     "a" => "AAA",
  4.     "a1" => array( "AAA","MMM"),
  5.     "b" => "BBB",
  6.     );
  7. $arr2 = array(1,2,3,4);
 
  1. $ php -dvld.active=1 d.php
  2. Finding entry points
  3. Branch analysis from position: 0
  4. Return found
  5. filename:      xxx/d.php
  6. function name:  (null)
  7. number of ops:  12
  8. compiled vars:  !0 = $arr, !1 = $arr2
  9. line     # *  op                           fetch          ext  return  operands
  10. ———————————————————————————
  11.    3     0  >   INIT_ARRAY                                       ~0      ‘AAA’, ‘a’
  12.    4     1      INIT_ARRAY                                       ~1      ‘AAA’
  13.          2      ADD_ARRAY_ELEMENT                                ~1      ‘MMM’
  14.          3      ADD_ARRAY_ELEMENT                                ~0      ~1, ‘a1’
  15.    5     4      ADD_ARRAY_ELEMENT                                ~0      ‘BBB’, ‘b’
  16.    6     5      ASSIGN                                                   !0, ~0
  17.    7     6      INIT_ARRAY                                       ~3      1
  18.          7      ADD_ARRAY_ELEMENT                                ~3      2
  19.          8      ADD_ARRAY_ELEMENT                                ~3      3
  20.          9      ADD_ARRAY_ELEMENT                                ~3      4
  21.         10      ASSIGN                                                   !1, ~3
  22.    8    11    > RETURN                                                   1
  24. branch: #  0; line:     3-    8; sop:     0; eop:    11
  25. path #1: 0, 

似乎没有太大差别。。。

留下评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。