python基础-数据结构-序列类型--list、tuple、range

序列类型

通用序列类型

大多数序列类型，包括可变类型和不可变类型，都支持以下表格中的操作。collections.abc.Sequence ABC（抽象基类）被提供用来更容易地在自定义序列类型上正确地实现这些操作。

此表按优先级升序列出了序列操作。在表格中，s 和 t 是具有相同类型的序列，n，i，j 和 k 是整数，而 x 是任何满足 s 所规定的类型和值限制的任意对象。

序列操作表

需要注意的是，in 和 not in 操作具有与比较操作相同的优先级。+ (拼接) 和 * (重复) 操作具有与对应数值运算相同的优先级。

• 序列比较: 相同类型的序列支持比较，特别地，tuple 和 list 的比较是通过比较对应元素的字典顺序。这意味着想要比较结果相等，则每个元素比较结果都必须相等，并且两个序列长度必须相同。

• 迭代器终止行为: 可变序列的正向和逆向迭代器使用一个索引来访问值。即使底层序列被改变，该索引也将持续向前（或向后）步进。迭代器只有在遇到 IndexError 或 StopIteration 时才会终结（或是当索引降至零以下）。

• 成员检测: in 和 not in 操作在通常情况下仅被用于简单的成员检测，但某些专门化序列（例如 str, bytes 和 bytearray）也使用它们进行子序列检测。

>>> "gg" in "eggs"
True
1
2

• 多重引用问题: 小于 0 的 n 值会被当作 0 来处理（生成一个与 s 同类型的空序列）。序列 s 中的项不会被拷贝，它们会被多次引用。例如：

>>> lists = [[]] * 3
>>> lists
[[], [], []]
>>> lists[0].append(3)
>>> lists
[[3], [3], [3]]
1
2
3
4
5
6

要避免这种问题，可以创建不同列表为元素的列表：

>>> lists = [[] for i in range(3)]
>>> lists[0].append(3)
>>> lists[1].append(5)
>>> lists[2].append(7)
>>> lists
[[3], [5], [7]]
1
2
3
4
5
6

• 负索引: 如果 i 或 j 为负值，则索引顺序是相对于序列 s 的末尾。索引号会被替换为 len(s) + i 或 len(s) + j。但要注意 -0 仍然为 0。

• 切片操作: s 从 i 到 j 的切片定义为所有满足 i <= k < j 的索引号 k 的项组成的序列。如果 i 或 j 大于 len(s), 则使用 len(s)。如果 i 被省略或为 None，则使用 0。如果 j 被省略或为 None，则使用 len(s)。如果 i 大于等于 j，则切片为空。

• 步长切片: s 从 i 到 j 步长为 k 的切片定义为所有满足 0 <= n < (j-i)/k 的索引号 x = i + n*k 的项组成的序列。当 k 为正值时，i 和 j 会被减至不大于 len(s)。当 k 为负值时，i 和 j 会被减至不大于 len(s) - 1。如果 i 或 j 被省略或为 None，它们会成为“终止”值。请注意，k 不可为零。如果 k 为 None，则当作 1 处理。

• 拼接开销: 拼接不可变序列总是会生成新的对象。这意味着通过重复拼接来构建序列的运行时开销将会基于序列总长度的乘方。为了获得线性的运行时开销，建议改用以下替代方案：

  • 对于 str 对象，可以构建一个列表并在最后使用 str.join()，或是写入一个 io.StringIO 实例并在结束时获取它的值。
  • 对于 bytes 对象，可以使用 bytes.join() 或 io.BytesIO，或者使用 bytearray 对象进行原地拼接。bytearray 对象是可变的，并且具有高效的重分配机制。
  • 对于 tuple 对象，建议扩展 list 类。
  • 对于其他类型，请查看相应的文档。

• 序列拼接和重复: 某些序列类型（例如 range）仅支持遵循特定模式的项序列，因此并不支持序列拼接或重复。

• 索引方法: 当 x 在 s 中找不到时，index 方法会引发 ValueError。不是所有实现都支持传入额外参数 i 和 j。这两个参数允许高效地搜索序列的子序列。传入这两个额外参数大致相当于使用 s[i:j].index(x)，但是不会复制任何数据，并且返回的索引是相对于序列的开头而非切片的开头。

通过实现上述这些操作，我们可以自定义自己的序列类型，使其符合 collections.abc.Sequence ABC 的要求，从而使这些操作在自定义序列类型上能够正确运行。

自定义序列

以下是一个简单的示例，展示如何创建一个自定义序列类型并实现部分序列操作，其中__getitem__(self,item)和__len(self)__是抽象方法，必须实现，这两个方法与许多操作都相关：

class Sequence(Collection[_T_co], Reversible[_T_co], Generic[_T_co]):
    @overload
    @abstractmethod
    def __getitem__(self, index: int) -> _T_co: ...
    @overload
    @abstractmethod
    def __getitem__(self, index: slice) -> Sequence[_T_co]: ...
    # Mixin methods
    def index(self, value: Any, start: int = 0, stop: int = ...) -> int: ...
    def count(self, value: Any) -> int: ...
    def __contains__(self, value: object) -> bool: ...
    def __iter__(self) -> Iterator[_T_co]: ...
    def __reversed__(self) -> Iterator[_T_co]: ...
1
2
3
4
5
6
7
8
9
10
11
12
13

from collections.abc import Sequence


class MySequence(Sequence):
    def __init__(self, data):
        self._data = data

    def __len__(self):
        return len(self._data)

    def __getitem__(self, index):
        return self._data[index]

    def __contains__(self, item):
        return item in self._data

    def __iter__(self):
        return iter(self._data)

    def __repr__(self):
        return f'MySequence({self._data})'

    def __mul__(self, other):
        if isinstance(other, int):
            return MySequence(self._data*3)
        raise TypeError
    def __add__(self, other):
        if isinstance(other, MySequence):
            return MySequence(self._data + other._data)
        raise TypeError
    
s = MySequence([2,2,3,4])
print(s)
print(s.count(1))
print(s.index(3))
print(s[1:])
print(s[1])
print(s * 3)
print(min(s))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

其中index()与count()是两个特殊的函数，如果是像示例这种简单的存储结构，不需要重载就可以使用，但是，一些稍微复杂的存储就需要重写index()与count()。

from collections.abc import Sequence
from typing import Tuple, List


class MySequence(Sequence):

    def __init__(self, x, y):
        assert len(x) == len(y)
        self.x = x
        self.y = y

    def __getitem__(self, index):
        if isinstance(index, slice):
            return MySequence(self.x[index], self.y[index])
        elif isinstance(index, int):
            return self.x[index], self.y[index]
        raise TypeError(f"Invalid index type: {type(index)}, must be int or slice")

    def __len__(self):
        return len(self.x)

    def __contains__(self, item):
        if isinstance(item, Tuple) or isinstance(item, List):
            if len(item) == 2:
                if item[0] in self.x and item[1] in self.y:
                    return True
        return False

    def __repr__(self):
        return f"MySequence(x:{self.x!r}, y:{self.y!r})"

    def __add__(self, other):
        if isinstance(other, MySequence):
            return MySequence(self.x + other.x, self.y + other.y)
        else:
            raise TypeError(f"Invalid index type: {type(other)}, must be {type(self)}")

    def index(self, value, start = 0, stop = None):
        if isinstance(value, Tuple) or isinstance(value, List):
            if len(value) == 2:
                for idx, x in enumerate(self.x):
                    if idx < start:
                        continue
                    if stop is not None and idx >= stop:
                        break
                    if x == value[0] and self.y[idx] == value[1]:
                        return idx
        return -1
    
    def __iter__(self):
        return iter(zip(self.x, self.y))

    def count(self, value):
        if isinstance(value, Tuple) or isinstance(value, List):
            if len(value) == 2:
                count = 0
                for x, y in zip(self.x, self.y):
                    if x==value[0] and y==value[1]:
                        count += 1
                return count
        return 0

