Удаление дубликатов из списка списков

Question

У меня есть список списков в Python:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

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

Как это можно сделать наиболее эффективным способом?

Результат приведенного выше списка должен быть:

k = [[5, 6, 2], [1, 2], [3], [4]]

Меня не волнует сохранение порядка.

Примечание: этот вопрос похож, но не совсем то, что мне нужно. Искал ТАК, но не нашел точного дубликата.

---

Бенчмаркинг:

import itertools, time


class Timer(object):
    def __init__(self, name=None):
        self.name = name

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        if self.name:
            print '[%s]' % self.name,
        print 'Elapsed: %s' % (time.time() - self.tstart)


k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000

print len(k)

with Timer('set'):
    for i in xrange(N):
        kt = [tuple(i) for i in k]
        skt = set(kt)
        kk = [list(i) for i in skt]


with Timer('sort'):
    for i in xrange(N):
        ks = sorted(k)
        dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]


with Timer('groupby'):
    for i in xrange(N):
        k = sorted(k)
        dedup = list(k for k, _ in itertools.groupby(k))

with Timer('loop in'):
    for i in xrange(N):
        new_k = []
        for elem in k:
            if elem not in new_k:
                new_k.append(elem)

"loop in" (квадратичный метод) быстрее всего для коротких списков. Для длинных списков это быстрее, чем у всех, кроме группового метода Имеет ли это смысл?

Для короткого списка (того, что в коде), 100000 итераций:

[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665

Для более длинного списка (тот, что в коде дублируется 5 раз):

[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599

Answer 1

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertools часто предлагает самые быстрые и мощные решения для такого рода проблем, и стоит хорошо , с которыми стоит познакомиться! -)

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

Тщательные измерения «точечной» производительности (код A против кода B для конкретного входа) являются частью этого чрезвычайно дорогостоящего процесса, и здесь помогает стандартный модуль библиотеки timeit. Тем не менее, проще использовать его в командной строке. Например, вот небольшой модуль для демонстрации общего подхода к этой проблеме, сохраните его как nodup.py:

import itertools

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

def doset(k, map=map, list=list, set=set, tuple=tuple):
  return map(list, set(map(tuple, k)))

def dosort(k, sorted=sorted, xrange=xrange, len=len):
  ks = sorted(k)
  return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]

def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list):
  ks = sorted(k)
  return [i for i, _ in itertools.groupby(ks)]

def donewk(k):
  newk = []
  for i in k:
    if i not in newk:
      newk.append(i)
  return newk

# sanity check that all functions compute the same result and don't alter k
if __name__ == '__main__':
  savek = list(k)
  for f in doset, dosort, dogroupby, donewk:
    resk = f(k)
    assert k == savek
    print '%10s %s' % (f.__name__, sorted(resk))

Обратите внимание на проверку работоспособности (выполняемую, когда вы просто выполняете python nodup.py) и базовую технику подъема (создание постоянных глобальных имен локально для каждой функции для скорости), чтобы поставить вещи в равное положение.

Теперь мы можем запускать проверки в крошечном списке примеров:

$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)'
100000 loops, best of 3: 11.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)'
100000 loops, best of 3: 9.68 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)'
100000 loops, best of 3: 8.74 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)'
100000 loops, best of 3: 4.44 usec per loop

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

$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])'
10000 loops, best of 3: 25.4 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])'
10000 loops, best of 3: 23.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])'
10000 loops, best of 3: 31.3 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])'
10000 loops, best of 3: 25 usec per loop

Квадратичный подход не плох, но сортировка и группировка лучше. И т. Д.

Если (как предполагает навязчивая идея производительности) эта операция находится в основном внутреннем цикле вашего приложения "раздвигающие границы", стоит попробовать тот же набор тестов на других репрезентативных входных выборках, возможно, обнаружив некоторую простую меру, которая может эвристически позволяет вам выбрать тот или иной подход (но, конечно, мера должна быть быстрой).

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

