你好，我是悦创。

我们先来看看今天要学习的内容：

  • 列表、集合、元组、字典
  • 链表

1. 你真的了解这四个数据类型吗？

  • 列表/list
  • 元组/tuple
  • 字典/dict
  • 集合/set

    1.1 列表 VS. 元组

  1. 可变与不可变
  2. 选择存储策略
    1. 存储经纬度用：元组
    2. 存储用户访问：列表

      1. 列表和元组存储方式的差异

      前面说了，列表和元组最重要的区别就是，列表是动态的、可变的，而元组是静态的、不可变的。这样的差异，势必会影响两者存储方式。我们可以来看下面的例子：
      1. l = [1, 2, 3]  # 直接创建列表，会比后期使用 append 节省空间
      2. l.__sizeof__()
      3. 64
      4. tup = (1, 2, 3)
      5. tup.__sizeof__()
      6. 48
      你可以看到，对列表和元组，我们放置了相同的元素，但是元组的存储空间，却比列表要少 16 字节。这是为什么呢？

      1 int = 8 字节 1 字节 = 8 位

事实上，由于列表是动态的，所以它需要存储指针，来指向对应的元素（上述例子中，对于 int 型，8 字节）。

另外，由于列表可变，所以需要额外存储已经分配的长度大小（8 字节），这样才可以实时追踪列表空间的使用情况，当空间不足时，及时分配额外空间。

对于静态大数据的存储，元组更加合适

  1. l = []
  2. l.__sizeof__() // 空列表的存储空间为 40 字节
  3. 40
  4. l.append(1)
  5. l.__sizeof__() 
  6. 72 // 加入了元素 1 之后，列表为其分配了可以存储 4 个元素的空间 (72 - 40)/8 = 4，可以存储 4 个 int
  7. l.append(2) 
  8. l.__sizeof__()
  9. 72 // 由于之前分配了空间，所以加入元素2，列表空间不变
  10. l.append(3)
  11. l.__sizeof__() 
  12. 72 // 同上
  13. l.append(4)
  14. l.__sizeof__() 
  15. 72 // 同上
  16. l.append(5)
  17. l.__sizeof__() 
  18. 104 // 加入元素5之后，列表的空间不足，所以又额外分配了可以存储 4 个元素的空间，也就是 72 + 4 * 8 = 104

上面的例子，大概描述了列表空间分配的过程。

我们可以看到，为了减小每次增加 / 删减操作时空间分配的开销，Python 每次分配空间时都会额外多分配一些，这样的机制（over-allocating）保证了其操作的高效性：增加 / 删除的时间复杂度均为 O(1)。

但是对于元组，情况就不同了。元组长度大小固定，元素不可变，所以存储空间固定。

看了前面的分析，你也许会觉得，这样的差异可以忽略不计。但是想象一下，如果列表和元组存储元素的个数是一亿，十亿甚至更大数量级时，你还能忽略这样的差异吗？

2. 列表和元组的性能

通过学习列表和元组存储方式的差异，我们可以得出结论：元组要比列表更加轻量级一些，所以总体上来说，元组的性能速度要略优于列表。

另外，Python 会在后台，对静态数据做一些资源缓存（resource caching）。通常来说，因为垃圾回收机制的存在，如果一些变量不被使用了，Python 就会回收它们所占用的内存，返还给操作系统，以便其他变量或其他应用使用。

但是对于一些静态变量，比如元组，如果它不被使用并且占用空间不大时，Python 会暂时缓存这部分内存。这样，下次我们再创建同样大小的元组时，Python 就可以不用再向操作系统发出请求，去寻找内存，而是可以直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。

下面的例子，是计算初始化一个相同元素的列表和元组分别所需的时间。我们可以看到，元组的初始化速度，要比列表快 5 倍。

  1. python3 -m timeit 'x=(1,2,3,4,5,6)'
  2. 20000000 loops, best of 5: 9.97 nsec per loop
  3. python3 -m timeit 'x=[1,2,3,4,5,6]'
  4. 5000000 loops, best of 5: 50.1 nsec per loop

