PHP内核探索:数组与链表

C语言中数组和链表的一些事情
服务器君一共花费了309.950 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

在C语言中,我们可以自定义各种各样的数据结构,用来把很多数据保存在一个变量里面,但是每种数据结构都有自己的优缺点,PHP内核规模如此庞大,是否已经找到了一些非常棒的解决方法呢?

我们在选择各种数据结构时,往往会考虑我们需要处理的数据规模以及需要的性能。下面让我们简要的看一下看C语言中数组和链表的一些事情。

数组

作者这里用的不是Array,而是Vector,可能指的是C++里的Vector,它与数组几乎是完全一样的,唯一的不同便是可以实现动态存储。本节下文都是用数组一词代替之,请各位注意。数组是内存中一块连续的区域,其每一个元素都具有一个唯一的下标值。

int a[3];
a[0]=1;
a[2]=3;

不仅是整数,其它类型的变量也可以保存在数组中,比如我们前面用到的zend_get_parameters_array_ex(),便把很多zval**类型的变量保存到一个数组里,为了使其正常工作,我们提前向系统申请了相应大小的内存空间。

zval ***args = safe_emalloc(ZEND_NUM_ARGS(), sizeof(zval**), 0);

这里我们仍然可以用一个整数来当作下标去数组中取出我们想要的数据,就像var_dump()的实现中通过args[i]来获取参数并把它传递给php_var_dump()函数那样。

使用数组最大的好处便是速度!读写都可以在O(1)内完成,因为它每个元素的大小都是一致的,只要知道下标,便可以瞬间计算出其对应的元素在内存中的位置,从而直接取出或者写入。

链表

链表也是一种经常被使用的一种数据结构。链表中的每一个元素都至少有两个元素,一个指向它的下一个元素,一个用来存放它自己的数据,就像下面定义的那样:

typedef struct _namelist namelist;
struct
{
	struct _namelist *next;
	char *name;
}_namelist;

我们可以声明一个其类型的元素:

static namelist *people;

假设每一个元素都代表一个人,元素中的name属性便是这个人的名字,我们通过这样的语句来得到它:people->name; 第二个属性指向后面的一个元素,那我们便可以这样来访问下一个人的名字:people->next->name, 或者下一个人的下一个人的名字:people->next->next->name,一次类推,直到next的值是NULL,代表结束。

//通过一个循环来遍历这个链表中的所有人~
void name_show(namelist *p)
{
	while (p)
	{
		printf("Name: %s\n", p->name);
		p = p->next;
	}
}

链表可以被用来实现FIFO模式,达到先进者先出的目的!

static namelist *people = NULL, *last_person = NULL;
void name_add(namelist *person)
{
    person->next = NULL;
    if (!last_person) {
        /* No one in the list yet */
        people = last_person = person;
        return;
    }
    /* Append new person to the end of the list */
    last_person->next = person;

    /* Update the list tail */
    last_person = person;
}
namelist *name_pop(void)
{
    namelist *first_person = people;
    if (people) {
    	people = people->next;
    }
    return first_person;
}

这样,我们便可以随意的向这个链表中添加或者删除数据,而不向数组那样,谨慎的考虑是否越界等问题。

上面实现的结构的学名叫做单向链表,也有地方叫单链表,反正是比较简单的意思~。它有一个致命的缺点,就是我们在插入或者读取某条数据的时候,都需要从这个链表的开始,一个个元素的向下寻找,直到找到这个元素为止。如果链表中的元素比较多,那它很容易成为我们程序中的CPU消耗大户,进而引起性能问题。为了解决这个问题,先人们发明了双向链表:

typedef struct _namelist namelist;
struct
{
	namelist *next, *prev;
	char *name;
} _namelist;

改动其实不大,就是在每个元素中都添加了一个prev属性,用来指向它的上一个元素。

void name_add(namelist *person)
{
	person->next = NULL;
	if (!last_person)
	{
		/* No one in the list yet */
		people = last_person = person;
		person->prev = NULL;
		return;
	}
	/* Append new person to the end of the list */
	last_person ->next = person;
	person->prev = last_person;

	/* Update the list tail */
	last_person = person;
}

单单通过上面的程序你还体会不到它的好处,但是设想一下,如果现在你有这个链表中其中一个元素的地址,并且想把它从链表中删除,那我们该怎么做呢?如果是单向链表的话,我们只能这样做:

void name_remove(namelist *person)
{
    namelist *p;
    if (person == people) {
        /* Happens to be the first person in the list */
        people = person->next;
        if (last_person == person) {
            /* Also happens to be the last person */
            last_person = NULL;
        }
        return;
    }
    /* Search for prior person */
    p = people;
    while (p) {
        if (p->next == person) {
            /* unlink */
            p->next = person->next;
            if (last_person == person) {
                /* This was the last element */
                last_person = p;
            }
            return;
        }
        p = p->next;
    }
    /* Not found in list */
}

现在让我们来看看双向链表是怎样来处理这个问题的:

void name_remove(namelist *person)
{
    if (people == person) {
        people = person->next;
    }
    if (last_person == person) {
        last_person = person->prev;
    }
    if (person->prev) {

        person->prev->next = person->next;
    }
    if (person->next) {
        person->next->prev = person->prev;
    }
}

对元素的遍历查找不见了,取而代之的是一个O(1)的运算,这将极大的提升我们程序的性能。

王者归来:HashTable才是我们的银弹!

也许你已经非常喜欢使用数组或者链表了,但我还是要向你推荐一种威力极大的数据结构,有了它之后,你可能会立即抛弃前两者,它就是HashTable.

