Сравните сложности перемещения с помощью установить список в/с в питона код

Question

Я хочу задать разницу во времени сложности 2 следующих подходов:

1. без использования устанавливается как в КОД 1
2. Используя набор как в CODE 2

Функция remove_duplicates() принимает список UNSORTED и удаляет элементы списка, которые являются одинаковыми.

КОД 1

def remove_duplicates(input_list): 
    result = [] 
    k = -1  # to store the index of current element being checked 
    for i in input_list: 
     k += 1 
     flag = False 
     for j in range(0,k,+1): 
      if(input_list[j] == i): 
       flag = True 
     if(flag==False): 
      result.append(i) 
     else: 
      continue 
    return result 

КОД 2

def remove_duplicates(input_list): 
    return list(set(input_list)) 

Answer 1

Поскольку вы просите сложности, давайте посмотрим на ваш первый решение:

внешний цикл будет работать n раз, с n - длина списка. Для каждой итерации вы снова повторяетесь над первым элементом k. Поэтому, если мы просто подсчитываем все внутренние петли, у нас есть как итерации n + (n-1) + (n-2) + … + 2 + 1. Это O (n²).

Чтобы проверить установленное решение, мы должны понять, как это работает. Создание набора из списка будет перебирать список ровно один раз. Для каждого элемента, который мы найдем в списке, этот элемент будет добавлен в набор. Добавление в набор выполняется в (среднем) постоянном времени. Таким образом, в целом это O (n).

Другим решением было бы сначала отсортировать список, а затем перебрать за над ним, чтобы найти дубликаты. Таким образом, у нас было бы X + O(n), где X - сложность алгоритма сортировки. Поскольку мы не можем сортировать быстрее, чем O (n), эта сложность определит сложность полного алгоритма.

Что касается космической сложности, то первая и третья могут быть выполнены на месте, поэтому мы нуждаемся в постоянном пространстве. Множество нуждается в O (n) в худшем случае.

Answer 2

Просто используйте list(set(input_list))

Answer 3

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

import timeit 
import random 
import functools 

def remove_duplicates_manual(input_list): 
    result = [] 
    k = -1  # to store the index of current element being checked 
    for i in input_list: 
     k += 1 
     flag = False 
     for j in range(0,k,+1): 
      if(input_list[j] == i): 
       flag = True 
     if(flag==False): 
      result.append(i) 
     else: 
      continue 

    return result 

def remove_duplicates_set(input_list): 
    return list(set(input_list)) 

l = [random.randint(0, 10) for x in xrange(1000)] 
rd_manual = functools.partial(remove_duplicates_manual, l) 
rd_set = functools.partial(remove_duplicates_set, l) 

print(timeit.timeit(rd_manual, number=100)) 
print(timeit.timeit(rd_set, number=100)) 

Этот код производит этот выход:

3,648878
0,001779

Таким образом, мы можем заключить, что метод set обычно будет быстрее дано список случайных целых чисел в диапазоне 0-10, но он может различаться для ваших данных и вашей системы. Кроме того, как упоминалось в комментариях и других ответах, есть также много способов, которыми вы могли бы настроить свой ручной алгоритм, чтобы сделать его быстрее.

Кроме того, вы должны отметить, что метод set может быть невозможен даже для некоторых данных.Наборы Python требуют хешируемых типов данных (так же, как словарные ключи), поэтому, если вы сортируете список изменяемых типов данных (например, другие списки), вы не сможете использовать list(set(input_list)).