CODEWITHSUNDEEP
python-3.xlistmultidimensional-array
Zabir Al Nazi Nabil
Zabir Al Nazi Nabil

Reputation: 11198

Efficient 2d list initialization [python]

I was writing a code for the adjacency matrix for a graph and found this question:

Best and/or fastest way to create lists in python

So, I simply wrote this to initialize my adjacency matrix as it seemed the fastest way to initialize a list so far.

import time
t1 = time.time()
matrix = [[0]*5000]*5000
t2 = time.time()

t2-t1

0.0

But after doing some operations, I realized each time I changed/appended an element the effect is applied to all the sub-lists, which means each list is just a reference and this will not work for a real scenario even though it's fast.

I can't use numpy, as algorithmic sites don't allow external modules/libraries. I think numpy would've been the ideal solution for the general scenario.

Now, obviously most other 2d/multi-dim list initialization answers suggest list comprehension,

import time
t1 = time.time()
matrix = [[0 for i in range(5000)] for j in range(5000)]
t2 = time.time()
print(t2-t1)

0.7021145820617676

But, it seems slow (compared to other languages) considering the strict time limit for solving a graph problem in an algorithmic site.

Is there a faster way to initialize a 2d/3d list in python?

Let me know if there is a duplicate, so far I didn't find anything which shows some time comparison between methods for multi-dimensional list initialization.

Upvotes: 0

Views: 1025

Answers (2)

Serge Ballesta
Serge Ballesta

Reputation: 148880

The problem comes from the second level of list. [0] * 5000 is fine because is builds a list of immutable values. So if you change a value in that list, you will actually replace it. But as lists are mutable you cannot use that method to build a list of lists.

But this:

[[0] * 5000 for i in range(5000)]

is still correct. It build 5000 different lists of (immutable) numbers, so it will allow you to change any individual element with no unwanted side effect. And it is much more efficient than your current code.

Upvotes: 2

Schach21
Schach21

Reputation: 450

I found a method that is faster than doing your comprehension list, but still much slower than doing matrix=[[0]*5000]*5000. I am not an expert, but I'd suspect that your method is so fast because it isn't really creating a list of size 5000x5000, but instead a list of size 5000 and repeating it, as you noticed.

Your method takes 2.098e-5 seconds in my computer. My method takes 0.1236 seconds in my computer (it is possible that my method takes longer in your computer, so it could be even slower).

mat = []
[mat.append([0]*5000) for i in range(5000)]

You could try it, maybe it mitigates your problem.

Upvotes: 0

Related Questions