Как удалить уникальные, а затем дублирующие словари в списке?

Question

Учитывая следующий список, содержащий несколько дубликатов и некоторые уникальные словари, каков наилучший метод для удаления уникальных словарей, а затем уменьшить дубликаты словарей до отдельных экземпляров? Должен сказать, что я только недавно начал заниматься Python, но это сделало этот проект , так что намного проще. Я просто немного озадачен этой проблемой.

Так что мой список выглядит следующим образом:

[{ 'file': u'/file.txt', 
    'line': u'line 666', 
    'rule': u'A DUPLICATE RULE'} 

{ 'file': u'/file.txt', 
    'line': u'line 666', 
    'rule': u'A DUPLICATE RULE'} 

{ 'file': u'/uniquefile.txt', 
    'line': u'line 999', 
    'rule': u'A UNIQUE RULE'}] 

Что я буду за это в конце концов, список должен выглядеть следующим образом:

[{ 'file': u'/file.txt', 
    'line': u'line 666', 
    'rule': u'A DUPLICATE RULE'}] 

Answer 1

Одна из идей заключается в сортировке данных. Предположим inputdata ваш список сверху:

from itertools import groupby 
from operator import itemgetter 

inputdata.sort(key=itemgetter(*inputdata[0])) # ensures order 
print [k for k, g in groupby(inputdata) if len(list(g)) > 1] 

принтами:

[{'line': u'line 666', 'file': u'/file.txt', 'rule': u'A DUPLICATE RULE'}] 

Answer 2

я хотел бы сделать еще один словарь, используя существующие словари в качестве ключей и количество вхождений в качестве значений. (Python не позволяет использовать словари в качестве клавиш для словаря, но есть несколько способов сделать это, упомянутое в this answer.) Тогда это просто вопрос итерации по нему и выбор ключей, в которых значение больше 1.

Конечно, использование словарей в качестве ключей зависит от их содержимого, которое не меняется со временем - по крайней мере, в течение того времени, когда вам нужно использовать результирующий словарь. (Вот почему Python не поддерживает его изначально.)

Answer 3

Другой способ это сделать счетчик для каждого типа данных Dict, на основе frozenset пунктов:

from operator import itemgetter 
from collections import defaultdict 

counter = defaultdict(int) 
for d in inputdata: 
    counter[frozenset(d.iteritems())] += 1 

result = [dict(item) for item, count in counter.iteritems() if count > 1] 
print result 

Я думаю, что это лучший ответ, потому что он очень прост для понимания и будет работать линейно.

Answer 4

>>> import itertools 
>>> list(a[0] for a in itertools.groupby(sorted(data)) if len(list(a[1])) > 1) 
[{'file': u'/file.txt', 'line': u'line 666', 'rule': u'A DUPLICATE RULE'}] 

Возможно, существует более оптимальный способ проверить это, чем len (список (a [1])).

Редактировать: Я добавил звонок для сортировки.

Answer 5

Другой вариант - создать свою собственную структуру данных вместо использования dict. Если вы это сделаете, вы можете переопределить __cmp__, __eq__ и __hash__. Это даст вам возможность использовать тип данных «set» во всей красе.

Вот одна из возможных реализаций, хотя я не делаю никаких обещаний о качестве хэш-рутину Я при условии:

class Thing(object): 
    def __init__(self, file, line, rule): 
     self.file = file 
     self.line = line 
     self.rule = rule 

    def __cmp__(self, other): 
     result = cmp(self.file, other.file) 
     if result == 0: 
      result = cmp(self.line, other.line) 
     if result == 0: 
      result = cmp(self.rule, other.rule) 
     return result 

    def __eq__(self, other): 
     return cmp(self, other) == 0 

    def __hash__(self): 
     return hash(self.file) * hash(self.line) * hash(self.rule) 

    def __str__(self): 
     return ', '.join([self.file, self.line, self.rule]) 

