Ytukyg

I have defined a python class named Edge as follows:

class Edge:

    def __init__(self):

        self.node1 = 0

        self.node2 = 0

        self.weight = 0

Now I have to create approximately 10^6 to 10^7 instances of Edge using:

edges= 

for (i,j,w) in ijw:

    edge = Edge()

    edge.node1 = i

    edge.node2 = j

    edge.weight = w

    edges.append(edge)

I took me approximately 2 seconds in Desktop. Is there any faster way to do?

You can't make it much faster, but I certainly would use __slots__ to save on memory allocations. Also make it possible to pass in the attribute values when creating the 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

With the updated __init__ you can use a list comprehension:

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

Together these can shave off a decent amount of time creating the objects, roughly halve the time needed.

Comparison creating 1 million objects; the setup:

>>> 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]'''

and the timings:

>>> 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

That's nearly 2 times as fast.

Increasing the random input list to 10^7 items, and the timing difference holds:

>>> 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

Another option is to skip the Edge class and implement the edges via a table, or adjacency matrix.

E.g.

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...

This does remove some flexibility though, but should be quite fast both to create and use.