Misuse of list comprehensions?

[John Salerno]

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?

 

[John Salerno]

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.

 

[Terry Reedy]

| | > 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.

 

[s0suk3]

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.

 

[John Salerno]

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...........

 

[Paddy]

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:

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.

 

[Paul McGuire]

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

Thank you, Paul. I knew I had seen a cleaner version than mine, and I
could not remember how it was done.



-- Paul

 

[Colin J. Williams]

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.

 

[Colin J. Williams]

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.

 

[Simon Forman]

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

 

[Bruno Desthuilliers]

Simon Forman a écrit :

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.

 

[cokofreedom]

''.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)

 

[Simon Forman]

Simon Forman a écrit :






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

 

[duncan smith]

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

 

[Bruno Desthuilliers]

Simon Forman a écrit :

I don't understand.

new will contain each unique item in s, sorted in order of the items'
first occurance in s, right?

Yep. Answered too fast, missed the key param. Sorry.

 

[Ian Kelly]

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)

 

[Arnaud Delobelle]

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!

 

[MRAB]

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)

 

[Gabriel Genellina]

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).

 

[Ian Kelly]

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.