Quelle est la méthode pythonique rapide pour copier en profondeur les données d'un dict ou d'une liste python ?

Question

Lorsque nous devons copier des données complètes à partir d'un dictionnaire contenant des types de données primitifs (pour simplifier, ignorons la présence de types de données comme datetime, etc. deepcopy Mais la copie profonde est plus lente que d'autres méthodes bricolées pour obtenir la même chose, c'est-à-dire en utilisant la sérialisation et la désérialisation, comme par exemple json-dump-json-load ou msgpack-pack-msgpack-unpack. La différence d'efficacité peut être vue ici :

>>> import timeit
>>> setup = '''
... import msgpack
... import json
... from copy import deepcopy
... data = {'name':'John Doe','ranks':{'sports':13,'edu':34,'arts':45},'grade':5}
... '''
>>> print(timeit.timeit('deepcopy(data)', setup=setup))
12.0860249996
>>> print(timeit.timeit('json.loads(json.dumps(data))', setup=setup))
9.07182312012
>>> print(timeit.timeit('msgpack.unpackb(msgpack.packb(data))', setup=setup))
1.42743492126

Les méthodes json et msgpack (ou cPickle) sont plus rapides qu'une deepcopy normale, ce qui est évident puisque la deepcopy ferait beaucoup plus en copiant tous les attributs de l'objet aussi.

Question : Existe-t-il un moyen plus pythonique/intégré de réaliser une simple copie de données d'un dictionnaire ou d'une liste, sans avoir toutes les surcharges de la deepcopy ?

Answer 1

Cela dépend vraiment de vos besoins. deepcopy a été construit avec l'intention de faire la chose (la plus) correcte. Il garde les références partagées, il ne récure pas dans des structures récursives infinies et ainsi de suite... Il peut le faire en gardant une memo dictionnaire dans lequel toutes les "choses" rencontrées sont insérées par référence. C'est ce qui le rend assez lent pour les copies de données pures. Cependant, je voudrais presque disent toujours que deepcopy es la façon la plus pythique de copier des données même si d'autres approches pourraient être plus rapides.

Si vous disposez de données pures et d'un nombre limité de types, vous pouvez créer votre propre système de gestion des données. deepcopy (construire à peu près après la mise en œuvre de deepcopy dans CPython ) :

_dispatcher = {}

def _copy_list(l, dispatch):
    ret = l.copy()
    for idx, item in enumerate(ret):
        cp = dispatch.get(type(item))
        if cp is not None:
            ret[idx] = cp(item, dispatch)
    return ret

def _copy_dict(d, dispatch):
    ret = d.copy()
    for key, value in ret.items():
        cp = dispatch.get(type(value))
        if cp is not None:
            ret[key] = cp(value, dispatch)

    return ret

_dispatcher[list] = _copy_list
_dispatcher[dict] = _copy_dict

def deepcopy(sth):
    cp = _dispatcher.get(type(sth))
    if cp is None:
        return sth
    else:
        return cp(sth, _dispatcher)

Cela ne fonctionne correctement que pour tous les types immuables non-conteneur et list y dict instances. Vous pouvez ajouter d'autres répartiteurs si vous en avez besoin.

# Timings done on Python 3.5.3 - Windows - on a really slow laptop :-/

import copy
import msgpack
import json

import string

data = {'name':'John Doe','ranks':{'sports':13,'edu':34,'arts':45},'grade':5}

%timeit deepcopy(data)
# 11.9 µs ± 280 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit copy.deepcopy(data)
# 64.3 µs ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit json.loads(json.dumps(data))
# 65.9 µs ± 2.53 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit msgpack.unpackb(msgpack.packb(data))
# 56.5 µs ± 2.53 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Voyons également comment il se comporte lors de la copie d'un grand dictionnaire contenant des chaînes de caractères et des entiers :

data = {''.join([a,b,c]): 1 for a in string.ascii_letters for b in string.ascii_letters for c in string.ascii_letters}

%timeit deepcopy(data)
# 194 ms ± 5.37 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit copy.deepcopy(data)
# 1.02 s ± 46.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit json.loads(json.dumps(data))
# 398 ms ± 20.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit msgpack.unpackb(msgpack.packb(data))
# 238 ms ± 8.81 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

Je pense que vous pouvez implémenter manuellement ce dont vous avez besoin en surchargeant object.__deepcopy__ .

Une façon pythonique de faire cela, je pense, est d'utiliser votre dict personnalisé étendu à partir du dict intégré et d'implémenter votre propre __deepcopy__ .

Answer 3

@MSeifert La réponse suggérée n'est pas exacte.

Jusqu'à présent, j'ai trouvé que ujson.loads(ujson.dumps(my_dict)) était l'option la plus rapide, ce qui semble étrange (comment traduire un dict en chaîne de caractères, puis de la chaîne de caractères au nouveau dict est plus rapide qu'une simple copie).

Voici un exemple des méthodes que j'ai essayées et de leur temps d'exécution pour un petit dictionnaire (les résultats sont bien sûr plus clairs avec un plus grand dictionnaire) :

x = {'a':1,'b':2,'c':3,'d':4, 'e':{'a':1,'b':2}}

#this function only handle dict of dicts very similar to the suggested solution
def fast_copy(d):
    output = d.copy()
    for key, value in output.items():
        output[key] = fast_copy(value) if isinstance(value, dict) else value        
    return output

from copy import deepcopy
import ujson

%timeit deepcopy(x)
13.5 µs ± 146 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit fast_copy(x)
2.57 µs ± 31.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit ujson.loads(ujson.dumps(x))
1.67 µs ± 14.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Y a-t-il une autre extension C qui pourrait fonctionner mieux que ujson ? Il est très étrange que ce soit la méthode la plus rapide pour copier un gros fichier.