PHP内部如何实现打乱字符串顺序函数str_shuffle

12 Feb 2019 Category: php

2019年春节已过,今天是上班第一天,还得翻一翻之前没有看完的PHP源码。

今天聊的是字符串顺序打乱函数str_shuffle。这个函数本身使用频率并不高。但是,其内部实现还是非常有趣的。

查看更多

简单聊聊字符串的翻转问题

29 Jan 2019 Category: php

字符串的翻转在日常开发使用程度比较少,但是面试过程中却是常有的。最近看php 源码中strrev,因此写一篇文记录对字符串翻转问题的一些学习。

查看更多

用php实现大小写转换功能

29 Jan 2019 Category: php

字符串的大小写转换功能在日常中经常使用。那么如何实现一个简单的大小写转换功能呢?

在php中,最终使用的是c语言的toupper,tolower函数将字符进行大小写转换。因此需要定义一个字符大小写转换的函数。

//字符转大写
protected function toupper($c){
 $ord = ord($c);
 return $ord>=97 && $ord<=122 ?chr($ord-32):$c;
}
//字符转小写
protected function tolower($c){
 $ord = ord($c);
 return $ord>=65 && $ord<=90 ?chr($ord+32):$c;
}

字符的大小写转换就是进行ascii码的转换。A-Z的ASCII码在65-90之间。a-z的ASCII码在97-122之间。对于不在转换区间的字符,应该原样返回

php中字符串大小写转换有下面几个函数strtolower,strtoupper, lcfirst,ucfirst,ucwords,lcfirst, 这几个函数都是成对的,因此仅以大写转小写为例说明如何实现这几个函数

strtoupper实现字符串从大写转小写。无非是遍历字符串的每个字符,将大写字符转换成小写。

public function strtolower($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $len = strlen($str);
 for($i=0;$i<$len;$i++){
  $str[$i] = $this->tolower($str[$i]);
 }
 return $str;
}

php字符串可以像数组一样用下标获取每个字符。因此对字符串每个字符遍历,转换成小写字符即可

lcfirst实现首字母大写的功能,因此比strtolower还要简单

public function ucfirst($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $str[0] = $this->toupper($str[0]);
 return $str;
}

lcwords 实现单词首字母转小写。说单词,其实是空格后面第一个字符。因此只需要在遍历到空格字符后面第一个非空字符串转换成小写即可。

public function lcwords($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $splitchar = [' ',"\n","\r","\f","\v"];
 $len = strlen($str);
 for($i=0;$i<$len;$i++){
  if(in_array($str[$i], $splitchar))
  {
   $i++;
   if($i>=$len)
   {
    break;
   }
   $str[$i] = $this->tolower($str[$i]);
  }
 }
 return $str;
}

主要要小心越界的问题。如果最后一个字符串是空字符。

至于为什么单词分割字符是代码中的那几项,主要是php源码就是根据那几项实现的。php源码中ucwords实现方式如下:

PHP_FUNCTION(ucwords)
{
 zend_string *str;
 char *delims = " \t\r\n\f\v";
 register char *r, *r_end;
 size_t delims_len = 6;
 char mask[256];

 ZEND_PARSE_PARAMETERS_START(1, 2)
  Z_PARAM_STR(str)
  Z_PARAM_OPTIONAL
  Z_PARAM_STRING(delims, delims_len)
 ZEND_PARSE_PARAMETERS_END();

 if (!ZSTR_LEN(str)) {
  RETURN_EMPTY_STRING();
 }
 php_charmask((unsigned char *)delims, delims_len, mask);

 ZVAL_STRINGL(return_value, ZSTR_VAL(str), ZSTR_LEN(str));
 r = Z_STRVAL_P(return_value);

 *r = toupper((unsigned char) *r);
 for (r_end = r + Z_STRLEN_P(return_value) - 1; r < r_end; ) {
  if (mask[(unsigned char)*r++]) {
   *r = toupper((unsigned char) *r);
  }
 }
}