Answer 2

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> k = sorted(k)
>>> k
[[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]]
>>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]]
>>> dedup
[[1, 2], [3], [4], [5, 6, 2]]

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

Answer 3

Делаем это вручную, создаем новый список k и добавляем записи, которые пока не найдены:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
new_k = []
for elem in k:
    if elem not in new_k:
        new_k.append(elem)
k = new_k
print k
# prints [[1, 2], [4], [5, 6, 2], [3]]

Прост в понимании, и вы сохраняете порядок первого вхождения каждого элемента, если это будет полезно, но я думаю, что это квадратичная по сложности, так как вы ищете все new_k для каждого элемента.

Answer 4

Все связанные с set решения этой проблемы до сих пор требуют создания целого set до итерации.

Можно сделать это ленивым и в то же время сохранить порядок, перебирая список списков и добавляя к «увиденному» set. Тогда выдайте список, только если он не найден в этом трекере set.

Этот рецепт unique_everseen доступен в itertools документах . Он также доступен в сторонней toolz библиотеке:

from toolz import unique

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

# lazy iterator
res = map(list, unique(map(tuple, k)))

print(list(res))

[[1, 2], [4], [5, 6, 2], [3]]

Обратите внимание, что преобразование tuple необходимо, поскольку списки не могут быть хэшируемыми.

Answer 5

Список кортежей и {} можно использовать для удаления дубликатов

>>> [list(tupl) for tupl in {tuple(item) for item in k }]
[[1, 2], [5, 6, 2], [3], [4]]
>>> 

Answer 6

Даже ваш «длинный» список довольно короткий. Кроме того, вы выбрали их, чтобы соответствовать фактическим данным? Производительность зависит от того, как эти данные на самом деле выглядят. Например, у вас есть короткий список повторяется снова и снова, чтобы сделать более длинный список. Это означает, что квадратичное решение линейно в ваших тестах, но не в реальности.

Для действительно больших списков заданный код - ваш лучший выбор - он линейный (хотя и требует много места). Методы sort и groupby имеют вид O (n log n), а метод loop in, очевидно, является квадратичным, поэтому вы знаете, как они будут масштабироваться, когда n становится действительно большим. Если это реальный размер данных, которые вы анализируете, то кого это волнует? Это крошечный.

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

kt = [tuple(i) for i in k]
skt = set(kt)

с

skt = set(tuple(i) for i in k)

Реальное решение может зависеть от дополнительной информации: Вы уверены, что список списков - это действительно нужное вам представление?

Answer 7

Это должно работать.

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

k_cleaned = []
for ele in k:
    if set(ele) not in [set(x) for x in k_cleaned]:
        k_cleaned.append(ele)
print(k_cleaned)

# output: [[1, 2], [4], [5, 6, 2], [3]]

Answer 8

Как ни странно, приведенные выше ответы удаляют «дубликаты», но что, если я хочу удалить также дублированное значение ?? Следующее должно быть полезно и не создает новый объект в памяти!

def dictRemoveDuplicates(self):
    a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']]


print(a)
temp = 0
position = -1
for pageNo, item in a:
    position+=1
    if pageNo != temp:
        temp = pageNo
        continue
    else:
        a[position] = 0
        a[position - 1] = 0
a = [x for x in a if x != 0]         
print(a)

и o / p:

[[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']]
[[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]

Answer 9

Создайте словарь с кортежем в качестве ключа и напечатайте ключи.

• создать словарь с кортежем в качестве ключа и индексом в качестве значения
• печать списка ключей словаря

---

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

dict_tuple = {tuple(item): index for index, item in enumerate(k)}

print [list(itm) for itm in dict_tuple.keys()]

# prints [[1, 2], [5, 6, 2], [3], [4]]

Answer 10

Другое, возможно, более общее и более простое решение - создать словарь, основанный на строковой версии объектов и получить в конце значения ():

>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values()
[['A', 'B'], ['A', 'A']]

Подвох в том, что это работает только для объектов, чье строковое представление является достаточно хорошим уникальным ключом (что верно для большинства нативных объектов).