Как перебрать два отсортированных списка в наибольшем порядке пар в Python

У меня есть две отсортированные итерации, например:

a = [C, B, A]
b = [3, 2, 1]

Я хочу создать список всех возможных пар, сначала объединив пары с наибольшим (самым низким индексом). Самый большой означает сначала все комбинации элемента < 1 (для обеих итераций), затем все комбинации индекса < 2 и т. д. Это НЕ декартово произведение. Желаемый результат:

combine(a, b)
>> ((C, 3), (B, 3), (C, 2), (B, 2), (A, 3), (A, 2), (C, 1), (B, 1), (A, 1))

Я посмотрел на itertools.product(), но это только генерирует декартово произведение.

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

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

«Я посмотрел на itertools.product(), но он генерирует только декартово произведение». Желаемый вывод, который вы показываете, содержит каждый элемент, который содержит декартово произведение, и никаких других. Единственная очевидная проблема - это порядок, и это не очень точно указано. Я не могу понять, что вы подразумеваете под «самыми большими парами». Почему (B, 3) «больше», чем (C, 2), а (B, 2) «больше», чем (A, 3)? Каково настоящее правило? (Кроме того, должны ли A, B, C быть строками? Или это другие переменные в вашей программе? В таком случае, как мы должны знать, как их сортировать, не зная значений?)

Karl Knechtel 17.05.2022 00:36

«Итерации могут быть длинными (миллионы элементов)». Убедитесь, что у вас есть хорошее представление о том, сколько пар будет сгенерировано и сколько времени коду придется потратить на их итерацию, даже если ему не нужно их хранить. все.

Karl Knechtel 17.05.2022 00:37

Если вы не хотите генерировать весь декартовский продукт, а затем сортировать, возможной хитростью является использование приоритетной очереди (также известной как куча: import heapq). Если C — самый большой элемент из первого уровня, а 3 — самый большой из второго итерации, то, очевидно, самой большой парой будет (C, 3). Тогда второй по величине парой будет либо (B, 3), либо (C, 2); добавить их обоих в очередь приоритетов.

Stef 17.05.2022 00:40

Если сгенерировать весь декартов продукт нормально, конечно, вы можете просто сгенерировать весь декартов продукт, а затем отсортировать его.

Stef 17.05.2022 00:41

Не могли бы вы уточнить, что вы подразумеваете под «самой большой парой» — как вы определяете размер/вес пары?

BrokenBenchmark 17.05.2022 00:42

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

Stefan 17.05.2022 01:11

Ах, так смысл в том, чтобы лениво генерировать их таким образом, чтобы не нужно было проходить весь путь через один вход, прежде чем переходить к следующему элементу в другом? (т. е. способ, который также будет работать, если входные данные генерируются лениво). Я знаю способы сделать это, если вы можете принять O (N) хранилище уже «увиденных» элементов. Иначе я не думаю, что это возможно.

Karl Knechtel 17.05.2022 01:13

@KarlKnechtel Точно, итерации могут иметь миллионы записей, но в большинстве случаев желаемый результат будет найден в комбинациях первых нескольких записей. Так что гораздо эффективнее сначала попробовать их.

Stefan 17.05.2022 01:15

@KarlKnechtel Если итерации можно повторять несколько раз, мы можем сделать это с памятью O (1).

Kelly Bundy 17.05.2022 01:17

Если они ranges или что-то в этом роде, то да. В противном случае они уже сами занимают O(N) памяти;)

Karl Knechtel 17.05.2022 01:28
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
1
11
47
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Если вы не слишком придирчивы к порядку, согласно комментариям, и целью является просто ленивая генерация, которая рассматривает входы «равномерно»: вот простой подход для двух входов. Просто отслеживайте элементы, которые были «увидены» до сих пор из каждого входа, перебирая два входа по кругу (см. также рецепты в документации). С каждым новым элементом выдавайте пары, которые он образует с элементами из другого входа.

