Подтвердить что ты не робота

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

У меня есть список 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]

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

4b9b3361

ОТВЕТЫ

Ответ 1

Я бы использовал 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: Transition Plan, если все еще используете 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})

Ответ 2

Вы можете адаптировать популярный рецепт 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]

Ответ 3

Если ваши объекты hashable (int является hashable), вы можете написать функцию полезности, используя fromkeys метод из collections.OrderedDict класса (или начиная с Python3.7 простым dict, так как они стали официально заказаны), как

from collections import OrderedDict


def nub(iterable):
    """Returns unique elements preserving order."""
    return OrderedDict.fromkeys(iterable).keys()

и тогда реализация iterate может быть упрощена до

from itertools import islice


def iterate(itr, upper=5):
    return islice(nub(itr), upper)

или если вы хотите всегда list в качестве вывода

def iterate(itr, upper=5):
    return list(nub(itr))[:upper]

улучшения

Как упомянул @Chris_Rands, это решение проходит через всю коллекцию, и мы можем улучшить это, написав утилиту nub в форме генератора, как уже делали другие:

def nub(iterable):
    seen = set()
    add_seen = seen.add
    for element in iterable:
        if element in seen:
            continue
        yield element
        add_seen(element)

Ответ 4

Вы можете использовать OrderedDict или, начиная с Python 3.7, обычный dict, так как они реализованы для сохранения порядка вставки. Обратите внимание, что это не будет работать с наборами.

N = 3
a = [1, 2, 2, 3, 3, 3, 4]
d = {x: True for x in a}
list(d.keys())[:N]

Ответ 5

Вот Pythonic подход с использованием itertools.takewhile():

In [95]: from itertools import takewhile

In [96]: seen = set()

In [97]: set(takewhile(lambda x: seen.add(x) or len(seen) <= 4, a))
Out[97]: {1, 2, 3, 4}

Ответ 6

Есть действительно удивительные ответы на этот вопрос, которые быстрые, компактные и блестящие! Причина, по которой я привожу здесь этот код, состоит в том, что я считаю, что существует множество случаев, когда вам не нужно терять 1 микросекунду, или вам не нужны дополнительные библиотеки в вашем коде для единовременного решения простой задачи.

a = [1,2,2,3,3,4,5,6]
res = []
for x in a:
    if x not in res:  # yes, not optimal, but doesnt need additional dict
        res.append(x)
        if len(res) == 5:
            break
print(res)

Ответ 7

Использование set с sorted+ key

sorted(set(a), key=list(a).index)[:5]
Out[136]: [1, 2, 3, 4, 5]

Ответ 8

Если предположить, что элементы упорядочены, как показано, это возможность весело провести время с groupby функции в itertools:

from itertools import groupby, islice

def first_unique(data, upper):
    return islice((key for (key, _) in groupby(data)), 0, upper)

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

print(list(first_unique(a, 5)))

Обновлен для использования islice вместо enumerate per @juanpa.arrivillaga. Вам даже не нужен set для отслеживания дубликатов.

Ответ 9

Дано

import itertools as it


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

Код

Простое понимание списка (похоже на ответ @cdlane).

[k for k, _ in it.groupby(a)][:5]
# [1, 2, 3, 4, 5]

В качестве альтернативы в Python 3. 6+:

list(dict.fromkeys(a))[:5]
# [1, 2, 3, 4, 5]

Ответ 10

Почему бы не использовать что-то подобное?

>>> a = [1, 2, 2, 3, 3, 4, 5, 6]
>>> list(set(a))[:5]
[1, 2, 3, 4, 5]

Ответ 11

Вы можете попробовать метод, который использует наборы. В sets Python возвращает неупорядоченные коллекции уникальных элементов. Следующий код дает пример того, как использовать se в вашей проблеме.

a = [1,2,2,3,3,4,5,6]
b = []
flag = True
while(flag):
    num = 5
    b = list(set(a))[:num]
    if(len(b)==5): flag = False

print b
>>>[1 2 3 4 5]

Ответ 12

a = [1,2,2,3,3,4,5,6]
def unique(a,size):
    return list(set(a))[:size]
print(unique(a,5))

Ответ 13

Пример списка:

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

Функция возвращает все или количество уникальных предметов, необходимых из списка

1-й аргумент - список для работы, 2-й аргумент (необязательно) - количество уникальных элементов (по умолчанию - Нет - это означает, что будут возвращены все уникальные элементы)

def unique_elements(lst, number_of_elements=None):
    return list(dict.fromkeys(lst))[:number_of_elements]

Вот пример, как это работает. Имя списка - "а", и нам нужно получить 2 уникальных элемента:

print(unique_elements(a, 2))

Выход:

output

Ответ 14

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

from collections import defaultdict
def function(lis,n):
    dic = defaultdict(int)

    sol=set()

    for i in lis:
            try:
                if dic[i]:
                    pass
                else:
                    sol.add(i)
                    dic[i]=1
                    if len(sol)>=n:
                        break
            except KeyError:
                pass

    return list(sol)

print(function(a,3))

выход

[1, 2, 3]

Ответ 15

Сделай это:

sorted(set(a), key=a)[:5]

Это работает, потому что наборы не повторяются.

Ответ 16

Вы используете набор, чтобы получить первые n уникальных значений, но он не сохраняет порядок внутри первых n уникальных значений.

n=5
s=set()
for i in a:
    if len(s)<n: s.add(i)
    else: break 
print(s)