Удалить дубликаты в списке в Python

153

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

Для этого списка: [{'a': 123}, {'b': 123}, {'a': 123}]

Я хотел бы это вернуть: [{'a': 123}, {'b': 123}]

Другой пример:

Для этого списка: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

Я хотел бы это вернуть: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Brenden
источник
Можете ли вы рассказать нам больше о проблеме, которую вы пытаетесь решить? Это кажется странной проблемой.
счастье
Я объединяю несколько списков диктов и есть дубликаты. Поэтому мне нужно удалить эти дубликаты.
Бренден
Я нашел решение в stackoverflow.com/questions/480214/… в ответе без использованияset()
Себастьян Вагнер

Ответы:

242

Попробуй это:

[dict(t) for t in {tuple(d.items()) for d in l}]

Стратегия заключается в преобразовании списка словарей в список кортежей, в которых кортежи содержат элементы словаря. Так как кортежи можно хэшировать, вы можете удалить дубликаты, используя set(используя здесь понимание набора , более старая альтернатива Python set(tuple(d.items()) for d in l)), и после этого заново создать словари из кортежей с помощью dict.

где:

  • l это оригинальный список
  • d является одним из словарей в списке
  • t является одним из кортежей, созданных из словаря

Редактировать: Если вы хотите сохранить порядок, строка выше не будет работать, так setкак не будет делать это. Однако, с помощью нескольких строк кода, вы также можете сделать это:

l = [{'a': 123, 'b': 1234},
        {'a': 3222, 'b': 1234},
        {'a': 123, 'b': 1234}]

seen = set()
new_l = []
for d in l:
    t = tuple(d.items())
    if t not in seen:
        seen.add(t)
        new_l.append(d)

print new_l

Пример вывода:

[{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Примечание: как указывает @alexis, может случиться так, что два словаря с одинаковыми ключами и значениями не приведут к одному и тому же кортежу. Это может произойти, если они пройдут через другую историю добавления / удаления ключей. Если это относится к вашей проблеме, то рассмотрите сортировку, d.items()как он предлагает.

jcollado
источник
35
Хорошее решение, но в нем есть ошибка: d.items()не гарантируется возврат элементов в определенном порядке. Вам следует tuple(sorted(d.items()))убедиться, что вы не получите разные кортежи для одних и тех же пар ключ-значение.
Alexis
@alexis Я сделал несколько тестов, и вы действительно правы. Если много ключей добавлено между ними и удалено позже, то это может иметь место. Большое спасибо за ваш комментарий.
Jcollado
Прохладно. Я добавил исправление в ваш ответ для будущих читателей, которые могут не прочитать весь разговор.
Алексис
2
Обратите внимание, что это не будет работать, если вы загрузите в этот список диктов от jsonмодуля, как я это сделал
Дхрув Гулати
2
Это правильное решение в этом случае, но не будет работать в случае вложенных словарей
Лоренцо Белли
51

Еще одна строка, основанная на списках:

>>> d = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> [i for n, i in enumerate(d) if i not in d[n + 1:]]
[{'b': 123}, {'a': 123}]

Здесь, поскольку мы можем использовать dictсравнение, мы сохраняем только те элементы, которых нет в остальной части начального списка (это понятие доступно только через индекс n, отсюда и использование enumerate).

Эммануэль
источник
2
Это также работает для списка словарей, которые состоят из списков по сравнению с первым ответом
gbozee
1
это также работает, когда в ваших словарях в качестве значения в качестве словаря может быть недоступен тип, в отличие от верхнего ответа.
Стив Росситер
1
здесь цель состоит в том, чтобы удалить дублирующиеся значения, а не ключевые, см. код этого ответа
Джамиль Нойда,
Это очень неэффективный код. if i not in d[n + 1:]перебирает весь список диктовок ( nно только вдвое сокращает общее количество операций), и вы делаете эту проверку для каждого элемента в своем словаре, так что этот код имеет O (n ^ 2) временную сложность
Борис
не работает для словарей со словарями в качестве значений
Roko Mijic
22

Другие ответы не будут работать, если вы работаете с вложенными словарями, такими как десериализованные объекты JSON. Для этого случая вы можете использовать:

import json
set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
X = [json.loads(t) for t in set_of_jsons]
stpk
источник
1
Большой! Хитрость в том, что объект dict нельзя напрямую добавить в набор, его нужно преобразовать в объект json с помощью dump ().
Reihan_amn
19

Если вы можете использовать сторонний пакет, то вы можете использовать iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> l = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> list(unique_everseen(l))
[{'a': 123}, {'b': 123}]

Он сохраняет порядок исходного списка и может также обрабатывать не подлежащие изменению элементы, такие как словари, используя более медленный алгоритм ( O(n*m)где вместо nэлементов находятся элементы в исходном списке и mуникальные элементы в исходном списке O(n)). Если ключи и значения являются хэшируемыми, вы можете использовать keyаргумент этой функции для создания хэшируемых элементов для «теста уникальности» (чтобы он работал O(n)).

В случае словаря (который сравнивается независимо от порядка) вам необходимо сопоставить его с другой структурой данных, которая сравнивается следующим образом, например frozenset:

>>> list(unique_everseen(l, key=lambda item: frozenset(item.items())))
[{'a': 123}, {'b': 123}]

Обратите внимание, что вы не должны использовать простой tupleподход (без сортировки), потому что равные словари не обязательно имеют одинаковый порядок (даже в Python 3.7, где порядок вставки - не абсолютный порядок - гарантирован):

>>> d1 = {1: 1, 9: 9}
>>> d2 = {9: 9, 1: 1}
>>> d1 == d2
True
>>> tuple(d1.items()) == tuple(d2.items())
False

И даже сортировка кортежа может не работать, если ключи не сортируются:

>>> d3 = {1: 1, 'a': 'a'}
>>> tuple(sorted(d3.items()))
TypeError: '<' not supported between instances of 'str' and 'int'

эталонный тест

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

Абсолютные времена:

введите описание изображения здесь

Сроки относительно самого быстрого подхода:

введите описание изображения здесь

Второй подход из четвертого здесь самый быстрый. unique_everseenПодход с keyфункцией находится на втором месте, однако это самый быстрый подход , который сохраняет заказ. Другие подходы от jcollado и thefourtheye почти такие же быстрые. Подход с использованием unique_everseenбез ключа и решений из Эммануэля и Scorpil очень медленно для длинных списков и ведут себя гораздо хуже , O(n*n)а O(n). Подход stpk с jsonне является, O(n*n)но он намного медленнее, чем аналогичные O(n)подходы.

Код для воспроизведения тестов:

from simple_benchmark import benchmark
import json
from collections import OrderedDict
from iteration_utilities import unique_everseen

def jcollado_1(l):
    return [dict(t) for t in {tuple(d.items()) for d in l}]

def jcollado_2(l):
    seen = set()
    new_l = []
    for d in l:
        t = tuple(d.items())
        if t not in seen:
            seen.add(t)
            new_l.append(d)
    return new_l

def Emmanuel(d):
    return [i for n, i in enumerate(d) if i not in d[n + 1:]]

def Scorpil(a):
    b = []
    for i in range(0, len(a)):
        if a[i] not in a[i+1:]:
            b.append(a[i])

def stpk(X):
    set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
    return [json.loads(t) for t in set_of_jsons]

def thefourtheye_1(data):
    return OrderedDict((frozenset(item.items()),item) for item in data).values()

def thefourtheye_2(data):
    return {frozenset(item.items()):item for item in data}.values()

def iu_1(l):
    return list(unique_everseen(l))

def iu_2(l):
    return list(unique_everseen(l, key=lambda inner_dict: frozenset(inner_dict.items())))

funcs = (jcollado_1, Emmanuel, stpk, Scorpil, thefourtheye_1, thefourtheye_2, iu_1, jcollado_2, iu_2)
arguments = {2**i: [{'a': j} for j in range(2**i)] for i in range(2, 12)}
b = benchmark(funcs, arguments, 'list size')

%matplotlib widget
import matplotlib as mpl
import matplotlib.pyplot as plt
plt.style.use('ggplot')
mpl.rcParams['figure.figsize'] = '8, 6'

b.plot(relative_to=thefourtheye_2)

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

# this is the only change for the benchmark
arguments = {2**i: [{'a': 1} for j in range(2**i)] for i in range(2, 12)}

введите описание изображения здесь

Времена не меняются значительно, за исключением unique_everseenбез keyфункции, которая в этом случае является самым быстрым решением. Тем не менее, это просто лучший случай (поэтому не репрезентативный) для этой функции с непредсказуемыми значениями, потому что время ее выполнения зависит от количества уникальных значений в списке: O(n*m)в данном случае это всего 1, и, следовательно, он выполняется O(n).


Отказ от ответственности: я автор iteration_utilities.

MSeifert
источник
15

Иногда петли старого стиля все еще полезны. Этот код немного длиннее, чем у jcollado, но очень легко читается:

a = [{'a': 123}, {'b': 123}, {'a': 123}]
b = []
for i in range(0, len(a)):
    if a[i] not in a[i+1:]:
        b.append(a[i])
Scorpil
источник
0В range(0, len(a))не нужно.
Хуан Антонио
12

Если вы хотите сохранить заказ, то вы можете сделать

from collections import OrderedDict
print OrderedDict((frozenset(item.items()),item) for item in data).values()
# [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Если порядок не имеет значения, то вы можете сделать

print {frozenset(item.items()):item for item in data}.values()
# [{'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]
thefourtheye
источник
Примечание: в python 3 ваш второй подход дает не сериализуемый dict_valuesвывод вместо списка. Вы должны снова разыграть все это в списке. list(frozen.....)
saran3h
12

Если вы используете Pandas в своем рабочем процессе, одним из вариантов является передача списка словарей непосредственно в pd.DataFrameконструктор. Затем используйте drop_duplicatesи to_dictметоды для получения требуемого результата.

import pandas as pd

d = [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

d_unique = pd.DataFrame(d).drop_duplicates().to_dict('records')

print(d_unique)

[{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]
JPP
источник
3

Не универсальный ответ , но если ваш список отсортирован по некоторому ключу, например так:

l=[{'a': {'b': 31}, 't': 1},
   {'a': {'b': 31}, 't': 1},
 {'a': {'b': 145}, 't': 2},
 {'a': {'b': 25231}, 't': 2},
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 112}, 't': 3}]

тогда решение так же просто, как:

import itertools
result = [a[0] for a in itertools.groupby(l)]

Результат:

[{'a': {'b': 31}, 't': 1},
{'a': {'b': 145}, 't': 2},
{'a': {'b': 25231}, 't': 2},
{'a': {'b': 112}, 't': 3}]

Работает с вложенными словарями и (очевидно) сохраняет порядок.

Highstaker
источник
1

Вы можете использовать набор, но вам нужно превратить дикты в тип hashable.

seq = [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]
unique = set()
for d in seq:
    t = tuple(d.iteritems())
    unique.add(t)

Уникальный сейчас равен

set([(('a', 3222), ('b', 1234)), (('a', 123), ('b', 1234))])

Чтобы вернуть слова:

[dict(x) for x in unique]
Matimus
источник
Порядок d.iteritems()не гарантируется - поэтому вы можете получить «дубликаты» в unique.
Данодонован
-1

Вот быстрое однострочное решение с вдвойне понятным списком (основанное на решении @Emmanuel).

При этом используется один ключ (например, a) в каждом диктовке в качестве первичного ключа, а не проверка соответствия всего диктовки.

[i for n, i in enumerate(list_of_dicts) if i.get(primary_key) not in [y.get(primary_key) for y in list_of_dicts[n + 1:]]]

Это не то, о чем просил OP, но это то, что привело меня в эту ветку, поэтому я решил опубликовать решение, с которым у меня получилось

сельдь
источник
-1

Не такой короткий, но легко читаемый:

list_of_data = [{'a': 123}, {'b': 123}, {'a': 123}]

list_of_data_uniq = []
for data in list_of_data:
    if data not in list_of_data_uniq:
        list_of_data_uniq.append(data)

Теперь список list_of_data_uniqбудет иметь уникальные диктанты.

user1723157
источник