Существует ли более быстрый / оптимизированный способ поиска уникальных комбинаций из набора / списка уникальных элементов в python - PullRequest
0 голосов
/ 10 апреля 2020

Я пытаюсь найти все возможные уникальные комбинации из n элементов, взятых за раз. Я использовал itertools.combination для того же самого, и у меня есть п = 85 . Поэтому, когда я нахожу комбинации для m = 5 , количество создаваемых комбинаций составляет около 3 кр, и это занимает много времени, поскольку на данный момент элементы представляют собой список строк, или точнее, это столбцы в алфавитном порядке, , а не числовые индексы . В настоящее время я работаю с pandas и itertools.combinsk, хотел бы знать, может ли процесс поиска комбинаций быть распараллеленным , чтобы каждый раз при дальнейших вычислениях давать одинаковые результаты далее по столбцам, или, может ли оптимизировать это графические данные GPU, например cuDF , хотя это не похоже на это. Кроме того, может ли преобразование имен столбцов в числа, а затем преобразование их в numpy массив для работы, пока поиск комбинаций работает быстрее? Пожалуйста, также предложите решения, где это можно было бы сделать быстрее на каком-то другом языке программирования. Не очень хороший программист. Хотелось бы увидеть некоторые математические и программные c решения с анализом сложности.

1 Ответ

0 голосов
/ 15 апреля 2020

Это именно проблема анализа сложности, и нет способа распараллелить ее так, чтобы это было удовлетворительно. С n=85 и m=5 существует 85^5 = 4437053125 возможных комбинаций, включая реверсирование и дубликаты.

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

Искусственный интеллект - это изучение методов поиска полезных решений внутри проблемных пространств, которые слишком велики для полного изучения. * Или жадный поиск может быстро дать вам хорошее решение, если предположить, что есть какой-то показатель c, который вы пытаетесь оптимизировать из общего числа комбинаций 85^5.

...