python数据结构

背景

之所以选择这个话题,有两方面原因:

  • 很多情况下,有些语句是看到别人这么用,自己就这么用,并不知道为什么要这么用
  • 写了一段代码,很简洁很美观,跑起来比驴还慢

只有知道内部原理,才能够写出美观的、高性能的代码。

总览

Python的內建类型主要包括数值、序列、映射、类、类型和异常等:

  • 数值(numerics),包括整数(int)、浮点数(float)、复数(complex)
  • 序列(sequences),包括列表(list)、元组(tuple)、范围(range)以及额外的如字符串(string/unicode string)、二进制序列(bytes)
  • 映射(mappings),如字典类型(dict)
  • 集合(set),包括可变集合(set)和不可变集合(fronzeset)
  • 模块(modules)
  • 类(classes)以及类型(class instances)
  • 函数(functions)
  • 方法(methods)
  • 代码对象(code objects)
  • 类型对象(type objects)
  • 空值(None)
  • 布尔值(True, False)
  • 内部对象,包括堆栈(stack/traceback)和切片(slice)
  • 一些属性(attribute),主要有object.__dict__, instance.__class__, class.__bases__,definition.__name__, definition.__qualname__, class.__mro__, class.mro(), class.__subclasses__()

重点:

  • 针对于所有的类型,会有布尔判断的需求,主要在ifwhile两种条件判断中,下面给出所有的非真判定:

    • None
    • False
    • 数值类型的0值,如0, 0.0, 0j
    • 空序列,如'', [], ()
    • 空映射,如{}
    • 用户自定类型,如果重载了__bool__()或者__len__(),判断前者为False或者后者为0
  • 逻辑运算,and, or, not

       x and y # if x is false, then x, else y
       x or y # if x is false, then y, else x
       not x # if x is false, then True else False
    

数值

python的数值类型非常强大,这也是很多情况下把python当做计算器的原因之一。主要有整数、浮点数和复数三种类型,可以通过函数int(), float(), complex()分别进行转化。数值类型的重点在于运算符操作,主要的运算符有:

运算 结果
x+y sum
x-y difference
x*y product
x/y quotient
x//y floored quotient
x%y remainder
-x negated
+x unchanged
abs(x) absolute value or magnitude
int(x) converted to integer
float(x) converted to floating point
complex(x, y) a complex number with real part re, imaginary part im. im defaults to zero
divmod(x,y) the pair (x // y, x % y)
pow(x, y) x to the power y
x ** y x to the power y

实数类型(int和float)还包括一些运算方法,部分实现在package math中:

运算 结果
math.trunc(x) 截取整数部分
round(x[,n]) 根据给定小数位n,进行四舍五入
math.floor(x) the greatest Integral <= x
math.ceil(x) the least Integral >= x

对于整数类型,我们还可以进行一些位运算,如:

运算 结果
`x y` bitwise or
x ^ y bitwise exclusive
x & y bitwise and
x << n x shifted left by n bits
x >> n x shifted right by n bits
~x inverted

序列

序列主要包括列表、元组、范围、二进制序列和字符串。针对序列类型,会有以下常用的运算操作:

运算 结果
x in s 判断x是否在序列s中,是则返回True
x not in s 与上述相反
s + t 两个序列连接
s * n or n * s 序列s重复n次,n为整数
s[i] s的第i个元素, i = len(s) + i if i < 0 else i
s[i:j] s的i到j切片
s[i:j:k] s的i到j切片,以k为步长
len(s) s的长度
min(s) s的最小值
max(s) s的最大值
s.index(x[, i[, j]]) 查找x在s序列中位于i/j之间第一次出现位置,i默认为0,j默认为len(s)
s.count(x) s中x出现次数

注意,序列分为可变序列和不可变序列,不可变序列支持了hash()而可变类型不支持,这也就是使得不可变序列可以作为dict的键,如stringtuple

可变类型可以进行改写操作,常见的有:

操作 结果
s[i] = x 改写第i个元素
s[i:j] = t 改写第i到j个元素
del s[i:j] 删除第i到j个元素
s[i:j:k] = t 改写第i到j个元素,以k为步长
del s[i:j:k] 删除第i到j个元素,以k为步长
s.append(x) 最末添加x
s.clear() 删除所有元素
s.copy() 创建副本,等同于s[:]
s.extend(t) or s += t 在s后面追加
s *= n copy为n份
s.insert(i, x) 在i位置插入x
s.pop([i]) 弹出第i项
s.remove(x) 删除值为x的项
s.reverse() 反转列表

List

列表的构建式:

  • 空列表,[]
  • 枚举值,[a], [a, b, c]
  • 别表生成式,[x for x in iteratable]
  • 类型转换,list(), list(iterable)

tuple

元组的构建式:

  • 空元组,()
  • 逗号结束符,a,或者(a,)
  • 逗号符,a,b,c或者(a,b,c)
  • 类型转换,tuple()或者tuple(iterable)

range

range的构建式:

  • 指定结束,range(10)
  • 指定最小最大以及步长,range(1,10,2)

字符串

字符串构建式:

  • 单引号,'a "b"'
  • 双引号,"a 'b'"
  • 三(单/双)引号,'''sss''', """ddd"""
  • 数组合并,"aaa" "bbb" == "aaabbb"

bytes类型

构建式和字符串类似,在前面添加b标志,如b'a'

bytes转换类型可以转换数值型,迭代式和对象(需实现fromhex)

Dict类型

常用操作:

  • len(d)
  • d[key]
  • d[key] = value
  • del d[key]
  • key in d
  • key not in d
  • iter(d),实际上是iter(d.keys())
  • clear()
  • copy()
  • fromkeys(seq[,value]),创建新的dict
  • get(key[,default])
  • items()
  • keys()
  • pop(key[,default])
  • popitem()随机
  • setdefault(key[,default])
  • update([other]),如d.update(red=1)
  • values()

两个实例

# example 1

#!coding=utf8
"""
由于字符串是非可变类型,因而在每次+=操作的时候都会进行一个内存copy,我们可以对比一下+=和join两者性能差别
"""

import time
import random

def record_time(f):
    def inner():
        ts = time.clock()
        f()
        te = time.clock()
        print("cost %f s" % (te - ts))
    return inner


# 生成器
def getString():
    example = ["abc", "bca", "cba"]
    while True:
        yield example[random.randint(0, len(example)-1)]



@record_time
def append1():
    result = ""
    i = 0
    for r in getString():
        if i > 10000000:
            break
        result += r
        i += 1
    return result

@record_time
def append2():
    result_array = []
    i = 0
    for r in getString():
        if i > 10000000:
            break
        result_array.append(r)
        i += 1
    return ''.join(result_array)

append1()
append2()
# example 2
#!coding=utf8
"""
一个反面的例子,关于为什么不要随意使用list.pop(0)
"""
import time
import random


def record_time(f):
    def inner(arg):
        ts = time.clock()
        result = f(arg)
        te = time.clock()
        print("cost %f s" % (te - ts))
        return result
    return inner


class Queue(object):

    data = []

    def push(self, value):
        self.data.append(value)

    def pop(self):
        try:
            value = self.data.pop(0)
        except:
            return None
        return value

    def back(self):
        return self.data[-1]

    def front(self):
        return self.data[0]

    def count(self):
        return len(self.data)


@record_time
def pop_queue(obj):
    i = 0
    while obj.pop() is not None:
        i += 1
    return i


q = Queue()

for i in xrange(1000000):
    q.push(random.randint(0, 100))


print("start pop ...")
print("pop queue count %d" % pop_queue(q))
print("end pop ...")
right