Python-сообщество

Ferroman · Март 2, 2010 19:12:41

Ищется наиболее красивый метод фильтрования списка с удалением дубликатов по свойству элемента. Например есть вот такой список словарей:

надо убрать все записи с именем, которое уже есть. Типа такого:
или

Понятно, что есть способ “в лоб” с флажком и перебором, но хотелось бы что-то более красивое (ленивое).
Вот так:

sml2 =filter(lambda x:x['name'] not in (y['name'] for y in sml[sml.index(x)+1:]), sml)

или

sml2 =filter(lambda x:[y['name'] for y in sml[sml.index(x):]].count(x['name']) <= 1, sml)

работает медленно, из-за постоянного формирования дополнительного списка.
Может можно что-то придумать с превращением списка в множество и убрать дубли таким образом…
Какие есть соображения?

bazooka · Март 2, 2010 19:49:03

>>> a = [{'name': 'a', 'value': 3}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}]
>>> b = dict((d['name'], d['value']) for d in a)
>>> b
{'a': 4, 'b': 3}
>>> a = [{'name': n, 'value': v} for n, v in b.items()]
>>> a
[{'name': 'a', 'value': 4}, {'name': 'b', 'value': 3}]

Отредактировано (Март 2, 2010 19:51:51)

pasaranax · Март 2, 2010 19:59:49

bazooka
тогда уж вот так

sml2 = dict((i['value'], i) for i in sml).values()

Отредактировано (Март 2, 2010 20:01:44)

Ferroman · Март 2, 2010 20:01:06

О, замечательный вариант, быстрый и понятный, спасибо.

Evg · Март 3, 2010 02:23:09

есть еще вариант с groupby

from itertools import groupby
l = [{'name': 'a', 'value': 3}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}]
l.sort(lambda a,b: cmp(a['name'], b['name']))
print list(v.next() for i,v in (groupby(l,lambda x:x['name'])))

но поди тож медленный

Отредактировано (Март 3, 2010 02:40:58)

pyuser · Март 3, 2010 03:57:28

Evg

import timeit
from operator import itemgetter
from itertools import groupby
#####################################################################################

setup = """from operator import itemgetter
from itertools import groupby
from __main__ import lst
"""

lst = [{'name': 'a', 'value': 3}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}]

def main():
    t1 = timeit.Timer("dict((i['name'], i) for i in lst).values()", setup=setup)
    t2 = timeit.Timer('list(v.next() for i,v in (groupby(sorted(lst,'\
            'key=itemgetter("name")), key=itemgetter("name"))))', setup=setup)
    t3 = timeit.Timer('list(v.next() for i,v in (groupby(sorted(lst,'\
            'key=lambda x: x["name"]), key=lambda x: x["name"])))', setup=setup)
    print(t1.timeit(100000))
    print(t2.timeit(100000))
    print(t3.timeit(100000))

if "__main__" == __name__:
    main()

0.569244694507
1.78762719843
2.08700323644

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

ЗЫ. тоже самое, но без list()

def main():
    t1 = timeit.Timer("dict((i['name'], i) for i in lst).values()", setup=setup)
    t2 = timeit.Timer('[v.next() for i,v in (groupby(sorted(lst,'\
            'key=itemgetter("name")), key=itemgetter("name")))]', setup=setup)
    t3 = timeit.Timer('[v.next() for i,v in (groupby(sorted(lst,'\
            'key=lambda x: x["name"]), key=lambda x: x["name"]))]', setup=setup)
    print(t1.timeit(100000))
    print(t2.timeit(100000))
    print(t3.timeit(100000))

0.58534422671
1.07169710117
1.28886408747

чуть быстрее, но общей картины не меняет

Отредактировано (Март 3, 2010 04:05:48)

Evg · Март 3, 2010 14:11:18

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

Evg · Март 3, 2010 14:35:17

Хотя картина таже и со списком на 1000

CNT = 1000
lst = [{'name':string.lowercase[random.randint(0,len(string.lowercase)-1)], 'value': 3} for i in xrange(0,CNT)]
print lst

50.6772648479
152.433669363
207.289446005

Dimka665 · Март 4, 2010 09:57:25

import timeit
from operator import itemgetter
from itertools import groupby
import string
import random
############################################

setup = """from operator import itemgetter
from itertools import groupby
from __main__ import lst

set2 = set()
set3 = set()
set4 = set()
"""

CNT = 1000
lst = [{'name':string.lowercase[random.randint(0,len(string.lowercase)-1)], 'value': 3} for i in xrange(0,CNT)]

def main():
    t1 = timeit.Timer("dict((i['name'], i) for i in lst).values()", setup=setup)
    t2 = timeit.Timer('list(v.next() for i,v in (groupby(sorted(lst,'\
            'key=itemgetter("name")), key=itemgetter("name"))))', setup=setup)
    t3 = timeit.Timer('list(v.next() for i,v in (groupby(sorted(lst,'\
            'key=lambda x: x["name"]), key=lambda x: x["name"])))', setup=setup)
    t5 = timeit.Timer("[(i, set2.add(i['name']))[0] for i in lst if i['name'] not in set2]", setup=setup)
    t6 = timeit.Timer("[i for i in lst if i['name'] not in set3 and not set3.add(i['name'])]", setup=setup)
    t7 = timeit.Timer("[i for i in lst if not(i['name'] in set4 or set4.add(i['name']))]", setup=setup)

    print(t1.timeit(10000))
    print(t2.timeit(10000))
    print(t3.timeit(10000))
    print(t5.timeit(10000))
    print(t6.timeit(10000))
    print(t7.timeit(10000))
    
if "__main__" == __name__:
    main()

2.29998445831
6.493301213
8.91664987092
1.04960292376
1.05072852553
1.09166592181

t5 и t6 примерно равны. а вот t7 стабильно медленнее t6. загадка.

Python-сообщество

Уведомления

#1 Март 2, 2010 19:12:41

Отфильтровать дубликаты по свойству.

#2 Март 2, 2010 19:49:03

Отфильтровать дубликаты по свойству.

#3 Март 2, 2010 19:59:49

Отфильтровать дубликаты по свойству.

#4 Март 2, 2010 20:01:06

Отфильтровать дубликаты по свойству.

#5 Март 3, 2010 02:23:09

Отфильтровать дубликаты по свойству.

#6 Март 3, 2010 03:57:28

Отфильтровать дубликаты по свойству.

#7 Март 3, 2010 14:11:18

Отфильтровать дубликаты по свойству.

#8 Март 3, 2010 14:35:17

Отфильтровать дубликаты по свойству.

#9 Март 4, 2010 09:57:25

Отфильтровать дубликаты по свойству.

Board footer