Сортировать список по наличию элементов в другом списке

Question

Предположим, у меня есть два списка:

a = ['30', '10', '90', '1111', '17']
b = ['60', '1201', '30', '17', '900']

Как бы вы отсортировали это наиболее эффективно, например:

список b отсортирован по a. Уникальные элементы в b должны быть помещены в конец отсортированного списка. Уникальные элементы в a можно игнорировать.

пример вывода:

c = ['30', '17', '60', '1201', '900']

Извините, это простой вопрос. Моя попытка застряла в точке пересечения.

intersection = sorted(set(a) & set(b), key = a.index)

Answer 1

Нет необходимости фактически сортировать здесь. Вы хотите, чтобы элементы в a были в b, в том же порядке, в котором они были в a; за которыми следуют элементы в b, которые не находятся в a, в том же порядке, в котором они были в b.

Мы можем просто сделать это с двумя фильтрами, используя наборы для быстрых тестов членства :

>>> a = ['30', '10', '90', '1111', '17']
>>> b = ['60', '1201', '30', '17', '900']
>>> a_set = set(a)
>>> b_set = set(b)
>>> [*filter(lambda x: x in b_set, a), *filter(lambda x: x not in a_set, b)]
['30', '17', '60', '1201', '900']

Или, если вы предпочитаете понимание:

>>> [*(x for x in a if x in b_set), *(x for x in b if x not in a_set)]
['30', '17', '60', '1201', '900']

Оба требуют линейного времени, что лучше, чем сортировка.

Answer 2

Вы можете создать собственный словарь, ключами которого будут записи в a, а значения - их положение. Затем сортируйте b в соответствии со значениями в словаре. Вы можете использовать dict.get для поиска и inf, если значение отсутствует:

a = ['30', '10', '90', '1111', '17']
b = ['60', '1201', '30', '17', '900']

d = {i:ix for ix, i in enumerate(a)}
#{'30': 0, '10': 1, '90': 2, '1111': 3, '17': 4}
sorted(b, key=lambda x: d.get(x, float('inf')))
#['30', '17', '60', '1201', '900']

Answer 3

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

Сортировать список по наличию элементов в другом списке

Код:

>>> sorted(b, key=set(a).__contains__, reverse=True)
['30', '17', '60', '1201', '900']

или

>>> sorted(b, key=lambda x, s=set(a): x not in s)
['30', '17', '60', '1201', '900']

Сортировка логических значений практически неотличима от линейного времени, и эти решения быстрее, чем общепринятые решения, как на данных вашего примера, так и на данных примера, которые я пробовал с миллионами случайных чисел (где около половины элементов b были в a).

Тесты

   n    b in a   kaya1    kaya2    heap1    heap2    heap3
----------------------------------------------------------
   1024 53.12%  0.00046  0.00033  0.00020  0.00067  0.00018
   2048 51.03%  0.00142  0.00069  0.00048  0.00071  0.00060
   4096 50.34%  0.00226  0.00232  0.00127  0.00183  0.00125
   8192 50.42%  0.00938  0.00843  0.00328  0.00471  0.00351
  16384 50.38%  0.02010  0.01647  0.00776  0.00992  0.00839
  32768 49.96%  0.03987  0.03165  0.01661  0.02326  0.01951
  65536 50.20%  0.08002  0.06548  0.03326  0.04828  0.03896
 131072 50.04%  0.16118  0.12863  0.06671  0.09642  0.07840
 262144 50.06%  0.32698  0.26757  0.13477  0.19342  0.15828
 524288 50.08%  0.66735  0.54627  0.27378  0.38365  0.32496
1048576 50.00%  1.34095  1.08972  0.54703  0.78028  0.65623
2097152 50.03%  2.68957  2.20556  1.13797  1.60649  1.33975
4194304 50.01%  5.36141  4.33496  2.25494  3.18520  2.70506
8388608 49.99% 10.72588  8.74114  4.56061  6.35421  5.36515

Примечание:

• n - это размер b.
• a подготовлен как set перед сравнительным анализом функций, чтобы сосредоточиться на их различиях. Размер a всегда равен 8388608, чтобы in a проверял постоянное время (даже set s замедляется при увеличении).
• b in a - это процент элементов b в a. Я сделал их так, чтобы это было около 50%.
• kaya1 и kaya2 взяты из принятого ответа @ kaya3, модифицированного так, чтобы они выполняли то, что я считаю заданием (сортировка b по наличие элементов в a, а не в «a & b», за которым следует «b \ a»).
• heap1 и heap2 - мои два вышеупомянутых решения с использованием sorted.
• heap3 - это самое быстрое решение без sorted, которое мне удалось написать.
• Результат - время в секундах.

Код теста:

from timeit import repeat
import random

def kaya1(a_set, b):
    return [*filter(lambda x: x in a_set, b), *filter(lambda x: x not in a_set, b)]

def kaya2(a_set, b):
    return [*(x for x in b if x in a_set), *(x for x in b if x not in a_set)]

def heap1(a_set, b):
    return sorted(b, key=a_set.__contains__, reverse=True)

def heap2(a_set, b):
    return sorted(b, key=lambda x: x not in a_set)

def heap3(a_set, b):
    not_in_a = []
    append = not_in_a.append
    in_a = [x for x in b if x in a_set or append(x)]
    in_a.extend(not_in_a)
    return in_a

print('   n    b in a   kaya1    kaya2    heap1    heap2    heap3')
print('----------------------------------------------------------')

A = random.sample(range(2**24), 2**23)
B = random.sample(range(2**24), 2**23)
a_set = set(A)

for e in range(10, 24):
    n = 2**e
    b = B[:n]
    print('%7d %5.2f%%' % (n, 100 * len(set(b) & a_set) / len(b)), end='')
    expect = None
    for sort in kaya1, kaya2, heap1, heap2, heap3:
        t = min(repeat(lambda: sort(a_set, b), number=1))
        print('%9.5f' % t, end='')
        output = sort(a_set, b)
        if expect is None:
            expect = output
        else:
            assert output == expect
    print()

Answer 4

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

c = [x for x in a if x in b] + [x for x in b if x not in a]

Однако это O (n ^ 2). Если ваш список большой и вы хотите его ускорить, попробуйте создать набор a и b соответственно и использовать их для проверки членства.

Answer 5

Может быть, это должно работать.

intersection = sorted(set(a) & set(b), key=a.index)
intersection.extend([ele for ele in b if ele not in intersection])