How do I make a flat list out of a list of lists?
Given a list of lists l
,
flat_list = [item for sublist in l for item in sublist]
which means:
flat_list = []
for sublist in l:
for item in sublist:
flat_list.append(item)
is faster than the shortcuts posted so far. (l
is the list to flatten.)
Here is the corresponding function:
def flatten(l):
return [item for sublist in l for item in sublist]
As evidence, you can use the timeit
module in the standard library:
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' '[item for sublist in l for item in sublist]'
10000 loops, best of 3: 143 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 3: 969 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 3: 1.1 msec per loop
Explanation: the shortcuts based on +
(including the implied use in sum
) are, of necessity, O(L**2)
when there are L sublists -- as the intermediate result list keeps getting longer, at each step a new intermediate result list object gets allocated, and all the items in the previous intermediate result must be copied over (as well as a few new ones added at the end). So, for simplicity and without actual loss of generality, say you have L sublists of I items each: the first I items are copied back and forth L-1 times, the second I items L-2 times, and so on; total number of copies is I times the sum of x for x from 1 to L excluded, i.e., I * (L**2)/2
.
The list comprehension just generates one list, once, and copies each item over (from its original place of residence to the result list) also exactly once.
Flatten an irregular (arbitrarily nested) list of lists
Using generator functions can make your example easier to read and improve performance.
Python 2
Using the Iterable
ABC added in 2.6:
from collections import Iterable
def flatten(xs):
for x in xs:
if isinstance(x, Iterable) and not isinstance(x, basestring):
for item in flatten(x):
yield item
else:
yield x
Python 3
In Python 3, basestring
is no more, but the tuple (str, bytes)
gives the same effect. Also, the yield from
operator returns an item from a generator one at a time.
from collections.abc import Iterable
def flatten(xs):
for x in xs:
if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
yield from flatten(x)
else:
yield x
How can I completely flatten a list (of lists (of lists) ... )
Unfortunately there's no direct built-in that completely flattens a data structure even when sub-lists are wrapped in item containers.
Some possible solutions:
Gather/take
You've already come up with a solution like this, but deepmap
can take care of all the tree iteration logic to simplify it. Its callback is called once for every leaf node of the data structure, so using take
as the callback means that gather
will collect a flat list of the leaf values:
sub reallyflat (+@list) { gather @list.deepmap: *.take }
Custom recursive function
You could use a subroutine like this to recursively slip
lists into their parent:
multi reallyflat (@list) { @list.map: { slip reallyflat $_ } }
multi reallyflat (\leaf) { leaf }
Another approach would be to recursively apply <>
to sub-lists to free them of any item containers they're wrapped in, and then call flat
on the result:
sub reallyflat (+@list) {
flat do for @list {
when Iterable { reallyflat $_<> }
default { $_ }
}
}
Multi-dimensional array indexing
The postcircumfix [ ]
operator can be used with a multi-dimensional subscript to get a flat list of leaf nodes up to a certain depth, though unfortunately the "infinite depth" version is not yet implemented:
say @ab[*;*]; # (a (b c) (d) e f [a (b c)] x (y z) w)
say @ab[*;*;*]; # (a b c d e f a (b c) x y z w)
say @ab[*;*;*;*]; # (a b c d e f a b c x y z w)
say @ab[**]; # HyperWhatever in array index not yet implemented. Sorry.
Still, if you know the maximum depth of your data structure this is a viable solution.
Avoiding containerization
The built-in flat
function can flatten a deeply nested lists of lists just fine. The problem is just that it doesn't descend into item containers (Scalar
s). Common sources of unintentional item containers in nested lists are:
An
Array
(but notList
) wraps each of its elements in a fresh item container, no matter if it had one before.- How to avoid: Use Lists of Lists instead of Arrays of Arrays, if you don't need the mutability that Array provides. Binding with
:=
can be used instead of assignment, to store aList
in a@
variable without turning it into anArray
:
my @a := 'a', ('b', 'c' );
my @b := ('d',), 'e', 'f', @a;
say flat @b; # (d e f a b c)
- How to avoid: Use Lists of Lists instead of Arrays of Arrays, if you don't need the mutability that Array provides. Binding with
$
variables are item containers.- How to avoid: When storing a list in a
$
variable and then inserting it as an element into another list, use<>
to decontainerize it. The parent list's container can also be bypassed using|
when passing it toflat
:
my $a = (3, 4, 5);
my $b = (1, 2, $a<>, 6);
say flat |$b; # (1 2 3 4 5 6)
- How to avoid: When storing a list in a
How to flatten List of Lists in Kotlin?
As answered by @DYS you can and should use flatten
to flatten a list. My answer covers how to achieve the special case stated in the question.
You can do it this way:
val a = listOf(
AA(LocalDate.now(), listOf(BB(1, "1", "1")))
)
val flattened = a.flatMap { aa -> mutableListOf<Any>(aa.date).also { it.addAll(aa.bb) }}
see complete example
Basically you use flatMap
, create a MutableList<Any>
with the date
and then addAll
items of BB
in the also
block. Probably there is a more elegant way to do it but this one came to me first.
Simply using flatten
does not work here, because AA does not implement iterable
.
How to flatten list of lists?
Use SelectMany
:
var legalEntityIds =
query.SelectMany(x => x.LegalEntities).Select(y => y.LegalEntityId).ToList();
or, using query syntax:
var legalEntityIds = (
from item in query
from legalEntity in item
select legalEntity.LegalEntityId
).ToList();
Related Topics
Split Up '...' Arguments and Distribute to Multiple Functions
Add Multiple Columns to R Data.Table in One Function Call
Create Categories by Comparing a Numeric Column with a Fixed Value
Ggplot2: Facet_Wrap Strip Color Based on Variable in Data Set
Difference Between Passing Options in Aes() and Outside of It in Ggplot2
How to Insert New Line in R Shiny String
Geometric Mean: Is There a Built-In
Short Formula Call for Many Variables When Building a Model
Opening Shiny App Directly in the Default Browser
Extracting Unique Numbers from String in R
When Should I Use the := Operator in Data.Table
Perform a Semi-Join with Data.Table
Error ".Onload Failed in Loadnamespace() for 'Tcltk'"
How to Add Table of Contents in Rmarkdown
Ggplot2, Facet_Grid, Free Scales
Handling Java.Lang.Outofmemoryerror When Writing to Excel from R