if __name__ == "__main__":
    s = MySequence([1,2,1,4,5], [6,7,6,9,10])
    print(s)
    print(s[0:3])
    print(s[2])
    print(len(s))
    a = MySequence([2,3,4], [5,6,7])
    print(s + a)
    # print(s + 3)
    print(s.index((1,6), start=2))
    print((1,2) not in s)
    print((1,6) in s)
    print(s.count([1,6]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

不可变序列类型

不可变序列类型普遍实现而可变序列类型未实现的唯一操作就是对 hash() 内置函数的支持。
这种支持允许不可变类型，例如 tuple 实例被用作 dict 键，以及存储在 set 和 frozenset 实例中。除了tuple以外，pyhon中还有4个基本的不可变序列：字符串str，冻结集合frozenset,字节串bytes,range对象。
尝试对包含有不可哈希值的不可变序列进行哈希运算将会导致 TypeError。

可变序列类型

在 Python 中，可变序列类型的操作主要集中在 collections.abc.MutableSequence 抽象基类 (ABC) 中。这个 ABC 提供了一些方法，以便在自定义可变序列类型时更容易正确地实现这些操作。

下面列出了一些常见的可变序列操作，其中 s 是可变序列类型的实例，t 是任意可迭代对象，而 x 是符合对 s 所规定类型与值限制的任何对象 (例如，bytearray 仅接受满足 0 <= x <= 255 值限制的整数)。

可变序列操作

下面是一个包含常见可变序列操作的表格，其中 s 是可变序列类型的实例，t 是任意可迭代对象，而 x 是符合对 s 所规定类型与值限制的任何对象：

通过使用 collections.abc.MutableSequence 抽象基类 (ABC)，可以实现这些操作，使自定义的可变序列类型支持标准的序列操作。

自定义可变序列类型

通过继承 collections.abc.MutableSequence 并实现其抽象方法，可以自定义自己的可变序列类型。下面是一个简单的示例：

from collections.abc import MutableSequence

class MyList(MutableSequence):
    def __init__(self, initial=None):
        self._data = list(initial) if initial is not None else []

    def __len__(self):
        return len(self._data)

    def __getitem__(self, index):
        return self._data[index]

    def __setitem__(self, index, value):
        self._data[index] = value

    def __delitem__(self, index):
        del self._data[index]

    def insert(self, index, value):
        self._data.insert(index, value)

ml = MyList([1, 2, 3])
ml.append(4)
print(ml)  # 输出: [1, 2, 3, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

通过实现这些方法，可以确保自定义的序列类型支持所有标准的可变序列操作，一般都是对list,dict等添加额外操作或者限制等，想要自己定一个多维的或者复杂的数据结构，使用python的效率是很低的，只能使用cpython重构。

list

列表是Python中常用的数据结构之一，它是一种可变序列，通常用于存放同类项目的集合。本文将介绍列表的构建方式以及列表的排序操作。

构建列表

在Python中，可以使用多种方式来构建列表：

1. 使用一对方括号表示空列表：[]
2. 使用方括号，其中的项以逗号分隔：[a]、[a, b, c]
3. 使用列表推导式：[x for x in iterable]
4. 使用列表构造器 list() 或 list(iterable)

构造器将根据提供的可迭代对象创建一个列表，如果没有给出参数，则创建一个空列表。例如，list('abc') 返回 ['a', 'b', 'c'] 而 list((1, 2, 3)) 返回 [1, 2, 3]。

排序操作

Python列表提供了丰富的排序操作，其中最常用的是 sort() 方法。该方法会对列表进行原地排序，接受两个仅限以关键字形式传入的参数：key 和 reverse。

• key 参数指定一个函数，用于从每个列表元素中提取比较键，默认为 None，表示直接对列表项排序。
• reverse 参数为一个布尔值，如果设为 True，则按反向顺序比较进行排序。

需要注意的是，sort() 方法会原地修改列表，不会返回排序后的新列表，如果需要新的已排序列表，应该使用 sorted() 函数。

from functools import cmp_to_key
def cmp(e1, e2):
    if abs(e1) > abs(e2):
        return 1
    elif abs(e1) == abs(e2):
        return 0
    return -1
ele = [1,-6,3,7,-3,8,-7]
ele.sort()
print(ele)
ele.sort(reverse=True)
print(ele)
ele.sort(key=abs)
print(ele)
ele.sort(key=cmp_to_key(cmp))
print(ele)

[-7, -6, -3, 1, 3, 7, 8]
[8, 7, 3, 1, -3, -6, -7]
[1, 3, -3, -6, 7, -7, 8]
[1, 3, -3, -6, 7, -7, 8]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

元组

元组是不可变序列，通常用于储存异构数据的多项集（例如由 enumerate() 内置函数所产生的二元组）。 元组也被用于需要同构数据的不可变序列的情况（例如允许存储到 set 或 dict 的实例）。
在 Python 中，可以用多种方式来构建元组：

1. 使用一对圆括号来表示空元组: ()
2. 使用一个后缀的逗号来表示单元组: a, 或 (a,)
3. 使用以逗号分隔的多个项: a, b, c 或 (a, b, c)
4. 使用内置的 tuple() 构造器：tuple() 或 tuple(iterable)

构造器将根据提供的可迭代对象创建一个元组，如果没有给出参数，则创建一个空元组。例如，tuple('abc') 返回 ('a', 'b', 'c') 而 tuple([1, 2, 3]) 返回 (1, 2, 3)。

决定生成元组的其实是逗号而不是圆括号。圆括号只是可选的，生成空元组或需要避免语法歧义的情况除外。例如，f(a, b, c) 是在调用函数时附带三个参数，而 f((a, b, c)) 则是在调用函数时附带一个三元组。

range对象

请参考python内置函数range

参考
https://docs.python.org/zh-cn/3/library/stdtypes.html#lists