Python - большой список эффективности

Question

У меня есть функция, unique(a), которая принимает список, a, чисел и возвращает только одно из каждого значения. В то же время он поддерживает порядок списка. У меня также есть функция, big_list(n), которая генерирует список len(n).

Причина, по которой я меняю направление списка, заключается в том, что при удалении значений он удаляет их из задней части исходного списка, просто чтобы сделать измененный список более чистым и читаемым при сравнении его с исходным списком ,

Функция работает, когда у меня относительно небольшая длина списка, который я создаю, но когда я получаю большие длины, например, 1 000 000 для ex, время выполнения занимает FOREVER.

Если кто-то может помочь мне, сделав мою функцию намного быстрее, это было бы здорово!

FYI: Мне нужно использовать набор в функции для задания, над которым я работаю. Мне все равно нужно удалить элементы списка со спины.

Заранее благодарен!

def big_list(n) : 
    # Create a list of n 'random' values in the range [-n/2,n/2] 
    return [ randrange(-n//2, n//2) for i in range(n) ] 

def unique(a) : 
    a = a[::-1] 
    b = set(a) 
    for i in b : 
     while a.count(i) != 1 : 
      a.remove(i) 
      a.count(i) 
    a = a[::-1] 
    return a 

Answer 1

Ваш алгоритм выполняет множество дополнительных элементов перемещения. Рассмотрим:

def unique(a): 
    b = set() 
    r = [] 
    for x in a: 
     if x not in b: 
      r.append(x) 
      b.insert(x) 
    return r 

Answer 2

Каждый раз, когда вы звоните a.count(i) он перебирает весь список, чтобы подсчитывать случаи. Это операция O (n), которую вы повторяете снова и снова. Когда вы определяете время выполнения O (n) внешнего цикла for i in b:, общая алгоритмическая сложность равна O (n).

Это не поможет, что есть второй ненужный a.count(i) внутри цикла while. Этот звонок не делает ничего, кроме времени пережевывания.

Вся эта проблема может быть выполнена в O (n) времени. Лучше всего было бы избежать list.count() и выяснить, как вы можете перебирать список и подсчитывать элементы самостоятельно. Если вы умны, вы можете делать все за один проход, никаких вложенных циклов (или неявных вложенных циклов) не требуется.

Answer 3

Вы можете найти исчерпывающий тест «уникальных» функций на this address. Мой личный фаворит

def unique(seq): 
    # Order preserving 
    seen = set() 
    return [x for x in seq if x not in seen and not seen.add(x)] 

потому что это самый быстрый и он сохраняет заказ при использовании наборов умно. Я думаю, что это f7, это указано в комментариях.