从Python列表中获取前n个唯一元素

Question

我有一个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]

我怀疑这是最优化的解决方案.是否有一种替代策略可以实现以更加pythonic和更有效的方式编写它？

Answer 1

我会用a 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 Planraise StopIteration

使用您的解决方案elif element not in itr[:index] and count<upper:使用O(k)查找-与k被切片的长度-使用一组减少了这对O(1)查找但会占用更多的内存,因为该组必须保持为好.它是速度与内存的权衡 - 更好的是应用程序/数据依赖.

考虑[1,2,3,4,4,4,4,5]vs [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})

Answer 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]

Answer 3

如果你的对象是可哈希(ints为可哈希),您可以用编写效用函数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)

Answer 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]

Answer 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}

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

Answer 7

假设元素的顺序如图所示，这是一个享受groupbyitertools 函数的机会：

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每个 @juanpa.arrivillaga。您甚至不需要set跟踪重复项。