조합 알고리즘 병렬화

Question

저는 C (n, k) 조합을 계산하고 n과 k 사이에 큰 차이가있는 프로그램을 작성하고 있습니다 (예 : n = 39, k = 13 -> 8122425444 조합). 또한 모든 조합을 실시간으로 계산할 필요가 있습니다. 문제는 내 알고리즘을 여러 스레드로 나눠서 더 빠르게 만들 수 있다는 것입니다.

public void getCombinations(List<Item> items) { 
    int n = items.size(); 
    int k = 13; 
    int[] res = new int[k]; 
    for (int i = 1; i <= k; i++) { 
     res[i - 1] = i; 
    } 
    int p = k; 
    while (p >= 1) { 
     //here I make a Set from items in List by ids in res[] 
     Set<Item> cards = convert(res, items); 
     //some calculations 
     if (res[k - 1] == n) { 
      p--; 
     } else { 
      p = k; 
     } 
     if (p >= 1) { 
      for (int i = k; i >= p; i--) { 
       res[i - 1] = res[p - 1] + i - p + 1; 
      } 
     } 
    } 
} 

private Set<Item> convert(int[] res, List<Item> items) { 
    Set<Item> set = new TreeSet<Item>(); 
    for (int i : res) { 
     set.add(items.get(i - 1)); 
    } 
    return set; 
} 

Answer 1

JDK 7을 사용하는 경우 fork/join을 사용하여이 알고리즘을 나누고 정복 할 수 있습니다.

단순하게 유지하려면 모든 스레드가 완료 될 때까지 입력의 하위 집합을 계산하고 CountDownLatch를 사용하는 스레드를 얻는 것이 좋습니다. 스레드 수는 CPU에 따라 다릅니다.

입력이 증가하여 여러 컴퓨터에서 계산할 수 있다고 생각되는 경우 Hadoop의 map/reduce를 사용할 수도 있습니다. 지도/축소 작업으로 정규화해야하지만 예제를 살펴보십시오.

Answer 2

조합을 분할하는 가장 간단한 방법은 조합을 조합하는 것입니다. ;)

가능한 "첫 번째"값마다 스레드 풀에서 새 작업을 만들 수 있습니다. 또는 새로운 작업으로 "첫 번째"와 "두 번째"의 가능한 쌍을 각각 만들 수 있습니다. 또는 3 개 등등. 당신은 당신이 cpus를 가지고있는만큼 많은 작업을 생성해야하기 때문에 보드를 넘을 필요가 없습니다.

39 개의 항목 중에서 13 개의 가능한 모든 항목을 만들고 싶습니다.

for(Item item: items) { 
    List<Item> items2 = new ArrayList<Item>(items); 
    items2.remove(item); 
    // create a task which considers all selections of 12 from 38 (plus item) 
    createCombinationsOf(item, item2, 12); 
} 

이렇게하면 39cpus와 거의 비슷한 작업을 할 수 있습니다. 당신이 더 많은 쌍 (39 * 38/2) 쌍을 만들고 싶다면.

Answer 3

귀하의 질문은 매우 모호합니다.

당신은 지금 어떤 문제가 있습니까? 알고리즘을 분할하고 정복하여 (스레딩, 조인 등) 구현하거나 문제를 하위 파트로 분할하는 방법을 파악합니다.

나중에 첫 단계를 수행해야합니다. 원래 문제를 몇 가지 작은 문제 (Executor 스레드 또는 처리 할 유사한 메커니즘으로 발송할 수 있음)로 나누는 방법과 결과에 참여하는 방법을 알고 있습니까?

Answer 4

저는이 크기의 조합 세트와 함께 작동하는 일부 코드 작업을하고 있습니다. 합리적인 시간 내에 출력물을 얻으려면 몇 가지 제안을하십시오.

• 조합 목록을 작성한 다음 처리하는 대신 조합에 대해 순위를 지정하도록 프로그램을 작성하십시오. n = 66까지의 모든 k 값에 대해 서명 된 64 비트 long 값을 각 조합에 안전하게 할당 할 수 있습니다. 그러면 숫자 시스템을 쉽게 분리하여 다른 스레드/하드웨어에 할당 할 수 있습니다. 귀하의 계산은 간단 경우
• , 당신은 일을하기 위해 OpenCL을 나 CUDA를 사용하여보고해야한다. 이 작업에는 몇 가지 옵션이 있습니다. Rootbeer 및 Aparapi 자바에 머무는와 GPU 정보의 라이브러리 돌봐셔서위한 옵션입니다. JavaCL은 C99에서 직접 커널을 작성하는 데 신경 쓰지 않는다면 OpenCL에 대한 좋은 바인딩입니다. AWS에는 이러한 유형의 작업을 수행하는 GPU 인스턴스가 있습니다.
• 각 조합에 대한 결과를 수집하기 위하여려고하는 경우에
, 당신은 정말 저장 공간을 고려해야 할 것입니다. C (39,13)의 예를 들어, 각 조합에 대해 길게 저장하려면 61 기가 미만이어야합니다. 이 크기의 데이터 세트를 다루기 위해서는 훌륭한 전략이 필요합니다.
• 전체 조합에 대해이 데이터를 간단한 결과로 롤업하려면 @algolicious의 제안에 따라 map/reduce를보고이 문제를 해결하십시오.
• 각 조합에 대한 답변이 필요하지만 약간의 오류는 정상인 경우 AI 알고리즘 또는 선형 해석기를 사용하여 데이터를 압축 할 수 있습니다. 이러한 기술은 결과 데이터에서 배울 점이있는 경우에만 작동합니다.
• 일부 오류는 작동하지 않지만 모든 대답이 필요한 경우 요소 순위에 따라 필요할 때마다 다시 계산하는 것이 좋습니다.