从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和高效的方式编写它？

- xssChauhan

---

尝试：set(a)[:n]翻译：此代码意图为从列表a中创建一个集合(set)，然后选择前n个元素，最终返回这些元素所构成的新的集合。 - Tony Pellerin

@TonyPellerin 不保证您获得前5个元素。 - juanpa.arrivillaga

你的代码已经很Pythonic了，只是效率不高。element not in itr[:index] 不够高效，应该使用集合（set）。 - juanpa.arrivillaga

这个列表是否总是有序的？ - user8408080

未来参考：如果您的代码能够正常运行并需要改进，最好将其发布在https://codereview.stackexchange.com上。 - Azat Ibrakov

Answer 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版本中，您将收到弃用警告，在仍使用raise StopIteration的情况下，3.7版本会引发RuntimeErrors：Transition Plan。

---

你的解决方案使用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})的内存

- Patrick Artner

---

你可以使用以下代码替换 if e in seen: continue，yield e 和 return：在末尾只需使用 return list(seen) 即可。 - mkrieger1

@mkrieger1 这并不能保证返回的项目与它们遇到的顺序相同。 - khelwood

生成器中的yield关键字 :) list(set)不 - Patrick Artner

有没有类似于有序集合的东西？ - mkrieger1

@mkrieger1 是的，但没有内置的。您可以像使用集合一样使用OrderedDict，或者在Python 3.7+中只使用普通的dict。 - juanpa.arrivillaga

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]

- jpp

---

另一种方法是创建一个无限生成器，然后使用 itertools.islice(gen, limit)。 - Chris_Rands

为什么不在你的第一个代码块中删除第三行，改为使用seen.add(element)呢？ - gosuto

@jorijnsmit，这是一种优化。在for循环的每次迭代中少了一个查找。您应该会在非常大的循环中注意到差异。 - jpp

这第二个解决方案是最快的，可以在这里看到。 - Jurgen Strydom

Answer 3

如果您的对象是可散列的（例如int是可散列的），您可以编写实用函数，使用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所提到的，这个解决方案遍历整个集合，我们可以通过编写类似其他人已经做过的generator形式的nub实用程序来改进它:

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

- Azat Ibrakov

---

我在考虑这个，肯定很短，但是它的时间复杂度是O(N)。 - Chris_Rands

Answer 4

这里介绍一种使用 itertools.takewhile() 的Pythonic方法：

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}

- Mazdak

---

这里“or”运算符的滥用被认为是Pythonic的定义是什么？ - cdlane

@cdlane 根据定义，这里使用的 or 是错误的。 - Mazdak

我认为应该使用适当的函数而不是lambda。在这里，seen.add没有返回布尔值，但仍然被用于真值检查。你的实现省去了编写生成器函数的步骤，这是一个受欢迎的建议。但是predicate函数应该更加明确。 - xssChauhan

我们对“Pythonic”有不同的概念：成为Pythonic意味着使用干净、易读的语言结构和数据结构。 - cdlane

我不同意这是Pythonic的，seen.add or len(seen) <= 4 不应该在像 takewhile 这样的函数中使用，出于相同的原因，您也不会在 map 或 filter 中使用它。 - juanpa.arrivillaga

Answer 5

你可以使用OrderedDict或自Python 3.7起，普通的dict，因为它们被实现以保留插入顺序。注意这不适用于集合（sets）。

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

- Jindra Helcl

---

在3.6中，有序字典是一种实现细节（在参考实现中...不确定其他解释器如何处理）。直到3.7之前它都不是官方功能。 - glibdud

我认为 d = dict.fromkeys(a) 会更好。 - user3064538

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)

- grapes

---

使用 set 而不是 list 进行 O(1) 查找。 - jpp

@teng ... 低效。 - juanpa.arrivillaga

@teng 同样效率低下。 - juanpa.arrivillaga

@grapes 但这样做效率很低。而且，谁在乎行号呢？你缺少行数吗？我没有看到你对我的回复。是的，我同意，这个实现方法可以工作，至少是正确的。顺便说一下，我没有给你点踩。 - juanpa.arrivillaga

@juanpa.arrivillaga，我知道，我知道，最好的答案是使用set()，正如其他参与者所提到的。我并不打算让这段代码变得更快，只是让它更简洁易懂。这个简单的问题引起了如此多的热情，以至于我无法抵挡参与的欲望。 - grapes

