Как обработать каждый элемент в упорядоченном списке с дубликатами только один раз в Python?

Question

У меня есть упорядоченный список объектов для обработки, который включает несколько дубликатов, и я хочу обработать только первое вхождение. В настоящее время я делаю это так в Python v2.7:

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

Есть ли в любом случае одновременно вставить новый элемент в seen и определить, присутствовал ли он уже или нет? (Это позволит избежать повторного поиска fmt в set.)

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)

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

(измерено с помощью CPython 2.7.3 на 2.5 ГГц Core Quad Q9300)

Answer 2

Я думаю, что ваш первый подход является лучшим. Даже unique_everseen рецепт от itertools recipes использует тот же подход.

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

Answer 3

Вы должны использовать набор:

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

Answer 4

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

Это сохранит порядок и удалит дубликаты

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

Answer 6

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

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