将分割的字符串放入一个mask中,在遍历字符串的过程中判断是否是mask的字符。如果是则对后面一位字符进行大写转换操作。

代码地址https://github.com/froyot/froyot.github.io/blob/master/code/php_stringchange.php

查看更多

php 中的similar_text如何实现的

25 Jan 2019 Category: php

PHP字符串处理函数中有一个similar_text用于计算两个字符串的相似程度。今天来看看similar_text如何实现的。

similar_text — 计算两个字符串的相似度,返回两个字符串中匹配字符的数目

两个字符串的相似程度计算依据 Programming Classics: Implementing the World’s Best Algorithms by Oliver (ISBN 0-131-00413-1) 的描述进行。注意该实现没有使用 Oliver 虚拟码中的堆栈,但是却进行了递归调用,这个做法可能会导致整个过程变慢或变快。也请注意,该算法的复杂度是 O(N**3),N 是最长字符串的长度。

上面的文档说明还是很绕。

源码中similar_text函数在内部调用了php_similar_char进行处理。ac是参数的个数。函数返回的是两个字符串中匹配字符的数目。如果想要获取相似的百分比,则需要传递一个引用参数获取。


sim = php_similar_char(ZSTR_VAL(t1), ZSTR_LEN(t1), ZSTR_VAL(t2), ZSTR_LEN(t2));

if (ac > 2) {
  Z_DVAL_P(percent) = sim * 200.0 / (ZSTR_LEN(t1) + ZSTR_LEN(t2));
}
RETURN_LONG(sim);

在php_similar_char中有调用了php_similar_str,在看php_similar_char前,先看看php_similar_str的功能。