但如果是索引操作的话，两者的速度差别非常小，几乎可以忽略不计。

  1. python3 -m timeit -s 'x=[1,2,3,4,5,6]' 'y=x[3]'
  2. 10000000 loops, best of 5: 22.2 nsec per loop
  3. python3 -m timeit -s 'x=(1,2,3,4,5,6)' 'y=x[3]'
  4. 10000000 loops, best of 5: 21.9 nsec per loop

当然，如果你想要增加、删减或者改变元素，那么列表显然更优。原因你现在肯定知道了，那就是对于元组，你必须得通过新建一个元组来完成。

3. 列表和元组的使用场景

那么列表和元组到底用哪一个呢？根据上面所说的特性，我们具体情况具体分析。

1. 如果存储的数据和数量不变，比如你有一个函数，需要返回的是一个地点的经纬度，然后直接传给前端渲染，那么肯定选用元组更合适。

  1. def get_location():
  2.     ..... 
  3.     return (longitude, latitude)

2. 如果存储的数据或数量是可变的，比如社交平台上的一个日志功能，是统计一个用户在一周之内看了哪些用户的帖子，那么则用列表更合适。

  1. viewer_owner_id_list = [] # 里面的每个元素记录了这个viewer一周内看过的所有owner的id
  2. records = queryDB(viewer_id) # 索引数据库，拿到某个viewer一周内的日志
  3. for record in records:
  4.     viewer_owner_id_list.append(record.id)


4. 思考题

1. 想创建一个空的列表，我们可以用下面的 A、B 两种方式，请问它们在效率上有什么区别吗？我们应该优先考虑使用哪种呢？可以说说你的理由。

  1. # 创建空列表
  2. # option A
  3. empty_list = list()
  5. # option B
  6. empty_list = []

密码：aiyc

1.2 字典 VS. 集合

  • 字典：键对值
  • 集合：值

04 | 字典、集合，你真的了解吗？

2. 任务「统计一片文章词频」

目标文本：I_Have_a_Dream.txt/https://www.aiyc.top/1774.html
解决代码如下，不过代码主要为了解决问题，优化后的代码，也会提供。本任务主要是为了让你熟悉各个数据类型的用法。

  1. # -*- coding: utf-8 -*-
  2. # @Time    : 2021/5/11 9:42 下午
  3. # @Author  : AI悦创
  4. # @FileName: words_count_main.py
  5. # @Software: PyCharm
  6. # @Blog    ：http://www.aiyc.top
  7. # @公众号   ：AI悦创
  8. words = []
  11. def find_word_count(words):
  12.     word_count = {}
  13.     # 1.0
  14.     # for word in set(words):
  15.     #     word_count[word] =  0
  16.     # for word in  words:
  17.     #     word_count[word] += 1
  18.     for word in words:
  19.         if word in word_count:
  20.             word_count[word] += 1
  21.         else:
  22.             word_count[word] = 1
  23.     return word_count
  26. with open('I_Have_a_Dream.txt', mode='r', encoding='utf-8') as f:
  27.     """
  28.     f.read() -> type: <class 'str'>
  29.     f.readline() -> type: <class 'str'> -> Read a line
  30.     f.readlines() -> type: <class 'list'> -> Read all
  31.     """
  32.     lines = f.readlines()
  33.     for line in lines:
  34.         line = line.replace(',', '')
  35.         line = line.replace(':', '')
  36.         line = line.replace('?', '')
  37.         line = line.replace('!', '')
  38.         line = line.replace('"', '')
  39.         line = line.replace('\n', '')
  40.         line = line.replace('”', '')
  41.         line = line.replace('.', '')
  42.         line = line.replace(';', '')
  43.         line = line.replace('“', '')
  44.         for word in line.split(' '):
  45.             if word: words.append(word)
  47. if __name__ == '__main__':
  48.     print(len(words))
  49.     print(len(set(words)))
  50.     r = find_word_count(words)
  51.     print(r)

补充：不推荐使用如下方式访问文件：

  1. f = open("text.txt", "w")
  2. f.read()
  3. f.close()

3. 链表

在我们接触的 Python 中的列表，其实就是可以做成链表的形式使用的。

  1. L = [3, 5, 6]
  2. L.append(7)

