Как эффективно подсчитать все конкатенации двух кортежей в более длинные цепочки в Python

Допустим, мы хотим построить длинную (металлическую) цепь, которая будет состоять из более мелких звеньев, соединенных вместе. Я знаю, какой длины должна быть цепочка: н. Ссылки представлены в виде двух кортежей: (а, б). Мы можем связать звенья вместе, если и только если они имеют один и тот же элемент на той стороне, с которой они будут связаны. Мне дан список списков длины п-1links — который представляет все ссылки, доступные мне в каждой позиции цепочки. Например:

links = [
    [
        ('a', 1),
        ('a', 2),
        ('a', 3),
        ('b', 1),
    ],
    [
        (1, 'A'),
        (2, 'A'),
        (2, 'B'),
    ],
    [
        ('A', 'a'),
        ('B', 'a'),
        ('B', 'b'),
    ]
]

В этом случае длина конечной цепочки будет: п = 4.
Здесь мы можем сгенерировать эти возможные цепочки:

('a', 1, 'A', 'a')
('b', 1, 'A', 'a')
('a', 2, 'A', 'a')
('a', 2, 'B', 'a')
('a', 2, 'B', 'b')

Эта процедура очень похожа на формирование длинной линии с головоломками домино, однако я не могу вращать плитки.

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

Я написал очень наивное решение с итерацией по всем ссылкам от начала до конца и сливаю их вместе, наращивая все возможные варианты конечной цепочки:


    # THIS CODE WAS ORIGINALLY BUGGED ONCE I POSTED IT
    # BUT IS FIXED NOW

    # initiate chains with links that could make up
    # the first position, then: iteratively grow them
    chains = links[0]
    
    # seach for all possible paths:
    # iterate over all positions
    for position in links[1:]:
        
        # temp array to help me grow the chain
        temp = []
            
        # over each chain in the current set of chains
        for chain in chains:

            # over each link in a given position
            for link in position:
                
                # check if the chain and link are chainable
                if chain[-1] == link[0]:
                    
                    # append new link to a pre-existing chain
                    temp.append(chain + tuple([link[1]]))
        
        # overwrite the current list of chains
        chains = temp

Это решение отлично работает, т.е. я совершенно убежден, что оно возвращает правильный результат. Тем не менее, это очень сильно медленно, мне нужно ускорить его, желательно ~ 100x. Поэтому я думаю, что мне нужно использовать умный алгоритм для подсчета всех возможностей, а не грубую конкатенацию, как указано выше... Поскольку мне нужно только подсчитать цепочки, а не перечислить их, возможно, будет процедура возврата, которая запустится от каждого возможного конечного звена и умножать возможности по пути; в итоге суммируя все окончательные ссылки? У меня есть некоторые смутные идеи, но я не могу прибить это...

Также был бы полезен небольшой код для создания реалистично большого ввода.

Kelly Bundy 09.04.2022 13:50

Не могли бы вы завершить код решения, сделав его понятной функцией? То есть, предположительно добавить строку def count_chains(links): сверху и return len(chains) снизу.

Kelly Bundy 09.04.2022 15:50
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
2
2
76
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

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

from collections import defaultdict, Counter

def count_chains(links):
    chains = defaultdict(lambda: 1)
    for position in links:
        temp = Counter()
        for a, b in position:
            temp[b] += chains[a]
        chains = temp
    return sum(chains.values())

Он делает почти то же самое, что и ваш, за исключением того, что вместо список цепочек, оканчивающихся на некоторые b-значения, я использую Прилавок цепочек, оканчивающихся на некоторые b-значения: chains говорит мне, сколько цепочек оканчивается на chains[b]. А Counters (и defaultdict) — это словари, поэтому мне не нужно искать и проверять для сопоставления коннекторов, я просто искать их.

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

Например, для b вычисление количества цепочек занимает около 2 мс, а именно:

21430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138752

Попробуйте онлайн!

Не могли бы вы уточнить свой ответ? Я имею в виду: объясните, как это работает? Я нигде не могу найти сравнение совместимости, что очень важно, не так ли?

maciek 09.04.2022 14:51

@maciek Он делает почти то же самое, что и ваш, за исключением того, что вместо chains быть список цепочек, заканчивающихся некоторыми b-значениями, я использую Прилавок цепочек, заканчивающихся некоторыми b-значениями: chains[b] говорит мне, сколько цепочек заканчивается в b. А Counters (и defaultdict) — это словари, поэтому мне не нужно искать и проверять для сопоставления коннекторов, я просто искать их.

Kelly Bundy 09.04.2022 14:57

Не могли бы вы включить эту информацию в ответ? Я хотел бы принять это, но я чувствую, что мы могли бы немного улучшить его для следующих поколений;)

maciek 09.04.2022 16:43

@maciek Хорошо, готово.

Kelly Bundy 09.04.2022 16:59

Вот мое решение с подходом к структуре данных Graph, которое будет более эффективным, чем ваше, имеющее кубическую временную сложность O (n3).

