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

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

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

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

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)

Answer 3

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

Кроме того, поскольку он сказал: «Вероятно, есть более оптимальный способ проверить это, чем len (list (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 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 (list (a [1])).

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

Answer 5

Другим способом является создание счетчика для каждого из данных dict, основанного на заморозке предметов:

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 6

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

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

Answer 7

Другой вариант - создать собственную структуру данных вместо использования 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