Фильтрация списка словарей для удаления дубликатов в ключе на основе другого ключа.

Question

У меня есть список словарей в Python 3.5.2, которые я пытаюсь «дедуплицировать».Все словари уникальны, но есть определенный ключ, на который я хотел бы дедуплицировать, сохраняя словарь с большинством ненулевых значений.

Например, у меня есть следующий список словарей:

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]

Я бы хотел отфильтровать l только по словарям с уникальными ключами id, сохранив в словаре наименьшее количество нулей.В этом случае функция должна сохранять значения d1 и d4.

. Я попытался создать новый ключ, пару val для «счетчика значений», например:

for d in l:
    d['val_count'] = len(set([v for v in d.values() if v]))

Теперь я застрял в том, как отфильтровать мой список диктов для уникального ids, где ключ val_count - это большее значение.

Я открыт для других подходов, но не могуиспользуйте pandas для этого проекта из-за нехватки ресурсов.

Ожидаемый результат:

l = [{"id":"a", "foo":"bar", "baz":"bat"},
 {"id":"b", "foo":"bar", "baz":"bat"}]

Answer 1

@ cdc200 , вы можете попробовать приведенный ниже код.Здесь я использовал понятие словаря.

Примечание »Словарь определяется как неупорядоченный набор элементов данных с уникальными ключами.

Я использовал OrderedDict () вместо dict () для сохранения порядка ключей.Посмотрите эту симпатичную небольшую статью OrderedDict на Python - GeeksforGeeks .

import json
from collections import OrderedDict

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]

d = OrderedDict ();

for index, item in enumerate(l):
    if item["id"] not in d:
        d[item["id"]] =item
    else:
        nones1, nones2 = 0, 0
        for k in item:
            if item[k] is None:
                 nones1 = nones1 + 1
            if d[item["id"]][k] is None:
                 nones2 = nones2 + 1

        if nones2 > nones1:
            d[item["id"]] = item

l = [dict_item for dict_item in d.values()]

print (l)

"""
{'foo': 'bar', 'id': 'a', 'baz': 'bat'}, {'foo': 'bar', 'id': 'b', 'baz': 'bat'}]
"""

# Pretty printing the above dictionary
print(json.dumps(l, indent=4))

"""
[
    {
        "foo": "bar",
        "id": "a",
        "baz": "bat"
    },
    {
        "foo": "bar",
        "id": "b",
        "baz": "bat"
    }
]
"""

Спасибо.

Answer 2

Я бы использовал groupby и просто выбрал первое из каждой группы:

1) Сначала отсортируйте ваш список по ключу (для создания групп) и по убыванию количества нулей (вашзаданная цель):

>>> l2=sorted(l, key=lambda d: (d['id'], -sum(1 for v in d.values() if v))) 

2) Затем сгруппируйте по id и возьмите первый элемент каждого итератора, представленный как d в групповом порядке в отсортированном списке:

>>> from itertools import groupby
>>> [next(d) for _,d in groupby(l2, key=lambda _d: _d['id'])]
[{'id': 'a', 'foo': 'bar', 'baz': 'bat'}, {'id': 'b', 'foo': 'bar', 'baz': 'bat'}]

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

>>> l2=sorted(enumerate(l), key=lambda t: (t[1]['id'], t[0], -sum(1 for v in t[1].values() if v)))
>>> [next(d)[1] for _,d in groupby(l2, key=lambda t: t[1]['id'])]

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

Answer 3

Если вы открыты для использования сторонней библиотеки, вы можете отсортировать по количеству None значений и затем подать в toolz.unique:

from toolz import unique
from operator import itemgetter

l_sorted = sorted(l, key=lambda x: sum(v is None for v in x.values()))
res = list(unique(l_sorted, key=itemgetter('id')))

[{'baz': 'bat', 'foo': 'bar', 'id': 'a'},
 {'baz': 'bat', 'foo': 'bar', 'id': 'b'}]

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

---

Тест производительности

Я включил только решения, которыедать ровно один результат для каждого идентификатора.Многие решения не обслуживают дублирующий словарь.

l = [d1, d2, d3, d4]*1000

%timeit dawg(l)  # 11.4 ms
%timeit jpp(l)   # 7.91 ms
%timeit tsw(l)   # 4.23 s

from operator import itemgetter
from itertools import groupby
from toolz import unique

def dawg(l):
    l2=sorted(enumerate(l), key=lambda t: (t[1]['id'], -sum(1 for v in t[1].values() if v), t[0]))
    return [next(d)[1] for _,d in groupby(l2, key=lambda t: t[1]['id'])]

def jpp(l):
    l_sorted = sorted(l, key=lambda x: sum(v is None for v in x.values()))
    return list(unique(l_sorted, key=itemgetter('id')))

def tsw(l):
    for d in l:
        d['val_count'] = len(set([v for v in d.values() if v]))
    new = [d for d in l if d['val_count'] == max([d_other['val_count'] for d_other in l if d_other['id'] == d['id']])]
    return [x for i, x in enumerate(new) if x['id'] not in {y['id'] for y in new[:i]}]

Answer 4

Я бы сделал так:

num = [list(x.values()).count(None) for x in l]
ls = [x for _,x in sorted(zip(num, l), key=lambda z: z[0])]

Затем сохраните столько значений, сколько хотите из отсортированного списка (ls).

Например, чтобы сохранить толькоте словари с наибольшим числом не- None значений (все словари с тем же числом не- None с), вы можете сделать это:

num = [list(x.values()).count(None) for x in l]
ls, ns = zip(*[(x, d) for d, x in sorted(zip(num, l), key=lambda z: z[0])])
top_l = ls[:list(reversed(ns)).index(ns[0])]

---

РЕДАКТИРОВАТЬ: На основе комментария @ jpp я обновил свой код, чтобы позаботиться о дубликатах id ключей.Вот обновленный код:

def agn(l):
    num = [list(x.values()).count(None) for x in l]
    ls, ns = zip(*[(x, d) for d, x in sorted(zip(num, l), key=lambda z: z[0])])
    top_l = ls[:list(reversed(ns)).index(ns[0])]
    return list(dict((d['id'], d) for d in top_l).values())

Давайте также добавим сравнение времени, используя те же определения и настройки, что и в @ jpp's answer :

In [113]: %timeit tsw(l)
3.9 s ± 60.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [114]: %timeit dawg(l)
7.48 ms ± 191 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [115]: %timeit jpp(l)
5.83 ms ± 104 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [116]: %timeit agn(l)
4.58 ms ± 86.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 5

Вот один из способов использования списка, который использует 'val_count' значения, которые вы уже рассчитали:

new = [d for d in l if d['val_count'] == max([d_other['val_count'] for d_other in l if d_other['id'] == d['id']])]

Дача:

[{'baz': 'bat', 'foo': 'bar', 'id': 'a', 'val_count': 3},
 {'baz': 'bat', 'foo': 'bar', 'id': 'b', 'val_count': 3}]

Это работает путем сравнения текущего'val_count' для словаря val_count' из всех словарей с одинаковым 'id'.Обратите внимание, что в случае связей все словари с максимальным значением 'val_count' сохраняются.

Следующая строка должна обрабатывать связи, сохраняя первый экземпляр только определенного 'id':

final = [x for i, x in enumerate(new) if x['id'] not in {y['id'] for y in new[:i]}]

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

Answer 6

Вы можете использовать max:

d1 = {"id":"a", "foo":"bar", "baz":"bat"}
d2 = {"id":"b", "foo":"bar", "baz":None}
d3 = {"id":"a", "foo":"bar", "baz":None}
d4 = {"id":"b", "foo":"bar", "baz":"bat"}
l = [d1, d2, d3, d4]
max_none = max(sum(c is None for c in i.values()) for i in l)
new_l = [i for i in l if sum(c is None for c in i.values()) < max_none]

Выход:

[{'foo': 'bar', 'baz': 'bat', 'id': 'a'}, {'foo': 'bar', 'baz': 'bat', 'id': 'b'}]