Как удалить идентичные элементы из списка и отсортировать его в Python?

Как я могу оптимально удалить одинаковые элементы из списка и отсортировать его в Python?

Скажем, у меня есть список:

my_list = ['a', 'a', 'b', 'c', 'd', 'a', 'e', 'd', 'f', 'e'] 

Я мог бы перебирать копию списка (так как вы не должны мутировать список во время итерации по нему), элемент для элемента и удалять весь элемент, кроме одного:

 for item in my_list[:]: # must iterate over a copy because mutating it count = my_list.count(item) # see how many are in the list if count > 1: for _ in range(count-1): # remove all but one of the element my_list.remove(item) 

Который удаляет избыточные элементы:

 ['b', 'c', 'a', 'd', 'f', 'e'] 

а затем отсортировать список:

 my_list.sort() 

поэтому my_list теперь:

 ['a', 'b', 'c', 'd', 'e', 'f'] 

Но какой самый эффективный и прямой (то есть перформативный) способ удалить идентичные элементы и отсортировать этот список?

* Этот вопрос возник на работе (я так жалел на это ответить, но один из наших старших разработчиков Python дошел до него), и я также рассказал об этом в своей местной группе Python Meetup, и у немногих людей было Хороший ответ для этого, поэтому я отвечаю на него в стиле Q & A, как это предлагает Stackoverflow .

    Лучший способ удалить избыточные элементы из списка – это сделать его как набор, и поскольку отсортированный принимает любой итеративный и возвращает список, это намного эффективнее, чем делать это кусочно.

     my_list = ['a', 'a', 'b', 'c', 'd', 'a', 'e', 'd', 'f', 'e'] def sorted_set(a_list): return sorted(set(a_list)) new_list = sorted_set(my_list) 

    и new_list:

     ['a', 'b', 'c', 'd', 'e', 'f'] 

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

     >>> my_list = [['a'], ['a'], ['b'], ['c']] >>> sorted(set(my_list)) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unhashable type: 'list' 

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

     >>> my_list = [tuple(i) for i in my_list] >>> sorted(set(my_list)) [('a',), ('b',), ('c',)] 

    Но в других случаях потребуется найти различные способы обхода. Это не было бы необходимо с другим решением (но, опять же, может быть намного дороже вычислить):

     def remove_extras_and_sort(my_list): for item in my_list[:]: count = my_list.count(item) if count > 1: for _ in range(count-1): my_list.remove(item) my_list.sort() return my_list 

    Что работает для подсписок:

     >>> my_list = [['a'], ['a'], ['b'], ['c']] >>> remove_extras_and_sort(my_list) [['a'], ['b'], ['c']] 

    Чтобы сравнить производительность:

     import timeit setup = ''' my_list = ['a', 'a', 'b', 'c', 'd', 'a', 'e', 'd', 'f', 'e'] def remove_extras_and_sort(my_list): for item in my_list[:]: count = my_list.count(item) if count > 1: for _ in range(count-1): my_list.remove(item) my_list.sort() return my_list def sorted_set(a_list): return sorted(set(a_list)) ''' timeit.timeit('sorted_set(my_list[:])', setup=setup) timeit.timeit('remove_extras_and_sort(my_list[:])', setup=setup) 

    Который возвращает время, когда я измеряю их в своей системе, соответственно:

     1.5562372207641602 4.558010101318359 

    Это означает, что метод, заданный в вопросе, может потребоваться больше, чем в 3 раза, для вычисления, учитывая необходимые накладные расходы для копирования списков каждый раз (если мы не будем копировать списки, мы просто сортируем список, который уже были отсортированы, так как установка запускается только один раз).


    Мы можем разобрать каждую функцию:

     import dis def remove_extras_and_sort(my_list): for item in my_list[:]: count = my_list.count(item) if count > 1: for _ in range(count-1): my_list.remove(item) my_list.sort() return my_list def sorted_set(a_list): return sorted(set(a_list)) 

    И просто посмотрев на результат, мы видим, что байт-код для первой функции более чем в шесть раз длиннее:

     >>> dis.dis(remove_extras_and_sort) 2 0 SETUP_LOOP 85 (to 88) 3 LOAD_FAST 0 (my_list) 6 SLICE+0 7 GET_ITER >> 8 FOR_ITER 76 (to 87) 11 STORE_FAST 1 (item) 3 14 LOAD_FAST 0 (my_list) 17 LOAD_ATTR 0 (count) 20 LOAD_FAST 1 (item) 23 CALL_FUNCTION 1 26 STORE_FAST 2 (count) 4 29 LOAD_FAST 2 (count) 32 LOAD_CONST 1 (1) 35 COMPARE_OP 4 (>) 38 POP_JUMP_IF_FALSE 8 5 41 SETUP_LOOP 40 (to 84) 44 LOAD_GLOBAL 1 (range) 47 LOAD_FAST 2 (count) 50 LOAD_CONST 1 (1) 53 BINARY_SUBTRACT 54 CALL_FUNCTION 1 57 GET_ITER >> 58 FOR_ITER 19 (to 80) 61 STORE_FAST 3 (_) 6 64 LOAD_FAST 0 (my_list) 67 LOAD_ATTR 2 (remove) 70 LOAD_FAST 1 (item) 73 CALL_FUNCTION 1 76 POP_TOP 77 JUMP_ABSOLUTE 58 >> 80 POP_BLOCK 81 JUMP_ABSOLUTE 8 >> 84 JUMP_ABSOLUTE 8 >> 87 POP_BLOCK 7 >> 88 LOAD_FAST 0 (my_list) 91 LOAD_ATTR 3 (sort) 94 CALL_FUNCTION 0 97 POP_TOP 8 98 LOAD_FAST 0 (my_list) 101 RETURN_VALUE 

    И рекомендуемый способ имеет гораздо более короткий байт-код:

     >>> dis.dis(sorted_set) 2 0 LOAD_GLOBAL 0 (sorted) 3 LOAD_GLOBAL 1 (set) 6 LOAD_FAST 0 (a_list) 9 CALL_FUNCTION 1 12 CALL_FUNCTION 1 15 RETURN_VALUE 

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


    Приложение: другие варианты, которые необходимо более полно изучить:

     def groupby_sorted(my_list): """if items in my_list are unhashable""" from itertools import groupby return [e for e, g in groupby(sorted(my_list))] def preserve_order_encountered(my_list): """elements in argument must be hashable - preserves order encountered""" from collections import OrderedDict return list(OrderedDict.fromkeys(my_list)) 

    Размещение элементов в наборе, а затем сортировка будет эффективной, но она полагается на элементы хешируемой:

     def sorted_set(a_list): return sorted(set(a_list)) timeit sorted_set(my_list) 100000 loops, best of 3: 3.19 µs per loop 

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

     def sorted_unique(a_list): l = sorted(a_list) return l[:1] + [b for a, b in zip(l, l[1:]) if a != b] 

    Это не так уж плохо по сравнению с использованием set :

     timeit sorted_unique(my_list) 100000 loops, best of 3: 6.6 µs per loop 

    Мы можем на самом деле лучше использовать itertools.groupby :

     def sorted_group(a_list): return [k for k, _ in groupby(sorted(a_list))] timeit sorted_group(my_list) 100000 loops, best of 3: 5.3 µs per loop 

    Наконец, если элементы являются примитивными значениями, стоит рассмотреть numpy; в этом случае (в небольшом списке) накладные расходы перевешивают любые выгоды, но он хорошо работает на больших наборах проблем:

     def sorted_np(a_list): return np.unique(np.sort(a_list)) timeit sorted_np(my_list) 10000 loops, best of 3: 42 µs per loop my_list = [random.randint(0, 10**6) for _ in range(10**6)] timeit sorted_set(my_list) 1 loops, best of 3: 454 ms per loop timeit sorted_np(my_list) 1 loops, best of 3: 333 ms per loop 

    Это две простые функции в python:

     my_list = ['a', 'a', 'b', 'c', 'd', 'a', 'e', 'd', 'f', 'e'] print sorted(set(my_list)) 

    и вы получаете то, что хотите;)

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

    надеюсь это поможет.

     my_list = ['a', 'a', 'b', 'c', 'd', 'a', 'e', 'd', 'f', 'e'] b=[] for x in my_list: try: z=b.index(x) except: b.append(x) b.sort() output ['a', 'b', 'c', 'd', 'e', 'f']