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__()

重点：

• 针对于所有的类型，会有布尔判断的需求，主要在if和while两种条件判断中，下面给出所有的非真判定：

  • 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()分别进行转化。数值类型的重点在于运算符操作，主要的运算符有：

实数类型（int和float）还包括一些运算方法，部分实现在package math中：

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

序列

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

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

可变类型可以进行改写操作，常见的有：

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 ...")