균형 분포 알고리즘

StackOverflow https://stackoverflow.com/questions/139580

문제

느슨하게 결합 된 클러스터를위한 코드를 작업하고 있습니다. 작업 중 최적의 성능을 달성하기 위해 어린이가 들어가거나 종료 할 때마다 클러스터가 데이터를 재구성해야합니다. 이것은 결국 선택 사항으로 만들어 지지만 현재는 기본적으로 데이터 밸런싱을 수행합니다. 내 밸런싱은 기본적으로 각 어린이가 컴퓨터 당 평균 파일 수 이상을 가지고 있고 하나 이상을 가지고 있지 않도록하는 것입니다. 부서가 깨끗하지 않으면 나머지는 더하기입니다. 그리고 나머지는 할 것입니다 언제나 아동의 수보다 적다 [0 사례를 제외하고는 제외 할 수 있지만] 균형을 잡은 어린이는 최대 AVG + 1을 가질 것입니다.

알고리즘이 O (n!)라는 것을 깨달을 때까지 모든 것이 잘 보입니다. 아이들의 목록을 내려 가서 너무 많고 너무 적은 사람을 찾아보십시오. 너무 많은 목록에있는 각 어린이에 대해 목록을 방문하여 너무 적은 어린이에게 보내십시오.

이것에 대한 더 나은 해결책이 있습니까? 나는 있어야한다고 생각합니다.

편집 : 여기에 내가 어떻게 파생 된 O (n!)를 보여주는 psuedocode가 있습니다.

foreach ( child in children ) {
    if ( child.dataLoad > avg + 1 ) {
        foreach ( child2 in children ) {
            if ( child != child2 && child2.dataLoad < avg ) {
                sendLoad(child, child2)
            }
        }
    }
}

편집 : o (n^2). foreach n, n => n*n => n^2. 오늘 아침 커피가 충분하지 않은 것 같아요! ;)

앞으로 나는보다 유연하고 탄력적 인 분포 방법 [가중 및 hueristics]으로 이동하고 싶지만 현재는 데이터의 균일 한 분포가 작동합니다.

도움이 되었습니까?

해결책

@ZVRBA : 목록을 정렬 할 필요조차 없습니다. 목록을 가로 지르면 두 번째로 평균 워크로드가 적은 모든 항목을 목록 끝으로 이동합니다 (첫 번째 트래버스에서 마지막 항목에 대한 포인터를 유지할 수 있음). 주문은 완벽 할 필요가 없으며 반복자가 마지막 단계에서 증강 또는 감소해야 할 때만 변경됩니다.

이전 답변을 참조하십시오

마지막 단계는 다음과 같습니다.

두 번째 단계에서는 child2에서 평균 작업량보다 낮은 첫 번째 항목에 대한 포인터를 유지하십시오 (이중 링크 목록을 가질 필요가 없음).

for each child in list {
  if child2 == nil then assert("Error in logic");
  while child.workload > avg + 1 {
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1)))
    if child2.workload == avg + 1 then child2 = child2.next;
  }
}

다른 팁

귀하의 분석이 잘못되었다고 생각합니다.

  • 평균을 찾기 위해 목록을 걸어가 O (n)
  • 데이터 청크가 너무 많거나 적은 어린이 목록을 만드는 것도 O (N)
  • 이동 데이터는 데이터 양에 비례합니다

O (n!)에 어떻게 도착 했습니까?

어린이 수에 목록을 정렬 할 수있어서 전면에는 너무 많은 일을하는 어린이가 있고 결국에는 일이 거의없는 어린이가 있도록 할 수 있습니다. 그런 다음 양쪽 끝에서 목록을 동시에 통과하십시오. 한 반복자는 과잉 데이터가있는 어린이를 가리 킵니다. 다른 반복은 데이터가 부족한 어린이에게 가리 킵니다. 데이터를 전송하고 하나의 반복자를 앞으로 또는 다른 반복자를 뒤로 이동하십시오.

일관된 해싱과 같은 완전히 다른 접근법을 시도 할 수 있습니다.

주제에 대한 비교적 쉬운 소개는 여기를 참조하십시오.http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(Karger et al에서 시작하여 더 깊은 서류가 있습니다)

Erlang에서 일관된 해싱의 작업 구현을 만들어 원하는 경우 검사 할 수 있습니다.

http://distributerl.googlecode.com/svn/trunk/chash.erl

게시 한 코드는 복잡성 O (N^2)입니다. 그럼에도 불구하고 Malach가 관찰 한대로 선형 시간에 할 수 있습니다. 여기서 N은 어린이 목록의 항목 수입니다.

고려 : 내부 루프에는 반복이 있으며 실행됩니다. 많으면 n 시간. n*n = n^2.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top