[Python] 二维数组初始化实践

背景

参考博客Python二维数组初始化问题_NobiShinnosuke的博客-CSDN博客_python 二维数组初始化，文中提到正确的初始化方式是a = [[0 for j in range(n)] for i in range(n)]，错误的初始化方式a = [0 * n] * n。

第一种正确初始化方式：n * n个元素直接从第一个元素生成而来，一开始的时候大伙都是第一个元素的快捷方式，找任意行任意列的元素都会找到第一个元素。当其他元素有了自己的值以后，就变成独立的元素啦。
第二种初始化方式：先由一个元素生成一行，再以这一行生成其他行。所以，即使其他行的某个元素改变了，其实也只是在改变第一行的元素。

本质上，两种初始化方式，是深拷贝与浅拷贝的区别（python中的深拷贝和浅拷贝 - 丫丫tester - 博客园）

最直观的理解就是：
1.深拷贝，拷贝的程度深，自己新开辟了一块内存，将被拷贝内容全部拷贝过来了；
2.浅拷贝，拷贝的程度浅，只拷贝原数据的首地址，然后通过原数据的首地址，去获取内容。
两者的优缺点对比：
（1）深拷贝拷贝程度高，将原数据复制到新的内存空间中。改变拷贝后的内容不影响原数据内容。但是深拷贝耗时长，且占用内存空间。
（2）浅拷贝拷贝程度低，只复制原数据的地址。其实是将副本的地址指向原数据地址。修改副本内容，是通过当前地址指向原数据地址，去修改。所以修改副本内容会影响到原数据内容。但是浅拷贝耗时短，占用内存空间少。

实践

实践四种方式：

方式一：

dp_ = [0] * (l2 + 1)
 
dp = [dp_ for i in range(l1 + 1)]

方式二：

dp_ = [0 for j in range(l2 + 1)]
 
dp = [dp_ for i in range(l1 + 1)]

方式三：

dp = [[0] * (l2 + 1)]*(l1 + 1)

方式四：

dp = [[0] * (l2 + 1) for i in range(l1 + 1)]

方式五：

dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]

其中，只有方式四、方式五是work的。

方式一、二、三本质上都是先由一个元素生成一行，再以这一行生成其他行。

方式三比较明显，需要注意下方式一、方式二，错误比较隐晦。

验证

最长公共子串这道题可以使用动态规划来做，用上面五种初始化二维数组的方式验证下。

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。 

数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)

示例1

输入：

"1AB2345CD","12345EF"

返回值：

"2345"

代码

#!/usr/bin/env python
# coding=utf-8
# Python version is 2.7,
 
def findCommonStr(str1, str2, init_type=1):
    l1 = len(str1)
    l2 = len(str2)
    if init_type==1:
        dp_ = [0] * (l2 + 1)
        dp = [dp_ for i in range(l1 + 1)]
    elif init_type==2:
        dp_ = [0 for j in range(l2 + 1)]
        dp = [dp_ for i in range(l1 + 1)]
    elif init_type==3:
        dp = [[0] * (l2 + 1)] * (l1 + 1)
    elif init_type==4:
        dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
    else:
        dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]
 
    max_length = 0
    max_last_index = 0
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                print(i, j, dp[i - 1][j - 1], dp[i][j])
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    max_last_index = i - 1
            else:
                dp[i][j] = 0
    return str1[max_last_index - max_length + 1:max_last_index + 1]
 
 
if __name__ == '__main__':
    print('1')
    res = findCommonStr('abcdefg', 'eebcdwwf', 1)
    print('result:',res)
 
    print('2')
    res = findCommonStr('abcdefg', 'eebcdwwf', 2)
    print('result:', res)
 
    print('3')
    res = findCommonStr('abcdefg', 'eebcdwwf', 3)
    print('result:', res)
 
    print('4')
    res = findCommonStr('abcdefg', 'eebcdwwf', 4)
    print('result:', res)
 
    print('5')
    res = findCommonStr('abcdefg', 'eebcdwwf', 5)
    print('result:', res)

打印结果：