Answer 7

假设元素按照所示顺序排序，这是一个使用itertools中的groupby函数玩乐的机会：

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

根据 @juanpa.arrivillaga 的建议，已更新为使用 islice 替代 enumerate。你甚至不需要一个 set 来跟踪重复内容。

- cdlane

---

你可以使用 islice。 - juanpa.arrivillaga

所以 groupby 保留顺序，很好，但这是一个实现细节还是一个特性？ - kubanczyk

@kubanczyk，是的，groupby主要用于已排序的数据，其中它成为聚合器。如果OP的数据未排序，则groupby无法解决此问题。但是，groupby可以与未排序的数据一起用于解决其他一些问题。在这种情况下，它可用于检测数据何时发生变化。 - cdlane

Answer 8

使用 sorted+key 结合 set

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

- BENY

---

这是低效的。 - juanpa.arrivillaga

@xssChauhan 这个代码确实可以按顺序返回结果，但我认为它的时间复杂度很低效，是O(n^2 * log n)。你可以使用O(N)的算法来完成。 - juanpa.arrivillaga

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

- pylang

Answer 10

性能分析

解决方案

哪个解决方案最快？有两个明显的答案（以及3个解决方案）获得了大部分票数。

1. Patrick Artner的解决方案 - 简称PA。
2. jpp的第一个解决方案 - 简称jpp1。
3. jpp的第二个解决方案 - 简称jpp2。

这是因为它们声称在O(N)中运行，而其他一些解决方案在O(N^2)中运行，或者不能保证返回列表的顺序。

实验设置

对于这个实验，考虑了3个变量。

1. N个元素。函数要搜索的前N个元素的数量。
2. 列表长度。列表越长，算法查找最后一个元素的距离就越远。
3. 重复限制。一个元素在下一个元素出现之前可以重复多少次。这是在1和重复限制之间均匀分布的。

数据生成的假设如下。这些假设对使用的算法有多严格取决于算法本身，但更多地是关于数据如何生成而不是算法本身的限制。

1. 元素在其重复序列首次出现在列表中后不会再次出现。
2. 元素是数字且递增的。
3. 元素属于int类型。

因此，在列表[1,1,1,2,2,3,4 ....]中，1、2、3永远不会再次出现。 4之后的下一个元素将是5，但在我们看到5之前，可能会有随机数量的4，最多达到重复限制。

为每个变量组合创建了一个新的数据集，并重新生成了20次。使用Python的timeit函数在每个数据集上对算法进行50次剖析。每种组合的20x50=1000次运行的平均时间在此处报告。由于算法是生成器，因此将它们的输出转换为列表以获取执行时间。

结果

正如预期的那样，搜索的元素越多，所需时间就越长。该图表显示执行时间确实是作者所声称的O(N)（直线证明了这一点）。

英文原文已经是中文了，以下是翻译：

图1. 改变搜索的前N个元素。

所有三种解决方案都不会消耗额外的计算时间。下面的图像显示当列表大小受限，而不是N个元素时会发生什么。长度为10k的列表，元素最多重复100次（因此平均重复50次），平均情况下会在200个元素（10000/50）左右用完所有独特的元素。如果这些图表中任何一个显示出超过200的计算时间增加，这将是一个值得关注的问题。

图2. 选择的前N个元素 > 独特元素数量的影响。

下面的图表再次显示，随着算法需要筛选的数据越多，处理时间会增加（以O(N)的速率）。增长率与变化前N个元素时相同。这是因为在两种情况下，遍历列表是常见的执行块，并且最终决定算法速度的执行块。

图3. 重复限制的变化。

结论：

在所有情况下，jpp发布的第二个解决方案是最快的解决方案。该解决方案仅比Patrick Artner发布的解决方案稍快，并且几乎比他的第一个解决方案快了一倍。

- Jurgen Strydom

---

这是非常有用的信息。是否也可以添加内存消耗分析？这样用户就可以考虑他们的限制并做出决策。 - xssChauhan

我同意，但在这种情况下，所有3个函数中存储的信息非常相似。此外，处理的数据集将比存储的信息大得多，因此与函数使用的内存相比可以忽略不计。 - Jurgen Strydom