разделение списка с использованием динамического программирования

Question

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

BackGround:

Я новичок в программировании и пытаюсь учиться.Таким образом, я взял проект, который меня заинтересовал, который включает в себя взятие списка и разбивку каждого числа, используя только числа из списка.Я знаю, что мог легко перебить это (что я и сделал), но я хотел также изучить Hbase, Hadoop и параллельную обработку, поэтому я хотел сделать это так, чтобы я мог разбить процесс на разных машинах.Я думал, что способ сделать это - использовать динамическое программирование и рекурсии для создания таблицы возможностей, которые можно разбить еще дальше.

Пример:

Если я отправлюсписок: [1,2, 4] Я должен получить {1: [[1]], 2: [[1, 1]], 4: [[2, 2]]}.По сути, это 2 + 2 = 4, 1 + 1 = 2 и 1 = 1. Поэтому, пытаясь увидеть все способы получения 4, я могу просто посмотреть этот список (который будет в базе данных) исм. 2 + 2 = 4, затем сломать 2. и т. д. У меня работает поисковая работа, но с неисправностью у меня проблемы.Использование грубой силы не позволит мне использовать большие числа (скажем, миллион, с тысячами чисел в списке) таким образом, чтобы я мог использовать hadoop или какой-либо другой инструмент для его масштабирования.Вот еще несколько примеров возможных результатов:

[1,2, 3, 4] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]]}
[1,2, 3, 4, 6, 10] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]], 6: [[2, 4], [3, 3]], 10: [[4, 6], [2, 2, 2, 2, 2]]}
[10, 30, 50] = 50: [[10, 10, 30]], 30: [[10, 10, 10]]}

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

Код, который я создал, чтобы заставить это работать, - здесь , но этот вопрос был о том, как исправить проблему проектирования.Я получил совет, что это проблема с разделом, огляделся и нашел гораздо более простые версии того, что я пытался сделать ( activestate ), но это не совсем то, что я пытаюсь сделать, потому что это разбивает числои не использует определенный набор данных для этого.

Вопрос:

Так что, надеюсь, я четко описал, что я пытаюсь сделать.Что мне нужно читать / изучать / изучать, чтобы создать таблицу раздела списка в python с использованием динамического программирования, чтобы он мог масштабироваться?Это просто хобби и не чувствительно ко времени, но я чувствую, что работаю над этим более 3 месяцев, и каждый раз я сталкиваюсь с проблемами дизайна, которые заставляют меня начинать с нуля.Как я могу построить это правильно (чтобы увидеть мой неправильный путь, смотрите мою ссылку выше)?Я нашел и нашел решения проблем с рюкзаком и разделами, но они, кажется, больше подходят для школьной работы и не предназначены для масштабирования с большими наборами данных.

Надеюсь, кто-нибудь может дать мне понимание, но, тем не менее, спасибо, что прочитали это.

Answer 1

Вы должны знать, что задачи DP сами по себе не являются оптимальными для независимых и распределенных вычислений.

Когда вы рассматриваете классические формы алгоритмов DP, у вас есть матрица / таблица / массив и вы последовательновычислить новые значения в определенном порядке.Каждое вычисление значения требует других значений, которые должны быть созданы ранее.Следовательно, вы теряете независимость данных и можете максимально рассчитать определенное количество полей массива одновременно, в зависимости от конкретных алгоритмов DP.Например, многие алгоритмы DP могут обрабатывать весь столбец таблицы параллельно, поскольку каждое поле опирается на поля из предыдущего столбца.Но это уже предел из-за зависимости данных всех оставшихся полей после этого столбца.

При этом вычисление суммирующих возможностей различных чисел, доступных в вашем списке, НЕ является проблемой DP.Вы вообще не решаете никаких подзадач, а просто собираете все возможные суммы (если они совпадают с одной из записей вашего списка).

Следовательно, я предлагаю следующий явно иной подход:

• Вычислить новый список со всеми возможными суммами.Это не зависит от данных и может быть распараллелено, но вам нужна некоторая верхняя граница для завершения.Пример: [1,2,4] становится [ [1],[2],[4],[1,1],[1,2],[1,4],...].Вам не нужно явно составлять этот список, а просто передавать каждую такую ​​комбинацию на следующий шаг.
• Оценить каждое вычисление, т.е. создать сумму и проверить, соответствует ли она значению из вашего исходного списка.Опять же, вы независимы от данных и можете выполнять все эти вычисления независимо.
• Объедините положительные результаты в итоговую структуру данных.

Итак, чтобы подвести итог и ответить на ваши вопросы:

• Подумайте, хотите ли вы вообще рассматривать эту проблему как DP.
• Возможно, вы захотите прочитать о параллелизме данных.Это особенно актуально при решении таких проблем с графическими процессорами, поэтому может пригодиться и соответствующая литература по CUDA / OpenCL.