import timeit

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next if next else []
        self.visited = False
        self.mem = None
    def __repr__(self):
        return f'<{self.val} {self.mem}>'
        
def epsi_sol(links, len_):
    nodes = {}
    start_nodes = set(i[0] for i in links[0]) # {'a', 'b'}

    # constructiong the graph
    for i in links:
        for j in i:
            if j[0] not in nodes:
                nodes[j[0]] = Node(j[0])
            if j[1] not in nodes:
                nodes[j[1]] = Node(j[1])

            nodes[j[0]].next.append(nodes[j[1]])

    def find_chain_with_length(node, length, valid_length):
        if length +1 == valid_length:
            return 1

        # if already visited just return
        if node.visited:
            return 0 
        
        if node.mem is not None:
            return node.mem

        # if this is not leaf node
        # we will mark it visited
        node.visited = True
        temp_count = 0
        for each_neighbor in node.next:
            temp_count += find_chain_with_length(each_neighbor, length+1, valid_length)
        # after visiting mark it unvisited
        node.visited = False
        node.mem = temp_count
        return temp_count

    solution_count = 0
    for each_start_node in start_nodes:
        solution_count += find_chain_with_length(nodes[each_start_node],0, len_)
    return solution_count

from collections import defaultdict, Counter

def kelly_sol(links, len_):
    chains = defaultdict(lambda: 1)
    for position in links[:len_]:
        temp = Counter()
        for a, b in position:
            temp[b] += chains[a]
        chains = temp
    return sum(chains.values())

def mac_sol(links, len_):
    chains = links[0]
    
    # seach for all possible paths:
    # iterate over all positions
    for position in links[1:]:
        
        # temp array to help me grow the chain
        temp = []
            
        # over each chain in the current set of chains
        for chain in chains:

            # over each link in a given position
            for link in position:
                
                # check if the chain and link are chainable
                if chain[-1] == link[0]:
                    
                    # append new link to a pre-existing chain
                    temp.append(chain + tuple([link[1]]))
        
        # overwrite the current list of chains
        chains = temp
    return len(chains)

# tests
for n in range(100, 1000, 100):
    links = [[(f'1_{i}', f'1_{i+1}'), (f'1_{i}', f'2_{i+1}'), (f'2_{i}', f'1_{i+1}'), (f'2_{i}', f'2_{i+1}')] for i in range(n)]
    print('-'*50)
    print(f'kelly_sol({n}) => {timeit.timeit(lambda: kelly_sol(links, n+1), number=2)} seconds')
    print(f'epsi_sol({n}) => {timeit.timeit(lambda: epsi_sol(links, n+1), number=2)} seconds')
    if n <50:
        print(f'mac_sol({n}) => {timeit.timeit(lambda: mac_sol(links, n+1), number=2)} seconds')
    print('-'*50)
--------------------------------------------------
kelly_sol(100) => 0.0013752000000000209 seconds
epsi_sol(100) => 0.0022567999999996147 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(200) => 0.0026332999999993945 seconds
epsi_sol(200) => 0.004522500000000207 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(300) => 0.003924899999999454 seconds
epsi_sol(300) => 0.006861199999999457 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(400) => 0.005278099999999952 seconds
epsi_sol(400) => 0.012999699999999947 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(500) => 0.006728900000000593 seconds
epsi_sol(500) => 0.01406989999999908 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(600) => 0.00828249999999997 seconds
epsi_sol(600) => 0.015398799999999824 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(700) => 0.009703200000000578 seconds
epsi_sol(700) => 0.01597070000000045 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(800) => 0.009961999999999804 seconds
epsi_sol(800) => 0.0196051999999991 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(900) => 0.014800799999999725 seconds
epsi_sol(900) => 0.02183789999999952 seconds
--------------------------------------------------

Что-то кажется неправильным, потому что links = [[(1, 1), (1, 2), (2, 1), (2, 2)]] ваш результат пуст.

Kelly Bundy 09.04.2022 15:09

Ни у них, ни у вас не кубические, они экспоненциальные.

Kelly Bundy 09.04.2022 15:12

@KellyBundy, потому что кажется, что нет действительной цепочки из 4 длин от [[(1, 1), (1, 2), (2, 1), (2, 2)]]. Из кода ООП я увидел 3 цикла for, поэтому я сказал кубический, хотя я не полностью прочитал его код.

Epsi95 09.04.2022 15:15

Отсюда четыре действительных цепочки. Как вычислено кодом ОП: [(1, 1), (1, 2), (2, 1), (2, 2)].

Kelly Bundy 09.04.2022 15:17

Ну количество цепочек может расти в геометрической прогрессии, и они и вы их все явно перечисляете.

Kelly Bundy 09.04.2022 15:19

Возможно, более крупный случай понятнее: для links = [[(1, 1), (1, 2), (2, 1), (2, 2)]] * 3 существует 16 допустимых цепочек: [(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 2, 2), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 1), (2, 2, 2, 2)].

Kelly Bundy 09.04.2022 15:20

на самом деле я создал граф таким образом, что для 1 будет один узел типа Node(1)

