Re: flattening lists
Op 11/10/2022 om 21:32 schreef SquidBits _: Does anyone else think there should be a flatten () function, which just turns a multi-dimensional list into a one-dimensional list in the order it's in. e.g. [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. I have had to flatten lists quite a few times and it's quite tedious to type out. It feels like this should be something built in to python, anyone else think this way? Depending on what you exactly mean by "flatten", it already is easy to flatten a list in python: >>> lst = [[1,2,3],[4,5,6,7],[8,9]] >>> list(itertools.chain.from_iterable(lst)) [1, 2, 3, 4, 5, 6, 7, 8, 9] -- Antoon Pardon -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
On Tue, Oct 11, 2022 at 12:48 PM SquidBits _ wrote: > Does anyone else think there should be a flatten () function, which just > turns a multi-dimensional list into a one-dimensional list in the order > it's in. e.g. > > [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. > > I have had to flatten lists quite a few times and it's quite tedious to > type out. It feels like this should be something built in to python, anyone > else think this way? > I think the usual argument against putting something like this in the standard library (I hope it won't be built in), is that there are many ways to define "flatten". That is, should it only go one level deep? All the way to the bottom? n levels deep? Should it do something special with lists, dicts, tuples, sets? This looks like a nice URL on the topic: https://www.pythonpool.com/flatten-list-python/ -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
On 2022-10-11 21:09, Stefan Ram wrote: r...@zedat.fu-berlin.de (Stefan Ram) writes: . I never understood "yield from" until just now, when I was thinking, "Maybe this could be the piece that fits in here!" PS: If I'm starting to think about it: Having succeeded after using it by trial in one case does not mean that I have understood it! This: yield from iterable is equivalent to: for item in iterable: yield item but is more efficient. That's really all you need to know! -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
On 12/10/2022 08.32, SquidBits _ wrote: Does anyone else think there should be a flatten () function, which just turns a multi-dimensional list into a one-dimensional list in the order it's in. e.g. [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. I have had to flatten lists quite a few times and it's quite tedious to type out. It feels like this should be something built in to python, anyone else think this way? There is a flatten function! First though, are we ONLY talking about 'flattening' a 2D list (per example, above) or might the requirements extend to multiple-dimensions? The solutions vary accordingly! Two-dimensions: (don't think this method previously-mentioned, but very readable) >>> l = [[1,2,3],[4,5,6,7],[8,9]] >>> flattened = list() >>> for element in l: ... flattened += element ... >>> flattened [1, 2, 3, 4, 5, 6, 7, 8, 9] (NB if "l" were three-dimensional, "flattened" would become 2D) Multi-dimensional: Reach for itertools: (https://docs.python.org/3/library/itertools.html#itertools.chain) >>> import itertools as it >>> iter_flattened = it.chain( *l ) >>> list( iter_flattened ) [1, 2, 3, 4, 5, 6, 7, 8, 9] Wrt "I have had to flatten lists quite a few times and it's quite tedious to type out.", isn't this a "code-smell"? Certainly motivation to generalise and write a solution as a function. Do it once, and do it right! Hence advice elsewhere to build a list-processing utility-library. On the other hand, has it already been done for us? An exercise for the reader: is reaching for itertools 'over-kill' in 2D? - speed-comparison between loading the itertools library and then employing the speedy method, or using a (built-in) for-loop at Python-speed with no import-overhead? (results will vary significantly according to len( l ), but do they remain consistently in-favor or one method or the other?) -- Regards, =dn -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
Is this what you usually do? l1 = [[1,2,3],[4,5,6,7],[8,9]] l2 = [] for lz in l1: l2.extend(lz) print(l2) # [1,2,3,4,5,6,7,8,9] Not all that "tedious", perhaps... I tend to accumulate little utilities like this in a file and point to it with a .pth file. Of course, you have to remember to include it if you share your program with someone else. On 10/11/2022 3:32 PM, SquidBits _ wrote: Does anyone else think there should be a flatten () function, which just turns a multi-dimensional list into a one-dimensional list in the order it's in. e.g. [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. I have had to flatten lists quite a few times and it's quite tedious to type out. It feels like this should be something built in to python, anyone else think this way? -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
On Tue, Oct 11, 2022 at 12:32:23PM -0700, SquidBits _ wrote: Does anyone else think there should be a flatten () function, which just turns a multi-dimensional list into a one-dimensional list in the order it's in. e.g. [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. I have had to flatten lists quite a few times and it's quite tedious to type out. It feels like this should be something built in to python, anyone else think this way? I typically don't mind things that are one liners, especially if the one liner is a list comprehension. def flatten1(inlist): return [l for sublist in inlist for l in sublist] givenlist = [[1, 2, 3], [4, 5, 6, 7], [8, 9]] print(flatten1(givenlist)) def flatten2(inlist): return sum(inlist, []) print(flatten2(givenlist)) Looking up "flatten" in python's source reveals the (not at all obvious to me as I don't use chain) alternative import itertools def flatten3(inlist): return list(itertools.chain.from_iterable) print(flatten3(givenlist)) I notice that "flatten" appears many times in python's source. I didn't check how many times it's used with the same meaning, though. - DLD -- https://mail.python.org/mailman/listinfo/python-list
Re: flattening lists
On Tue, Oct 11, 2022 at 12:48 PM SquidBits _ wrote: > > Does anyone else think there should be a flatten () function, which just > turns a multi-dimensional list into a one-dimensional list in the order it's > in. e.g. > > [[1,2,3],[4,5,6,7],[8,9]] becomes [1,2,3,4,5,6,7,8,9]. > > I have had to flatten lists quite a few times and it's quite tedious to type > out. It feels like this should be something built in to python, anyone else > think this way? x = [[1,2,3],[4,5,6,7],[8,9]] [i for j in x for i in j] [1, 2, 3, 4, 5, 6, 7, 8, 9] -- https://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 5, 2:07 pm, rdmur...@bitdance.com wrote: > Quoth J Kenneth King : > > > > > mk writes: > > > > Hello everybody, > > > > Any better solution than this? > > > > def flatten(x): > > > res = [] > > > for el in x: > > > if isinstance(el,list): > > > res.extend(flatten(el)) > > > else: > > > res.append(el) > > > return res > > > > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] > > > print flatten(a) > > > > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] > > > > Regards, > > > mk > > >http://mail.python.org/pipermail/python-list/2005-July/330367.html > > That's worth reading. I'm not sure why I'm finding this fun, but who > cares. I tried a couple of other functions after reading that article, > and it looks like a generator that scans the nested lists is actually > the winner, and also is in many ways the most elegant implementation. > Of course, as noted in the emails following above article, the test data > is really inadequate for proper optimization testing ;) > > - > from __future__ import print_function > from timeit import Timer > from itertools import chain > > # This is the one from the article quoted above. > def flatten6(seq): > i = 0 > while (i != len(seq)): > while hasattr(seq[i], '__iter__'): > seq[i:i+1] = seq[i] > i = i + 1 > return seq > > #This is my favorite from a readability standpoint out of > #all the things I tried. It also performs the best. > def flatten8(seq): > for x in seq: > if not hasattr(x, '__iter__'): yield x > else: > for y in flatten8(x): > yield y > > l = [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, > [5, 4], 3], 4, 3], 3, 1, 45], 9], 10]] > > if __name__=="__main__": > print(l) > print('flatten6', flatten6(l)) > print('flatten8', list(flatten8(l))) > print('flatten6', Timer("flatten6(l)", "from temp3 import flatten6, > l").timeit()) > print('flatten8', Timer("list(flatten8(l))", "from temp3 import flatten8, > l").timeit()) > > - > > >src/python/Python-3.0/python temp3.py > > [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, > 4], 3], 4, 3], 3, 1, 45], 9], 10]] > flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, > 3, 3, 1, 45, 9, 10] > flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, > 3, 3, 1, 45, 9, 10] > flatten6 32.8386368752 > flatten8 30.7509689331 > > >python temp3.py > > [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, > 4], 3], 4, 3], 3, 1, 45], 9], 10]] > flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, > 3, 3, 1, 45, 9, 10] > flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, > 3, 3, 1, 45, 9, 10] > flatten6 34.730714798 > flatten8 32.3252940178 > > --RDM I think the generator is clearer with a try statement, like in Magnus Lie Hetland's solution from Beginning Python: def flatten(nested): try: # Don't iterate over string-like objs. try: nested + '' except TypeError: pass else: raise TypeError for sub in nested: for elem in flatten(sub): yield elem except TypeError: # The for doesn't work for single elements. yield nested You can't iterate over string-like objs because the all strings are built of infinite empty lists at the beginning, leading to infinite recursion. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 7, 3:07 pm, wrote: > On Sat, 7 Feb 2009 12:50:22 -0800 (PST) > Rhamphoryncus wrote: > > Can you explain this in a little more detail? > > In the application, there is one main numpy array of type "O". > Each element of the array corresponds to one cell in a grid. The user > may enter a Python expression into the grid cell. The input is > evaled and the result is stored in the numpy array (the actual process > is a bit more complicated). Therefore, the object inside a numpy array > element may be an inconsistent, nested, iterable type. > > The user now may access the result grid via __getitem__. When doing > this, a numpy array that is as flat as possible while comprising the > maximum possible data depth is returned, i.e.: > > 1. Non-string and non-unicode iterables of similar length for each of > the cells form extra dimensions. > > 2. In order to remove different container types, the result is > flattened, cast into a numpy.array and re-shaped. > > 3. Dimensions of length 1 are eliminated. > > Therefore, the user can conveniently use numpy ufuncs on the results. > > I am referring to the flatten operation in step 2 I'm afraid I still don't understand it, but I'm only minimally familiar with numpy, nevermind your spreadsheet app. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Sat, 7 Feb 2009 12:50:22 -0800 (PST) Rhamphoryncus wrote: > On Feb 7, 1:39 pm, wrote: > > On Sat, 7 Feb 2009 01:06:06 -0800 (PST) > > Rhamphoryncus wrote: > > > > > What usecase do you have for such inconsistently structured data? > > > > I have a similar use case in pyspread, which is a Python spreadsheet > > that employs numpy object arrays. Since the Python objects in the > > numpy arrays are derived from user input, they can be anything, > > including nested lists as well as strings, etc. > > > > Since I consider my work-around that treats strings as a special > > case a rather ugly hack, I would welcome a robust, generic approach > > to the OP's problem. > > Can you explain this in a little more detail? In the application, there is one main numpy array of type "O". Each element of the array corresponds to one cell in a grid. The user may enter a Python expression into the grid cell. The input is evaled and the result is stored in the numpy array (the actual process is a bit more complicated). Therefore, the object inside a numpy array element may be an inconsistent, nested, iterable type. The user now may access the result grid via __getitem__. When doing this, a numpy array that is as flat as possible while comprising the maximum possible data depth is returned, i.e.: 1. Non-string and non-unicode iterables of similar length for each of the cells form extra dimensions. 2. In order to remove different container types, the result is flattened, cast into a numpy.array and re-shaped. 3. Dimensions of length 1 are eliminated. Therefore, the user can conveniently use numpy ufuncs on the results. I am referring to the flatten operation in step 2 -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 7, 1:39 pm, wrote: > On Sat, 7 Feb 2009 01:06:06 -0800 (PST) > Rhamphoryncus wrote: > > > What usecase do you have for such inconsistently structured data? > > I have a similar use case in pyspread, which is a Python spreadsheet > that employs numpy object arrays. Since the Python objects in the numpy > arrays are derived from user input, they can be anything, including > nested lists as well as strings, etc. > > Since I consider my work-around that treats strings as a special case a > rather ugly hack, I would welcome a robust, generic approach to the > OP's problem. Can you explain this in a little more detail? -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Sat, 7 Feb 2009 01:06:06 -0800 (PST) Rhamphoryncus wrote: > On Feb 6, 10:21 pm, rdmur...@bitdance.com wrote: > > Quoth Mensanator : > > > def flatten(listOfLists): > > > return list(chain.from_iterable(listOfLists)) > > > > Python 2.6.1 (r261:67515, Jan 7 2009, 17:09:13) > > [GCC 4.3.2] on linux2 > > Type "help", "copyright", "credits" or "license" for more > > information. >>> from itertools import chain > > >>> list(chain.from_iterable([1, 2, [3, 4]])) > > Traceback (most recent call last): > > File "", line 1, in > > TypeError: 'int' object is not iterable > > >>> list(chain(*[1, 2, [3, 4]])) > > Traceback (most recent call last): > > File "", line 1, in > > TypeError: 'int' object is not iterable > > >>> list(chain.from_iterable(['abcd', 'efg', [3, 4]])) > > ['a', 'b', 'c', 'd', 'e', 'f', 'g', 3, 4] > > What usecase do you have for such inconsistently structured data? I have a similar use case in pyspread, which is a Python spreadsheet that employs numpy object arrays. Since the Python objects in the numpy arrays are derived from user input, they can be anything, including nested lists as well as strings, etc. Since I consider my work-around that treats strings as a special case a rather ugly hack, I would welcome a robust, generic approach to the OP's problem. Martin -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Rhamphoryncus wrote: > On Feb 6, 10:21=A0pm, rdmur...@bitdance.com wrote: > > Quoth Mensanator : > > > def flatten(listOfLists): > > > =A0 =A0 return list(chain.from_iterable(listOfLists)) > > > > =A0 =A0 Python 2.6.1 (r261:67515, Jan =A07 2009, 17:09:13) > > =A0 =A0 [GCC 4.3.2] on linux2 > > =A0 =A0 Type "help", "copyright", "credits" or "license" for more informa= > tion. > > =A0 =A0 >>> from itertools import chain > > =A0 =A0 >>> list(chain.from_iterable([1, 2, [3, 4]])) > > =A0 =A0 Traceback (most recent call last): > > =A0 =A0 =A0 File "", line 1, in > > =A0 =A0 TypeError: 'int' object is not iterable > > =A0 =A0 >>> list(chain(*[1, 2, [3, 4]])) > > =A0 =A0 Traceback (most recent call last): > > =A0 =A0 =A0 File "", line 1, in > > =A0 =A0 TypeError: 'int' object is not iterable > > =A0 =A0 >>> list(chain.from_iterable(['abcd', 'efg', [3, 4]])) > > =A0 =A0 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 3, 4] > > What usecase do you have for such inconsistently structured data? > > If I'm building a tree I use my own type for the nodes, keeping them > purely internal, so I can always use isinstance without worrying about > getting something inconvenient passed in. I don't have any use cases myself, I'm just pointing out that this doesn't answer the concerns of the OP, who presumably does. --RDM -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 6, 10:21 pm, rdmur...@bitdance.com wrote: > Quoth Mensanator : > > def flatten(listOfLists): > > return list(chain.from_iterable(listOfLists)) > > Python 2.6.1 (r261:67515, Jan 7 2009, 17:09:13) > [GCC 4.3.2] on linux2 > Type "help", "copyright", "credits" or "license" for more information. > >>> from itertools import chain > >>> list(chain.from_iterable([1, 2, [3, 4]])) > Traceback (most recent call last): > File "", line 1, in > TypeError: 'int' object is not iterable > >>> list(chain(*[1, 2, [3, 4]])) > Traceback (most recent call last): > File "", line 1, in > TypeError: 'int' object is not iterable > >>> list(chain.from_iterable(['abcd', 'efg', [3, 4]])) > ['a', 'b', 'c', 'd', 'e', 'f', 'g', 3, 4] What usecase do you have for such inconsistently structured data? If I'm building a tree I use my own type for the nodes, keeping them purely internal, so I can always use isinstance without worrying about getting something inconvenient passed in. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Quoth Mensanator : > On Feb 6, 3:23=A0pm, Rhamphoryncus wrote: > > On Feb 5, 1:16=A0pm, Michele Simionato > > wrote: > > > > > On Feb 5, 7:24=A0pm, a...@pythoncraft.com (Aahz) wrote: > > > > In article > > > > , > > > > Michele Simionato =A0 wrote: > > > > >Looks fine to me. In some situations you may also use hasattr(el, > > > > >'__iter__') instead of isinstance(el, list) (it depends if you want to > > > > >flatten generic iterables or only lists). > > > > Of course, once you do that, you need to special-case strings... > > > > > Strings are iterable but have no __iter__ method, which is fine in > > > this context, since I would say 99.9% of times one wants to treat them > > > as atomic objects, so no need to special case. > > > > Don't worry, that little oddity was fixed for you: > > > > Python 3.0+ (unknown, Dec =A08 2008, 14:26:15) > > [GCC 4.3.2] on linux2 > > Type "help", "copyright", "credits" or "license" for more information. > > >>> str.__iter__ > > > >>> bytes.__iter__ > > > >>> bytearray.__iter__ > > > > > > I'm in the "why do you need more than 1 depth?" camp. Dispatching > > based on your own type should be given an extra look. Dispatching > > based passed in types should be given three extra looks. > > > > I didn't realize itertools.chain(*iterable) worked. I guess that > > needs to be pushed as the canonical form. > > What about this (from the Recipes section of the itertools manual)? > > def flatten(listOfLists): > return list(chain.from_iterable(listOfLists)) Python 2.6.1 (r261:67515, Jan 7 2009, 17:09:13) [GCC 4.3.2] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from itertools import chain >>> list(chain.from_iterable([1, 2, [3, 4]])) Traceback (most recent call last): File "", line 1, in TypeError: 'int' object is not iterable >>> list(chain(*[1, 2, [3, 4]])) Traceback (most recent call last): File "", line 1, in TypeError: 'int' object is not iterable >>> list(chain.from_iterable(['abcd', 'efg', [3, 4]])) ['a', 'b', 'c', 'd', 'e', 'f', 'g', 3, 4] --RDM -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 6, 10:23 pm, Rhamphoryncus wrote: > On Feb 5, 1:16 pm, Michele Simionato > wrote: > > > On Feb 5, 7:24 pm, a...@pythoncraft.com (Aahz) wrote: > > > > In article > > > , > > > Michele Simionato wrote: > > > > >Looks fine to me. In some situations you may also use hasattr(el, > > > >'__iter__') instead of isinstance(el, list) (it depends if you want to > > > >flatten generic iterables or only lists). > > > > Of course, once you do that, you need to special-case strings... > > > Strings are iterable but have no __iter__ method, which is fine in > > this context, since I would say 99.9% of times one wants to treat them > > as atomic objects, so no need to special case. > > Don't worry, that little oddity was fixed for you: Acc! I have a few places in my code with checks of the kind ``hasattr(x, '__iter__')`` and I guess those spots will be tricky when converting to Python 3. I guess 2to3 cannot help either :-( -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 6, 3:23 pm, Rhamphoryncus wrote: > On Feb 5, 1:16 pm, Michele Simionato > wrote: > > > On Feb 5, 7:24 pm, a...@pythoncraft.com (Aahz) wrote: > > > > In article > > > , > > > Michele Simionato wrote: > > > > >Looks fine to me. In some situations you may also use hasattr(el, > > > >'__iter__') instead of isinstance(el, list) (it depends if you want to > > > >flatten generic iterables or only lists). > > > > Of course, once you do that, you need to special-case strings... > > > Strings are iterable but have no __iter__ method, which is fine in > > this context, since I would say 99.9% of times one wants to treat them > > as atomic objects, so no need to special case. > > Don't worry, that little oddity was fixed for you: > > Python 3.0+ (unknown, Dec 8 2008, 14:26:15) > [GCC 4.3.2] on linux2 > Type "help", "copyright", "credits" or "license" for more information.>>> > str.__iter__ > > >>> bytes.__iter__ > > >>> bytearray.__iter__ > > > > I'm in the "why do you need more than 1 depth?" camp. Dispatching > based on your own type should be given an extra look. Dispatching > based passed in types should be given three extra looks. > > I didn't realize itertools.chain(*iterable) worked. I guess that > needs to be pushed as the canonical form. What about this (from the Recipes section of the itertools manual)? def flatten(listOfLists): return list(chain.from_iterable(listOfLists)) -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 5, 1:16 pm, Michele Simionato wrote: > On Feb 5, 7:24 pm, a...@pythoncraft.com (Aahz) wrote: > > > In article > > , > > Michele Simionato wrote: > > > >Looks fine to me. In some situations you may also use hasattr(el, > > >'__iter__') instead of isinstance(el, list) (it depends if you want to > > >flatten generic iterables or only lists). > > > Of course, once you do that, you need to special-case strings... > > Strings are iterable but have no __iter__ method, which is fine in > this context, since I would say 99.9% of times one wants to treat them > as atomic objects, so no need to special case. Don't worry, that little oddity was fixed for you: Python 3.0+ (unknown, Dec 8 2008, 14:26:15) [GCC 4.3.2] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> str.__iter__ >>> bytes.__iter__ >>> bytearray.__iter__ I'm in the "why do you need more than 1 depth?" camp. Dispatching based on your own type should be given an extra look. Dispatching based passed in types should be given three extra looks. I didn't realize itertools.chain(*iterable) worked. I guess that needs to be pushed as the canonical form. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mk gmail.com> writes: > Hmm, I'm surprised by even that! Apparently list creation is more > expensive than I thought - it seems somewhat more expensive than the > cost of interpreting bytecode for "if var is None". Either list creation > is somewhat costly, or "if var is None" is really cheap. Creating a list requires several function calls on the C level (including the dictionary lookup for the name "list") and memory allocation, which is usually quite expensive. In contrast, the eval loop for "is None" basically uses a pointer comparison. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 5, 7:24 pm, a...@pythoncraft.com (Aahz) wrote: > In article > , > Michele Simionato wrote: > > > > >Looks fine to me. In some situations you may also use hasattr(el, > >'__iter__') instead of isinstance(el, list) (it depends if you want to > >flatten generic iterables or only lists). > > Of course, once you do that, you need to special-case strings... Strings are iterable but have no __iter__ method, which is fine in this context, since I would say 99.9% of times one wants to treat them as atomic objects, so no need to special case. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Thu, 05 Feb 2009 11:06:39 -0800, Tobiah wrote: > >> Hello everybody, >> >> Any better solution than this? > > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print str(a).replace('[', > '').replace(']', '').split(', ') > > ;) Or: a = ['text', 'string', 3, [4, 5, 6], [[7, 8], [9, 10]]] print eval("[" + str(a).replace('[', '').replace(']', '') + "]") Just tongue in cheek... -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
> Hello everybody, > > Any better solution than this? a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print str(a).replace('[', '').replace(']', '').split(', ') ;) -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Quoth J Kenneth King : > mk writes: > > > Hello everybody, > > > > Any better solution than this? > > > > def flatten(x): > > res = [] > > for el in x: > > if isinstance(el,list): > > res.extend(flatten(el)) > > else: > > res.append(el) > > return res > > > > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] > > print flatten(a) > > > > > > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] > > > > Regards, > > mk > > http://mail.python.org/pipermail/python-list/2005-July/330367.html That's worth reading. I'm not sure why I'm finding this fun, but who cares. I tried a couple of other functions after reading that article, and it looks like a generator that scans the nested lists is actually the winner, and also is in many ways the most elegant implementation. Of course, as noted in the emails following above article, the test data is really inadequate for proper optimization testing ;) - from __future__ import print_function from timeit import Timer from itertools import chain # This is the one from the article quoted above. def flatten6(seq): i = 0 while (i != len(seq)): while hasattr(seq[i], '__iter__'): seq[i:i+1] = seq[i] i = i + 1 return seq #This is my favorite from a readability standpoint out of #all the things I tried. It also performs the best. def flatten8(seq): for x in seq: if not hasattr(x, '__iter__'): yield x else: for y in flatten8(x): yield y l = [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, 4], 3], 4, 3], 3, 1, 45], 9], 10]] if __name__=="__main__": print(l) print('flatten6', flatten6(l)) print('flatten8', list(flatten8(l))) print('flatten6', Timer("flatten6(l)", "from temp3 import flatten6, l").timeit()) print('flatten8', Timer("list(flatten8(l))", "from temp3 import flatten8, l").timeit()) - >src/python/Python-3.0/python temp3.py [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, 4], 3], 4, 3], 3, 1, 45], 9], 10]] flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10] flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10] flatten6 32.8386368752 flatten8 30.7509689331 >python temp3.py [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, 4], 3], 4, 3], 3, 1, 45], 9], 10]] flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10] flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10] flatten6 34.730714798 flatten8 32.3252940178 --RDM -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
In article , Michele Simionato wrote: > >Looks fine to me. In some situations you may also use hasattr(el, >'__iter__') instead of isinstance(el, list) (it depends if you want to >flatten generic iterables or only lists). Of course, once you do that, you need to special-case strings... -- Aahz (a...@pythoncraft.com) <*> http://www.pythoncraft.com/ Weinberg's Second Law: If builders built buildings the way programmers wrote programs, then the first woodpecker that came along would destroy civilization. -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Quoth rdmur...@bitdance.com: > This is all premature optimization, except for the goopy code, which is > presumably used enough to make it worth optimizing. And guess what? > The goopy code wins. What the people theorizing about the speed of > extend vs list creation miss is that the things with high overhead in the > above functions are (1) isinstance and (2) the recursive function call. > The goopy code avoids this by using type and is, and by unrolling the > lowest level without a function call. On the other hand, extend > _is_ faster than append if you aren't creating a new list, so the > goopy code can be optimized a little more. > > I remembered the bit about high function call overhead, but the rest > of it measured: Oooh, that's embarrassing. Not only didn't I read the code carefully enough, I didn't test the actual output of the functions. The goopy code doesn't flatten to arbitrary depth, so of course it is faster. --RDM -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mk wrote: >Brian Allen Vanderburg II wrote: >> I think it may be just a 'little' more efficient to do this: >> >> def flatten(x, res=None): >>if res is None: >> res = [] >>for el in x: >> if isinstance(el, (tuple, list)): >> flatten(el, res) >> else: >> res.append(el) >>return res > > >Hmm why should it be more efficient [than def flatten(x): res = [] for el in x: if isinstance(el,list): res.extend(flatten(el)) else: res.append(el) return res ]? extend operation should not be very costly? It's not a question of extend/append, it's the fact that your original function creates (and destroys) a new list for every recursive call. Which, if you've got large nested lists, will have an impact. -- \S -- si...@chiark.greenend.org.uk -- http://www.chaos.org.uk/~sion/ "Frankly I have no feelings towards penguins one way or the other" -- Arthur C. Clarke her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mk writes: > Hello everybody, > > Any better solution than this? > > def flatten(x): > res = [] > for el in x: > if isinstance(el,list): > res.extend(flatten(el)) > else: > res.append(el) > return res > > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] > print flatten(a) > > > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] > > Regards, > mk http://mail.python.org/pipermail/python-list/2005-July/330367.html -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Baolong zhen wrote: > On Thu, Feb 5, 2009 at 10:17 PM, mk wrote: > > > Brian Allen Vanderburg II wrote: > > >> def flatten(x): > > >> res = [] > > >> for el in x: > > >> if isinstance(el,list): > > >> res.extend(flatten(el)) > > >> else: > > >> res.append(el) > > >> return res > > > > > > > > I think it may be just a 'little' more efficient to do this: > > > > > > def flatten(x, res=None): > > >if res is None: > > > res = [] > > > > > >for el in x: > > > if isinstance(el, (tuple, list)): > > > flatten(el, res) > > > else: > > > res.append(el) > > > > > >return res > > > > > > Hmm why should it be more efficient? extend operation should not be very > > costly? > > less list creation. (Took me a while to find the content of your post because you top posted it. I've taken the liberty of correcting that.) This is all premature optimization, except for the goopy code, which is presumably used enough to make it worth optimizing. And guess what? The goopy code wins. What the people theorizing about the speed of extend vs list creation miss is that the things with high overhead in the above functions are (1) isinstance and (2) the recursive function call. The goopy code avoids this by using type and is, and by unrolling the lowest level without a function call. On the other hand, extend _is_ faster than append if you aren't creating a new list, so the goopy code can be optimized a little more. I remembered the bit about high function call overhead, but the rest of it measured: temp.py - from __future__ import print_function from timeit import Timer def flatten1(x): res = [] for el in x: if isinstance(el, list): res.extend(flatten1(el)) else: res.append(el) return res def flatten1a(x): res = [] for el in x: if isinstance(el, (tuple, list)): res.extend(flatten1a(el)) else: res.append(el) return res def flatten1b(x): res = [] for el in x: if type(el) is list or type(el) is tuple: res.extend(flatten1b(el)) else: res.append(el) return res def flatten2(x, res=None): if res is None: res = [] for el in x: if isinstance(el, list): flatten2(el, res) else: res.append(el) return res def flatten2a(x, res=None): if res is None: res = [] for el in x: if isinstance(el, (tuple, list)): flatten2a(el, res) else: res.append(el) return res def flatten2b(x, res=None): if res is None: res = [] for el in x: if type(el) is list or type(el) is tuple: flatten2b(el, res) else: res.append(el) return res def flatten3z(seq): lst = [] for x in seq: if type(x) is list or type(x) is tuple: for val in x: lst.append(val) else: lst.append(x) return lst def flatten3(seq): lst = [] for el in seq: if type(el) == list or type(el) is tuple: lst.extend(flatten3z(el)) else: lst.append(el) return lst def flatten3y(seq): lst = [] for x in seq: if type(x) is list or type(x) is tuple: lst.extend(x) else: lst.append(x) return lst def flatten3a(seq): lst = [] for el in seq: if type(el) == list or type(el) is tuple: lst.extend(flatten3y(el)) else: lst.append(el) return lst l = [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [5, 4], 3], 4, 3], 3, 1, 45], 9], 10]] cases = dict( base = Timer(), c1 = Timer("flatten1(l)", "from temp import flatten1, l"), c1a = Timer("flatten1a(l)", "from temp import flatten1a, l"), c1b = Timer("flatten1b(l)", "from temp import flatten1b, l"), c2 = Timer("flatten2(l)", "from temp import flatten2, l"), c2a = Timer("flatten2a(l)", "from temp import flatten2a, l"), c2b = Timer("flatten2b(l)", "from temp import flatten2b, l"), c3 = Timer("flatten3(l)", "from temp import flatten3, l"), c3a = Timer("flatten3a(l)", "from temp import flatten3a, l"), ) if __name__=="__main__": for (name, case) in sorted(cases.items()): print("{0:4s} {1}".format(name, case.timeit())) - It is also interesting to note that python3.0 is faster in this particular case (unless there are timing vagrancies on my machine, which is possible, though the results were fairly consistent over several runs of the script). The second run below is using python2.6.1. >src/python/Python-3.0/python temp.py base 0.0278329849243 c1 30.4776289463 c1a 44.3886289597 c1b 32.5621030331 c2 25.6131818295 c2a 39.0944678783 c2b 27.1573381424 c3 15.346280098 c3a 14.3178970814 >python temp.py base 0.02882695
Re: Flattening lists
> Either list creation is somewhat > costly, or "if var is None" is really cheap. "if x is y" is extremely cheap, I believe. Unlike most comparisons which are (relatively) expensive, that one is just comparing simple object address. You can't override "is" so there's a whole series of checks that don't have to get done. You don't have to go through the richcompare machinery, check if there's a __ne__, etc, etc. --S -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Brian Allen Vanderburg II wrote: Is list creation really more costly than above? Probably not. I wrote a small test program using a list several levels deep, each list containing 5 sublists at each level and finally just a list of numbers. Flattening 1000 times took about 3.9 seconds for the one creating a list at each level, and 3.2 for the one not creating the list at each level. Hmm, I'm surprised by even that! Apparently list creation is more expensive than I thought - it seems somewhat more expensive than the cost of interpreting bytecode for "if var is None". Either list creation is somewhat costly, or "if var is None" is really cheap. Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mrk...@gmail.com wrote: Baolong zhen wrote: less list creation. At the cost of doing this at each 'flatten' call: if res is None: res = [] The number of situations of executing above code is the same as the number of list creations (once for each 'flatten' call, obviously). Is list creation really more costly than above? Probably not. I wrote a small test program using a list several levels deep, each list containing 5 sublists at each level and finally just a list of numbers. Flattening 1000 times took about 3.9 seconds for the one creating a list at each level, and 3.2 for the one not creating the list at each level. Brian Vanderburg II -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Michele Simionato wrote: Looks fine to me. In some situations you may also use hasattr(el, '__iter__') instead of isinstance(el, list) (it depends if you want to flatten generic iterables or only lists). Thanks! Such stuff is what I'm looking for. Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Mark Dickinson wrote: I often find myself needing a 'concat' method that turns a list of lists (or iterable of iterables) into a single list; itertools.chain does this quite nicely. But I don't think I've ever encountered a need for the full recursive version. You're most probably right in this; however, my main goal here was finding 'more Pythonic' way of doing this and learning this way rather than the practical purpose of flattening deeply nested lists. Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mk wrote: Hello everybody, Any better solution than this? def flatten(x): res = [] for el in x: if isinstance(el,list): res.extend(flatten(el)) else: res.append(el) return res a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print flatten(a) It depends on what you mean by "better". More features? Here is the function from Sage (http://www.sagemath.org), which is a modified version of a more standard implementation to give a max_level argument. The first few lines of documentation: def flatten(in_list, ltypes=(list, tuple), max_level=sys.maxint): """ Flattens a nested list. INPUT: in_list -- a list or tuple ltypes -- optional list of particular types to flatten max_level -- the maximum level to flatten OUTPUT: a flat list of the entries of in_list (lots of examples follow this documentation) The implementation: http://www.sagemath.org/hg/sage-main/file/b0aa7ef45b3c/sage/misc/flatten.py Jason -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 5, 2:17 pm, mk wrote: > Hello everybody, > > Any better solution than this? > > def flatten(x): > res = [] > for el in x: > if isinstance(el,list): > res.extend(flatten(el)) > else: > res.append(el) > return res > > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] > print flatten(a) > > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] > > Regards, > mk Looks fine to me. In some situations you may also use hasattr(el, '__iter__') instead of isinstance(el, list) (it depends if you want to flatten generic iterables or only lists). -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Baolong zhen wrote: less list creation. At the cost of doing this at each 'flatten' call: if res is None: res = [] The number of situations of executing above code is the same as the number of list creations (once for each 'flatten' call, obviously). Is list creation really more costly than above? Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
On Feb 5, 1:17 pm, mk wrote: > Hello everybody, > > Any better solution than this? > > def flatten(x): Just out of interest, how often do people really need such a recursive flatten, as opposed to a single-level version? I often find myself needing a 'concat' method that turns a list of lists (or iterable of iterables) into a single list; itertools.chain does this quite nicely. But I don't think I've ever encountered a need for the full recursive version. Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
less list creation. On Thu, Feb 5, 2009 at 10:17 PM, mk wrote: > Brian Allen Vanderburg II wrote: > >> def flatten(x): > >> res = [] > >> for el in x: > >> if isinstance(el,list): > >> res.extend(flatten(el)) > >> else: > >> res.append(el) > >> return res > > > > > I think it may be just a 'little' more efficient to do this: > > > > def flatten(x, res=None): > >if res is None: > > res = [] > > > >for el in x: > > if isinstance(el, (tuple, list)): > > flatten(el, res) > > else: > > res.append(el) > > > >return res > > > Hmm why should it be more efficient? extend operation should not be very > costly? > > > Regards, > mk > > -- > http://mail.python.org/mailman/listinfo/python-list > -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Brian Allen Vanderburg II wrote: def flatten(x): res = [] for el in x: if isinstance(el,list): res.extend(flatten(el)) else: res.append(el) return res I think it may be just a 'little' more efficient to do this: def flatten(x, res=None): if res is None: res = [] for el in x: if isinstance(el, (tuple, list)): flatten(el, res) else: res.append(el) return res Hmm why should it be more efficient? extend operation should not be very costly? Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
These functions come from goopy: def flatten1(seq): """ Return a list with the contents of SEQ with sub-lists and tuples "exploded". This is only done one-level deep. """ lst = [] for x in seq: if type(x) is list or type(x) is tuple: for val in x: lst.append(val) else: lst.append(x) return lst def flatten(seq): """ Returns a list of the contents of seq with sublists and tuples "exploded". The resulting list does not contain any sequences, and all inner sequences are exploded. For example: >>> flatten([7,(6,[5,4],3),2,1]) [7,6,5,4,3,2,1] """ lst = [] for el in seq: if type(el) == list or type(el) is tuple: lst.extend(flatten(el)) else: lst.append(el) return lst Brian Allen Vanderburg II wrote: mrk...@gmail.com wrote: Hello everybody, Any better solution than this? def flatten(x): res = [] for el in x: if isinstance(el,list): res.extend(flatten(el)) else: res.append(el) return res a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print flatten(a) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Regards, mk -- http://mail.python.org/mailman/listinfo/python-list I think it may be just a 'little' more efficient to do this: def flatten(x, res=None): if res is None: res = [] for el in x: if isinstance(el, (tuple, list)): flatten(el, res) else: res.append(el) return res Brian Vanderburg II -- http://mail.python.org/mailman/listinfo/python-list -- Shane Geiger, IT Director Council For Economic Education / www.councilforeconed.org sgei...@councilforeconed.org / 402-438-8958 Teaching Opportunity -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
Brian Allen Vanderburg II wrote: >> def flatten(x): >> res = [] >> for el in x: >> if isinstance(el,list): >> res.extend(flatten(el)) >> else: >> res.append(el) >> return res > > I think it may be just a 'little' more efficient to do this: > > def flatten(x, res=None): >if res is None: > res = [] > >for el in x: > if isinstance(el, (tuple, list)): > flatten(el, res) > else: > res.append(el) > >return res Hmm why should it be more efficient? extend operation should not be very costly? Regards, mk -- http://mail.python.org/mailman/listinfo/python-list
Re: Flattening lists
mrk...@gmail.com wrote: Hello everybody, Any better solution than this? def flatten(x): res = [] for el in x: if isinstance(el,list): res.extend(flatten(el)) else: res.append(el) return res a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print flatten(a) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Regards, mk -- http://mail.python.org/mailman/listinfo/python-list I think it may be just a 'little' more efficient to do this: def flatten(x, res=None): if res is None: res = [] for el in x: if isinstance(el, (tuple, list)): flatten(el, res) else: res.append(el) return res Brian Vanderburg II -- http://mail.python.org/mailman/listinfo/python-list