동적 프로그래밍을 사용하는 목록의 파티션

Question

나는 여기서 일하기 위해 노력해 왔던 프로젝트와 관련하여 약간의 글을 올렸으며 계속해서 디자인 문제에 시달리고 처음부터 디자인해야합니다. 그래서 내가하려는 일을 게시 할 수 있는지, 누군가 내가 원하는 결과를 얻을 수있는 방법을 이해하도록 도와 줄 수 있는지 궁금합니다.

배경 :

내가 프로그래밍에 새로운 배우려고 노력 해요. 그래서 나는 기본적으로 목록을 가져 와서 목록에서 숫자 만 사용하여 각 번호를 분해하는 프로젝트에 관심이 많았다. 나는이 일을 쉽게 무력화 할 수 있었지만 Hbase, Hadoop 및 병렬 처리법을 배우기를 원했기 때문에 다양한 기계에서 프로세스를 깨뜨릴 수있는 방식으로 작업을 원했습니다. 나는 이것을하기위한 방법이 역동적 인 프로그래밍과 재귀를 사용하여 더 세분화 될 수있는 가능성의 테이블을 만드는 것이라고 생각했다.

예 :

나는 목록을 제출하는 경우 : [1,2, 4]를 내가 {1: [[1]], 2: [[1, 1]], 4: [[2, 2]]}을 얻어야한다. 기본적으로 말하는 것은 2 + 2 = 4, 1 + 1 = 2 및 1 = 1..so가 4를 만드는 모든 방법을보고자한다면이 목록 (데이터베이스에 있음)을 조회 할 수 있고 2 + 2 = 4를 본 다음 2. 2. 등을 세분화합니다. 조회 작업이 있지만 문제가있는 분석이 있습니다. 무차별 대입 (brute force)을 사용하면 hadoop이나 다른 도구를 사용하여 확장 할 수있는 방식으로 많은 수 (예 : 백만 개, 목록의 수는 1,000 개)를 사용할 수 없습니다. 여기에 가능한 결과를 좀 더 예는 다음과 같습니다

[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]]} 

이 접근 방식의 논리는 내가 백만 숫자 목록을 보내 그래서 만약 그것이 목록에서 다음 가능한 데이터를 COMPUT 시간이 걸리지 않을 것입니다 그것은 수 그것을 빠르게하고 심지어 hadoop 클러스터로 확장 할 수 있습니다.

이 코드가 작동하도록 만든 코드는 here이지만이 문제는 디자인 문제를 해결하는 방법에 관한 것입니다. 나는 이것이 파티션 문제이고 주위를 둘러 보았고 내가하려고했던 것의 훨씬 단순한 버전을 발견했다. (정확하게는 내가 뭘하려고하는지 정확히 알지 못한다. 숫자를 분해하고 특정 것을 사용하지 않기 때문이다. 그것을하기위한 데이터 세트.

질문 :

그래서 다행스럽게도 필자는 분명 내가 뭘하려고 오전 설명했다. 동적 프로그래밍을 사용하여 파이썬에서 목록의 파티션 테이블을 작성하여 배율을 조정할 수 있도록 읽기/공부/학습해야하는 것은 무엇입니까? 그저 취미이고 시간에 민감하지는 않지만 3 달 넘게이 작업을하고 있으며 처음부터 시작해야하는 디자인 문제가 발생할 때마다 느낀다. 이 방법을 올바로 구현하려면 어떻게해야합니까? 내가 봤 거든 배낭 문제 및 파티션 문제에 대한 해결책을 찾았지만 그들은 학교 일을 더 많은 것 같아요 대규모 데이터 세트로 확장 할 수 있도록 만들어지지 않았습니다.

누군가가 내게 통찰력을 줄 수 있기를 바랍니다. 그러나 관계없이이 책을 읽어 주셔서 감사합니다.

Answer 1

독립적이거나 분산 된 계산에서는 DP 문제 자체가 최적이 아니라는 점에 유의해야합니다.

DP 알고리즘의 고전적 형태를 고려할 때 매트릭스/테이블/어레이가 있고 특정 순서로 새 값을 연속적으로 계산합니다. 값을 계산할 때마다 이전에 만들어야하는 다른 값이 필요합니다. 따라서 데이터 독립성을 잃고 특정 DP 알고리즘에 따라 동시에 특정 수의 배열 필드를 최대로 계산할 수 있습니다.예를 들어 많은 DP 알고리즘은 각 필드가 이전 열의 필드를 사용하므로 전체 테이블 열을 병렬로 처리 할 수 ​​있습니다. 그러나 그것은 그 컬럼 이후의 모든 나머지 필드의 데이터 종속성으로 인해 이미 한계가 있습니다.

즉, 목록에서 사용할 수있는 다양한 숫자의 합계를 계산하는 것은 DP 문제가 아닙니다. 하위 문제는 전혀 해결하지 않지만 가능한 모든 합계를 수집합니다 (목록 항목 중 하나와 일치하는 경우).

• 계산 가능한 모든 합산으로 새로운 목록 :

  는 그러므로, 나는 다음과 같은 전망이 좋은 다른 접근 방식을 제안한다. 이것은 데이터에 독립적이며 병렬화 될 수 있지만 종료를 위해서는 약간의 상한이 필요합니다. 예 : [1,2,4]은 [ [1],[2],[4],[1,1],[1,2],[1,4],...]이됩니다. 이 목록을 명시 적으로 작성할 필요는 없지만 각 조합을 다음 단계로 전달하십시오.

• 각 계산을 평가합니다. 즉, 합계를 만들고 원래 목록의 값과 일치하는지 확인합니다. 다시 말하지만, 당신은 데이터에 독립적이어서 이러한 모든 계산을 독립적으로 수행 할 수 있습니다.
• 긍정적 인 결과를 최종 데이터 구조에 결합하십시오.

그래서 그것을 요약하여 질문에 대답합니다 :

• 다시 생각을, 당신은 전혀 DP로이 문제를 생각할지 여부를 선택합니다.
• 데이터 병렬 처리에 대해 읽어 볼 수 있습니다. 이는 GPU로 이러한 문제를 해결할 때 특히 중요하므로 CUDA/OpenCL 관련 문서가 유용 할 수 있습니다.