static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  size_t l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {
    for (q = (char *) txt2; q < end2; q++) {
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
      if (l > *max) {
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}

php_similar_str内部跑了三个嵌套的循环,这就难怪文档中描述的,时间复杂度是O(N**3)。在最里面的循环中,检查两个字符串连续一致的个数。最里层循环结束之后,判断是否大于已经获取到的最大相似数目。并记录最大相似情况下两个字符串相似处开始的位置。

在php_similar_char,通过php_similar_str拿到最大相似数目,以及两个字符串起始位置。在底下,则把text1,text2分为最大相似字符串前的字符,最大相似字符串,最大相似字符串后面字符串三个部分,分别在递归调用计算两个字符串中相似字符串前后两个部分对应的相似长度。直到字符串长度为0.

static size_t php_similar_char(const char *txt1, size_t len1, const char *txt2, size_t len2)
{
  size_t sum;
  size_t pos1 = 0, pos2 = 0, max;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
  if ((sum = max)) {
    if (pos1 && pos2) {
      sum += php_similar_char(txt1, pos1,
                  txt2, pos2);
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
                  txt2 + pos2 + max, len2 - pos2 - max);
    }
  }

  return sum;
}

看到这,similar_text只能大概计算相似程度。其中有几个小问题。

1.两个空字符串的相似度是0。 2.假设两个字符串’abcdefg’,’qabdefgabc’,直观上这两个字符串中“匹配字符”的数目有a,b,c,d,e,f,g 但是当你执行similar_text拿到的结果确是6。

看看整个执行过程:

a、获取最常匹配串的长度’defg’,长度4,pos1=3,pos2=3 b、获取abc,qab相似长度度2 c、获取空字符串和abc相似度0

所以相似字符串长度为6.

3.顺序敏感 顺序敏感其实也是由于拆分的问题导致的。比如字符串”PHP IS GREAT” 和字符串”WITH MYSQL” 不同的顺序得到的结果分别是2,3。

查看更多

substr_replace如何替换多个字符串不同位置不同长度的子串

22 Jan 2019 Category: php

都知道substr_replace可以替换指定位置的子串。比如substr_repace("Hello Test",'xxxx',1,4)替换成Hxxxx Test

那么如何实现替换多个字符串不同位置不同长度的子串。

$data = [
'Hello Test',
'QQ mytest',
'Sina email'
]

比如上面一个数组,现在需要把数组第i个元素的第i个字符串后面的4个字符串替换陈xxxx

$data = [
	'Hxxxx Test',
	'QQxxxxest',
	'Sinxxxxail'
]

其实,substr_replace也可以实现多个字符串子串的替换。

查看更多

如果让 strpos 查找一个整数类型的数字会发生什么?

18 Jan 2019 Category: php

每次数据来了,想要查找这个字符串中某个字符,上来就是使用strpos。strpos用于查找字符串中某个子串第一次出现的位置。

那么,如果不小心给strpos传入的是一个整数类型又会怎么样呢?

假设有一个字符串”I don’t happy ! xxxx585xxx”,现在需要把585以及后面的全部去掉。585是文件,或者数据库读取出来的,且做了数字类型格式化。

$str = "I don't happy ! xxxx585xxx";
$find = 585;
$s = substr($str, 0,strpos($str, $find));
var_dump($s);

直接使用strpop($str,$find);获取字符串的起始位置,然后再使用substr做一个截取。看似没有错误,但实际上跑完之后却是把整个字符串都删掉了。上面得到的是一个空字符串

查看更多

最简单的php trim函数并不简单

16 Jan 2019 Category: php

字符串的处理在任何程序中应该是最最常见的了吧。php 的trim函数就是用来去除字符串的字符串。最常用的就是去除空格了。但是,这个简单的函数,是否真的像你认为的那样简单呢?

trim函数的定义如下:


trim ( string $str [, string $character_mask = " \t\n\r\0\x0B" ] ) : string

trim是两边去除,还有ltrim 从左边去除,rtrim从右边去除,在php源码中,最终都是通过一个函数处理的。所以一下关于trim是对php 内部统一的trim而言。

源码在ext/standard/string.c中php_trim函数中。

trim函数处理逻辑:

  • 判断是否设置去除内容what,没设置则去除默认字符串
  • 判断去除内容的长度,分为1个字符,多个字符去除
  • 使用model分别与1,2按位与运算,确定是否进行左右去除

查看更多

PHP赋值的内部原理

12 Jan 2019 Category: php

在PHP中,一个变量被赋值,内部到底经历了怎样的逻辑判断呢?

PHP在内核中是通过zval这个结构体来存储变量的,它的定义在Zend/zend.h文件里

struct _zval_struct {
    zvalue_value value; /* 变量的值 */
    zend_uint refcount__gc;
    zend_uchar type;    /* 变量当前的数据类型 */
    zend_uchar is_ref__gc;
};
typedef struct _zval_struct zval;

//在Zend/zend_types.h里定义的:
typedef unsigned int zend_uint;
typedef unsigned char zend_uchar;

使用xdebug的xdebug_debug_zval函数可以打印出变量的refcount,is_ref的值。

$a = 'Hello World';
$b = $a;

以上内容在内核中怎么执行呢?

    zval *helloval;
    MAKE_STD_ZVAL(helloval);
    ZVAL_STRING(helloval, "Hello World", 1);
    zend_hash_add(EG(active_symbol_table), "a", sizeof("a"),&helloval, sizeof(zval*), NULL);
    ZVAL_ADDREF(helloval); //这句很特殊,我们显式的增加了helloval结构体的refcount
    zend_hash_add(EG(active_symbol_table), "b", sizeof("b"),&helloval, sizeof(zval*), NULL);

可以看出来,当变量赋值的时候,其实两个变量指向的是同一个地址空间。那么问题来了,如果指向同一个地址空间,那不是修改a,b也会跟着改变。这就涉及php的写时复制机制。 以上代码,如果后面一行为$b = '123'判断过程如下:

  • 如果这个变量的zval部分的refcount小于2,代表没有别的变量在用,则直接修改这个值
  • 否则,复制一份zval 的值,减少原zval的refcount的值,初始化新的zval的refcount,修改新复制的zval

查看更多