为了 1% 情形,牺牲 99% 情形下的性能:蜗牛般的 Python 深拷贝

最近使用 Python 一个项目,发现 Python 的深拷贝 copy.deepcopy 实在是太慢了。

相关背景

在 Python 中, 我们有两种拷贝对象的方式:浅拷贝和深拷贝。浅拷贝和深拷贝都可以在 copy 模块中找到, 其中 copy.copy() 进行浅拷贝操作, copy.deepcopy() 进行深拷贝操作。浅拷贝是在另一块地址中创建一个新的对象,但是新对象内的子对象引用指向源对象的子对象。如果这时候我们修改源对象的子对象的属性, 新对象中子对象的属性也会改变。为了获取一个和源对象没有任何关系的全新对象,我们需要深拷贝。深拷贝是在另一块地址中创建一个新的对象,同时对象内的子对象也是新开辟的,和源对象对比仅仅是值相同。

下面用一个例子说明浅拷贝和深拷贝的区别。下面的代码将输出 “b [2,2,3]” 和 “c [1,2,3]”。

import copy
class A:
   def __init__(self):
       array = [1,2,3]
a = A()
b = copy.copy(a)
c = copy.deepcopy(a)
a.array[0] = 2
print "b",b.array
print "c",c.array

b 是由 a 浅拷贝而来,c 是由 a 深拷贝而来。修改 a.array 之后, b.array 也随之发生变化。其实 a.array 和 b.array 指向同一个对象。而 c.array 则保持原样。

深拷贝比浅拷贝符合人类的直觉,代价就是深拷贝实在是太慢了。下面代码中,case1 和 case2 是等价的。在我的机器上测试,case1 不到一秒,而 case2 则达到了 十秒。那么深拷贝为什么那么慢呢?

import copy
class A:
   def __init__(self):
       array = [1,2,3]
a = [A() for i in xrange(100000)]
a[10].array[0] = 100
### case1
b = [A() for i in xrange(100000)]
for i in xrange(100000):
    for j in xrange(3):
       b[i].array[j] = a[i].array[j]
### case2
c = copy.deepcopy(a)

深拷贝分析

为了搞清楚为什么 Python 深拷贝这么慢,我阅读了下 Python 2.7 版本的 copy.deepcopy 的实现: https://github.com/python/cpython/blob/2.7/Lib/copy.py。其大体结构为:

def deepcopy(x, memo=None, _nil=[]):

    if memo is None:
        memo = {}

    d = id(x)
    y = memo.get(d, _nil)
    if y is not _nil:
        return y

    cls = type(x)

    copier = _deepcopy_dispatch.get(cls)
    if copier:
        y = copier(x, memo)
    else:
        ... ## 其他特殊的拷贝方式

    memo[d] = y
    return y

其中 memo 保存着所有拷贝过的对象。为什么要设置 memo 呢?在某些特殊情况下,一个对象的相关对象可以指向它自己,比如双向链表。如果不将拷贝过的对象存着,那程序将陷入死循环。另外一个值得注意的点是 copier = _deepcopy_dispatch.get(cls),这行代码根据待拷贝对象的类型,选择相应的拷贝函数。可选的拷贝函数有:用于拷贝基本数据类型的 _deepcopy_atomic, 用于拷贝列表的 _deepcopy_list,用于拷贝元组 _deepcopy_tuple,用于拷贝字典 的 _deepcopy_dict,用于拷贝自定义对象的 _deepcopy_inst 等等。其中比较重要的拷贝函数 __deepcopy_inst 代码如下所示:如果对象有 _ _ deepcopy _ _ 函数,则使用该函数进行拷贝;如果没有,那么先拷贝初始构造参数,然后构造一个对象,再拷贝对象状态。

def _deepcopy_inst(x, memo):
    if hasattr(x, '__deepcopy__'):
        return x.__deepcopy__(memo)
    if hasattr(x, '__getinitargs__'):
        args = x.__getinitargs__()
        args = deepcopy(args, memo)
        y = x.__class__(*args)
    else:
        y = _EmptyClass()
        y.__class__ = x.__class__
    memo[id(x)] = y
    if hasattr(x, '__getstate__'):
        state = x.__getstate__()
    else:
        state = x.__dict__
    state = deepcopy(state, memo)
    if hasattr(y, '__setstate__'):
        y.__setstate__(state)
    else:
        y.__dict__.update(state)
    return y

深拷贝需要维护一个 memo 用于记录已经拷贝的对象,这是它比较慢的原因。在绝大多数情况下,程序里都不存在相互引用。但作为通用模块,Python 深拷贝必须为了这 1% 情形,牺牲 99% 情形下的性能。

