儘可能均勻地將間隔分爲n部分

Question

如何更有效地做到這一點？我認爲有一個標準的快速方法來做到這一點。但我無法找到。

這是用於在n個cpu內核之間劃分一些內存的工作。

輸出：

# Divide [0, 11) to 4 parts # 
interval 0: [0, 3) with length: 3 
interval 1: [3, 6) with length: 3 
interval 2: [6, 9) with length: 3 
interval 3: [9, 11) with length: 2 
# Divide [0, 12) to 4 parts # 
interval 0: [0, 3) with length: 3 
interval 1: [3, 6) with length: 3 
interval 2: [6, 9) with length: 3 
interval 3: [9, 12) with length: 3 

程序：

#include <iostream> 

int part(int L, int n_parts, int part_id) { 
    int out = L/n_parts * part_id; 
    int r = L % n_parts; 
    if (part_id < r) { 
     out += part_id; 
    } else { 
     out += r; 
    } 
    return out; 
} 

void test(int L, int n_parts) { 
    std::cout << "# Divide [0, " << L << ") to " 
       << n_parts << " parts #\n"; 
    for (int i = 0; i < n_parts; ++i) { 
     int st = part(L, n_parts, i); 
     int en = part(L, n_parts, i + 1); 
     int len = en - st; 
     std::cout << "interval " << i <<": [" << st 
        << ", " << en << ") " 
        << "with length: " << len 
        << "\n"; 
    } 
} 

int main() { 
    test(11, 4); 
    test(12, 4); 
} 

到目前爲止，它使用1個區，1％，1次乘法，1點相比，和1除了（嗒嗒機器人在左右） 。

Answer 1

我平時寫解決這類問題，像這樣：

size_t num_of_elements = 10'000; 
size_t num_of_groups = 17; 
for(size_t i = 0; i < num_of_groups; i++) { 
    std::pair<size_t, size_t> pair{ 
     i * num_of_elements/num_of_groups, 
     (i + 1) * num_of_elements/num_of_groups 
    }; 
    std::cout << "Group " << (i+1) << ": [" << pair.first << "," << pair.second << ") - " << (pair.second - pair.first) << " elements." << std::endl; 
} 

我們得到以下的結果，如果衝裁成mundane int main() program：

Group 1: [0,588) - 588 elements. 
Group 2: [588,1176) - 588 elements. 
Group 3: [1176,1764) - 588 elements. 
Group 4: [1764,2352) - 588 elements. 
Group 5: [2352,2941) - 589 elements. 
Group 6: [2941,3529) - 588 elements. 
Group 7: [3529,4117) - 588 elements. 
Group 8: [4117,4705) - 588 elements. 
Group 9: [4705,5294) - 589 elements. 
Group 10: [5294,5882) - 588 elements. 
Group 11: [5882,6470) - 588 elements. 
Group 12: [6470,7058) - 588 elements. 
Group 13: [7058,7647) - 589 elements. 
Group 14: [7647,8235) - 588 elements. 
Group 15: [8235,8823) - 588 elements. 
Group 16: [8823,9411) - 588 elements. 
Group 17: [9411,10000) - 589 elements. 

如果你想要這個邏輯提取到一個功能：

std::pair<size_t, size_t> get_bounds(size_t group_id, size_t num_of_groups, size_t num_of_elements) { 
    return std::make_pair<size_t, size_t>(
     group_id * num_of_elements/num_of_groups, 
     (group_id + 1) * num_of_elements/num_of_groups 
    ); 
}