如何自己实现一个类似的结构呢？可以查询元素、添加元素、插入元素、删除元素
那我们先来简单的、系统的了解一下链表的定义。与数组相似，链表也是一种线性数据结构。这里有一个例子：
image.png
正如你所看到的，链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

链表有两种类型：单链表和双链表。上面给出的例子是一个单链表，这里有一个双链表的例子：
image.png
不过，我这里主要讲解当链表结构。链表是一种线性数据结构，它通过引用字段将所有分离的元素链接在一起。

其实，不就类似我们的铁链。

3.1 定义一个最简单的链表

  1. class IntList(object):
  2.     def __init__(self):
  3.         """
  4.         first:存自己本身的数据
  5.         rest:存下一个节点，也就下一个节点是谁
  6.         """
  7.         self.first = None
  8.         self.rest = None

image.png
image.png

  1. l1 = IntList()
  2. l1.first = 5
  4. l2 = IntList()
  5. l2.first = 10
  7. l3 = IntList()
  8. l3.first = 15

image.png
上面代码其实就可以理解为，创建了每一节车厢，那我们该如何吧车厢链接起来呢？

  1. l1.rest = l2
  2. l2.rest = l3
  3. # 正好使用两行代码连在一起了，也就是火车的两个铁链
  4. # PS: 如果你这么写的话：l1.rest = l2.first > 注意：这将不是链接一个车厢，而是连接一个 Value。
  5. # 所以：l1.rest = l2 才是连接车厢

image.png
但是，要是像下面代码这样写是不行的。这就好像，我们的火车一节连着一节，连的是一整个车厢不是就一部分。其中，lx.first 是一个值。
image.png

可以使用：http://pythontutor.com/ 来讲解

那我们如何输出数据呢？

  1. print("第一节车厢：{}".format(l1.first))
  2. print("第二节车厢：{}".format(l1.rest.first))
  3. print("第三节车厢：{}".format(l1.rest.rest.first))

3.2 「改进」如何只用一个 l 来操作呢？

  1. class IntList(object):
  2.     def __init__(self):
  3.         self.first = None
  4.         self.rest = None
  6. l = IntList()
  7. l.first = 5
  8. l.rest = None
  10. l.rest = IntList()
  11. l.rest.first = 10
  12. l.rest.rest = None
  14. l.rest.rest = IntList()
  15. l.rest.rest.first = 15
  1. class IntList(object):
  2.     def __init__(self):
  3.         self.first = None
  4.         self.rest = None
  6. l = IntList()
  7. l.first = 5
  8. l.rest = IntList()
  9. l.rest.first = 10
  10. l.rest.rest = IntList()
  11. l.rest.rest.first = 15

image.png

3.3 问题

不知道，大家有没有发现，如果这么写的话。我们要写10节车厢或者以上的话不得写死了。

  1. class IntList(object):
  2.     def __init__(self):
  3.         self.first = None
  4.         self.rest = None
  6. l = IntList()
  7. l.first = 5
  8. l.rest = None
  10. l.rest = IntList()
  11. l.rest.first = 10
  12. l.rest.rest = None
  14. l.rest.rest = IntList()
  15. l.rest.rest.first = 15
  17. l.rest.rest.rest = IntList()
  18. l.rest.rest.rest.first = 20
  20. l.rest.rest.rest.rest = IntList()
  21. l.rest.rest.rest.rest.first = 25

image.png
所以，我们虽然实现了链表的结构，但是不完美。我们可以再进一步的去改进一下。

首先，我们肯定不希望之后还是要写一堆 rest 这样肯定是超级麻烦的。

3.4 改进代码

  1. class IntList(object):
  2.     def __init__(self, first, rest):
  3.         self.first = first
  4.         self.rest = rest
  6. l1 = IntList(5, None)
  7. l2 = IntList(10, l1)
  8. l3 = IntList(15, l2)

image.png
当然，我们也可以就用一个 l：

  1. class IntList(object):
  2.     def __init__(self, first, rest):
  3.         self.first = first
  4.         self.rest = rest
  6. l = IntList(5, None)
  7. l = IntList(10, l)
  8. l = IntList(15, l)

