Найти - Пользователи
Полная версия: Удалить дубликаты в списке не нарушив их порядок
Начало » Python для новичков » Удалить дубликаты в списке не нарушив их порядок
1 2 3
fata1ex
Медленно и неправильно, зато воднустрочку:
>>> mylist = [1,1,2,1,4,5,6,6,8]
>>> [elem for idx, elem in enumerate(mylist) if elem not in mylist[:idx]]
[1, 2, 4, 5, 6, 8]
>>> zip(*filter(lambda (idx, elem): elem not in mylist[:idx], enumerate(mylist)))[1]
(1, 2, 4, 5, 6, 8)

Кстати, конструкция
seen = set()
filter(lambda x: x not in seen and not seen.add(x), mylist)
Заметно уступает set_compr.
odnochlen
fata1ex
зато воднустрочку:
Перлотрах?
EBFE
tfox
Здесь черт ногу поломает
Ну можно и так:
def unique(_):
    __ = set()
    ___ = __.add
    return [_ for _ in _ if _ not in __ and not ___ (_)]

def unique2(_, __ = type({( )})):
    __ = type("(_._)", (__,),{'_':__.add}) ()
    return [_ for _ in _ if _ not in __ and not __._(_)]

def unique3(_, __ = type({( )})):
    __ = type("""
                      .-=-.          .--.
          __        .'     '.       /  " )
  _     .'  '.     /   .-.   \     /  .-'\
 ( \   / .-.  \   /   /   \   \   /  /    ^
  \ `-` /   \  `-'   /     \   `-`  /
jgs`-.-`     '.____.'       `.____.'""", (__,),
 {'_' : __.__dict__[filter(lambda _: '_' not in _,
                    sorted(__.__dict__))[::-1].pop()]})( {( )} )
    return [_ for _ in _ if _ not in __ and not __._(_)]


odnochlen
А не нарушает ли это концепцию ФП (функция получается грязной, результат для одного элемента зависит от другого)?.
Конечно нарушает
Но грязно в этом случае имхо скорее зависимость от logical expression evaluation order / ассоциативности. Обычно ожидается что “expr1 or/and/… expr2” <=> “expr2 or/and/… expr1” .
A тут “подлянка”:
if not collect.add(e) and e not in collect" 
будет выдавать совершенно другой результат.
tfox
def unique(lst):
    [b]seen = set()[/b]
    result = []
    for x in lst:
        if x in seen:
            continue
        seen.add(x)
        result.append(x)
    return result

А зачем здесь использовать множество?
Все прекрасно работает и без множества.

def unique(lst):
    result = []
    for x in lst:
        if x in result:
            continue
        result.append(x)
    return result
fata1ex
Программисту хорошо бы знать базовые структуры данных и понимать, как они работают. Поговаривают, что с этого надо начинать изучать программирование.
tfox
Вы правы.
reclosedev, использовал множество так там элементы уникальны. В множестве дубликатов не будет. Хотя оператор in прекрасно работает и со списками. Думаю, что потребность использовать множество здесь отпадает.
fata1ex
1000 21
bench_set_loop 0.618780851364
bench_list_loop 1.7107770443
10000 21
bench_set_loop 5.74140501022
bench_list_loop 17.0790119171

Вы неправильно думаете. Вместо: “О, кажется, и так работает, значит они ошиблись, а я и так всё знаю”, надо было подумать: “Зачем-то же он написал именно множество, наверно, неспроста. Зачем-то же мне сказали о структурах данных, наверно, не просто так. А что я изменил в своём коде, а как это могло повлиять на работу программы, а чем отличается список от множества?”.
EBFE
tfox
А зачем здесь использовать множество?
Все прекрасно работает и без множества.
Множества в Pythone реализованы через Хеш-таблицу.
Т.е поиск, вставка элементов в среднем выполняются за время O(1).
Поиск в списке выполняется за время O(n) n = количество элементов в списке.
Получается, вариант с множеством выполняется за ~ O(n), со списком за O(n^2).
def bench_unique_set(lst):
    seen = set()
    result = []
    for x in lst:
        if x in seen:
            continue
        seen.add(x)
        result.append(x)
    return result
def bench_unique_list(lst):
    result = []
    for x in lst:
        if x in result:
            continue
        result.append(x)
    return result
import timeit
import random
for elem in (10000, 30000, 50000, 100000):
    mylist = [random.randint(0, elem) for i in range(elem)]
    print elem, len(set(mylist))
    for name, func in [(k,v) for k,v in globals().items()
                       if k.startswith('bench')]:
        print " %-20s %s" % (name, timeit.timeit(
              lambda: func(mylist),number = 1))
10000 6328
 bench_unique_set     0.00341678590387
 bench_unique_list    0.853494333394
30000 19064
 bench_unique_set     0.00928298693915
 bench_unique_list    7.69523085824
50000 31700
 bench_unique_set     0.0212902408726
 bench_unique_list    21.3993917074
100000 63186
 bench_unique_set     0.047203690252
 bench_unique_list    87.1938787334
tfox
А, понятно. Поскольку массивы данных у меня маленькие то разницы никакой не почувствовал.
odnochlen
Зато вот тут человек прочувствовал ее в полной мере.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB