Быстрый способ пересечения строк в списке

Если у вас есть такой список:

shops=['A','B','C','D']

И хотел бы создать следующие новые списки (я пересекаю каждый элемент друг с другом и создаю строку, где первая часть имеет буквенно-буквенный формат перед вторым):

['A-B', 'A-C', 'A-D']

['A-B', 'B-C', 'B-D']

['A-C', 'B-C', 'C-D']

['A-D', 'B-D', 'C-D']

У меня есть что-то вроде этого:

for a in shops:
    cons = []
    for b in shops:
        if a!=b:
            con = [a,b]
            con = sorted(con, key=lambda x: float(x))
            cons.append(con[0]+'-'+con[1])
    print(cons)

Однако это довольно медленно для больших списков (например, 1000, где у меня есть 1000 * 999 * 0,5 выходов). Я искал более эффективный способ сделать это?

Я мог бы использовать предложение if-else для сортировки, например.

for a in shops:
    cons = []
    for b in shops:
        if a<b:
            cons.append(a+"-"+b)
        elif a>b:
            cons.append(b+"-"+a)
    print(cons)

Который, я еще не приурочен - однако я думал, что основным замедлением является двойной цикл for

Ответ 1

Вы можете создать вложенное понимание списка с некоторыми дополнительными проверками:

>>> shops=['A','B','C','D']
>>> [["-".join((min(a,b), max(a,b))) for b in shops if b != a] for a in shops]
[['A-B', 'A-C', 'A-D'],
 ['A-B', 'B-C', 'B-D'],
 ['A-C', 'B-C', 'C-D'],
 ['A-D', 'B-D', 'C-D']]

Обратите внимание, что это, вероятно, будет не намного быстрее, чем ваш код, поскольку вам все равно придется создавать все эти комбинации. На практике вы можете сделать это генераторным выражением, поэтому элементы генерируются не сразу, а только "по мере необходимости":

gen = (["-".join((min(a,b), max(a,b))) for b in shops if b != a] for a in shops)
for item in gen:
    print(item)

Обновление: я сделал некоторый анализ времени, используя IPython %timeit. Оказывается, ваша вторая реализация является самой быстрой. Протестировано со списком из 100 строк (map(str, range(100))) и после включения каждого из методов в генераторы.

In [32]: %timeit list(test.f1())         # your first implementation
100 loops, best of 3: 13.5 ms per loop

In [33]: %timeit list(test.f2())         # your second implementation
1000 loops, best of 3: 1.63 ms per loop

In [34]: %timeit list(test.g())          # my implementation
100 loops, best of 3: 3.49 ms per loop

Вы можете ускорить его, используя простой if/else вместо min/max, как во второй реализации, тогда они примерно одинаково быстры.

(["-".join((a,b) if a < b else (b,a)) for b in shops if b != a] for a in shops)

Ответ 2

Если список отсортирован и нет дубликатов, вы можете отслеживать свою позицию в списке, чтобы избежать необходимости выполнять сравнения, чтобы получить заказ.

from itertools import chain, islice

combos = []
for i, s in enumerate(shops):
    combo = ['{0}-{1}'.format(a, b) for a, b in chain(
        ((c, s) for c in islice(shops, None, i),
        ((s, c) for c in islice(shops, i+1))]
    combos.append(combo)

EDIT: обновлено для использования генераторов

Ответ 3

Основываясь на том, что вы сказали:

Я пересекаю каждый элемент со всеми остальными и создаю строку, где сначала часть буквенно-цифра перед вторым

Вы можете использовать 2 комбинации, например:

>>> form itertools import combinations
>>> list(combinations(['_'.join(i) for i in combinations(shops,2)],3)
... )
[('A_B', 'A_C', 'A_D'), ('A_B', 'A_C', 'B_C'), ('A_B', 'A_C', 'B_D'), ('A_B', 'A_C', 'C_D'), ('A_B', 'A_D', 'B_C'), ('A_B', 'A_D', 'B_D'), ('A_B', 'A_D', 'C_D'), ('A_B', 'B_C', 'B_D'), ('A_B', 'B_C', 'C_D'), ('A_B', 'B_D', 'C_D'), ('A_C', 'A_D', 'B_C'), ('A_C', 'A_D', 'B_D'), ('A_C', 'A_D', 'C_D'), ('A_C', 'B_C', 'B_D'), ('A_C', 'B_C', 'C_D'), ('A_C', 'B_D', 'C_D'), ('A_D', 'B_C', 'B_D'), ('A_D', 'B_C', 'C_D'), ('A_D', 'B_D', 'C_D'), ('B_C', 'B_D', 'C_D')]
>>>

Сначала вы можете использовать комбинацию в понимании списка для создания упорядоченных пар и объединить их с помощью str.join. Затем используйте другие комбинации для создания тринальных наборов.