To Convert a 2D array into 1D array in python , i found this method on leetcode. But can't find How its working logically step by step ? Please explain. Also someone said on leetcode that : "This could be quadratic runtime complexity when array size gets really large"
Is this true? if yes, How?
a = [[4,2,5],[1,8,2],[7,5,6]]
flat = sum(a,[])
flat
output : [4, 2, 5, 1, 8, 2, 7, 5, 6]
CodePudding user response:
How sum
works?
In Python, lists can be concatenated with operator
:
>>> [1] [2, 3]
[1, 2, 3]
The sum
function in Python is similar to:
>>> def my_sum(iterable, start=0):
... for v in iterable:
... start = start v
... return start
...
So for sum(a, [])
, you can understand the following operations:
>>> [] [4, 2, 5] [1, 8, 2] [7, 5, 6]
[4, 2, 5, 1, 8, 2, 7, 5, 6]
But this will not be a good practice, because each concatenation will produce a new list, rather than concatenation in place on one of the lists:
>>> a = [1]
>>> b = [2, 3]
>>> c = a b
>>> a, b, c
([1], [2, 3], [1, 2, 3])
This means that each concatenation requires O(n m)
time (n and m are the lengths of the two lists respectively), rather than O(m)
. For m lists with length n, the first time a list of length n will be concatenated with another list of length n, and the next time a list of length 2n will be concatenated with a list of length n... at the end, the total time spent will be:
(n n) (2n n) ... (mn n) = (m^2 3m) * n / 2 = O(m^2 * n)
Better practice
The simple method is to use in place concatenate each time:
def concatenate(lists):
result = []
for lst in lists:
result = lst
return result
A more concise way is to use functools.reduce
and operator.iconcat
:
>>> from functools import reduce
>>> from operator import iconcat
>>> reduce(iconcat, a, [])
[4, 2, 5, 1, 8, 2, 7, 5, 6]
You can also use itertools.chain.from_iterable
to chain these lists, and then use the list
to construct:
>>> from itertools import chain
>>> list(chain.from_iterable(a))
[4, 2, 5, 1, 8, 2, 7, 5, 6]
Or use nested list comprehension:
>>> [val for lst in a for val in lst]
[4, 2, 5, 1, 8, 2, 7, 5, 6]
For performance comparison, please refer to: How do I make a flat list out of a list of lists?
CodePudding user response:
Here sum()
works as follows:
By default, sum()
takes one required parameter which is a sequence of integers, as for the second optional parameter, it is defaulted to 0
to indicate that the sequence is of type int
.
However, in the above case, it passes list of lists to sum()
with the optional start
parameter set to []
to indicate the sequence type is list
which concatenates them.
However, there are better solutions to this problem. One of which is to use a for loop.
For further information, please check the documentation.