Проверка дубликатов в плоском списке

Пример 1

['one', 'two', 'one'] должен вернуть True .

Пример 2.

['one', 'two', 'three'] должны возвращать False .

  • Соответствие букв на любом языке
  • в чем разница между matplotlib.pyplot и matplotlib.figure?
  • Python os.system без вывода
  • Как вычислить вероятность значения, заданного списком выборок из дистрибутива в Python?
  • Какие инструменты scikit-learn могут обрабатывать многомерный вывод?
  • Django скачать файл
  • Как сделать тайм-аут subprocess.call с помощью python 2.7.6?
  • python pandas read_csv quotechar не работает
  • 5 Solutions collect form web for “Проверка дубликатов в плоском списке”

    Используйте set() для удаления дубликатов, если все значения хешируются :

     >>> your_list = ['one', 'two', 'one'] >>> len(your_list) != len(set(your_list)) True 

    Рекомендуется только для коротких списков:

     any(thelist.count(x) > 1 for x in thelist) 

    Не используйте длинный список – это может занять время, пропорциональное квадрату количества элементов в списке!

    Для более длинных списков с элементами хеширования (строки, числа и с):

     def anydup(thelist): seen = set() for x in thelist: if x in seen: return True seen.add(x) return False 

    Если ваши предметы не являются хешируемыми (подсписками, диктофонами и т. Д.), Он становится более увядшим, хотя может быть возможно получить O (N logN), если они, по крайней мере, сопоставимы. Но вам нужно знать или тестировать характеристики элементов (хешируемые или нет, сопоставимые или нет), чтобы получить максимальную производительность, которую вы можете – O (N) для hashables, O (N log N) для не-хешируемых сопоставимых данных, в противном случае это до нуля (N квадрат), и никто не может с этим поделать :-(.

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

     xs = [1, 2, 1] s = set() any(x in s or s.add(x) for x in xs) # You can use a similar approach to actually retrieve the duplicates. s = set() duplicates = set(x for x in xs if x in s or s.add(x)) 

    Если вы любите стиль функционального программирования, вот полезная функция, самодокументированный и протестированный код с использованием doctest .

     def decompose(a_list): """Turns a list into a set of all elements and a set of duplicated elements. Returns a pair of sets. The first one contains elements that are found at least once in the list. The second one contains elements that appear more than once. >>> decompose([1,2,3,5,3,2,6]) (set([1, 2, 3, 5, 6]), set([2, 3])) """ return reduce( lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))), a_list, (set(), set())) if __name__ == "__main__": import doctest doctest.testmod() 

    Оттуда вы можете проверить однозначность, проверяя, является ли второй элемент возвращенной пары пустым:

     def is_set(l): """Test if there is no duplicate element in l. >>> is_set([1,2,3]) True >>> is_set([1,2,1]) False >>> is_set([]) True """ return not decompose(l)[1] 

    Обратите внимание, что это не эффективно, так как вы явно строите разложение. Но по линии использования сокращения вы можете подойти к чему-то эквивалентному (но немного менее эффективному), чтобы ответить 5:

     def is_set(l): try: def func(s, o): if o in s: raise Exception return s.union([o]) reduce(func, l, set()) return True except: return False 

    Недавно я ответил на соответствующий вопрос, чтобы установить все дубликаты в списке, используя генератор. Это имеет то преимущество, что если использовать только для того, чтобы установить «если есть дубликат», вам просто нужно получить первый элемент, а остальные можно проигнорировать, что является конечным ярлыком.

    Это интересный подход на основе набора, который я адаптировал прямо из moooeeeep :

     def getDupes(l): seen = set() seen_add = seen.add for x in l: if x in seen or seen_add(x): yield x 

    Соответственно, будет list(getDupes(etc)) полный список list(getDupes(etc)) . Чтобы просто проверить, «если» есть обман, его следует обернуть следующим образом:

     def hasDupes(l): try: if getDupes(c).next(): return True # Found a dupe except StopIteration: pass return False 

    Это хорошо масштабируется и обеспечивает последовательное время работы везде, где обман входит в список – я тестировал списки со списком до 1 м. Если вы знаете что-то о данных, в частности, о том, что обманщики, вероятно, появятся в первой половине или другие вещи, которые позволят вам перекосить ваши требования, например, чтобы получить настоящие обманы, тогда есть несколько действительно альтернативных локаторов обмана которые могут превзойти. Я рекомендую …

    Простой подход на основе диктофона, очень читаемый:

     def getDupes(c): d = {} for i in c: if i in d: if d[i]: yield i d[i] = False else: d[i] = True 

    Использовать itertools (по существу, ifilter / izip / tee) в отсортированном списке, очень эффективно, если вы получаете все обманы, хотя не так быстро, чтобы получить только первое:

     def getDupes(c): a, b = itertools.tee(sorted(c)) next(b, None) r = None for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)): if k != r: yield k r = k 

    Это были лучшие исполнители из подходов, которые я пробовал для полного списка обломов , причем первый обман произошел где-то в списке элементов 1 м от начала до середины. Удивительно, как мало накладных, добавил шаг сортировки. Ваш пробег может отличаться, но вот мои конкретные результаты:

     Finding FIRST duplicate, single dupe places "n" elements in to 1m element array Test set len change : 50 - . . . . . -- 0.002 Test in dict : 50 - . . . . . -- 0.002 Test in set : 50 - . . . . . -- 0.002 Test sort/adjacent : 50 - . . . . . -- 0.023 Test sort/groupby : 50 - . . . . . -- 0.026 Test sort/zip : 50 - . . . . . -- 1.102 Test sort/izip : 50 - . . . . . -- 0.035 Test sort/tee/izip : 50 - . . . . . -- 0.024 Test moooeeeep : 50 - . . . . . -- 0.001 * Test iter*/sorted : 50 - . . . . . -- 0.027 Test set len change : 5000 - . . . . . -- 0.017 Test in dict : 5000 - . . . . . -- 0.003 * Test in set : 5000 - . . . . . -- 0.004 Test sort/adjacent : 5000 - . . . . . -- 0.031 Test sort/groupby : 5000 - . . . . . -- 0.035 Test sort/zip : 5000 - . . . . . -- 1.080 Test sort/izip : 5000 - . . . . . -- 0.043 Test sort/tee/izip : 5000 - . . . . . -- 0.031 Test moooeeeep : 5000 - . . . . . -- 0.003 * Test iter*/sorted : 5000 - . . . . . -- 0.031 Test set len change : 50000 - . . . . . -- 0.035 Test in dict : 50000 - . . . . . -- 0.023 Test in set : 50000 - . . . . . -- 0.023 Test sort/adjacent : 50000 - . . . . . -- 0.036 Test sort/groupby : 50000 - . . . . . -- 0.134 Test sort/zip : 50000 - . . . . . -- 1.121 Test sort/izip : 50000 - . . . . . -- 0.054 Test sort/tee/izip : 50000 - . . . . . -- 0.045 Test moooeeeep : 50000 - . . . . . -- 0.019 * Test iter*/sorted : 50000 - . . . . . -- 0.055 Test set len change : 500000 - . . . . . -- 0.249 Test in dict : 500000 - . . . . . -- 0.145 Test in set : 500000 - . . . . . -- 0.165 Test sort/adjacent : 500000 - . . . . . -- 0.139 Test sort/groupby : 500000 - . . . . . -- 1.138 Test sort/zip : 500000 - . . . . . -- 1.159 Test sort/izip : 500000 - . . . . . -- 0.126 Test sort/tee/izip : 500000 - . . . . . -- 0.120 * Test moooeeeep : 500000 - . . . . . -- 0.131 Test iter*/sorted : 500000 - . . . . . -- 0.157 
    Python - лучший язык программирования в мире.