首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    合理选择数据结构

    写程序很重要的一点是选择合理的数据结构,不合适的数据结构在如今高性能计算机盛行的情况下,小数据量体现不出什么来,但是在超大数据的时候, 你所面临的困境将会无穷的放大。 在python里主要的数据结构,也就是内置数据结构,包括了列表,元组,字典以及集合。这四种数据结构分别具有不同的特性,影响着python的方方面面。 列表和元组类似于C的数组,但是不同的是,列表是动态的数组,具有着增删改查的操作,元组是静态的数组,本身是不可变的(除非里面包含了可变的容器类) 。那python为啥还要实现元组呢?按照python之禅所述,Special cases aren't special enough to break the rules...There should be one-- and preferably only one --obvious way to do it. 这是因为元组可以缓存于python的运行环境,在每次使用元组时我们都无需去访问内核分配内存,元组和列表代表着两种不同的方式,元组是一个不会改变事物的多种属性,而 列表是保存多个相对独立的对象的集合。 列表的搜索,如果在已知次序的情况下,使用二分法效率会变得很好,但是如前言所述,在相对独立的对象的数据集合中,有序是比较少见的情况,这意味着对列表的搜索 在python内部结构就只能是遍历。python的内建排序不是如《python源码剖析》所述是快速排序,而是Tim排序,这个排序是google发明的,可以在最好的情况下实现O(n)的复杂度排序 ,在最坏的情况下也有O(log(n))。对于数据的搜索, def b_search(i, haystack): imin, imax = 0, len(haystack) while True: if imin > imax: return -1 mid = (imin + imax) // 2 if haystack[mid] > i: imax = mid elif haystack[mid] < i: imin = mid + 1 else: return mid python的二分搜索实现很简单,因为你不需要再考虑内存溢出以及安全性,这些python已经帮你做好了。还有和二分搜索相似的,就是二叉搜索树。至于如果你不想自己实现 你可以选择bisect模块帮你解决这个问题。 元组因为其的不可改变性,对于列表为了其可变性牺牲的额外的内存以及使用它们进行的额外的计算,元组就内存消耗和速度就快的多了。并且小元组在申请了内存后也就是 不会返还给系统,还留待未来使用,在接下来需要新元组时就不需要向系统申请内存了。 下面看看字典和集合,字典在很多语言内都有实现,也就是映射,属于key-value的一种,在python里集合也是类似字典的结构,只不过没有了value,只有key了。 字典和集合的查询无需遍历,只需要计算散列函数就可获得其值,但这也意味着这两种数据结构会占用更大的内存,而且O(1)的复杂度也取决于散列函数的计算复杂度。 字典插入时,会计算键的散列值,理想的散列函数对应的键应该是就是整数,不会出现任何形式的冲突。计算出散列值后,很重要的一点要计算掩码,来得知value应该存放的 位置。对于冲突的处理,python使用的是开放定址法,会在一个数组里不断‘嗅探’,获得空的内存空间。当然,在字典的内存不够用时,自然会申请空间,这意味着我们需要重新散列值和 掩码。 所以,每种数据结构都有其不同的特性,所以这也意味着选择一个良好的数据数据会使得你的代码效率快上不少。

    02

    Python学习笔记整理(七)Pytho

    一、元组介绍 元组(tuple)是无法修改的其他对象的结合.元组由简单的对象构成,元组与列表类似,不过元组不能在原处修改。通常写成圆括号中的一系列项。 1、元组的属性 *任意对象的有序集合 与字符串和列表类似,元组是一个位置有序的对象集合。与列表相同,可以嵌入任何类别的对象到其中,可以嵌套元组,列表,字典。 *通过偏移存取 同字符串,列表一样,在元组中的元素通过偏移来访问。支持所有基于偏移的操作,如果索引和分片 *属于不可变序列类型 类似于字符串,元组不可变,不支持在原处修改。与字符串和列表类似,元组有序列. 注意:元组的不可变性只使用与元组本身顶层而非其内容,元组的内部的列表,字典可以像往常那样修改。 *对象引用的数组 与列表类似,元组最好被认为是对象引用的数组。元组存储指向其他对象的存取点(引用),并且对元组进行索引操作的速度相对较快。 2、常见的元组操作 运算        解释 ()        空元组 t1=(0,)        单个元组的元组(非表达式) t2=(0,'A',1.3,4) 四个元素的元组 t2=0,'A',1.3,4  四个元素的元组 t3=(1,('A','B'))  嵌套元组 t4=(1,('A', 'B'),[4,5,6],{'name':'diege','age':18})    元组嵌套元组,列表,字典 t1[i]        索引 t1[i][j]    嵌套的索引 t1[i:j]        分片 len(t1)        长度,每一个元素算一个,不过元素是列表还是字典 len(t4)+len(t4[1])+len(t4[2])+len(t4[3]) t1+t2        合并 t2*3        重复 for x in t1:    迭代 'diege' i t2    成员关系 二、实际应用中的元组 1、元组的特殊语法,逗号和圆括号 >>> x=(40) >>> x 40 >>> x=(40,) >>> x (40,) 在不引起语法冲突的情况下,python允许忽略元组的圆括号,仅当元组做为文字传递给函数调用(圆括号很重要)以及当元组在print语句中列出(逗号很重要)的特殊情况时,圆括号才是必不可少的。 2、转换以及不可变性 除了常量语法不同外,元组的操作和字符串以及列表是一致的,值得注意的区别在于+ *以及分片操作应用于元组后将返回新的元组。并且元组不提供字符串,列表,字典中的方法。例如像对元组进行排序,通常先得将它转换为列表才能获得使用排序方法调用的权限将它变成一个可变的对象。 >>> T=('cc','aa','dd','bb') >>> temp=list(T) >>> temp.sort() >>> temp ['aa', 'bb', 'cc', 'dd'] >>> T=tuple(temp) >>> T ('aa', 'bb', 'cc', 'dd') 注意:元组的不可变性只使用与元组本身顶层而非其内容,元组的内部的列表,字典可以像往常那样修改。 >>> T=('a',[8,9],3.14) >>> T[1]=10 Traceback (most recent call last):   File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment >>> T[1][1]=10 >>> T ('a', [8, 10], 3.14) 3、为什么有了列表还要元组? Python的创造者,提到过把元组看作是简单的对象组合,把列表看成是随时间改变的数据结构。最佳答案似乎是元组的不可改变性提供了某种完整性,保证了数据的完整性。列表是定序集合的选择工具,可能需要进行修改。而元组能够处理其他固定关系的情况。 三、文件介绍 文件这个主要内置对象类型提供了一种可以存取Python程序内部文件的方法。 内置open函数会创建一个Python文件对象,可以作为计算机上的一个文件连接,在调用open之后,可以通过调用返回文件对象的方法来读写相关外部文件。文件可以通过调用open或file来打开。open通常比file更常用,因为file几乎都是为面向对象程序设计量身打造的。文件对象只是常见文件处理任务输出模块。多数文件方法都是执行外部文件的相关文件对象的输如输出有关,但其他文件方法可让查找文件中新位置,刷新输出缓冲等。 1、打开文件 处理模式没没有指定则默认为'r'。代表输入打开文件。'w'代表输出生成并打开文件,'a'代表为在文件尾部追加内容而打开文件。 "+"意味着同时为输入输出打开文件(也就是

    03
    领券