稀疏数组

数据结构
#1

稀疏数组

之前有听到过这个数据结构,今天才彻底研究了一下

在二维数组种,如果存在大量的空位(默认为0或者其他)。会比较浪费内存,可以通过一种数据结构(稀疏数组)来表示二维数组,但是不会浪费这么多的内存。

示例

一个二维数组

[[ 0][ 0][ 0][22][ 0][ 0][15]]
[[ 0][11][ 0][ 0][ 0][17][ 0]]
[[ 0][ 0][ 0][-6][ 0][ 0][ 0]]
[[ 0][ 0][ 0][ 0][ 0][39][ 0]]
[[91][ 0][ 0][ 0][ 0][ 0][ 0]]
[[ 0][ 0][28][ 0][ 0][ 0][ 0]]

可以看到,大部分的位置都是空的(默认0)。真正的有效数据只有 8 个。一个int 4 字节一共占用了:168 字节

压缩为一个稀疏数组

[[ 6][ 7][ 8]]
	* 6 表示原始数组有6行
	* 7 表示原始数组有7列
	* 8 表示一共有8个有效数据(非0)
[[ 0][ 3][22]]
	* 0 表示第0行
	* 3 表示第3列
	* 22 表示第0行第3列的值是22	
[[ 0][ 6][15]]
	* 0 表示第0行
	* 6 表示第6列
	* 15 表示第0行第6列的值是22
[[ 1][ 1][11]]
[[ 1][ 5][17]]
[[ 2][ 3][-6]]
[[ 3][ 5][39]]
[[ 4][ 0][91]]
[[ 5][ 2][28]]

稀疏数组也是一个二维数组,但是只有3列。第一行记录原始数组的元信息:列数行数有效数据数
从第二行及其以后,每一行表示一个有效数据在原始数组中的行号,列号,值。

内存占用:108 字节。必原始数组少占用了 60 字节的空间

Pyhon实现

def compressed_array(arr):
    # 有效的数据量
    count = 0
    for i in arr:
        for x in i:
            if x != 0:
                count += 1

    # 列数
    col = len(arr)

    # 行数
    row = len(arr[0])

    # 稀疏数组
    ret = []

    # 初始化元信息
    meta_info = [col, row, count]
    ret.append(meta_info)

    # 遍历有效数据
    for i, v in enumerate(arr):
        for x, z in enumerate(v):
            if z != 0:
                data_info = [i, x, z]
                ret.append(data_info)

    return ret


def decompression_array(arr):

    ret = []

    # 行数
    col = arr[0][0]

    # 列数
    row = arr[0][1]

    for i in range(col):
        # 初始化子数组
        sub_arr = [0 for i in range(row)]
        ret.append(sub_arr)

    for i, sub_arr in enumerate(arr):
        # 忽略第一行元数据
        if i != 0:
            ret[sub_arr[0]][sub_arr[1]] = sub_arr[2]

    return ret

# 转换原始数组为稀疏数组
result = compressed_array([[0, 0, 0, 22, 0, 0, 15],
                        [0, 11, 0, 0, 0, 17, 0],
                        [0, 0, 0, -6, 0, 0, 0],
                        [0, 0, 0, 0, 0, 39, 0],
                        [91, 0, 0, 0, 0, 0, 0],
                        [0, 0, 28, 0, 0, 0, 0]])

print(result)

# 转换稀疏数组为原始数组
result = decompression_array(result)

print(result)

大多数这种问题,都是一个空间和时间的抉择。

#2

总之。牛逼

#3

业务中那些场景能用到?

#4

我也不知道。以后遇到使用场景也许就知道了。