Получение первых n уникальных элементов из списка Python - PullRequest
Новая
       20

Получение первых n уникальных элементов из списка Python

0 голосов
/ 21 декабря 2018

У меня есть список Python, где элементы могут повторяться. 

>>> a = [1,2,2,3,3,4,5,6]

Я хочу получить первые n уникальные элементы из списка.Итак, в этом случае, если мне нужны первые 5 уникальных элементов, они будут: 

[1,2,3,4,5]

Я пришел к решению с использованием генераторов: 

def iterate(itr, upper=5):

    count = 0
    for index, element in enumerate(itr):
        if index==0:
            count += 1
            yield element

        elif element not in itr[:index] and count<upper:
            count += 1
            yield element

Используется:

>>> i = iterate(a, 5)
>>> [e for e in i]
[1,2,3,4,5]

Я сомневаюсь, что это самое оптимальное решение.Есть ли альтернативная стратегия, которую я могу реализовать, чтобы написать ее более питонно и эффективно?

Ответы [ 12 ]

0 голосов
/ 21 декабря 2018

Вы можете адаптировать популярный рецепт itertools unique_everseen : 

def unique_everseen_limit(iterable, limit=5):
    seen = set()
    seen_add = seen.add
    for element in iterable:
        if element not in seen:
            seen_add(element)
            yield element
        if len(seen) == limit:
            break

a = [1,2,2,3,3,4,5,6]

res = list(unique_everseen_limit(a))  # [1, 2, 3, 4, 5]

В качестве альтернативы, как предлагает @Chris_Rands, вы можете использовать itertools.islice для извлечения фиксированного числа значений из неограниченного генератора: 

from itertools import islice

def unique_everseen(iterable):
    seen = set()
    seen_add = seen.add
    for element in iterable:
        if element not in seen:
            seen_add(element)
            yield element

res = list(islice(unique_everseen(a), 5))  # [1, 2, 3, 4, 5]

Обратите внимание, что рецепт unique_everseen доступен в сторонних библиотеках через more_itertools.unique_everseen или toolz.unique, чтобы вы могли использовать: 

from itertools import islice
from more_itertools import unique_everseen
from toolz import unique

res = list(islice(unique_everseen(a), 5))  # [1, 2, 3, 4, 5]
res = list(islice(unique(a), 5))           # [1, 2, 3, 4, 5]
0 голосов
/ 21 декабря 2018

Я бы использовал set для запоминания увиденного и возврата из генератора, когда у вас достаточно seen: 

a = [1,2,2,3,3,4,5,6]

def get_unique_N(iterable, N):
    """Yields (in order) the first N unique elements of iterable. 
    Might yield less if data too short."""
    seen = set()
    for e in iterable:
        if e in seen:
            continue
        seen.add(e)
        yield e
        if len(seen) == N:
            return

k = get_unique_N([1,2,2,3,3,4,5,6], 4)
print(list(k))

Выход: 

[1,2,3,4]

Согласно PEP-479 вы должны return от генераторов, а не raise StopIteration - спасибо @ khelwood & @ iBug за этот комментарий -никто никогда не узнает.

С 3.6 вы получаете устаревшее предупреждение, с 3.7 выдает RuntimeErrors: План перехода , если все еще используете raise StopIteration

Ваше решение с использованием elif element not in itr[:index] and count<upper: используетO(k) поисков - с k длиной отрезка - использование набора уменьшает это до O(1) поисков, но использует больше памяти, потому что набор также должен храниться.Это компромисс между скоростью и памятью - что лучше, зависит от приложения / данных.

Рассмотрим [1,2,3,4,4,4,4,5] против [1]*1000+[2]*1000+[3]*1000+[4]*1000+[5]*1000+[6]:

Для 6 уникальных номеров (в более длинном списке):

  • у вас будет поиск O(1)+O(2)+...+O(5001)
  • у меня будет 5001*O(1) поиск + память на set( {1,2,3,4,5,6})
Страница:
...