一个场景

上面给出了深拷贝效率对比的结果,已经可以看出深拷贝很慢了,但没有办法直观感受深拷贝拖累整个程序的运行速度。下面给一个实际项目的例子,最近在写的一些游戏环境。玩家程序获得游戏环境给出的信息,当前玩家程序选择合适的动作,游戏环境根据该动作推进游戏逻辑;重复上述过程,直到分出胜负;整个过程如下所示。给玩家程序的信息必须从游戏环境深拷贝出来。如果给玩家的信息是从游戏环境浅拷贝出来的,那么玩家程序有可能通过信息获取游戏秘密或者操纵游戏。

我们已经知道默认的深拷贝很慢。为了改进深拷贝的效率,我们在信息类以及相关类都添加了 _ _ deepcopy _ _ 函数,下面是信息类示例。

class FiveCardStudInfo(roomai.abstract.AbstractInfo):
    public_state  = None
    person_state  = None

    def __deepcopy__(self, memodict={}):
        info = FiveCardStudInfo()
        info.public_state = self.public_state.__deepcopy__()
        info.public_state = self.person_state.__deepcopy__()
        return info

简单做了一个效率对比实验:让随机玩法玩家打一千局梭哈,统计耗时。实验结果如下所示。

使用原始深拷贝,程序运行时间为 143 秒,其中深拷贝时间 134 秒,深拷贝时间占整个程序时间的 94%。使用了改进深拷贝,程序运行时间是 23 秒,其中深拷贝时间 16 秒,占比为 69 %。虽然深拷贝依然占到了 69%,相比之间 94 % 已经下降很多。整个程序运行时间也从 134 秒减少到 23 秒了。

总结

Python 的深拷贝很慢,原因在于深拷贝需要维护一个 memo 用于记录已经拷贝的对象。而维护这个 memo 的原因是为了避免相互引用造成的死循环。绝大多数情况下,程序中不存在相互引用。但作为通用模块,Python 深拷贝必须为了这 1% 情形,牺牲 99% 情形下的性能。真是无奈呀。我们可以通过自己实现 _ _ deepcopy _ _ 函数来改进其效率。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏noteless

为什么需要创建型模式以及简单工厂模式(三)

但是,构造方法全都是一样的名字,使用创建型模式---比如工厂模式的话,你哪怕什么都不做

9620
来自专栏企鹅号快讯

从零基础开始学习PHP(六)

发布上一篇博文的时候、不小心忘记添加打赏功能了、这篇文章补上!如文中有误之处、还望大神指出以便改正、也可以更好的帮助后来者学习。 ? PHP中变量的类型 目标 ...

20390
来自专栏java学习

Java每日一练(2017/7/20)

最新通知 ●回复"每日一练"获取以前的题目! ●【新】Ajax知识点视频更新了!(回复【学习视频】获取下载链接) ●【新】HTML5知识点视频更新了!(回复【前...

26760
来自专栏龙首琴剑庐

Java总论及三大特性理解

1、对象(object)     万物皆为对象(根类Object类)。     程序是对象的集合(面向对象程序设计语言OOP)。     每个对象都有自己的由其...

31160
来自专栏Python小屋

Python字符串处理小案例

连续5天30个小时的Python培训圆满结束,明天早上5点半出发赶飞机回烟台,晚上收拾行李的时候突然想起来20年前做过的一个C语言题目:假设有一个字符串,里面有...

30450
来自专栏WindCoder

日期判断

8510
来自专栏magicsoar

确保你想要修改的char*是可以修改的

void change(char *source) { source[0] = 'D'; cout<<source<<endl; 考虑一下,你有...

20150
来自专栏CDA数据分析师

码如其人,同学你能写一手漂亮的Python函数吗

与多数现代编程语言一样,在 Python 中,函数是抽象和封装的基本方法之一。你在开发阶段或许已经写过数百个函数,但并非每个函数都生而平等。写出「糟糕的」函数会...

15130
来自专栏calmound

UVA Machined Surfaces

题意:这道题我读了很久,也没有读懂最后看的解体报告才懂得题意,题目不难,但是还是错了两次,几个字符窜,左边的‘x’向右边移动当和右边的‘x’连接时候,求剩下的字...

36760
来自专栏林冠宏的技术文章

介绍一个很爽的 php 字符串特定检索函数---strpos()

大家在用 php 开发的时候 是否 有遇到过,对于一个获取的字符串,如果想要特定检测它是否 含有某个特定的字符或者子字符串,总是找不到好方法,或者根本做不到,迫...

19570

扫码关注云+社区

领取腾讯云代金券