Python: эффективно и элегантно удаляйте все дубликаты из большого списка списков

Question

У меня есть список координат xy в виде списков:

print(xy[0:10])

[[104.44464000013596, 21.900339999891116],
 [9.574480000151937, 0.32839999976022227],
 [9.932610000251373, 0.19092000005798582],
 [9.821009999711748, 0.26556000039374794],
 [9.877130000349268, -0.6701499997226392],
 [149.51198999973872, -28.469329999879562],
 [149.35872999988965, -28.684280000021943],
 [9.859010000211413, -0.03293000041912819],
 [9.38918000035676, -0.9979400000309511],
 [77.35380000007001, 32.926530000359264]]

Здесь показаны первые 10, но в моем списке ~ 100 000 пар координат.

Я хотел быудалить все дубликаты списков из этого списка, но эффективно.В качестве более простого для понимания примера я хотел бы создать функцию remove_dupes, которая выдает следующий результат:

a = [[1, 2], [3, 4], [5, 6], [1, 2], [1, 2], [8, 9], [3, 4]]
b = remove_dupes(a)
print(b)
b = [[5, 6], [8 ,9]]

Обратите внимание, что порядок важен для сохранения.

Однако, посколькуУ меня такой большой список, я считаю, что использование метода .count () и итерация по списку слишком трудоемки.Я также пробовал различные приемы с set () и уникальной функцией numpy.

Вот самая быстрая версия, которую я мог придумать:

xy = [[x1,y1], [x2,y2], ... [xn, yn]]

def remove_dupes(xy):

    xy = [tuple(p) for p in xy] # Tupelize coordinates list for hashing

    p_hash = [hash(tuple(p)) for p in xy] # Hash each coordinate-pair list to a single value

    counts = Counter(p_hash) # Get counts (dictionary) for each unique hash value

    p_remove = [key for (key, value) in counts.items() if value > 1] # Store keys with count > 1

    p_hash = np.array(p_hash) # Cast from list to numpy array 

    remove = np.zeros((len(xy),1), dtype=np.bool) # Initialize storage

    for p in p_remove: # Loop through each non-unique hash and set all the indices where it appears to True // Most time-consuming portion
        remove[np.where(p==p_hash)[0]] = True

    xy = np.array(xy) # Cast back to numpy array for indexing

    xy = xy[remove.flat==False, :]  # Keep only the non-duplicates

    return xy

Это займет ~ 2 секунды для ~ 100 000 значений (и займет больше времени, если будет больше дублирующих пар, троек и т. Д..).Что меня беспокоит, так это то, что есть функции, такие как numpy.unique (), которые возвращают счетчики и индексы в доли секунды, но я не могу понять, как согласовать их выходные данные для решения этой проблемы.Я просмотрел пару дюжин других сообщений Stackexchange, которые были похожи, но я не нашел ничего, что было бы одновременно эффективным и элегантным.Кто-нибудь есть какие-либо предложения для более элегантного способа решения этой проблемы, чем я представил здесь?

РЕДАКТИРОВАТЬ:

Я получил два ответа, которые обеспечивают правильный результат (и сохранить порядок).RafaelC предоставил опцию Pandas, а DYZ предоставил опцию Counter.Я не очень хорошо разбираюсь в том, как правильно рассчитывать время, но я выполнил оба теста по 100 итераций (для одних и тех же данных) со следующими результатами (используя time.time ())

Панды: 13,02 сек

Счетчик: 28,15 с

Я не уверен, почему реализация Pandas быстрее;одно отличие состоит в том, что решение Pandas возвращает кортежи (что нормально), поэтому я попробовал решение Counter без преобразования обратно в списки, и это было еще 25 секунд.

Answer 1

В словарях Python 3.6+ сохраняется порядок вставки, поэтому решение DYZ Counter можно значительно улучшить, полагаясь на это:

[list(k) for k, c in Counter(map(tuple, a)).items() if c == 1]

На моем компьютере это быстрее, чем решение для панд.

Рада от RafaelC также может значительно ускорить работу.Ключ в том, чтобы переключиться с Series на DataFrame:

s = pd.DataFrame(a)
return s[~s.duplicated(keep=False)].values.tolist()

На моем компьютере это почти в два раза быстрее, чем оригинальное решение для панд.Ключ к ускорению заключается в том, что он избегает выполнения подготовительной работы за пределами панд (list(map(tuple, l))).

Answer 2

Я бы использовал pandas

s = pd.Series(list(map(tuple, l)))
s[~s.duplicated(keep=False)].tolist()

Принимает

211 ms ± 16.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

для 100000 записей, так что ускорение в 10 раз.

Answer 3

У меня есть эффективное решение, которое также встроено в

import itertools
xy = [[104.44464000013596, 21.900339999891116],
 [9.574480000151937, 0.32839999976022227],
 [9.932610000251373, 0.19092000005798582],
 [9.821009999711748, 0.26556000039374794],
 [9.877130000349268, -0.6701499997226392],
 [149.51198999973872, -28.469329999879562],
 [149.35872999988965, -28.684280000021943],
 [9.859010000211413, -0.03293000041912819],
 [9.38918000035676, -0.9979400000309511],
 [77.35380000007001, 32.926530000359264]]

xy.sort() # sorting the data
sorted_data = list(xy for xy,_ in itertools.groupby(xy)) # grouping

Примечание. Я протестировал два метода, используя numpy и itertools .Numpy занял 13 секунд в данных длины 10000000, а intertools занял 1 секунду в данных длины 10000000

Answer 4

Рассмотрите возможность использования счетчика:

from collections import Counter

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

nodups = {k for k,cnt in Counter(map(tuple, a)).items() if cnt == 1}

Теперь, поскольку порядок важен, отфильтруйте исходный список от не дублирований:

[list(k) for k in map(tuple, a) if k in nodups]
#[[5, 6], [8, 9]]