things = [ Thing(u'/file.txt', u'line 666', u'A DUPLICATE RULE'), 
    Thing(u'/file.txt', u'line 666', u'A DUPLICATE RULE'), 
    Thing(u'/uniquefile.txt', u'line 999', u'A UNIQUE RULE')] 

duplicate_things = set() 
unique_things = set() 
for t in things: 
    if t in unique_things: 
     duplicate_things.add(t) 
    else: 
     unique_things.add(t) 

Если вам нужно, чтобы вернуться к списку, просто построить один из результирующего набора :

unique_things = list(unique_things) 
duplicate_things = list(duplicate_things) 

это немного больше кода, чтобы создать свой собственный класс, как это, но может дать вам другие варианты вниз по дороге, если ваша программа растет по сложности.

Редактировать

ОК, мои руки быстрее, чем мои глаза сегодня, но я думаю, что это исправить решает проблему указал @nosklo

Answer 6

Этот ответ основан на ответ Стивена Huwig в. Он похож на его, но я использую sorted() в списке, так что groupby() работает правильно.

Кроме того, поскольку он сказал: «Вероятно, существует более оптимальный способ проверить это, чем len (список (a [1]).», Я решил использовать другой способ проверить не уникальные элементы. Вместо того, чтобы форсировать весь список, я пытаюсь дважды вызвать метод .next() на итераторе. Если он работает дважды, в итераторе есть по крайней мере два элемента, и мы закончили с ним; если мы получим исключение StopIteration при первом или втором вызове .next(), в итераторе было ноль или один элемент. (На самом деле, так как мы получили этот итератор из itertools.groupby мы знаем, что это будет иметь по крайней мере один пункт в нем.)

Кроме того, вместо того, чтобы использовать явное индексирование кортежа как a[0] и a[1], я использовал кортеж распаковку, так это то, что круто дети, кажется, делают эти дни.

Наконец, вместо выражения генератора для вычисления списка и использования list(), чтобы заставить его развернуть его в список, я просто использовал понимание списка.

data = [ 
    { 
     'file': u'/file.txt', 
     'line': u'line 666', 
     'rule': u'A DUPLICATE RULE' 
    }, 

    { 'file': u'/uniquefile.txt', 
     'line': u'line 999', 
     'rule': u'A UNIQUE RULE' 
    }, 

    { 'file': u'/file.txt', 
     'line': u'line 666', 
     'rule': u'A DUPLICATE RULE' 
    }, 

] 

from itertools import groupby 

def notunique(itr): 
    try: 
     itr.next() 
     itr.next() 
     return True 
    except StopIteration: 
     return False 

def unique_list(lst): 
    return [key for key, itr in groupby(sorted(lst)) if notunique(itr)] 

print(unique_list(data)) 

Answer 7

Я всегда предпочитаю работать с объектами вместо dicts, если поля одинаковы для каждого элемента.

Итак, я определяю класс:

class rule(object): 
    def __init__(self, file, line, rule): 
     self.file = file 
     self.line = line 
     self.rule = rule 

    #Not a "magic" method, just a helper for all the methods below :) 
    def _tuple_(self): 
     return (self.file, self.line, self.rule) 

    def __eq__(self, other): 
     return cmp(self, other) == 0 

    def __cmp__(self, other): 
     return cmp(self._tuple_(), rule._tuple_(other)) 

    def __hash__(self): 
     return hash(self._tuple_()) 

    def __repr__(self): 
     return repr(self._tuple_()) 

Теперь создать список этих объектов, и сортировать его. ruledict_list может быть примером данных в вашем вопросе.

rules = [rule(**r) for r in ruledict_list] 
rules.sort() 

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

pos = 0 
while(pos < len(rules)): 
    while pos < len(rules)-1 and rules[pos] == rules[pos+1]: 
     print "Skipping rule %s" % rules[pos] 
     pos+=1 
    rules.pop(pos) 
rule_set = set(rules)