Python sparse lists

reference

Every learning data structures like learn 4, never abandon, hope this can insist, refer to: www.bilibili.com/video/BV1E4… If there are any mistakes, please mention them

Most of the stored values are duplicate, so you only need to record the values that are not the same and keep the default values, which can save memory or disk space

Python version implementation

""" 11x11 0 means there are no pieces 1 means white 2 means black
origin_list = []
for i in range(11):
    tempList = []
    for j in range(11):
        tempList.append(0)
    origin_list.append(tempList)

origin_list[0] [1] = 1
origin_list[1] [2] = 2
origin_list[3] [4] = 2


# Convert to a sparse list
def listToSparseList(l: list) - >list:
    # Number of non-zero elements
    num = 0
    # sparse array
    sparseList = []
    for i in range(len(l)):
        for j in range(len(l)):
            ifl[i][j] ! =0:
                num += 1
                t = (i, j, l[i][j])
                sparseList.append(t)
    sparseList.append((11.11, num))
    return sparseList


# Sparse list converts the original list
def sparseListToList(l: list) - >list:
    line, row, _ = l[-1]
    restore_list = []
    for i in range(line):
        tempList = []
        for j in range(row):
            tempList.append(0)
        restore_list.append(tempList)
    for i in range(len(l)-1):
        x, y, z = l[i]
        restore_list[x][y] = z
    return restore_list


Print the original checkerboard
for l in origin_list:
    print(l)

# Convert to a sparse list
sparseList = listToSparseList(origin_list)
for i in sparseList:
    print(i)

The sparse list is converted to the original list
restoreList = sparseListToList(sparseList)
for l in restoreList:
    print(l)

Copy the code