image.png
这样写，肯定比之前的书写要简洁。但是又出现问题了，就是我们每一个衔接的数据是显示出来了，但这个问题我们后面解决。接下来，我们先来添加个 size 函数。

3.5 添加一个 size() 方法，方便用户查询链表的大小

这个地方，需要递归作为前置知识：
01-Python 递归详解

  1. def size(self):
  2.     if self.rest is None:
  3.         return 1
  4.     else:
  5.         return 1 + self.rest.size()
  1. 第一次： self.rest()

image.png

  1. 第二次：self.rest.size() —> self.rest.rest is None

image.png

  1. self.rest.rest.size() —> self.rest.rest.rest is None

image.png
接下来，上 GIF：
动画.gif

3.6 不使用递归如何实现？

  1. def get_length(self, linked):
  2.     """方法二"""
  3.     length = 0
  4.     while linked:
  5.         length += 1
  6.         linked = linked.rest
  7.     return length

不过上面写的虽然实现了，但是总体来说有点奇怪，在调用的时候：

  1. print(l.get_length(l)) # 这样调用有点奇怪

所以，进行改进：

  1. def iterative_size(self):
  2.         # l == self 抽象理解
  3.         p = self
  4.         total_size = 0
  5.         while p is not None:
  6.             total_size += 1
  7.             p = p.rest
  8.         return total_size

这样调用就很自然了：

  1. print(l.iterative_size())

3.7 改进

添加一个 get() 方法，方便用户查询某个元素：

  1. def get(self, index):
  2.     if i == 0:
  3.         return self.first
  4.     else:
  5.         return self.rest.get(index-1)
  1. def get_index(self, index):
  2.         '''第二种查询方法'''
  3.         if index < 0：
  4.             return -1
  5.         node = self.first
  6.         for _ in range(index+1):
  7.             node = node.rest
  8.        return node.first

3.8 Question

Week1：Python 基础数据类型和链表 - 图16
现在的链表更像是一个“没穿衣服的”数据结构。
内部数据也是直接爆露出来的，
有些地方也是看起来很奇怪。
image.png
None 和 l 应该是内部的数据，不应该让外部的人看见的。

  1. class IntNode(object):
  2.     def __init__(self, item, next):
  3.         self.item = item
  4.         self.next = next
  6. class SLList(object):
  7.     def __init__(self, x):
  8.         self.first = IntNode(x, None)

我们可以对比一下：

  1. l = SLList(10)
  2. # l = IntList(5, None) 比之前的好

但是目前不能添加多个车厢（链表），添加多个链表的数据都会被覆盖：

  1. l = SLList(5)
  2. l = SLList(10)
  3. l = SLList(15)

动画.gif
所以，我们需要添加一个函数来添加数据。

  1. def add_first(self, x):
  2.     self.first = IntNode(x, self.first)

这样，我们添加数据就是：

  1. l = SLList(5)
  2. l.add_first(10)
  3. l.add_first(15)

image.png
SLList 新增加一个方法叫 get_first() ，用来让用户获取当前链表第一个元素：

  1. def get_first(self):
  2.     return self.first.item

3.9 比较一下

image.png

  1. # filename: compare.py
  2. class IntList(object):
  3.     def __init__(self, f, r):
  4.         """
  5.         first:存自己本身的数据
  6.         rest:存下一个节点，也就下一个节点是谁
  7.         """
  8.         self.first = f
  9.         self.rest = r
  11.     def size(self):
  12.         """方法一"""
  13.         # l == self 抽象理解
  14.         if self.rest is None:
  15.             return 1
  16.         else:
  17.             return 1 + self.rest.size()
  19.     def get_length(self, linked):
  20.         """方法二"""
  21.         length = 0
  22.         while linked:
  23.             length += 1
  24.             linked = linked.rest
  25.         return length
  27.     def iterative_size(self):
  28.         # l == self 抽象理解
  29.         p = self
  30.         total_size = 0
  31.         while p is not None:
  32.             total_size += 1
  33.             p = p.rest
  34.         return total_size
  36.     def get(self, index):
  37.         if i == 0:
  38.             return self.first
  39.         else:
  40.             return self.rest.get(index-1)
  43. l1 = IntList(5, None)
  44. l2 = IntList(10, l1)
  45. l3 = IntList(15, l2)
  46. print(l1.first)
  47. print(l2.first)
  48. print(l3.first)

