алгоритм для поиска независимых наборов

Question

Люди, У меня проблема. Я пишу скрипт в python, который состоит из нескольких модулей. Некоторые из модулей зависят от других модулей, поэтому их следует запускать только после успешного запуска зависимых модулей. Таким образом, каждый модуль происходит от модуля базового класса и переопределяет список, называемый DEPENDENCIES, который представляет собой список зависимостей, которые должны выполняться, прежде чем этот модуль будет запущен. Существует один модуль, который нужно запускать перед всеми другими модулями. В настоящее время я делаю что-то вроде этого.

modules_to_run.append(a) 
modules_to_run.append(b) 
modules_to_run.append(c) 
..... 
.....  
modules_to_run.append(z) 


# Very simplistically just run the Analysis modules sequentially in 
# an order that respects their dependencies 
foundOne = True 
while foundOne and len(modules_to_run) > 0: 
    foundOne = False 
    for module in modules_to_run: 
     if len(module.DEPENDENCIES) == 0: 
      foundOne = True 
      print_log("Executing module %s..." % module.__name__, log) 
      try: 
       module().execute() 
       modules_to_run.remove(module) 
       for module2 in modules_to_run: 
        try: 
         module2.DEPENDENCIES.remove(module) 
        except: 
         #module may not be in module2's DEPENDENCIES 
         pass 
      except Exception as e: 
       print_log("ERROR: %s did not run to completion" % module.__name__, log) 
       modules_to_run.remove(module) 
       print_log(e, log) 

for module in modules_to_run: 
    name = module.__name__ 
    print_log("ERROR: %s has unmet dependencies and could not be run:" % name, log) 
    print_log(module.DEPENDENCIES, log) 

Теперь я вижу, что некоторые модули занимают много времени, и выполнение сценария слишком велико. Поэтому я хотел сделать его многопоточным, чтобы независимые модули могли запускаться одновременно, тем самым экономя время. Поэтому я хочу решение, где после каждой итерации я буду пересчитывать «n» независимые модули (где «n» - максимальное количество потоков, обычно 2 для начала) и выполнять их параллельно и ждать их завершения до следующей итерации , Я не знаю много об алгоритмах, поэтому я застрял. Можете ли вы, пожалуйста, помочь мне найти алгоритм, который найдет max 'n' множество независимых модулей после каждой итерации, которые никак не зависят друг от друга.

Answer 1

Недавно я опубликовал описание topological sortingin a question about make -j. Serendipity! Из статьи Википедии:

Каноническое применение топологической сортировки (топологический порядок) заключается в планировании последовательности заданий или задач; алгоритмы топологической сортировки были впервые изучены в начале 1960-х годов в контексте метода PERT для планирования в управлении проектами (Jarnagin 1960). Работы представлены вершинами, и есть край от x до y, если задание x должно быть завершено до начала работы y (например, при стирке одежды стиральная машина должна закончить, прежде чем мы высушим одежду). Затем топологическая сортировка дает порядок выполнения заданий.

Грубые наброски:

1. Построить график зависимости.
2. Найти n модули, не имеющие зависимости. Они могут выполняться параллельно.
3. Удалите эти модули с графика.
4. Повторите шаг 2 до завершения.

Прочтите эти ссылки для более подробного описания.

Answer 2

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

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

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

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

Две ловушки, чтобы быть в курсе:

Если зависимости содержат циклы (А зависит от В зависимости от C в зависимости от A) она может цикл навсегда (это означает, что проблема не имеет решения). Вы должны обнаружить этот случай, отчет и ошибку.

Модули, которые вы можете запустить, могут быть меньше количества потоков. Это не должно быть ошибкой. Затем вы нашли решение либо при наличии n доступных модулей для запуска, либо при запросе каждого модуля, если они могут быть запущены.