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

Программа python3, которая вводит список и выводит, если он уникален или нет. Ниже приведен пример:Оптимизированный код для проверки уникального элемента списка

list_a = [1,2,3,4,5] #unique 
list_b = [1,2,2,3,4] #not unique

Я написал python3 сценарий для решения этой проблемы:

for i in range(len(list_a)): 
    j = i+1 
    for j in range(len(list_a)): 
     if list_a[i] == list_a[j]: 
     print ("not unique") 
     else: 
     print ("unique")

Это единственный способ проверить это. Держу пари, это не так! Я хочу, чтобы какой-то оптимизированный код был эквивалентен выше или просто, что делает «уникальным» или «не уникальным» для данного списка. Спасибо заранее.

источник

2013-10-27 SujitS

Оба примера отсортированы. Сортируются ли ваши входы? Я думаю, что это значительно изменит алгоритм. – mirk

О нет, это не так. Не отсортировано – SujitS

Самый простой способ сделать это сравнить длину набора данного списка с длиной списка:

if len(l) != len(set(l)): 
    # not unique

источник

2013-10-27 15:24:44 soon

Вы можете использовать all() и наборы, это будет короткое замыкание, как только повторный элемент найден ,

>>> def solve(lis): 
...  seen = set() 
...  return all(item not in seen and not seen.add(item) for item in lis) 
... 
>>> solve(range(5)) 
True 
>>> solve([1,2,2,3,4]) 
False

источник

2013-10-27 15:24:46

Это, по-видимому, самый эффективный алгоритм. – wheaties

Интересно, в какой момент накладные расходы на это начинают стоить дороже, чем это экономит ..... – tacaswell

Это намного медленнее, чем просто создать набор всего. Для списка из 100 пунктов (без дубликатов или дубликатов в конце списка) это уже заняло в 5 раз больше. Для списка с дубликатом в начале это действительно примерно в два раза быстрее, но когда дубликат находится посередине, это уже в 2,5 раза медленнее. Кажется, что точка изменения находится вокруг индекса 15 (из 100), где эти решения становятся медленнее, чем простая проверка длины. Поэтому я бы сказал: не стоит. Лучше в лучшем случае, но намного хуже в среднем и худшем случае, в то время как проверка длины имеет * постоянное * время. – poke

Бросьте список в комплекте:

set_a = set(list_a) 
if len(set_a) == len(list_a): 
    print("unique") 
else: 
    print("not unique")

источник

2013-10-27 15:24:55 tacaswell

Вы можете использовать AVL деревья, добавить каждый элемент по одному в дереве, а вставленный элемент еще не в дереве.

В случае больших списков он будет очень быстрым в сравнении с текущим кодом.

источник

2013-10-27 15:32:23

Реализация какой-либо структуры данных сопоставления сама по себе является излишней. – delnan

Я не говорю, что он должен реализовать его сам: он может использовать https://github.com/pgrafov/python-avl-tree/ (например). Определяется метод «найти». –

Если проверка уникального или уникального значения - это все, что вы хотите сделать, дерево AVL довольно преувеличено. Простая хеш-таблица с постоянной вставкой и поиском более эффективна, чем что-либо еще. – poke

Если вы хотите, чтобы легко найти повторяющиеся элементы, которые вы можете использовать collections.Counter:

import collections 
a = [1, 2, 2, 3] 
b = collections.Counter(a) 
duplicates = [i for i in b if b[i] > 1]

Переменная b является объектом, который действует немного как словарь с ключами быть значение из a и ценности, которые число, указывающее, как много раз это значение появилось в исходном списке.

print(b[2])

даст 2.

Переменная duplicates имеет все повторяющиеся элементы, и вы можете использовать его как это:

if duplicates: 
    print("not unique") 
else: 
    print("unique")

Это больше, чем создание набора, но у вас есть гораздо больше информации вы можете использовать.

источник

2013-10-27 15:46:48 pawelulita

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

ответ

Смежные вопросы