重み付け輪訓アルゴリズム--最大公約数法

階調を作るときに重み付け輪訓アルゴリズムを使う必要があるので、最も簡単な最大公約数法を選び、ここで記録をします(以下は原文を抜粋し、一部の文字を修正します)
基本的な方法:
このアルゴリズムの原理は、サーバ配列Sにおいて、まず、すべてのサーバ重みの最大値max(S)と、すべてのサーバ重みの最大公約数gcd(S)とを計算することである.
indexは、今回のリクエストが来たときに選択したサーバのインデックスを表し、初期値は-1である.current_Weightは現在のスケジューリングの重み値を表し、初期値はmax(S)である.
要求が来るとindex+1からサーバ配列Sのポーリングが開始され、その重みがcurrent_以上であることが判明するWeightの最初のサーバで、リクエストを処理します.結果シーケンスにインデックスを記録します.
サーバ配列をポーリングすると、配列の最後に達すると、最初から検索が再開され、current_が減少します.Weightの値:current_weight -= gcd(S).current_Weightが0に等しい場合はmax(S)にリセットします.
demoコード:

#include 
#include 
#include 
#include 

typedef struct
{
    int weight;
    char name[2];
}server;


int getsum(int *set, int size)
{
    int i = 0; 
    int res = 0;

    for (i = 0; i < size; i++)
        res += set[i];

    return res;
}

int gcd(int a, int b)
{
    int c;
    while(b)
    {
        c = b;
        b = a % b;
        a = c;
    }

    return a;
}

int getgcd(int *set, int size)
{
    int i = 0; 
    int res = set[0];

    for (i = 1; i < size; i++)
        res = gcd(res, set[i]);

    return res;
}

int getmax(int *set, int size)
{
    int i = 0; 
    int res = set[0];

    for (i = 1; i < size; i++)
    {
        if (res < set[i]) res = set[i];
    }

    return res;
}


int lb_wrr__getwrr(server *ss, int size, int gcd, int maxweight, int *i, int *cw) 
{
    while (1) 
    {
        *i = (*i + 1) % size;
        if (*i == 0) 
        {
            *cw = *cw - gcd;
            if (*cw <= 0) 
            {
                *cw = maxweight;
                if (*cw == 0) 
                {
                    return -1;
                }
            }
        }
        if (ss[*i].weight >= *cw) 
        {
            return *i;
        }
    }
}

void wrr(server *ss, int *weights, int size)
{
    int i = 0;

    int gcd = getgcd(weights, size);
    int max = getmax(weights, size);
    int sum = getsum(weights, size);
    

    int index = -1;
    int curweight = 0;

    for (i = 0; i < sum; i++) 
    {
        lb_wrr__getwrr(ss, size, gcd, max, &(index), &(curweight));
        printf("%s(%d) ", ss[index].name, ss[index].weight);
    }

    printf("
");
    return;
}

server *initServers(char **names, int *weights, int size)
{
    int i = 0;
    server *ss = calloc(size, sizeof(server));

    
    for (i = 0; i < size; i++)
    {
        ss[i].weight = weights[i];
        memcpy(ss[i].name, names[i], 2);
    }

    return ss;
}

int main()
{
    int i = 0;
    
    int weights[] = {1, 2, 4};
    char *names[] = {"a", "b", "c"};
    int size = sizeof(weights) / sizeof(int);


    server *ss = initServers(names, weights, size);

    printf("server is ");
    for (i = 0; i < size; i++)
    {
        printf("%s(%d) ", ss[i].name, ss[i].weight);
    }
    printf("
");

    printf("
wrr sequence is ");
    wrr(ss, weights, size);

    return;
}

上のコードでは、アルゴリズムのコア部分はwrrとlb_です.wrr__getwrr関数.wrr関数では、まず、すべてのサーバの重みの最大公約数gcd、重みの最大値max、および重みの和sumを計算します.
初期の場合、indexは-1、curweightは0で、lb_を順次呼び出します.wrr__getwrr関数は,今回選択したサーバインデックスindexを得る.
プロセスの説明:
アルゴリズムの核心思想はlb_に現れている.wrr__getwrr関数で.サーバ配列{a(1),b(2),c(4)}の場合、gcdは1、maxweightは4である.
この関数が1回目に呼び出されると、i(index)は−1、cw(current_weight)は0となり、ループに入ると、iはまず0となるため、cwはmaxweightとなる.iからサーバ配列ssのポーリングが開始され、最初の重みがcw以上のサーバはcであるため、iは2に設定され、その値が返される.
2回目にこの関数を呼び出すと,iは2,cwはmaxweightとなる.サイクルに入ると、iはまず0に設定されるので、cwはcw−gcd、すなわち3に設定される.iからサーバ配列ssのポーリングが開始され、最初の重みがcwに等しいサーバかcかより大きいため、iは2に設定され、その値が返される.
この関数を3回目に呼び出すと,iは2,cwは3となる.サイクルに入ると、iはまず0に設定されるので、cwはcw−gcd、すなわち2に設定される.iからサーバ配列ssのポーリングが開始され、最初の重みがcw以上のサーバはbであるため、iは1に設定され、その値が返される.
この関数を4回目に呼び出すと,iは1,cwは2となる.ループに入ると、iはまず2に設定され、iからサーバ配列ssがポーリングされ、最初の重みがcw以上のサーバはcであるため、iは2に設定され、その値が返される.
この関数を5回目に呼び出すと,iは2,cwは2となる.サイクルに入ると、iはまず0に設定されるので、cwはcw−gcd、すなわち1に設定される.iからサーバ配列ssのポーリングが開始され、最初の重みがcw以上のサーバはaであるため、iは0に設定され、その値が返される.
6回目にこの関数を呼び出すと,iは0,cwは1となる.ループに入ると、iはまず1に設定され、iからサーバ配列ssがポーリングされ、最初の重みがcw以上のサーバはbであるため、iは1に設定され、その値が返される.
この関数を7回目に呼び出すと,iは1,cwは1となる.ループに入ると、iはまず2に設定され、iからサーバ配列ssがポーリングされ、最初の重みがcw以上のサーバはcであるため、iは2に設定され、その値が返される.
 
7(1+2+4)回の呼び出し後、各サーバが選択された回数はちょうど重み値です.