HashTable即具有双向链表的优点,同时具有能与数据匹敌的操作性能,这个数据结构几乎是PHP内核实现的基础,我们在内核代码的任何地方都发现它的痕迹。

前面我们接触过,所有的用户端定义的变量保存在一个符号表里,而这个符号表其实就是一个HashTable,它的每一个元素都是一个zval*类型的变量。不仅如此,保存用户定义的函数、类、资源等的容器都是以HashTable的形式在内核中实现的。

Zend Engine中HashTable的元素其实是指针,对其的这个改进使得HashTable能够包容各种类型的数据,从小小的标量,到复杂的PHP5中实现的类等复合数据。本章接下来的内容,我们将详细的研究如何使用zend内置的API来操作HashTable这个数据结构。

延伸阅读

此文章所在专题列表如下:

  1. PHP内核探索:从SAPI接口开始
  2. PHP内核探索:一次请求的开始与结束
  3. PHP内核探索:一次请求生命周期
  4. PHP内核探索:单进程SAPI生命周期
  5. PHP内核探索:多进程/线程的SAPI生命周期
  6. PHP内核探索:Zend引擎
  7. PHP内核探索:再次探讨SAPI
  8. PHP内核探索:Apache模块介绍
  9. PHP内核探索:通过mod_php5支持PHP
  10. PHP内核探索:Apache运行与钩子函数
  11. PHP内核探索:嵌入式PHP
  12. PHP内核探索:PHP的FastCGI
  13. PHP内核探索:如何执行PHP脚本
  14. PHP内核探索:PHP脚本的执行细节
  15. PHP内核探索:操作码OpCode
  16. PHP内核探索:PHP里的opcode
  17. PHP内核探索:解释器的执行过程
  18. PHP内核探索:变量概述
  19. PHP内核探索:变量存储与类型
  20. PHP内核探索:PHP中的哈希表
  21. PHP内核探索:理解Zend里的哈希表
  22. PHP内核探索:PHP哈希算法设计
  23. PHP内核探索:翻译一篇HashTables文章
  24. PHP内核探索:哈希碰撞攻击是什么?
  25. PHP内核探索:常量的实现
  26. PHP内核探索:变量的存储
  27. PHP内核探索:变量的类型
  28. PHP内核探索:变量的值操作
  29. PHP内核探索:变量的创建
  30. PHP内核探索:预定义变量
  31. PHP内核探索:变量的检索
  32. PHP内核探索:变量的类型转换
  33. PHP内核探索:弱类型变量的实现
  34. PHP内核探索:静态变量的实现
  35. PHP内核探索:变量类型提示
  36. PHP内核探索:变量的生命周期
  37. PHP内核探索:变量赋值与销毁
  38. PHP内核探索:变量作用域
  39. PHP内核探索:诡异的变量名
  40. PHP内核探索:变量的value和type存储
  41. PHP内核探索:全局变量Global
  42. PHP内核探索:变量类型的转换
  43. PHP内核探索:内存管理开篇
  44. PHP内核探索:Zend内存管理器
  45. PHP内核探索:PHP的内存管理
  46. PHP内核探索:内存的申请与销毁
  47. PHP内核探索:引用计数与写时复制
  48. PHP内核探索:PHP5.3的垃圾回收机制
  49. PHP内核探索:内存管理中的cache
  50. PHP内核探索:写时复制COW机制
  51. PHP内核探索:数组与链表
  52. PHP内核探索:使用哈希表API
  53. PHP内核探索:数组操作
  54. PHP内核探索:数组源码分析
  55. PHP内核探索:函数的分类
  56. PHP内核探索:函数的内部结构
  57. PHP内核探索:函数结构转换
  58. PHP内核探索:定义函数的过程
  59. PHP内核探索:函数的参数
  60. PHP内核探索:zend_parse_parameters函数
  61. PHP内核探索:函数返回值
  62. PHP内核探索:形参return value
  63. PHP内核探索:函数调用与执行
  64. PHP内核探索:引用与函数执行
  65. PHP内核探索:匿名函数及闭包
  66. PHP内核探索:面向对象开篇
  67. PHP内核探索:类的结构和实现
  68. PHP内核探索:类的成员变量
  69. PHP内核探索:类的成员方法
  70. PHP内核探索:类的原型zend_class_entry
  71. PHP内核探索:类的定义
  72. PHP内核探索:访问控制
  73. PHP内核探索:继承,多态与抽象类
  74. PHP内核探索:魔术函数与延迟绑定
  75. PHP内核探索:保留类与特殊类
  76. PHP内核探索:对象
  77. PHP内核探索:创建对象实例
  78. PHP内核探索:对象属性读写
  79. PHP内核探索:命名空间
  80. PHP内核探索:定义接口
  81. PHP内核探索:继承与实现接口
  82. PHP内核探索:资源resource类型
  83. PHP内核探索:Zend虚拟机
  84. PHP内核探索:虚拟机的词法解析
  85. PHP内核探索:虚拟机的语法分析
  86. PHP内核探索:中间代码opcode的执行
  87. PHP内核探索:代码的加密与解密
  88. PHP内核探索:zend_execute的具体执行过程
  89. PHP内核探索:变量的引用与计数规则
  90. PHP内核探索:新垃圾回收机制说明

本文地址:http://www.nowamagic.net/librarys/veda/detail/1455,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1455

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫•迈克康奈尔 (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与时俱进的内容,包括对新语言、新的开发过程与方法论的讨论等等。这是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种种实践方法。

更多计算机宝库...