Python字典追加数组时旧条目被更新的问题排查

在实现支持自定义扩容算法的ArrayList时，编写analyzePerformance函数测试性能时发现：每次向字典中添加包含不同长度sizes数组的条目后，旧字典条目里的sizes数组也会被更新为最长的版本。

相关代码 #

ArrayList类代码 #

class ArrayList:
    def __init__(self, growfn):
        '''Initializes the empty ArrayList with the specified growth function.'''
        self.size = 0
        self.used = 0
        self.array = []
        self.grow = growfn

    def get(self, index):
        if index < self.size:
            return self.array[index]
        # exception handling
        return None

    def add(self, value):
        if self.used == self.size:
            newSize = self.grow(self.size)
            if newSize <= self.size:
                # exception handling
                return
            newArray = self.array[:]+[None for i in range(self.size,newSize)]
            self.array = newArray
            self.size = newSize
        self.array[self.used] = value
        self.used = self.used + 1
        return None

测试函数代码 #

def analyzePerformance(nList, gfn, tries):
    data = []
    sizes_array = []
    averages = []
    arr = ArrayList(gfn)
    for num in nList:
        for j in range(tries):
            current_size = 0
            start = time()
            while arr.size < num:
                arr.add(None)
                if arr.size != current_size:
                    sizes_array.append(arr.size)
                    current_size = arr.size
            end = time()
            averages.append(end - start)
        data.append(dict({'grow': gfn, 'N': num, 'seconds': mean(averages), 'sizes': sizes_array})) 
    return data

调用代码 #

def main():
    for result in analyzePerformance([1,10,100], double, 11):
        print(result)

当前输出 #

{'grow': <function double at 0x7f3274eb4f28>, 'N': 1, 'seconds': 3.034418279474432e-07, 'sizes': [1, 2, 4, 8, 16, 32, 64, 128]}
{'grow': <function double at 0x7f3274eb4f28>, 'N': 10, 'seconds': 4.659999500621449e-07, 'sizes': [1, 2, 4, 8, 16, 32, 64, 128]}
{'grow': <function double at 0x7f3274eb4f28>, 'N': 100, 'seconds': 7.369301535866477e-07, 'sizes': [1, 2, 4, 8, 16, 32, 64, 128]}

期望输出 #

{'grow': <function double at 0x7f3274eb4f28>, 'N': 1, 'seconds': 3.034418279474432e-07, 'sizes': [1]}
{'grow': <function double at 0x7f3274eb4f28>, 'N': 10, 'seconds': 4.659999500621449e-07, 'sizes': [1, 2, 4, 8, 16]}
{'grow': <function double at 0x7f3274eb4f28>, 'N': 100, 'seconds': 7.369301535866477e-07, 'sizes': [1, 2, 4, 8, 16, 32, 64, 128]}

问题原因 #

Python中列表是可变对象，你在analyzePerformance函数里只初始化了一次sizes_array，所有添加到data列表的字典，其sizes字段都引用了同一个sizes_array对象。后续循环中对sizes_array的append操作，会直接修改这个共享的列表，导致所有旧字典条目里的sizes都跟着变化。

解决方案 #

有两种可行的修复方式：

方式1：每次循环重新初始化sizes_array #

将sizes_array = []放到for num in nList:循环内部，确保每个num对应的测试都使用独立的列表：

def analyzePerformance(nList, gfn, tries):
    data = []
    averages = []
    arr = ArrayList(gfn)
    for num in nList:
        sizes_array = []  # 移到循环内部，每次循环创建新列表
        for j in range(tries):
            current_size = 0
            start = time()
            while arr.size < num:
                arr.add(None)
                if arr.size != current_size:
                    sizes_array.append(arr.size)
                    current_size = arr.size
            end = time()
            averages.append(end - start)
        data.append(dict({'grow': gfn, 'N': num, 'seconds': mean(averages), 'sizes': sizes_array})) 
    return data

方式2：添加字典时创建列表副本 #

如果需要保留外部的sizes_array，可以在添加到字典时，创建当前列表的副本，避免引用共享：

# 修改data.append的行，用copy()创建副本
data.append(dict({'grow': gfn, 'N': num, 'seconds': mean(averages), 'sizes': sizes_array.copy()})) 
# 或者用list()转换：sizes: list(sizes_array)

内容的提问来源于stack exchange，提问作者Anon