Chalarangelo / 30-seconds-of-python

Short Python code snippets for all your development needs
https://www.30secondsofcode.org/python/p/1
Creative Commons Attribution 4.0 International
8.83k stars 1.26k forks source link

[FEATURE] Improve filter_unique and filter_non_unique running time #170

Closed mx-psi closed 4 years ago

mx-psi commented 4 years ago

The filter_non_unique and filter_unique snippets currently have a quadratic running time; in both cases they count each item in the original list. This can be improved to linear time by using a counter from the collections module (at the expense of linear space).

Improvement of filter_unique

from collections import Counter

def filter_unique(lst):
  counter = Counter(lst)
  return [item for item, count in counter.items() if count > 1]

Improvement of filter_non_unique

from collections import Counter

def filter_non_unique(lst):
  counter = Counter(lst)
  return [item for item, count in counter.items() if count == 1]
Chalarangelo commented 4 years ago

If you can PR these changes along with their explanations, I'd be glad to merge them. Thanks for the feedback!