Как удалить дубликаты списка списков на основе элемента во вложенном списке - PullRequest
Новая
       27

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

0 голосов
/ 27 января 2020

Я хочу удалить дубликаты из списка списков. Первый элемент НЕ всегда уникален для каждого второго элемента во вложенном списке. Первое значение уникально для всего списка списков. Числа встречаются только один раз во всем списке списков, но не упорядочены. 

my_list = [[4, 'C'], [1, 'A'], [3, 'B'], [2, 'A'], [5, 'C']]

Удаление дубликатов основано на втором элементе во вложенном списке. Мне нужно минимальное значение для каждого уникального второго элемента, например: 

my_unique_list = [[1, 'A'], [3, 'B'], [4, 'C']]

Не имеет значения, в каком порядке выводится.

Итак, выберите 1 для 'A' (поскольку 1 меньше, чем 2 из [2, 'A']), 3 для 'B' (других значений для 'B' нет) и 4 для 'C' (так как 4 меньше 5 из [5, 'C']).

Ответы [ 3 ]

9 голосов
/ 27 января 2020

Используйте словарь для сопоставления уникальных букв (вторых значений) с минимальным значением для каждой буквы, а затем просто используйте пары [value, key] из этого словаря в качестве вывода: 

minimi = {}
inf = float('inf')
for val, key in my_list:
    # float('inf') as default value is always larger, so val is picked
    # if the key isn't present yet.
    minimi[key] = min(val, minimi.get(key, inf))

my_unique_list = [[v, k] for k, v in minimi.items()]

Используя словарь в качестве посредника вы можете фильтровать ввод по линейному времени.

Демонстрация: 

>>> my_list = [[4, 'C'], [1, 'A'], [3, 'B'], [2, 'A'], [5,'C']]
>>> minimi, inf = {}, float('inf')
>>> for val, key in my_list:
...     minimi[key] = min(val, minimi.get(key, inf))
...
>>> minimi
{'C': 4, 'A': 1, 'B': 3}
>>> my_unique_list = [[v, k] for k, v in minimi.items()]
>>> my_unique_list
[[4, 'C'], [1, 'A'], [3, 'B']]

Почему вы должны заботиться о времени выполнения? Потому что по мере того, как ваш вклад растет, увеличивается и ваше время выполнения. Для подходов, которые занимают O (N ^ 2) (квадратичное c) время, когда вы go с 1000 единиц до 1 миллиона (то есть в 1000 раз больше), ваше время выполнения увеличится в 1 миллион раз! Для подходов O (N logN) (тех, которые используют сортировку) время выполнения увеличилось бы в ~ 2000 раз, в то время как линейный подход, как указано выше, занял бы в 1000 раз больше времени, линейно масштабируясь как масштаб ваших входных данных.

Для больших входных данных, которые могут иметь значение между «занимает час или два», чтобы «занимает миллионы лет».

Вот сравнение временного испытания между этим подходом и подходом сортировки и задания Замира ( O (N logN)), а также подход TJ C World Pandas (также O (N logN)): 

from string import ascii_uppercase
from functools import partial
from timeit import Timer
import random
import pandas as pd

def gen_data(N):
    return [[random.randrange(1_000_000), random.choice(ascii_uppercase)] for _ in range(N)]

def with_dict(l, _min=min, _inf=float('inf')):
    minimi = {}
    m_get = minimi.get
    for val, key in l:
        minimi[key] = _min(val, m_get(key, _inf))
    return [[v, k] for k, v in minimi.items()]

def with_set_and_sort(l):
    already_encountered = set()
    ae_add = already_encountered.add
    return [i for i in sorted(l) if i[1] not in already_encountered and not ae_add(i[1])]

def with_pandas(l):
    return (
        pd.DataFrame(l)
        .sort_values(by=0)
        .drop_duplicates(1)
        .to_numpy()
        .tolist()
    )

for n in (100, 1000, 10_000, 100_000, 1_000_000):
    testdata = gen_data(n)
    print(f"{n:,} entries:")
    for test in (with_dict, with_set_and_sort, with_pandas):
        count, total = Timer(partial(test, testdata)).autorange()
        print(f"{test.__name__:>20}: {total/count * 1000:8.3f}ms")
    print()

Я использовал все небольшие приемы производительности, о которых я знаю ; избегая повторного поиска глобальных переменных и атрибутов путем кэширования их в локальных именах вне циклов.

Это приводит к выводу: 

100 entries:
           with_dict:    0.028ms
   with_set_and_sort:    0.032ms
         with_pandas:    2.070ms

1,000 entries:
           with_dict:    0.242ms
   with_set_and_sort:    0.369ms
         with_pandas:    2.312ms

10,000 entries:
           with_dict:    2.331ms
   with_set_and_sort:    5.639ms
         with_pandas:    5.476ms

100,000 entries:
           with_dict:   23.105ms
   with_set_and_sort:  127.772ms
         with_pandas:   40.330ms

1,000,000 entries:
           with_dict:  245.982ms
   with_set_and_sort: 2494.305ms
         with_pandas:  578.952ms

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

Pandas проигрывает здесь на всех фронтах. Фреймы данных - отличный инструмент, но здесь он не тот. Это огромные структуры данных, поэтому при небольших входах их высокая служебная нагрузка ставит их в миллисекундный диапазон, намного отставая от двух других вариантов. При 10 тыс. Записей он начинает превосходить подход сортировки и задания, но даже несмотря на то, что операции с кадрами данных сильно оптимизированы, рост времени выполнения сортировки с большими входными данными все еще не может превзойти линейный подход.

1 голос
/ 27 января 2020 
already_encountered = set()
my_new_list = [i for i in sorted(my_list) if i[1] not in already_encountered and not already_encountered.add(i[1])]

Выход: 

[[1, 'A'], [3, 'B'], [4, 'C']]
0 голосов
/ 27 января 2020

Использование панд; 

>>> import pandas as pd
>>> my_list = [[1, 'A'], [2, 'A'], [3, 'B'], [4, 'C'], [5,'C']]
>>> df = pd.DataFrame(my_list)
>>> df.sort_values(by = 0).drop_duplicates(1).to_numpy().tolist()
[[1, 'A'], [3, 'B'], [4, 'C']]
...