Я пытаюсь найти все циклы в моих данных, используя функцию networkx.simple_cycles () в python.Как написано в документации по networkx " Это нерекурсивная версия итератора / генератора алгоритма Джонсона ".Алгоритм Джонсона имеет временную сложность: ((узлы + ребра) * (циклы + 1)) и пространственную сложность: (узлы + ребра) .
Я создал ориентированный граф из данных транзакции с ребрами как От узла ---> К узлу .Я удаляю узлы, которые имеют степень 0 или степень 0, поскольку они не будут участвовать в циклах (элементарных цепях).Детали моего графика после удаления узлов в 0 и в градусах следующие:
Для 1,09 миллионов записей:
Number of nodes remaining-39278;
Number of edges-26324;
Number of cycles- Not able to get any output as the code keeps on running.
Для 1,08 миллионов записей:
Number of nodes remaining-38664;
Number of edges-25710;
Number of cycles- 5612438.
Для 1,05 миллиона записей:
Number of nodes remaining-36737;
Number of edges-23784;
Number of cycles- 69671.
Для 1,01 миллиона записей:
Number of nodes remaining-34393;
Number of edges-21566;
Number of cycles- 3079.
Для 1 миллиона записей:
Number of nodes remaining-33841;
Number of edges-21125;
Number of cycles- 3072.
Я хочу понятьвзаимосвязь сложности времени и пространства с конфигурацией системы.Учитывая все эти детали об алгоритме, как я могу узнать, какая конфигурация системы будет подходить для определенного размера данных.Почему я не могу запустить этот алгоритм за пределами 1,08 миллионов данных?
Конфигурация моей системы: AMD PRO A12-8800B (2,1 ГГц, до 3,4 ГГц, 2 МБ кэш-памяти, 4 ядра) с AMD Radeon R7 Graphics.8 ГБ ОЗУ.