[동적 기획] m개의 정수를 포함하는 수조를 n개의 수조로 나누고 각 수조의 합은 가능한 한 가깝다

1 배경
ClickHouse 클러스터 용량 축소는 데이터가 손실되지 않도록 용량이 필요한 노드의 데이터를 다른 노드로 마이그레이션하여 각 기계로 마이그레이션되는 데이터의 양을 최대한 균형 있게 할 계획입니다.데이터의 이동은partition 단위로 모든 partition의 데이터 양을 알고 있습니다.
추상
m개의 정수를 포함하는 수조를 n개의 수조로 나누어 각각 수조와 최대한 가깝게 하다
3 사고방식
이 문제는 전형적인 동적 기획의 문제로 이론적으로 가장 좋은 문제를 찾을 수 없지만 이번에는 실제 생산에서의 문제를 해결하기 위한 것이지 AC를 원하지 않는다. 그래서 우리는 상대적으로 합리적인 알고리즘을 찾아서 파티션의 분배가 상대적으로 균형이 잡히면 된다.
입력:int 배열, 그룹 수 divisionNum

대수조 역순 정렬

계산수조의 평균치 avg

수조를 두루 훑어보다.

만약에 첫 번째 수가 avg보다 크면 이 수를 단독으로 한 조로 한다. 왜냐하면 다음 수를 더해도 avg에 더 가깝게 구할 수 없기 때문이다.그리고 남은 수를 다시 평균을 구하는 것은 남은 수를 더욱 평균적으로 분배해야 한다는 것을 의미한다. 그러면 극치의 영향을 피하고 다음 계산을 다시 시작할 수 있다

만약에 첫 번째 수num이 avg보다 작다면 우리는 이 수를 수조에 넣고 (또는 약간) 개수를 찾아서델타=avg-num에 더 가깝게 해야 한다.

수조를 계속 훑어보고 어떤 수 k=delta를 발견하면 k를 수조에 넣고 이번 라운드 찾기를 끝냅니다

a > delta > b가 발견되면이때 계속 판단해야 한다. 만약에 (delta-b)>(a-delta) b를 수조에 넣고 delta=delta-b를 계속 훑어본다.(delta-b) <(a-delta), distance = delta-b를 저장한 다음 a를 배열에 넣고 계속 아래로 옮겨다니며

우리는 밤을 하나 들었다.
수조는 500,18,28,2,27,35,22,10,6,5,3,2,1이다.4조로 나누다
순서: 500, 35, 28, 27, 22, 18, 10, 6, 5, 3, 2, 2, 1
평균 avg = 164.75 계산
배열 반복:

제1라운드: 500>avg, 500을 추출하여 단독으로 한 조로 한다.나머지 수조는 35,28,27,22,18,10,6,5,3,2,1

계산 avg = 53

2라운드:35 delta=53-35=18;

이어서 28>18, 계속 반복, 27>18, 22>18, 18=18, 그래서 18을 꺼내 2조에 가입하고 2라운드를 끝냅니다. 나머지 수조는 28, 27, 22, 10, 6, 5, 3, 2, 1

입니다.

3라운드:28 delta=53-28=25

27>델타>22,27-delta=2,델타-22=3,distance=2,22를 임시수조,델타=3;

18 >3, ... ,5 > 3, 3==3,distance = delta-3 = 0;그래서 22와 3을 3조에 넣고 3라운드를 끝냈다. 수조는 27, 10, 6, 5, 2, 1

에 속했다.

4라운드: 남은 수를 한 조로 직접 되돌려 4조로 가입

결과:
arr 0 is : 500, sum = 500
arr 1 is : 35 18, sum = 53
arr 2 is : 28 22 3, sum = 53
arr 3 is : 27 10 6 5 2 2 1, sum = 53
실현

import math

#      n   ，          
def GetAvgArr(number_list, arr_num):
    avg_arrays = []
    if len(number_list) == 0 or len(number_list) < arr_num:
        return avg_arrays
    

    # 1.      
    sum_value = 0
    mean_value = 0
    number_list_float = []
    for num in number_list: 
        number_list_float.append(float(num))
        sum_value += float(num)
    
    mean_value = sum_value / float(arr_num)

    # 2.     
    number_list_float.sort(reverse=True)
    
    for cnt in range(0, arr_num):
#         print("mean = ", mean_value)
        arr = []
        if cnt == arr_num-1: 
            #     ，         
            avg_arrays.append(transFloatToIntList(number_list_float))
            break
        
        #        max >= mean，        
        if len(number_list_float) > 0 and number_list_float[0] >= mean_value: 
            arr = [number_list_float[0]]
            avg_arrays.append(transFloatToIntList(arr))
            sum_value = sum_value - number_list_float[0]

            #       partition    
            mean_value = sum_value / float(arr_num-len(avg_arrays))
        else: 
            #         
            arr, _ = getList(number_list_float, mean_value, math.pow(mean_value, 2))
            avg_arrays.append(transFloatToIntList(arr))
        
        #                  ，         
        number_list_float = removeFromFloatList(number_list_float, arr)

    return avg_arrays


#  []float  []int
def transFloatToIntList(float_list):
    res = []
    for item in float_list:
        res.append(int(item))
    
    return res


#    remove_nums          originalList    
def removeFromFloatList(original_list, remove_nums):
    res = []
    start = 0
    for remove in remove_nums:
        for i in range(start, len(original_list)):
            if original_list[i] == remove:
                res.extend(original_list[start:i])
                start = i + 1
                break
    
    res.extend(original_list[start:])
    return res


def getList(arr, delta, distance):
    res = []
    if len(arr) == 0:
        return res, -1
    

    for i in range(0, len(arr)-1):
        if delta == arr[i]:
            res.append(arr[i])
            return res, 0
        elif delta < arr[i]:
            continue
        elif delta > arr[i]:
            if i == 0:
                res.append(arr[i])
                delta = delta - arr[i]
                distance = math.pow(delta, 2)
                tmp, d = getList(arr[i+1:], delta, distance)
                res.extend(tmp)
                return res, d
            else:
                dis1 = math.pow(arr[i-1]-delta, 2)
                dis2 = math.pow(delta-arr[i], 2)
                if dis1 > dis2:
                    res.append(arr[i])
                    delta = delta - arr[i]
                    tmp, d = getList(arr[i+1:], delta, dis2)
                    res.extend(tmp)
                    return res, d
                else:
                    tmp, d = getList(arr[i:], delta, dis2)
                    if dis1 > d:
                        res.extend(tmp)
                        return res, d
                    

                    res.append(arr[i-1])
                    return res, dis1
       
    dis = math.pow(delta-arr[len(arr)-1], 2)

    if dis < distance:
        return arr[len(arr)-1:], dis
    
    return [], -1

테스트

def main():
    partition_list = [500, 18, 28, 2, 27, 35, 22, 10, 6, 5, 3, 2, 1]
    print("test partitionList is : {}".format(partition_list))
    print("result is :")
    arrays = GetAvgArr(partition_list, 4)
    for i, arr in enumerate(arrays):
        print("arr {} is : {}, ".format(i, arr))
        sum_value = 0
        for value in arr:
            sum_value += value
        
        print("sum = {}".format(sum_value))