python数据结构进阶

列表和元组

都是一个可以放置任意数据类型的有序集合，他们中的元素不必都为统一数据类型(这与大部分编程语言都不一样)。

• 列表是动态的，长度大小不固定，可以随意地增加、删减或者改变元素（mutable）。
• 而元组是静态的，长度大小固定，无法增加删减或者改变（immutable）。
• Python 中的列表和元组都支持负数索引，列表和元组都支持切片操作，都可以随意嵌套，可以通过 list() 和 tuple() 函数相互转换：
  他们都有些常用的内置函数：

l = [3, 2, 3, 7, 8, 1]
l.count(3)      # 统计3出现的次数
2
l.index(7)        # 返回7第一次出现的索引
3
l.reverse()       # 原地倒转列表，元组没有该函数
l
[1, 8, 7, 3, 2, 3]
l.sort()             # 原地排序，元组没有该函数
l
[1, 2, 3, 3, 7, 8]

tup = (3, 2, 3, 7, 8, 1)
tup.count(3)
2
tup.index(7)
3
list(reversed(tup))      # reversed() 返回一个倒转后的迭代器
[1, 8, 7, 3, 2, 3]
sorted(tup)
[1, 2, 3, 3, 7, 8]           # sorted() 返回排好序的新列表。

列表与元组的重要差异

前面说了，列表和元组最重要的区别就是，列表是动态的、可变的，而元组是静态的、不可变的。这样的差异，势必会影响两者存储方式。我们可以来看下面的例子：

l = [1, 2, 3]
l.__sizeof__()
64
tup = (1, 2, 3)
tup.__sizeof__()
48

放置了相同元素，两者的存储空间却有差异，这是因为列表是动态的，所以它需要存储指针，来指向对应的元素（上述例子中，对于 int 型，8 字节）。另外，由于列表可变，所以需要额外存储已经分配的长度大小（8 字节），这样才可以实时追踪列表空间的使用情况，当空间不足时，及时分配额外空间。为了减小每次增加 / 删减操作时空间分配的开销，Python 每次分配空间时都会额外多分配一些，这样的机制（over-allocating）保证了其操作的高效性：增加 / 删除的时间复杂度均为 O(1)。
而元组是不变的，所以存储空间不变

列表与元组的性能

1. 首先由上述得到结论元祖要比列表轻量些，因此元组的性能速度略优于列表。
2. python在后台会对静态数据做资源缓存，因此当元组不被使用且占空间不大时python会暂时缓存这部分内存，下次创建大小一致的元组时不再去申请内存，二是直接去之前分配的内存空间，加快程序运行速度
3. 但如果是索引操作则两者速度基本一致
4. 增删改时列表更优，因为元组执行这些操作需要新建一个元组

列表和元组的使用场景

1. 如果存储的数据和数量不变，适合元组
2. 如果存储的数据和数量可变，适合列表
   注：

# 创建空列表
# option A
empty_list = list()  # list()是一个function call，较为费时间

# option B
empty_list = []      # []是个内置的C语言实现方法，更快

字典和集合

基础

字典是一系列由键（key）和值（value）配对组成的元素的集合，在 Python3.7+，字典被确定为有序，而 3.6 之前是无序的，其长度大小可变，元素可以任意地删减和改变。相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。
集合与字典的区别在于没有键值配对，是一系列无序的、唯一的元素组合。字典和集合中无论键与值都可以是混合类型，如
s = {1, 'hello', 5.0}
字典和集合的创建，字典的键只能是不可变数据类型(int，float，string，tuple)

d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])
d4 = dict(name='jason', age=20, gender='male') 
d1 == d2 == d3 ==d4
True

s1 = {1, 2, 3}
s2 = set([1, 2, 3])
s1 == s2
True

字典与集合取值

• 字典可以直接索引键，若不存在则抛出异常，也可以使用get(key,default)索引，若存在返回值，不存在返回default

d = {'name': 'jason', 'age': 20}
d['name']
'jason'
d['location']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'location'
-------------------------
d = {'name': 'jason', 'age': 20}
d.get('name')
'jason'
d.get('location', 'null')
'null'

• 集合并不支持索引操作，因为集合本质上是一个哈希表，和列表不一样
• 判断一个元素(键)在不在字典或集合内，我们可以用 value in dict/set 来判断。

s = {1, 2, 3}
1 in s
True
10 in s
False

d = {'name': 'jason', 'age': 20}
'name' in d
True
'location' in d
False

