如何在Python中处理有序列表中的重复项，确保每个重复项只被处理一次？

Question

我有一个待处理的有序事项清单，其中包含一些重复项，我只想处理第一次出现的。目前，在Python v2.7中，我是这样做的：

seen = set()
for (value, fmt) in formats:
  if fmt not in seen:
    seen.add(fmt)
    process(value, fmt)

有没有一种方法可以同时将新元素插入到seen中并检测它是否已经存在？（这将避免在set中重复查找fmt。）

seen = set()
for (value, fmt) in formats:
  # myInsert() would return true if item was not already present.
  if seen.myInsert(fmt):
    process(value, fmt)

或者，我可以在循环之前过滤我的formats以排除重复条目吗？

unique_formats = removeDuplicates(formats, key=itemgetter(1))
for (value, fmt) in unique_formats:
  process(value, fmt)

- WilliamKF

---

集合查找后跟add()真的是值得优化的整体性能瓶颈吗？ - NPE

不是在这种情况下，但我仍然想知道如何处理很少出现但很重要的情况。此外，我希望代码更加简洁，只需一个函数调用而不是两个。 - WilliamKF

我会选择你提供的第一种解决方案，但要将add函数定义为本地变量。-> seen = set（），add = seen.add，并调用add（fmt）。 - SaCry

请在问题正文中发布您列表的一小部分。 - Ashwini Chaudhary

@SaCry，我不太明白你在建议什么，请你能否详细说明一下？ - WilliamKF

Answer 1

您可以在add()之前和之后获取集合的长度。如果长度没有改变，则表示该格式已经存在于集合中。

seen = set()
for (value, fmt) in formats:
    l1 = len(seen)
    seen.add(fmt)
    if l1 != len(seen):
         process(value, fmt)

您的问题假设in测试是一项昂贵的操作。事实证明这并不是真的。使用len()可能需要更多时间，尽管两者都非常快速；

In [4]: seen = set(range(10000))

In [5]: %timeit 5995 in seen
10000000 loops, best of 3: 122 ns per loop

In [6]: %timeit len(seen)
1000000 loops, best of 3: 167 ns per loop

(在2.5 GHz Core Quad Q9300上使用CPython 2.7.3测量)

- Roland Smith

---

既然add()和elem in seen都是O(1)操作，所以这并没有改进任何东西。除了你在这里使用了一些额外的内存之外。 - Ashwini Chaudhary

Answer 2

我认为你的第一种方法是最好的。甚至itertools recipes中的unique_everseen配方也使用了相同的方法。

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

- Ashwini Chaudhary

---

在我看来，这是正确的方法。这是一个迭代逻辑，因此您可以将其封装为生成器，编写 for something in looper(whatever):，然后继续进行工作。 - DSM

Answer 3

你必须使用一个集合：

for (value, fmt) in set(formats):
   process(value, fmt)

- Ionut Hulub

---

同时，这将采取独特的对。如果几个值具有相同的fmt，那么它们将不会执行相同的操作。 - Ismail Badawi

此外，set(ness) 应该只适用于 fmt，而不是值。 - WilliamKF

Answer 4

from ordereddict import OrderedDict
unique_formats = list(OrderedDict.fromkeys(format))
process(unique_formats)

这将保留顺序并删除重复项

- cashmere

---

但这并不保证它只会存储首次出现的键。 - Ashwini Chaudhary

Answer 5

你可以使用itertools.groupby按照一对中的第二个元素进行分组，然后只考虑第一个值。

>>> from itertools import imap, groupby
>>> from operator import itemgetter
>>> formats = [(1, 'xxx'), (2, 'xxx'), (3, 'yyy'), (4, 'yyy')]
>>> for fmt, value in imap(lambda (x, y): (x, next(y)[0]), groupby(formats, itemgetter(1)):
...    print('%s: %s', fmt, value)
...
xxx: 1
yyy: 3

- Ismail Badawi

---

这将在非连续重复中出现问题。 - DSM

如果“formats”是这样的：[(1，'xxx')，(2，'yyy')，(3，'xxx')，(4，'yyy')]，怎么办？ - Ashwini Chaudhary

Answer 6

如果你的列表是有序的，那么相同的格式肯定会相邻出现。这意味着你不需要使用一个集合来追踪过去的值。只需使用一个变量记录最近处理的格式即可。

last = None
for (value, fmt) in formats:
    if fmt != last:
        last = fmt
        process(value, fmt)

- Blckknght

---

如果列表未排序，则此操作将需要O(NlogN)的时间。 - Ashwini Chaudhary

@AshwiniChaudhary 不，如果列表未排序，则仍需要O（N）时间，但它将错误地处理一些重复项。我依赖提问者的断言，即输入确实已按格式排序，并呈现最简单的可能代码，适用于该情况。逻辑可能归结为与@isbadawi的答案相同的事情，使用groupby，但由于我的代码不需要lambda，因此它可能会运行得稍微快一些。 - Blckknght

列表必须按照“fmt”元素排序，否则这将无法工作。http://ideone.com/sX4RpB - Ashwini Chaudhary