J'ai défini un python class nommé Edge comme suit:

class Edge:
    def __init__(self):
        self.node1 = 0
        self.node2 = 0
        self.weight = 0

Maintenant, je dois créer environ 10 ^ 6 à 10 ^ 7 instances d'Edge en utilisant:

edges= []
for (i,j,w) in ijw:
    edge = Edge()
    edge.node1 = i
    edge.node2 = j
    edge.weight = w
    edges.append(edge)

J'ai mis environ 2 secondes dans Desktop. Existe-t-il un moyen plus rapide de le faire?

5
ted930511 20 nov. 2018 à 10:52

3 réponses

Meilleure réponse

Vous ne pouvez pas le rendre beaucoup plus rapide, mais j'utiliserais certainement __slots__ pour économiser sur les allocations de mémoire. Permet également de passer les valeurs d'attribut lors de la création de l'instance:

class Edge:
    __slots__ = ('node1', 'node2', 'weight')
    def __init__(self, node1=0, node2=0, weight=0):
        self.node1 = node1
        self.node2 = node2
        self.weight = weight

Avec la mise à jour __init__, vous pouvez utiliser une compréhension de liste:

edges = [Edge(*args) for args in ijw]

Ensemble, ceux-ci peuvent réduire considérablement le temps de création des objets, soit environ la moitié du temps nécessaire.

Comparaison créant 1 million d'objets; La mise en place:

>>> from random import randrange
>>> ijw = [(randrange(100), randrange(100), randrange(1000)) for _ in range(10 ** 6)]
>>> class OrigEdge:
...     def __init__(self):
...         self.node1 = 0
...         self.node2 = 0
...         self.weight = 0
...
>>> origloop = '''\
... edges= []
... for (i,j,w) in ijw:
...     edge = Edge()
...     edge.node1 = i
...     edge.node2 = j
...     edge.weight = w
...     edges.append(edge)
... '''
>>> class SlotsEdge:
...     __slots__ = ('node1', 'node2', 'weight')
...     def __init__(self, node1=0, node2=0, weight=0):
...         self.node1 = node1
...         self.node2 = node2
...         self.weight = weight
...
>>> listcomploop = '''[Edge(*args) for args in ijw]'''

Et les horaires:

>>> from timeit import Timer
>>> count, total = Timer(origloop, 'from __main__ import OrigEdge as Edge, ijw').autorange()
>>> (total / count) * 1000 # milliseconds
722.1121070033405
>>> count, total = Timer(listcomploop, 'from __main__ import SlotsEdge as Edge, ijw').autorange()
>>> (total / count) * 1000 # milliseconds
386.6706900007557

C'est presque 2 fois plus rapide.

L'augmentation de la liste d'entrée aléatoire à 10 ^ 7 éléments, et la différence de synchronisation est valable:

>>> ijw = [(randrange(100), randrange(100), randrange(1000)) for _ in range(10 ** 7)]
>>> count, total = Timer(origloop, 'from __main__ import OrigEdge as Edge, ijw').autorange()
>>> (total / count)
7.183759553998243
>>> count, total = Timer(listcomploop, 'from __main__ import SlotsEdge as Edge, ijw').autorange()
>>> (total / count)
3.8709938440006226
10
Martijn Pieters 20 nov. 2018 à 08:53

Une autre option consiste à ignorer la classe Edge et à implémenter les bords via une table ou une matrice d'adjacence.

Par exemple.

A = create_adjacency_graph(ijw)  # Implement to return a IxJ (sparse?) matrix of weights
edge_a_weight = A[3, 56]
edge_b_weight = A[670, 1023]
# etc...

Cela supprime cependant une certaine flexibilité, mais devrait être assez rapide à la fois pour créer et utiliser.

1
Hannes Ovrén 20 nov. 2018 à 08:01

Il existe une autre méthode d'économie rapide et de mémoire utilisant la bibliothèque recordclass:

from recordclass import dataobject

from random import randrange
import sys
ijw = [(randrange(100), randrange(100), randrange(1000)) for _ in range(10 ** 7)]

class EdgeDO(dataobject):
    __fields__ = 'node1', 'node2', 'weight'
    __options__ = {'argsonly':True}

class EdgeSlots:
    __slots__ = 'node1', 'node2', 'weight'

    def __init__(self, node1, node2, weight):
         self.node1 = node1
         self.node2 = node2
         self.weight = weight

def list_size(lst):
    return sum(sys.getsizeof(o) for o in lst)

%time list_do = [EdgeDO(n1, n2, w) for n1, n2, w in ijw]
%time list_slots = [EdgeSlots(n1, n2, w) for n1, n2, w in ijw]

print('size (dataobject):', list_size(list_do))
print('size (__slots__): ', list_size(list_slots))

Il y a la sortie:

CPU times: user 2.23 s, sys: 20 ms, total: 2.25 s
Wall time: 2.25 s
CPU times: user 6.79 s, sys: 84.1 ms, total: 6.87 s
Wall time: 6.87 s
size (dataobject): 400000000
size (__slots__):  640000000
1
intellimath 4 juin 2019 à 14:41