DjangoBB LoFi version

Полная версия: Удаление одинаковых элементов в списке.

Начало » Python для новичков » Удаление одинаковых элементов в списке.

1 2 3 4 5

py.user.next

Май 20, 2010 09:18:27

для pasaranax

>>> super(list, {}.keys())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: super(type, obj): obj must be an instance or subtype of type
>>>

и в то же время

>>> class A(list):
...     i = 1
...
>>> al = A([1, 2])
>>> al
[1, 2]
>>> al.i
1
>>> super(list, al)
<super: <class 'list'>, <A object>>
>>>

anshik

Янв. 26, 2011 13:18:40

Есть исходный список списков, как удалить одинаковые списки в списке ( :) простите)
out = [,,,, ]

Вот так сейчас

    x4_x5 = []
    for i in out:
        if i not in x4_x5:
            x4_x5.append(i)

Проблема, что исходндный список out из более 30к элементов, так что нужно как можно быстрее сделать, сейчас это 12.0940001011 секунд.

С наборами и зип-упаковкой не получается, т.к. элементы являются списками.

    for e in out:
        if out.count(e) > 1:
            out.remove(e)

57.9070000648 секунд

Ещё хуже

Борисенков Сергей

Янв. 26, 2011 13:45:14

Уточняющий вопрос: вложенные списки всегда из двух элементов?
И какова глубина вложенности?

anshik

Янв. 26, 2011 14:11:52

Борисенков Сергей
Уточняющий вопрос: вложенные списки всегда из двух элементов?
И какова глубина вложенности?

Да, всегда из двух элементов, это цепи соединений [,,…]

Борисенков Сергей

Янв. 26, 2011 14:14:02

Тогда может так:

При тесте из 30000 элементов 0.141 сек.

anshik

Янв. 26, 2011 15:05:13

В этой реализации есть косяк
x4_x5_b =

Оно разбивает на (ключ, значение), и получается, что цепь такого вида:

Остаётся одна, а мне нужно чтобы остались обе, но работает быстро :)

Борисенков Сергей

Янв. 26, 2011 15:18:21

Прошу прощения - не досмотрел!
А так:

s={}
for i in out:
    s[i[0]+'#'+i[1]]=0
t=[i.split('#') for i in s.keys()    ]

pyuser

Янв. 27, 2011 01:54:52

anshik Вам бы первую страницу этого топика почитать, если, по каким-либо причинам Вас не устраивает set, то воспользуйтесь советом из седьмого поста.

Борисенков Сергей

Янв. 27, 2011 07:57:02

pyuser вы немного не досмотрели условия задачи у anshik`а (на Python 2.6):
>>> out=[,]
>>> t=dict(zip(out, out)).keys()
Traceback (most recent call last):
File “<stdin>”, line 1, in <module>
TypeError: unhashable type: ‘list’
>>>

Возможен вариант:

s=dict(map(lambda i:[i[0]+'#'+i[1],0],out))
t=[i.split('#') for i in s.keys()    ]

но у меня он получился медленне первого в два с половиной раза :)

pyuser

Янв. 27, 2011 09:06:48

Борисенков Сергей
вы немного не досмотрели условия задачи

условие - получить список уникальных значений, что я не досмотрел?

Борисенков Сергей
Traceback (most recent call last):
File “<stdin>”, line 1, in <module>
TypeError: unhashable type: ‘list’

Ну это же не повод опускать руки ;)

import timeit

from itertools import imap, izip, izip_longest
###################################################################################

def test1(lst):
    s = dict(map(lambda i: [i[0] + '#' + i[1], 0], lst))
    return [i.split('#') for i in s.keys()]

def test2(lst):
    s={}
    for i in lst:
        s[i[0] + '#' + i[1]] = 0
    return [i.split('#') for i in s.keys()]

def test3(lst):
    return reduce(lambda y,z: not (z in y) and y.append(z) or y, lst, [])

def test4(lst):
    return list(set(map(tuple, lst)))

def test5(lst):
    x = [tuple(x) for x in lst]
    return list(dict(izip(x, x)).iterkeys())

def test6(lst):
    return list(dict(izip_longest((tuple(x) for x in lst), [])).iterkeys())
###################################################################################

if "__main__" == __name__:
    data = [['XP11:25C', 'X3:89'],['XP12:5B', 'X3:89'],['XP12:15B', 'X3:89'],
            ['XP12:25B', 'X3:89'], ['XP12:25B', 'X3:89']]
    print("test1", timeit.timeit("test1(data)",
        "from __main__ import test1, data", number=1000000))
    print("test2", timeit.timeit("test2(data)",
        "from __main__ import test2, data", number=1000000))
    print("test3", timeit.timeit("test3(data)",
        "from __main__ import test3, data", number=1000000))
    print("test4", timeit.timeit("test4(data)",
        "from __main__ import test4, data", number=1000000))
    print("test5", timeit.timeit("test5(data)",
        "from __main__ import test5, data", number=1000000))
    print("test6", timeit.timeit("test6(data)",
        "from __main__ import test6, data", number=1000000))

результат:

test1 7.75889498911
test2 4.86464391964
test3 2.71476288664
test4 2.61486176313
test5 4.69240897403
test6 4.87071962446

set, как и ожидалось, самый быстрый вариант.

anshik, если список out, генерируете Вы сами, рассмотрите возможность получения списка кортежей вместо списка списков, тогда удаление повторяющихся элементов будет еще быстрее.
при прочих равных условиях:

test4 1.20101419959
test5 2.98147578504