找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 3338|回复: 1

[资源与教程] python内置数据结构大起底-List篇

0

主题

0

帖子

0

积分

贫民

积分
0
Andy_Lkm6z 发表于 2018-8-15 19:03:09 | 显示全部楼层 |阅读模式
本帖最后由 Andy_Lkm6z 于 2018-8-15 19:06 编辑

                        python内置的多种数据结构为编程提供了相当的便利,灵活的使用python中的内置数据类型可以达到事半功倍的效果,本文是对Python一些常用数据类型的整理,并列举出来了一些使用技巧。

使用最多的数据结构 listlist内置了许多方法,常用的如:
  • list.append(x)
  • list.insert(i,x)
  • list.remove(x)
  • list.pop(i)
  • list.index(x, start, end)
  • list.sort(key, reverse)
  • list.reverse()
  • list.copy()

上面的方法中,根据字面意思就能知道方法的作用,灵活使用这些方法,可以实现出来其他的数据结构。
使用list实现stackstack是一个后进先出的数据结构,不理解stack的可以参看我的这篇博客,他的接口一般被这样定义:

1
2
3
4
5
6
7
8
9
10
11
// Stack 接口,java代码表示
public Interface Stack<Item>{
    // 添加一个元素
    public void push(Item item);

    // 移除最后添加的元素,并返回这个元素
    public Item pop();

    // 空监测
    public isEmpty();
}

在python的list中,pop()方法依旧存在,使用不带参数的pop方法,就会从移除list最后一个元素,而push()方法则等价于list的append方法。所以可以直接把list当做stack来使用。
1
2
3
4
stack = []
stack.append('a')  # stack = ['a']
stack.append('b')  # stack = ['b']
last = stack.pop() # last='b', stack=['a']

如果你觉得这样做不是很安全,万一一不小心调用了别的方法,很容易破坏数据结构,那么你可以使用list自己实现一个Stack(虽然这看上去有点脱裤子放屁):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Stack:
    def __init__(self):
        ¦   self._stack = []
   
    def is_empty(self):
        return False if self.stack else True

    def pop(self):
    return self._stack.pop()

    def push(self, item):
        self._stack.append(item)

    def __iter__(self):
        for item in self._stack:
            yield item

使用list实现queuequeue的特点是先进先出,不理解queue的可以参看我的这篇文章,queue的接口一般包含如下几种方法:

1
2
3
4
5
6
7
8
// Queue接口,java代码表示
public Interface Queue<Item>{
    // 入队操作,添加到最右(后)
    public void enqueue(Item);
    //出队操作,移除最早入队的(最左边)
    public Item dequeue();
    public isEmpty();
}

值得庆祝的是,当我们要使用queue的时候并不要自己去编写一个queque的结构,直接使用python
collecti**模块里面的deque即可,当然你也可以尝试自己实现。
deque保留了list的append方法,但是有而外的添加了一个popleft方法,从而实现了dequeque的操作。
1
2
3
4
5
6
from collecti** import deque
queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
queue.append(3) # [1, 2, 3]
first = queue.popleft() # first=1, queue=[2, 3]

list Comprehensi** 列表推导python官方文档列出了三中创建列表的方式,他们分别是迭代器,lambda和列表推导
1
2
3
4
5
6
7
8
9
10
# 使用迭代去
squares = []
for x in range(10):
    squares.append(x**2)

# 使用lambda
squares = list(map(lambda x:x**2, range(10)))

# 使用列表推导
squares = [x**2 for x in range(10)]

列表推导式可以让代码变得更加简洁,解决2SUM问题,使用列表推导只需要一行代码即可暴力求解:

1
2
# 从1到100,两两组合,求所有合为105的组合
[(x, y) for x in range(1,101) y in range(1,101) if (x != y and x+y == 105)]

列表推导式还支持嵌套,如生成一个二维数组

1
2
# 生成一个5*5的二维数组
[[i for i in range(5)] for col in range(5) ]

del操作list之所以能够把很多不同类型的数据放在一个集合里面,其他原因在于python的引用特性,所以对于列表内的任何一个元素都可以直接del。
1
2
3
a = [1, 2, 3, 4, 5]
del a[0] # 可以直接del
del a[2:4] # 也可以按照范围del,范围是左闭右开[2:4)

引用的陷阱
1
[[i for i in range(5)] for col in range(5) ]

这是上面用来创建二维数组的例子,有些比较聪明的人,可能会想到利用python的语言特性,与时代吗可能会这么写:

1
[[i for i in range(5)] * 5]

这看上去很简洁,并且两段代码输出的内容确实一毛一样的,但这并不称得上是聪明,简直愚蠢。事实上,当你尝试修改二维数组的任何一列的时候,每一列都会被改变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
a = [[i for i in range(5)] * 5]
# output a:
# [
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
# ]
a[0][0] = 5
# output a:
# [
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
# ]

出现上面巨大bug的原因就是,内存中事实上只创建了a[0],后面的几列由于使用的是*操作符,都没有创建新的内存空间,本质上他们是同一块内存块。
copy和deepcopy同样的问题还会出现在数组拷贝的时候。

1
2
3
4
a = [[1,2,3], [4,5,6]]
b = a.copy()
a[0][0] = [9]
print(a, b)

上面的代码使用list的copy方法,把a复制了一份给b,按照字面意思理解,也就是说重新开辟了一块儿内存空间,并把a的内容copy进去,这样a和b就完全是两个独立的内存空间了。
但事实上上面的代码,修改了a[0][0]之后,b[0][0]紧跟着也变成了9.这就有点匪夷所思了。这是由于拷贝的深度有限,list默认的copy在一维数组使用并没有太大问题,但一旦数组内包含了其他深一层的引用,copy只会复制最上层,这样对于两块内存块来说,再往下一层,本质上还是使用了同一块内存块。所以就发生了上面匪夷所思的问题。
解决问题的办法是使用深拷贝,python
的list并没有实现deepcopy,但我们可以在copy模块中找到他。
1
2
3
import copy
a = [[1,2,3], [4,5,6]]
b = copy.deepcopy(a)

然后从最外层到最内层,完完全全的拷贝了a,a与b再也不会有哪一个元素共同同一块儿内存了。
总结python对list的实现和功能的设计恰到好处,既不感到臃肿,又绝对够用,毕竟他是python数据结构的核心。在某些情况下你也可以选择不使用list,这个时候可以参见python的collecti**模块,寻找其他适合你的集合类型。
         
回复

使用道具 举报

2

主题

13

帖子

13

积分

贫民

积分
13
wzj9527 发表于 2019-5-28 11:16:52 | 显示全部楼层
这个必须要点赞
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表