1
\$\begingroup\$

I'm guessing this has quadratic time complexity, \$O(n^2)\$, and \$O(2n)\$ for memory complexity. I wonder if I can do something within the list comprehension to just .pop(n) something out of the list instead of relying on a second list. Thoughts?

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[[listLettersAlreadyFound.append(letter) for letter in list(word) if letter not in listLettersAlreadyFound] for word in listx]
print listLettersAlreadyFound
\$\endgroup\$
5
\$\begingroup\$

The reason you get \$O(n^2)\$ time complexity is due to you going through listLettersAlreadyFound, whilst checking if the new item is in that. To improve the performance, you could create another set, reducing time complexity to \$O(n)\$.

But before that, listLettersAlreadyFound is long, first list is unneeded, but lettersAlreadyFound is the same as previous_letters. And you should use snake_case rather than CamelCase.

I also find your comprehensions hard to read, you need to space the logic on different lines. Take:

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[
    [
        listLettersAlreadyFound.append(letter)
        for letter in list(word)
        if letter not in listLettersAlreadyFound
    ]
    for word in listx
]
print listLettersAlreadyFound

From this it's easy to notice that a comprehension is probably not the best choice here. You don't actually want the list, you only want the side affects from the list. This goes against the spirit of Functional Programming, which is what comprehensions are. And so you should instead just use a simple for loop.

Merging the above all together could get you some \$O(n^2)\$ time complexity code, that also has \$O(2n)\$ memory:

words = ['cat', 'dog','rabbit']
unique_letters = []
previous_letters = set()

for letter in (letter for word in words for letter in word):
    if letter in previous_letters:
        continue
    previous_letters.add(letter)
    unique_letters.append(letter)

print unique_letters

Finally if you don't care about the order of the letters, you can change the for loop to be set. And instead just use:

words = ['cat', 'dog','rabbit']

print set(letter for word in words for letter in word)

Also .pop(n) will keep the \$O(n^2)\$ time complexity, and so I'd suggest you don't use it, if you really want better memory performance, use a for loop, as it'd keep the code readable, not a list comprehension.

\$\endgroup\$
  • 1
    \$\begingroup\$ If order is not important, you can also do something like: list(set(''.join(words))) \$\endgroup\$ – Grajdeanu Alex. Dec 18 '16 at 17:39
  • 1
    \$\begingroup\$ @Dex'ter I already mentioned that, however I went for comprehensions, if they later use different datatype. \$\endgroup\$ – Peilonrayz Dec 18 '16 at 18:09
  • \$\begingroup\$ Thanks a million for your help guys. I know about "set" but I got this exercise from a book and I thought about trying with list comprehensions before watching the video with the solution: interactivepython.org/runestone/static/pythonds/Introduction/… \$\endgroup\$ – theMarceloR Dec 19 '16 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.