Python内置对象实现的方法及注意事项

maiziedu · · 2085 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。
![QQ截图20150928150103.png](http://studygolang.qiniudn.com/150928/e6361a28482c2d44561584940a75112b.png) Python语言中,所有的东西都是对象,因此对于python初学者来说,搞清楚python对象的具体实现非常重要。 Python中的对象主要分为类型对象和实例对象,但也不排除有同时属于类型和实例的对象,而不管是什么对象,除了内置的类型对象外,都存在于堆上,内置的类型对象则静态分配内存。下面我们就一起来看看python常见的内置对象及其实现方法吧。 1、int int这个对象比较简单,但还是需要重点了解,以便高效的实现。python首先有小整数对象。默认在[-5, 257)。如果超出范围则使用通用的缓冲池,对于大整数则有PyIntBlock,用来作缓冲池。一个block大小大概为1000个字节,去掉头部(8字节),可以存82个整数对象。block之间通过指针相连,首指针为block_list,free_list则维护着一条可以链表,free_list链表的下一项由未用的PyIntObject的ob_type来维持。 如果没有缓冲池可用的时候怎么办呢?这个时候python会调用fill_free_list来创建一个新的block,并将其插入block_list,再把free_list指向这个block的objects中的最后一个元素。当某个block中的某个int被释放时,它将自己的ob_type指向free_list,并修改free_list等于它的地址,其实就是一个头部插入,这样把多个block间的objects数组联系起来防止出现内存泄漏。但值得注意的是小整数对象池其实也是生活在block里面,在是整个python环境初始化的时候生成。因此,为int分配的内存是永远也不会被python释放的,所有的int对象使用的内存大小和同时存在的int数量的最大值有关。 2、string String为变长对象,主要用于对变长对象内存的管理,每个string对象除了头部外还保存了hash值(ob_shash,避免重复计算,初始-1)、是否已经被intern机制处理过(ob_sstate)、指向实际内存的指针(ob_sval),ob_sval指向的应该是一段ob_size+1长度的内存(为了兼容C,字符串要以'\0'结尾)。在从char *创建string时还是比较直接的,就是检查一些边界情况、初始化hash等,最后逐个拷贝char。python中有一个nullstring指向空字符串,通过intern机制共享,所以不会同时存在多个空字符串。对单个的char,python也会维持一个缓冲池。创建单个char的string时,如果缓冲池里已有,则直接返回。如果没有,根据char创建string,再对它进行intern,再存入缓冲池。 对于已经被创建的string,python会维持一个string用来保存,如果新创建string已经在这个dict,也就是已经被intern机制处理过了,那么就会直接返回dict中的值。一般两个相同的字符串的id是相同的。要注意的是,无论字符串有没有存在于这个dict中,python都会创建一个新要string,原因是因为保存在dict中只能是PyObject,因此肯定要创建一个python对象。intern后的string有两种状态,mortal和immortal,区别在于后者永远不会被gc回收。但创建string时使用的是PyObject_Malloc开头的分配函数,一般来讲它不会每次都从os分配内存,而是从python维持的一个内存池中分配。 3、list list不仅是变长对象,还是可变对象。在变长头部之外PyListObject还保存了一个PyObject **ob_item指针,一个int allocated。ob_item就是指向实际成员的指针,allocated代表了list当前申请的内存能装多少个PyObject,变长头内的ob_size则代表list中已有多少个PyObject。当创建一个list时,需要指定list的大小(参数size),要申请的内存可以分为两部分,一个是list本身,一个是指向成员变量的指针。如果list缓冲池可用(numfree > 0),那就从缓冲池中给list分配一块内存,否则使用PyObject_GC_NEW来分配空间(和string不同,因为list中的成员可以指向其它python对象,这个函数和python垃圾回收的三色标记法有关)。然后再根据size大小分配一段连续的内存来保存指向各个成员的指针,新创建的list中的ob_size和allocated都为size。 创建list后给list里的某个位置赋值比较简单,就是简单的设定指针而已。添加操作要复杂一些,首先会调整list的大小,使得allocate>=size>=allocate/2。如果该等式已经满足,那么不更改list大小,如果不满足的话通过new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize得出新的allocated大小,再通过PyMem_Resize来调整保存成员指针的内存。resize后则使用最简单的策略移动从插入到结尾的成员指针,再设置该位置上的成员。删除成员时实际删除后的也要进行resize操作,和插入时类似。实际删除的操作则由list_ass_slice来实现,它有两种用法,一是更改list中的某一段为特定的值,另一种就是删除list中的某一段。list中每删除一个元素都会造成内存拷贝。一个值得注意的细节是由于从list中删除或是更改的对象需要减少引用计数,但减少引用计数时又会循环调用一些list函数,可能会造成list索引值的破坏,因而函数中得用一个temp数组保留从list中剥离的成员,等删除工作完成,list结构已经确定的情况下再逐一减少其引用。当list被销毁时,对其成员逐个减少引用,然后检查缓冲区是否已经满,如果没有的话就将该list放入缓冲区,这样下次再创建list的时候就不用为list对象本身再分配对象了。 4、dict python中的dict是用hash表实现,解决冲突的方法是开放定址法,即二次探测,删除时使用伪删除技术(顺便说下在一致性假设下,如果用k来表示hash表的使用率的话,那么一次成功查找需要的比较次数为1/k * ln(1/(1-k)),插入时的比较次数最多为1/(1-k))。 在一个dict中,每个(key,value)对组成一个entry,entry中还另外存储了key的hash值。对每个entry来说有三种状态unused(key,value皆为NULL,初始状态),active(key,value不为NULL,存储了元素),dump(对应于伪删除技术,key=dummy,value=NULL)。dict实际上就是entry的集合,定义如下: typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; /* # Active + # Dummy */ Py_ssize_t ma_used; /* # Active */ /* The table contains ma_mask + 1 slots, and that's a power of 2. * We store the mask instead of the size because the mask is more * frequently needed. */ Py_ssize_t ma_mask; /* ma_table points to ma_smalltable for small tables, else to * additional malloc'ed memory. ma_table is never NULL! This rule * saves repeated runtime null-tests in the workhorse getitem and * setitem calls. */ PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; }; PyDict_MINSIZE一般被设为8。使用PyDict_New来创建一个新dict时,其实就是分配相应的内存,将ma_fill,ma_used设为0,ma_mask设为7(8-1),ma_table指向ma_smalltable,ma_lookup默认为lookdict_string。在实现dict时python也使用了缓冲池,方法和list基本一样。 ma_lookup这个函数指针确定了散裂函数和冲突发生时的二次散裂函数,在dict中进行搜索有两种方法,lookdict_string和lookdict,后一种是更一般的方法。由于python中dict用的非常广泛,而这些dict中大多数key都是string,因而专门提供了一个搜索方法来进行加速,其实两种方法的本质都是一样的。搜索的具体过程如下: (1) 获得探测链中当前应该检测的entry; (2)如果是unused状态,那搜索失败,应该返回一个可用的(可以被设置值)的entry,所以如果freeslot不为空(之前找到了dummy态的entry)就返回freeslot指向的entry,否则返回当前entry; (3) 如果entry为dummy态且freeslot未设置,则设置freeslot,继续查找下一个; (4) 依次检查当前entry的key和查找的key是否引用相同、值相同,若不是继续查找下一个。需要注意的是,dict使用哪种方法进行查找取决于待查找的key,如果是string的话则利用lookdict_string,和本身已经有的entry中的key无关。 dict的插入和删除基于之前的搜索,很好理解。当插入时先搜索该key,得到一个entry,再根据它的状态来修改它达到插入的上目的。删除操作也类似。需要注意的是插入元素的时候,会检查ma_fill/(ma_mask+1)是否大于2/3,如果装载率的确大于这个值并且有unused或dummy的entry被填充的时候,就会调整dict的大小,新的大小最小为minsize=ma_userd*(ma_used>50000?2:4),显然改变dict大小会造成内存移动,因此这时候可以丢弃dummy的entry。新的dict大小从8开始逐次*2增长,直到大于minsize。接下来就是一些初始化动作,逐个检查entry并插入新的dict等。 以上就是python中常见的集中内置对象,及其实现方法、注意事项等,希望对python初学者在学习相关内容时有所帮助。由于python对象的内容比较多,本文只做了个简要的说明,如果有补充的,也欢迎补充分享。 相关阅读:《 Python 3.5新特性有哪些?》 http://www.maiziedu.com/group/article/5508/

入群交流(该群和以上内容无关):Go中文网 QQ交流群:731990104 或 加微信入微信群:274768166 备注:入群; 公众号:Go语言中文网

2085 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传