字典和集合也同样支持增加、删除、更新等操作，不再赘述，唯一注意点为集合的 pop() 操作是删除集合中最后一个元素，可是集合本身是无序的，你无法知道会删除哪个元素。
也可以进行排序

d = {'b': 1, 'a': 2, 'c': 10}
d_sorted_by_key = sorted(d.items(), key=lambda x: x[0]) # 根据字典键的升序排序
d_sorted_by_value = sorted(d.items(), key=lambda x: x[1]) # 根据字典值的升序排序
d_sorted_by_key
[('a', 2), ('b', 1), ('c', 10)]
d_sorted_by_value
[('b', 1), ('a', 2), ('c', 10)]
----------------------------------
s = {3, 4, 2, 1}
sorted(s) # 对集合的元素进行升序排序，集合没有sort函数，即不能s.sort()
[1, 2, 3, 4]

字典和集合的性能

• 首先查找数据中指定的元素，用列表存放数据的话即使排好序后用二分查找时间复杂度得O(logn)+O(nlogn)（二分查找+快速排序），而用字典为O(1)
• 若想获得很多商品有多少种不同的价格，集合的优势就出现了

# list version
def find_unique_price_using_list(products):      
    unique_price_list = []                # 用列表存放
    for _, price in products: # A       # 当多维数组或字典遍历时有元素用不到可以使用"_"代替
        if price not in unique_price_list: #B    # 这里判断也是每次得查看列表中元素，相当于一次循环
            unique_price_list.append(price)
    return len(unique_price_list)

def find_unique_price_using_set(products): 
    unique_price_set = set() 
    for _, price in products: 
        unique_price_set.add(price)      # 这里集合的添加和查找操作都是O(1)
    return len(unique_price_set)

products = [
    (143121312, 100), 
    (432314553, 30),
    (32421912367, 150),
    (937153201, 30)
]

上述用列表的时间复杂度为O(n^2)，而集合的时间复杂度为O(n)

字典和集合的工作原理

不同于其他数据结构，字典和集合的内部结构都是一张哈希表。

• 对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。
  举个例子，有这样一个字典：

{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}

老版本Python哈希表会把这个字典存为：

entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'mike'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]

这种结构会随着存储元素的增多而变得越来越稀疏，为提高空间利用率，现在的哈希表回吧索引和哈希值、键、值单独分开

indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'mike'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]

这样空间利用率得到很大提高。
插入操作原理：向字典和集合中插入一个元素时，python会首先计算键的哈希值，计算出应该插入的位置，若此位置为空则插入，若此位置已被占用则比较两个元素的哈希值和键是否相等：

1. 若两者都相等，则表明这个元素已存在，如果值不同则更新值
2. 若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。
   查找操作原理：根据哈希值找到其应该处于的位置，然后比较该位置上元素的哈希值和键与查找元素是否相等，如果相等则直接返回，不等则继续找，直到找到空位或抛出异常为止。
   删除操作原理对于删除操作，Python 会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除（目的就是减少删除的时间）。
   不难理解，哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入，当剩余空间小于 1/3 时，Python 会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。
   注

# Option A
d = {'name': 'jason', 'age': 20, 'gender': 'male'}   # 效率更高，调用C实现

# Option B
d = dict({'name': 'jason', 'age': 20, 'gender': 'male'})  # 效率不如上面

字符串

1. python中单引号、双引号、三引号的字符串没有任何区别
2. 字符串也支持索引切片和遍历
3. 字符串不可变（java也一样，但java中StringBuilder是可变字符串类型），想要修改就创建新的字符串
4. 在字符串拼接时使用 str1 += str2，若str1没有其他引用，就会原地扩充字符串大小，不用重新分配内存存放新字符串并拷贝，时间复杂度就降低为O(n)（感觉这条与上条冲突），字符串拼接还可以使用string.join(iterable)，字符串分割string.split(separator)、string.strip(str)，表示去掉首尾的 str 字符串；string.lstrip(str)，表示只去掉开头的 str 字符串；string.rstrip(str)，表示只去掉尾部的 str 字符串。

def query_data(namespace, table):
    """
    given namespace and table, query database to get corresponding
    data         
    """

path = 'hive://ads/training_table'
namespace = path.split('//')[1].split('/')[0] # 返回'ads'
table = path.split('//')[1].split('/')[1] # 返回 'training_table'
data = query_data(namespace, table) 

5. 字符串的两种常用格式化

print('no data available for person with id: {}, name: {}'.format(id, name))
print('no data available for person with id: %s, name: %s' % (id, name))