Удалить уникальные значения из списка и сохранить только дубликаты

Question

Я ищу, чтобы запустить список идентификаторов и вернуть список всех идентификаторов, которые произошли более одного раза. Это было то, что я установил, что работает:

singles = list(ids) 
duplicates = [] 
while len(singles) > 0: 
    elem = singles.pop() 
    if elem in singles: 
     duplicates.append(elem) 

Но список идентификаторов, вероятно, получить довольно долго, и я реально не хочу время цикла определяющегося дорогой лены вызов, если я могу избежать его. (Я мог бы пойти неэлегантным путем и позвонить len один раз, а затем просто уменьшить его на каждую итерацию, но я бы предпочел избежать этого, если бы мог).

Answer 1

Умный способ сделать это, чтобы использовать структуру данных, которая позволяет легко и эффективно, как Counter:

>>> ids = [random.randrange(100) for _ in range(200)] 
>>> from collections import Counter 
>>> counts = Counter(ids) 
>>> dupids = [id for id in ids if counts[id] > 1] 

Построение Counter принимает O (N) время, в отличие от O (N log N) времени для сортировки, или O (N^2) для подсчета каждого элемента с нуля каждый раз.

---

В качестве примечания:

But the ids list is likely to get quite long, and I realistically don't want a while loop predicated on an expensive len call if I can avoid it.

len не дорого. Это постоянное время, и (по крайней мере, в списке встроенных типов list), это примерно так же быстро, как функция может попасть на Python, не делая ничего вообще.

Часть вашего дорогого кода вызывает в цикле elem in singles, что означает, что для каждого элемента вы должны сравнивать его с потенциально любым другим элементом, что означает квадратичное время.

Answer 2

Вы могли бы сделать так,

>>> ids = [1,2,3,2,3,5] 
>>> set(i for i in ids if ids.count(i) > 1) 
{2, 3} 

Answer 3

Если вы не заботитесь о том порядке, в котором извлекаются эти идентификаторы, эффективный подход будет состоять в шаге сортировки (который является O (N журнал (N))), за которым следуют иды, за которыми следуют сами (это O (N)). Таким образом, этот подход является общим O (N log (N)).

Answer 4

Я полагаю, что это будет работать быстрее:

occasions = {} 
for id in ids: 
    try: 
     occasions[id] += 1 
    except KeyError: 
     occasions[id] = 0 
result = [id for id in ids if occasions[id] > 1]