Re: Misuse of list comprehensions?
On May 20, 8:51 pm, Diez B. Roggisch [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: John Salerno: What does everyone think about this? The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. It uses append because it refers to itself in the if-expression. So the append(c) is needed - and thus the assignment possible but essentially useless. Diez Yes it does, it build a list of 'None's. And if list.append is concerned, the example given has no use, since: x = [c for c in cs] is essentially the same as x = [] [x.append(c) for c in cs] If, you're talking about other function calls, it might be an abuse or not depending on personal preference. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On Tue, May 20, 2008 at 11:19 AM, John Salerno [EMAIL PROTECTED] wrote: Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] After being corrected about missing the construction of a None-containing list, one needs of course to think about the waste of resources, as a possible result-list is created in any case. Yeah, I was already aware of the list of Nones, which is why I asked. Simply typing the list comprehension without an assignment just *looked* wrong, too. It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Ian Kelly [EMAIL PROTECTED] writes: On Tue, May 20, 2008 at 11:19 AM, John Salerno [EMAIL PROTECTED] wrote: Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] After being corrected about missing the construction of a None-containing list, one needs of course to think about the waste of resources, as a possible result-list is created in any case. Yeah, I was already aware of the list of Nones, which is why I asked. Simply typing the list comprehension without an assignment just *looked* wrong, too. It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) This is crazy! -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 27, 6:43 pm, Ian Kelly [EMAIL PROTECTED] wrote: On Tue, May 20, 2008 at 11:19 AM, John Salerno [EMAIL PROTECTED] wrote: Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] After being corrected about missing the construction of a None-containing list, one needs of course to think about the waste of resources, as a possible result-list is created in any case. Yeah, I was already aware of the list of Nones, which is why I asked. Simply typing the list comprehension without an assignment just *looked* wrong, too. It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) It could be shorter: def compress(s): new = [] return filter(None, (new.append(c) for c in s if c not in new)) or ''.join(new) :-) -- http://mail.python.org/mailman/listinfo/python-list
RE: Misuse of list comprehensions?
Ian Kelly wrote: It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) Are you aware that filter() returns a list populated from its arguments? Tim Delaney -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
En Tue, 27 May 2008 14:43:52 -0300, Ian Kelly [EMAIL PROTECTED] escribió: It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) filter returns a newly created list, so this code is as wasteful as a list comprehension (and harder to read). -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On Tue, May 27, 2008 at 7:09 PM, Delaney, Timothy (Tim) [EMAIL PROTECTED] wrote: Ian Kelly wrote: It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) Are you aware that filter() returns a list populated from its arguments? Yes. In this case, it returns an empty list. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On Tue, May 27, 2008 at 8:08 PM, Gabriel Genellina [EMAIL PROTECTED] wrote: En Tue, 27 May 2008 14:43:52 -0300, Ian Kelly [EMAIL PROTECTED] escribió: It sounds like the wasteful list creation is the biggest objection to using a list comprehension. I'm curious what people think of this alternative, which avoids populating the list by using a generator expression instead (apart from the fact that this is still quadratic, which I'm aware of). def compress(s): new = [] filter(None, (new.append(c) for c in s if c not in new)) return ''.join(new) filter returns a newly created list, so this code is as wasteful as a list comprehension (and harder to read). Here it returns a newly created *empty* list, which is not nearly as wasteful as one that's linear in the size of the input. I'll grant you the second point, though. I very much doubt that I would ever actually use this myself. I was just curious what others would think of it. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Simon Forman wrote: On May 21, 4:36 am, Bruno Desthuilliers bruno. [EMAIL PROTECTED] wrote: Simon Forman a écrit : On May 20, 8:58 am, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 10:50 am, [EMAIL PROTECTED] wrote: You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). -- Paul If order is important, you can use sorted() instead of list() like so: def compress(s): new = sorted(set(s), key=s.index) return return ''.join(new) This won't still preserve the *original* order. I don't understand. new will contain each unique item in s, sorted in order of the items' first occurance in s, right? There are other ways to do it (other functions that could be passed to sorted() as the key arg) of course, but this seems like a good value of original order, no? :) Regards, ~S But, I think, worst case quadratic performance through generating all the indices. Duncan -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Simon Forman a écrit : On May 20, 8:58 am, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 10:50 am, [EMAIL PROTECTED] wrote: You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). -- Paul If order is important, you can use sorted() instead of list() like so: def compress(s): new = sorted(set(s), key=s.index) return return ''.join(new) This won't still preserve the *original* order. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
''.join(seen.add(c) or c for c in s if c not in seen) From what I can understand... .join will be a String of unique 'c' values. 'seen.add(c) or c' will always point to the second statement 'c' because seen.add(c) returns None. 'if c not in seen' will ensure 'c' being added to both the .join and seen is unique. That is really clever! I like it :) (but does require a bit of knowledge about .add return None and the affect that has on the .. or .. statement) -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 21, 4:36 am, Bruno Desthuilliers bruno. [EMAIL PROTECTED] wrote: Simon Forman a écrit : On May 20, 8:58 am, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 10:50 am, [EMAIL PROTECTED] wrote: You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). -- Paul If order is important, you can use sorted() instead of list() like so: def compress(s): new = sorted(set(s), key=s.index) return return ''.join(new) This won't still preserve the *original* order. I don't understand. new will contain each unique item in s, sorted in order of the items' first occurance in s, right? There are other ways to do it (other functions that could be passed to sorted() as the key arg) of course, but this seems like a good value of original order, no? :) Regards, ~S -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? the above code is pretty much of a no-no because it has quadratic runtime behavior. That being said, I use that idiom myself. But I don't see anything wrong with using a list-comp as loop-abbreviation. because that is it's actual purpose. And also it is common in non-functional languages that l-values aren't always assigned, if the aren't needed. It's the consequence of having side-effects in a language - and python has them. Diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno: What does everyone think about this? The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
[EMAIL PROTECTED] wrote: John Salerno: What does everyone think about this? The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. It uses append because it refers to itself in the if-expression. So the append(c) is needed - and thus the assignment possible but essentially useless. Diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno a écrit : I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. (snip) def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) As far as I'm concerned (and I'm a big fan of list-comps, generator expressions etc), this is definitively an abuse. And a waste of resources since it builds a useless list of 'None'. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Diez B. Roggisch [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: John Salerno: What does everyone think about this? The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. This line: [new.append(c) for c in s if c not in new] ...throws away the list built by the comprehension itself, composed of None values (returned by append). It uses append because it refers to itself in the if-expression. So the append(c) is needed The append is not in question here. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Hrvoje Niksic wrote: Diez B. Roggisch [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: John Salerno: What does everyone think about this? The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. This line: [new.append(c) for c in s if c not in new] ...throws away the list built by the comprehension itself, composed of None values (returned by append). Ah. You are right of course. Diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Diez B. Roggisch [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. It uses append because it refers to itself in the if-expression. So the append(c) is needed - and thus the assignment possible but essentially useless. Yes it does. A list comprehension *always* creates a list. In this case it will be a list of None, since that is what list.append() returns. See this: new=[] s=This is a foolish use of list comprehensions [ new.append(c) for c in s if c not in new ] [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None] Yes, you do get a correct result in 'new', but you *also* create a 17 long list with all elements set to None, that is immediately thrown away. -- Thomas Bellman, Lysator Computer Club, Linköping University, Sweden I refuse to have a battle of wits with an ! bellman @ lysator.liu.se unarmed person.! Make Love -- Nicht Wahr! -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Thomas Bellman wrote: Diez B. Roggisch [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: The Example 2 builds a list, that is then thrown away. It's just a waste of memory (and time). No, it doesn't. It uses append because it refers to itself in the if-expression. So the append(c) is needed - and thus the assignment possible but essentially useless. Yes it does. A list comprehension *always* creates a list. In this case it will be a list of None, since that is what list.append() returns. See this: Yep - no idea how that slipped me. I still don't mind the occasional waste of a list-creation over a more concise looping-construct, but I totally admit that one has to be aware of this. more than I was Diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
That being said, I use that idiom myself. But I don't see anything wrong with using a list-comp as loop-abbreviation. because that is it's actual purpose. And also it is common in non-functional languages that l-values aren't always assigned, if the aren't needed. It's the consequence of having side-effects in a language - and python has them. After being corrected about missing the construction of a None-containing list, one needs of course to think about the waste of resources, as a possible result-list is created in any case. I personally still don't mind that (if we talk about a few hundred objects a top) - but it makes a strong point against a general usage. Diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 8:13 am, John Salerno [EMAIL PROTECTED] wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Why not make the list comp the actual list you are trying to build? def compress(s): seen = set() new = [c for c in s if c not in seen and (seen.add(c) or True)] return ''.join(new) or just: def compress(s): seen = set() return ''.join(c for c in s if c not in seen and (seen.add(c) or True)) Using the set also gets rid of that nasty quadratic performance thingy. -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Paul McGuire [EMAIL PROTECTED] writes: On May 20, 8:13 am, John Salerno [EMAIL PROTECTED] wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Why not make the list comp the actual list you are trying to build? def compress(s): seen = set() new = [c for c in s if c not in seen and (seen.add(c) or True)] split hairs Isn't c not in seen and (seen.add(c) or True) the same as seen.add(c) or c not in seen ? return ''.join(new) (notice I haven't closed the tag!) -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 9:58 am, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 8:13 am, John Salerno [EMAIL PROTECTED] wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Why not make the list comp the actual list you are trying to build? def compress(s): seen = set() new = [c for c in s if c not in seen and (seen.add(c) or True)] return ''.join(new) or just: def compress(s): seen = set() return ''.join(c for c in s if c not in seen and (seen.add(c) or True)) Using the set also gets rid of that nasty quadratic performance thingy. You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 10:17 am, Arnaud Delobelle [EMAIL PROTECTED] wrote: Paul McGuire [EMAIL PROTECTED] writes: On May 20, 8:13 am, John Salerno [EMAIL PROTECTED] wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Why not make the list comp the actual list you are trying to build? def compress(s): seen = set() new = [c for c in s if c not in seen and (seen.add(c) or True)] split hairs Isn't c not in seen and (seen.add(c) or True) the same as seen.add(c) or c not in seen ? return ''.join(new) (notice I haven't closed the tag!) -- Arnaud- Hide quoted text - - Show quoted text - Unfortunately, no. seen.add(c) or c not in seen will never return true, since c gets added to seen before testing if c in seen. -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 10:50 am, [EMAIL PROTECTED] wrote: You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 3:58 pm, Paul McGuire [EMAIL PROTECTED] wrote: def compress(s): seen = set() return ''.join(c for c in s if c not in seen and (seen.add(c) or True)) Slightly nicer is to move the set add out of the conditional... def compress(s): seen = set() return ''.join(seen.add(c) or c for c in s if c not in seen) I wouldn't write it this way though :) -- Paul Hankin -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Paul McGuire [EMAIL PROTECTED] writes: On May 20, 10:17 am, Arnaud Delobelle [EMAIL PROTECTED] wrote: [...] split hairs Isn't c not in seen and (seen.add(c) or True) the same as seen.add(c) or c not in seen ? return ''.join(new) (notice I haven't closed the tag!) -- Arnaud- Hide quoted text - - Show quoted text - Unfortunately, no. seen.add(c) or c not in seen will never return true, since c gets added to seen before testing if c in seen. -- Paul Ha you're right of course. But I haven't closed the tag yet, so: c not in seen and (seen.add(c) or True) is definitely the same as c not in seen and not seen.add(c) which is not (c in seen or seen.add(c)) :) /split hairs -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] After being corrected about missing the construction of a None-containing list, one needs of course to think about the waste of resources, as a possible result-list is created in any case. Yeah, I was already aware of the list of Nones, which is why I asked. Simply typing the list comprehension without an assignment just *looked* wrong, too. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Paul McGuire [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] On May 20, 10:50 am, [EMAIL PROTECTED] wrote: def compress(s): return list(set(s)) That does the trick. Wow, I just *knew* there had to be some built-in function that would make this problem trivial! :) Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). Good point. For me it doesn't matter because it wasn't my problem originally. I just had a question about the list comp. But if order matters, then I guess set doesn't work? -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Bruno Desthuilliers [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) As far as I'm concerned (and I'm a big fan of list-comps, generator expressions etc), this is definitively an abuse. And a waste of resources since it builds a useless list of 'None'. I agree with you. After being proud of myself for about 20 seconds, it suddenly seemed like an abuse rather than a clever way to do it in one line. :) It just looked wrong to have a list comp. without an assignment, etc. Actually, though, I wasn't so much thinking of the waste of resources as I was that what was happening didn't seem to be explicit or evident enough. So despite the fact that the for loop with the nested if is the exact same code, it just seems more appropriate. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] | Diez B. Roggisch [EMAIL PROTECTED] wrote in message | news:[EMAIL PROTECTED] | the above code is pretty much of a no-no because it has quadratic runtime | behavior. | | | What's that mean, exactly? Are you referring to both examples, or just the | second one? Both. Searching new takes longer each time. More exactly, the number of comparisons should be about len(s)*len(new_final)/2, depending on how duplicates are distributed in s. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno [EMAIL PROTECTED] writes: Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] the above code is pretty much of a no-no because it has quadratic runtime behavior. What's that mean, exactly? It means that running time will increase with the square of the problem size. 2.000.000 items will take 4 times as long as 1.000.000 items, and 5.000.000 items will take 25 times as long as 1.000.000 items. Are you referring to both examples, or just the second one? The problem is that the lookup you did to see if an item had already been seen, is done by a linear search of a list. The search time is linearly proportional to the number of items on the list 'new', but since the number of times you do that search increases with the length of the input, the total runtime for your function increases even more. This thus applies to both your examples, since they really do the same thing. However, it actually depends on what your input is. For the runtime to increase with the square of the input length in your function, the number of *unique* items on the input must be a constant fraction of the input length. By that I mean that, for example, 5% of the input items are unique, so that if your input is 100 items, then the list 'new' will be 5 items at the end of the function, and if your input is 5.000.000 items, then 'new' will become 250.000 items long. This might not be the case in your use. If you for example know that the input only consists of integers between 0 and 10, then 'new' will never become longer than 11 items, regardless of whether the input is 20 or 20.000.000.000 items. The runtime of your function then suddenly becomes linear in the problem size instead of quadratic. Even so, maintaining the set of already seen items as a set is likely to be faster than keeping them as a list, even for a fairly small number of unique items. One small exception from this, though. If only maintaining one data structure (the ordered list 'new' in your code) makes your working set fit within the processor cache, while maintaining two data structures (a list for keeping the order, and a set for searching) will make it *not* fit within the cache, then it *might* actually be faster to just maintain the list. Unlikely, but not entirely impossible, and just a small change of the problem size can change the balance again. -- Thomas Bellman, Lysator Computer Club, Linköping University, Sweden What sane person could live in this world ! bellman @ lysator.liu.se and not be crazy? -- Ursula K LeGuin ! Make Love -- Nicht Wahr! -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 12:22 pm, John Salerno [EMAIL PROTECTED] wrote: Paul McGuire [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] On May 20, 10:50 am, [EMAIL PROTECTED] wrote: def compress(s): return list(set(s)) That does the trick. Wow, I just *knew* there had to be some built-in function that would make this problem trivial! :) Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). Good point. For me it doesn't matter because it wasn't my problem originally. I just had a question about the list comp. But if order matters, then I guess set doesn't work? Yeah, it doesn't work. I didn't know that detail about sets until now (like dicts, you can't expect the order to remain the same). I also forgot that you were joining the list, so the return statement would have looked like return ''.join(set(s)), but you have to go with the list comprehension if you want it to keep the same order. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Thomas Bellman [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] John Salerno [EMAIL PROTECTED] writes: Diez B. Roggisch [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] the above code is pretty much of a no-no because it has quadratic runtime behavior. What's that mean, exactly? However, it actually depends on what your input is. For the runtime to increase with the square of the input length in your function, the number of *unique* items on the input must be a constant fraction of the input length. Whew! Let me re-read your post... :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 3:58 pm, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 8:13 am, John Salerno [EMAIL PROTECTED] wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Why not make the list comp the actual list you are trying to build? ... Because it obscures the intent of the code. - Paddy. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 11:08 am, Paul Hankin [EMAIL PROTECTED] wrote: On May 20, 3:58 pm, Paul McGuire [EMAIL PROTECTED] wrote: def compress(s): seen = set() return ''.join(c for c in s if c not in seen and (seen.add(c) or True)) Slightly nicer is to move the set add out of the conditional... def compress(s): seen = set() return ''.join(seen.add(c) or c for c in s if c not in seen) I wouldn't write it this way though :) -- Paul Hankin Thank you, Paul. I knew I had seen a cleaner version than mine, and I could not remember how it was done. -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
Colin J. Williams wrote: John Salerno wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Alternative ways of of looking at the problem are: # compress.py import sets def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) def compress1(s): new= [] d= dict(zip(s, len(s)*[[]])) return d.keys() def compress2(st): s= sets.Set(st) return s if __name__ == __main__: s= 'In example 1, the intention to make an in-place change is explicit, and it is' print (compress(s)) print (compress1(s)) print (compress2(s)) Results: In exampl1,thiok-cgsd ['a', ' ', 'c', 'e', 'i', 'g', 'I', 'h', 'k', '-', 'm', 'l', 'o', 'n', '1', 'p', 's', 't', 'x', ',', 'd'] Set(['a', ' ', 'c', 'e', 'i', 'g', 'I', 'h', 'k', '-', 'm', 'l', 'o', 'n', '1', 'p', 's', 't', 'x', ',', 'd']) Colin W. I should have read all the responses before responding! Paul McGuire had already suggested a set approach Colin W. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? You might use this: def compress(s) return ''.join([ u for u in s if u not in locals()['_[1]'] ]) -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
John Salerno wrote: I posted this code last night in response to another thread, and after I posted it I got to wondering if I had misused the list comprehension. Here's the two examples: Example 1: def compress(s): new = [] for c in s: if c not in new: new.append(c) return ''.join(new) -- Example 2: def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) -- In example 1, the intention to make an in-place change is explicit, and it's being used as everyone expects it to be used. In example 2, however, I began to think this might be an abuse of list comprehensions, because I'm not assigning the result to anything (nor am I even using the result in any way). What does everyone think about this? Should list comprehensions be used this way, or should they only be used to actually create a new list that will then be assigned to a variable/returned/etc.? Alternative ways of of looking at the problem are: # compress.py import sets def compress(s): new = [] [new.append(c) for c in s if c not in new] return ''.join(new) def compress1(s): new= [] d= dict(zip(s, len(s)*[[]])) return d.keys() def compress2(st): s= sets.Set(st) return s if __name__ == __main__: s= 'In example 1, the intention to make an in-place change is explicit, and it is' print (compress(s)) print (compress1(s)) print (compress2(s)) Results: In exampl1,thiok-cgsd ['a', ' ', 'c', 'e', 'i', 'g', 'I', 'h', 'k', '-', 'm', 'l', 'o', 'n', '1', 'p', 's', 't', 'x', ',', 'd'] Set(['a', ' ', 'c', 'e', 'i', 'g', 'I', 'h', 'k', '-', 'm', 'l', 'o', 'n', '1', 'p', 's', 't', 'x', ',', 'd']) Colin W. -- http://mail.python.org/mailman/listinfo/python-list
Re: Misuse of list comprehensions?
On May 20, 8:58 am, Paul McGuire [EMAIL PROTECTED] wrote: On May 20, 10:50 am, [EMAIL PROTECTED] wrote: You don't need all those conditionals. A set differs from a list precisely in the fact that each element is unique. And since the function is expecting s to be an iterable object, it can be constructed even without a for loop: def compress(s): return list(set(s)) That does the trick. Only if order does not need to be maintained. list(set(s)) will not necessarily keep the unique characters in the order they are seen. We'll have to check with the OP to see if this is important (I just assumed that it was because of the use of list comps). -- Paul If order is important, you can use sorted() instead of list() like so: def compress(s): new = sorted(set(s), key=s.index) return return ''.join(new) ~Simon -- http://mail.python.org/mailman/listinfo/python-list