Однако, чтобы это работало, нам нужно знать, из какого источника мы извлекаем данные в циклической итерации. Мы могли бы изменить реализацию roundrobin так, чтобы yield эта информация была в какой-то закодированной форме; но я думаю, что для наших целей будет проще просто написать весь алгоритм напрямую, черпая оттуда вдохновение.

Таким образом:

def lazy_pairs(a, b):
    a_seen, b_seen = [], []
    a_active, b_active = True, True
    a_iter, b_iter = iter(a), iter(b)
    while a_active or b_active:
        if a_active:
            try:
                a_next = next(a_iter)
            except StopIteration:
                a_active = False
            else:
                for b_old in b_seen:
                    yield (a_next, b_old)
                a_seen.append(a_next)
        if b_active:
            try:
                b_next = next(b_iter)
            except StopIteration:
                b_active = False
            else:
                for a_old in a_seen:
                    yield (a_old, b_next)
                b_seen.append(b_next)

Обобщение для большего количества входных данных остается в качестве упражнения. (Обратите внимание, что вы можете вернуться к itertools.product, чтобы найти все возможности, связанные с элементом, только что взятым из одного входа, и видимыми элементами из всех остальных.)

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

Karl Knechtel 17.05.2022 01:30

Как оказалось, один из проектов на моем заднем плане дизайна — это класс для представления итерируемого объекта с «резервным хранилищем», так что вы можете учитывать предыдущие элементы, не загружая все следующие. Именно этот алгоритм я и собирался включить в пакет.

Karl Knechtel 17.05.2022 01:32

С yield from zip(repeat(a_next), b_seen) (как и с другим) у вас это займет примерно в 3 раза больше времени, чем у меня.

Kelly Bundy 17.05.2022 02:43
Ответ принят как подходящий

Используя рецепт roundrobin, о котором упомянул Карл (дословно скопировано из рецепты, можно также импортировать его из больше-itertools). Думаю, так будет быстрее, так как вся тяжелая работа выполняется в C-коде различных itertools.

from itertools import repeat, chain, cycle, islice

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

def pairs(a, b):
    aseen = []
    bseen = []
    def agen():
        for aa in a:
            aseen.append(aa)
            yield zip(repeat(aa), bseen)
    def bgen():
        for bb in b:
            bseen.append(bb)
            yield zip(aseen, repeat(bb))
    return chain.from_iterable(roundrobin(agen(), bgen()))

a = ['C', 'B', 'A']
b = [3, 2, 1]
print(*pairs(a, b))

Выход (Попробуйте онлайн!):

('C', 3) ('B', 3) ('C', 2) ('B', 2) ('A', 3) ('A', 2) ('C', 1) ('B', 1) ('A', 1)

Тест с двумя итерациями по 2000 элементов в каждой (Попробуйте онлайн!):

 50 ms   50 ms   50 ms  Kelly
241 ms  241 ms  242 ms  Karl

В качестве альтернативы, если две итерации могут повторяться несколько раз, нам не нужно сохранять то, что мы видели (Попробуйте онлайн!):

def pairs(a, b):
    def agen():
        for i, x in enumerate(a):
            yield zip(repeat(x), islice(b, i))
    def bgen():
        for i, x in enumerate(b, 1):
            yield zip(islice(a, i), repeat(x))
    return chain.from_iterable(roundrobin(agen(), bgen()))

(Добавлю в тест позже... Должно быть немного медленнее, чем мое первое решение.)

Экстремальная версия карты/itertools (Попробуйте онлайн!):

def pairs(a, b):
    return chain.from_iterable(roundrobin(
        map(zip,
            map(repeat, a),
            map(islice, repeat(b), count())),
        map(zip,
            map(islice, repeat(a), count(1)),
            map(repeat, b))
    ))

А, циклический перебор генераторы, чтобы избежать проблем с отслеживанием! Аккуратный.

Karl Knechtel 17.05.2022 02:49

@КарлКнехтель Краткое решение.

Kelly Bundy 17.05.2022 03:14

(Я думаю, что это ближе к тому, что вы имели в виду.)

Kelly Bundy 17.05.2022 03:14

Это очень элегантно!

Stefan 17.05.2022 10:47

Другие вопросы по теме