image.png
image.png

4.0 然而还是有点问题

如果，我破解出了 SLList 里面的变量的名称，一样可以修改，比如：

  1. l.first.next.next = 8

4.1 改进

将 first 变量改为私有变量。

  1. class IntNode(object):
  2.     def __init__(self, item, next):
  3.         self.item = item
  4.         self.next = next
  6. class SLList(object):
  7.     def __init__(self, x):
  8.         self.__first = IntNode(x, None)
  10.     def add_first(self, x):
  11.         self.__first = IntNode(x, self.__first)
  13. l = SLList(5)
  14. l.add_first(10)
  15. l.add_first(15)
  16. # print(l.get_first())

class 里的私有变量只能再 class 的内部访问：

print(l.__first)
AttributeError: 'SLList' object has no attribute '__first'

4.2 为什么要设计私有变量？

将类的内部细节隐藏起来

  • 用户不需要了解太多类的细节
  • 设计者可以拥有更为安全的对于程序的控制全

以汽车来类比

  • 公共的方法或变量：油门、方向盘
  • 私有的方法或变量：燃油管道、旋转阀

4.3 改进

SLList 新增加一个方法叫 add_last() ，用来让用户向链表末尾添加一个元素。

def add_last(self, x):
    p = self.__first
    while p.next is not None:
        p = p.next
    p.next = IntNode(x, None)

l.add_last(20)

image.png

4.4 改进

SLList 新增加一个方法叫 size() ：

def __size(self, p):
    if p.next is None:
        return 1
    else:
        return 1 + self.__size(p.next)

def size(self):
    return self.__size(self.__first)

每次查询 size() 都要把整个链表遍历一遍，是不是低效了？
image.png

# -*- coding: utf-8 -*-
# @Author: AI悦创
# @Date:   2021-10-15 14:50:07
# @Last Modified by:   aiyc
# @Last Modified time: 2021-10-18 15:49:59
class IntNode(object):
    def __init__(self, item, next):
        self.item = item
        self.next = next

class SLList(object):
    def __init__(self, x):
        self.__first = IntNode(x, None)
        self.__size = 1

    def add_first(self, x):
        self.__first = IntNode(x, self.__first)
        self.__size += 1

    def get_first(self):
        return self.first.item

    def add_last(self, x):
        p = self.__first
        while p.next is not None:
            p = p.next
        p.next = IntNode(x, None)
        self.__size += 1

    def __size(self, p):
        if p.next is None:
            return 1
        else:
            return 1 + self.__size(p.next)

    # def size(self):
    #     return self.__size(self.__first)

    def size(self):
        return self.__size

l = SLList(5)
l.add_first(10)
l.add_first(15)
l.add_last(20)
# print(l.__first)

4.5 改进

如果，我希望创建一个空链表呢？

# -*- coding: utf-8 -*-
# @Author: AI悦创
# @Date:   2021-10-18 15:53:48
# @Last Modified by:   aiyc
# @Last Modified time: 2021-10-18 15:58:12
class IntNode(object):
    def __init__(self, item, next):
        self.item = item
        self.next = next

class SLList(object):
    def __init__(self, x=None):
        self.__first = IntNode(x, None)
        self.__size = 1

    def add_first(self, x):
        if self.__first.item is None:
            self.__first.item = x
        else:
            self.__first = IntNode(x, self.__first)
            self.__size += 1

    def get_first(self):
        return self.first.item

    def add_last(self, x):
        p = self.__first
        while p.next is not None:
            p = p.next
        p.next = IntNode(x, None)
        self.__size += 1

    def __size(self, p):
        if p.next is None:
            return 1
        else:
            return 1 + self.__size(p.next)

    # def size(self):
    #     return self.__size(self.__first)

    def size(self):
        return self.__size

l = SLList()
l.add_first(5)
l.add_first(10)
l.add_first(15)
l.add_last(20)
# print(l.__first)