У меня есть список списков в Python:
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
И я хочу удалить из него повторяющиеся элементы. Было бы, если бы это был обычный список, а не списки, которые я мог бы использовать set. Но, к сожалению, этот список не хешируется и не может создавать наборы списков. Только кортежей. Таким образом, я могу превратить все списки в кортежи, а затем использовать set и вернуться к спискам. Но это не быстро.
Как это сделать наиболее эффективно?
Результат список выше должен быть:
k = [[5, 6, 2], [1, 2], [3], [4]]
Меня не волнует сохранение порядка.
Примечание: этот вопрос похож, но не совсем то, что я нуждаться. Выполнил поиск SO, но не нашел точного дубликата.
Сравнительный анализ:
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 for i in xrange(len(ks)) if i == 0 or ks != 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)
Зацикливание (квадратичный метод) быстрее всего подходит для коротких списков. Для длинных списков это быстрее, чем все, кроме метода groupby. Имеет ли это смысл?
Для краткого списка (того, что в коде), 100 000 итераций:
[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
Подробнее здесь: https://stackoverflow.com/questions/221 ... t-of-lists