1
2 3 0 1
3 4 0 1
4 5 0 1
5 1 0 1
5 2 1 2
6 8 0 1
result: de
2
2 3 0 1
3 4 0 1
4 5 0 1
5 1 0 1
5 2 1 2
6 8 0 1
result: de
3
2 3 0 1
3 4 0 1
4 5 0 1
5 1 0 1
5 2 1 2
6 8 0 1
result: de
4
2 3 0 1
3 4 1 2
4 5 2 3
5 1 0 1
5 2 0 1
6 8 0 1
result: bcd
5
2 3 0 1
3 4 1 2
4 5 2 3
5 1 0 1
5 2 0 1
6 8 0 1
result: bcd
 
Process finished with exit code 0

内存地址

id() 函数返回对象的唯一标识符，标识符是一个整数。

CPython 中 id() 函数用于获取对象的内存地址。

if __name__ == '__main__':
    l1 = 1
    l2 = 1
    dp_ = [0] * (l2 + 1)
    dp = [dp_ for i in range(l1 + 1)]
    print('dp_ = [0] * (l2 + 1)')
    print('dp = [dp_ for i in range(l1 + 1)]')
    print(id(dp[0]))
    print(id(dp[1]))
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
    dp[0][0] = 1
    print('dp[0][0] = 1')
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
 
 
    n = 2
    dp_ = [0 for j in range(l2 + 1)]
    dp = [dp_ for i in range(l1 + 1)]
    print('dp_ = [0 for j in range(l2 + 1)]')
    print('dp = [dp_ for i in range(l1 + 1)]')
    print(id(dp[0]))
    print(id(dp[1]))
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
    dp[0][0] = 1
    print('dp[0][0] = 1')
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
 
    dp = [[0] * (l2 + 1)] * (l1 + 1)
    print('[[0] * (l2 + 1)] * (l1 + 1)')
    print(id(dp[0]))
    print(id(dp[1]))
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
    dp[0][0] = 1
    print('dp[0][0] = 1')
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
 
    dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
    print('dp = [[0] * (l2 + 1) for i in range(l1 + 1)]')
    print(id(dp[0]))
    print(id(dp[1]))
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
    dp[0][0] = 1
    print('dp[0][0] = 1')
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
 
    dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]
    print('dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]')
    print(id(dp[0]))
    print(id(dp[1]))
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))
    dp[0][0] = 1
    print('dp[0][0] = 1')
    print(id(dp[0][0]))
    print(id(dp[0][1]))
    print(id(dp[1][0]))
    print(id(dp[1][1]))

打印结果：

dp_ = [0] * (l2 + 1)
dp = [dp_ for i in range(l1 + 1)]
4349485256
4349485256
4304854112
4304854112
4304854112
4304854112
dp[0][0] = 1
4304854144
4304854112
4304854144
4304854112
 
 
dp_ = [0 for j in range(l2 + 1)]
dp = [dp_ for i in range(l1 + 1)]
4349487048
4349487048
4304854112
4304854112
4304854112
4304854112
dp[0][0] = 1
4304854144
4304854112
4304854144
4304854112
 
 
dp = [[0] * (l2 + 1)] * (l1 + 1)
4349485256
4349485256
4304854112
4304854112
4304854112
4304854112
dp[0][0] = 1
4304854144
4304854112
4304854144
4304854112
 
 
dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
4349486792
4349486728
4304854112
4304854112
4304854112
4304854112
dp[0][0] = 1
4304854144
4304854112
4304854112
4304854112
 
 
dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]
4349485256
4349216072
4304854112
4304854112
4304854112
4304854112
dp[0][0] = 1
4304854144
4304854112
4304854112
4304854112
 
 
 
Process finished with exit code 0

对比上面五种方式，说明：

在正确的初始化方式中，对于二维数组的每一行，每行的地址都不同。对于单个元素而言，都是直接从第一个元素生成而来，一开始的时候大伙都是第一个元素的快捷方式，找任意行任意列的元素都会找到第一个元素。当其他元素有了自己的值以后，就变成独立的元素，且只会改变自己，不会改变同一列其他行的元素。

而如果先由一个元素生成一行，再以这一行生成其他行，每行的地址都相同。所以，即使其他行的某个元素改变了，其实也只是在改变第一行的元素。