Epsi95 09.04.2022 15:22

Я не знаю о вашем графике (не читал его), но ваш solution — это явный список всех цепочек, не так ли?

Kelly Bundy 09.04.2022 15:23

попробуй links = [[(f'1_{i}', f'1_{i+1}'), (f'1_{i}', f'2_{i+1}'), (f'2_{i}', f'1_{i+1}'), (f'2_{i}', f'2_{i+1}')] for i in range(1000)]

Epsi95 09.04.2022 15:26

Тогда вы получите [['1_0', '1_1', '1_2', '1_3'], ['1_0', '1_1', '1_2', '2_3'], ['1_0', '1_1', '2_2', '1_3'], ['1_0', '1_1', '2_2', '2_3'], ['1_0', '2_1', '1_2', '1_3'], ['1_0', '2_1', '1_2', '2_3'], ['1_0', '2_1', '2_2', '1_3'], ['1_0', '2_1', '2_2', '2_3'], ['2_0', '1_1', '1_2', '1_3'], ['2_0', '1_1', '1_2', '2_3'], ['2_0', '1_1', '2_2', '1_3'], ['2_0', '1_1', '2_2', '2_3'], ['2_0', '2_1', '1_2', '1_3'], ['2_0', '2_1', '1_2', '2_3'], ['2_0', '2_1', '2_2', '1_3'], ['2_0', '2_1', '2_2', '2_3']]

Epsi95 09.04.2022 15:26

нет, это не явный список цепочки. Это просто графическое представление link, после чего вы просто проходите по графу и вычисляете действительные ссылки. Ненужные комбинации исключаются в первую очередь.

Epsi95 09.04.2022 15:27

Не уверен, что вы имеете в виду. Он выглядит как обычный list, а print(type(solution)) показывает, что это действительно так. А print(type(solution[0])) показывает, что этот внутренний список тоже обычный list.

Kelly Bundy 09.04.2022 15:45

Большое спасибо за ваши усилия @Epsi95, но ответ Келли намного быстрее, и, поскольку этот вопрос был об оптимизации, я приму ее ответ :)

maciek 09.04.2022 18:14

@KellyBundy извините, я не понимаю вашего аргумента, надеюсь, вы сможете понять график и то, как я правильно перемещаюсь.

Epsi95 10.04.2022 00:35

@maciek конечно, я изменил свой код, чтобы сохранить только подсчет, а не все возможные результаты. Я сделал один тайминг, мой в два раза медленнее, чем у Келли, возможно, из-за накладных расходов на создание и рекурсию объекта узла, но я должен согласиться, что у Келли отличное решение.

Epsi95 10.04.2022 00:37

@Epsi95 Да, я только что понял, что твой len_ не означает n. Какой смысл в этом параметре? Разве это не должно быть длиной lists?

Kelly Bundy 10.04.2022 00:50

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

Epsi95 10.04.2022 00:51

Упс, по-видимому, на самом деле это длина плюс 1. Это довольно запутанно и неудобно. И для links = [[(1, 1), (1, 2), (2, 1), (2, 2)]] * 2 вы вычисляете 12 вместо 8, а для links = [[(1, 1), (1, 2), (2, 1), (2, 2)]] * 3 вы вычисляете 0 вместо 16.

Kelly Bundy 10.04.2022 00:54

Я уже говорил вам, если у вас одинаковые значения, узел будет таким же. В вашем решении, когда вы перебираете список и делаете temp[b] += chains[a], вы по своей сути раздваиваетесь 1 and 1, а я нет. Используйте эту f-строку, о которой я упоминал ранее. А неразбериха и неудобства — это вопрос другого ракурса 😏

Epsi95 10.04.2022 00:57

Ах, так вы думаете, что значения не должны повторяться в более поздних позициях? Пример ОП делает это с 'a' и 'b', поэтому я думаю, что мы не должны игнорировать эту возможность.

Kelly Bundy 10.04.2022 01:00

Конечно, они могут, вы можете запустить пример ops, но да, если вы используете тот же узел в середине, мой код не будет работать. ibb.co/jMxWd2d

Epsi95 10.04.2022 01:06

С этим можно легко справиться, если я просто добавлю уникальный идентификатор при создании узлов, таких как nodes[j[0]] = Node(f'j[0]_{index_in_link}')

Epsi95 10.04.2022 01:13

Хм, я только что заметил вескую причину, по которой мой тест всего в два раза быстрее вашего в ваших тестах (я ожидал, что ваши накладные расходы будут больше): я думал, что Counter в наши дни примерно так же быстр, как defaultdict, но, по-видимому, это не так. 't, по крайней мере, не для такого небольшого количества ключей/операций. Если я заменю свой Counter() на defaultdict(int), мое решение станет примерно в четыре раза быстрее вашего в ваших тестах. Я обычно предпочитаю счетчик для подсчета, но если он может иметь такое большое влияние, я должен пересмотреть...

Kelly Bundy 10.04.2022 01:45

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

Похожие вопросы