我正在研究一些繁重的演算法，現在我正在嘗試使其成為多執行緒。它有一個帶有 2 個嵌套回圈的回圈：
for (int i = 0; i < n; i) {
for (int j = i 1; j < n; j) {
for (int k = j 1; k < n; k) {
function(i, j, k);
}
}
}
我知道，function呼叫次數將等于
但我還有最后一個問題：我不知道如何計算i，j并且k基于b( 0 <= b < binom(n, 3))
for (int b = start; b < end; b) {
// how to calculate i, j, k?
}
如何計算這些值？
編輯：我的主要想法是從不同的執行緒呼叫這樣的函式：
void calculate(int start, int end) {
for (int b = start; b < end; b) {
int i = ...;
int j = ...;
int k = ...;
function(i, j, k);
}
}
int total = binom(n, 3);
// thread A:
calculate(0, total / 2);
// thread B:
calculate(total / 2, total);
uj5u.com熱心網友回復：
在這篇文章中，我分享了一個名為的類multi_index，它基本上可以滿足您的需求，即
for(auto m : multi_index(3,3,4))
{
// now m[i] holds index of i-th loop
// m[0] goes from 0 to 2
// m[1] goes from 0 to 2
// m[2] goes from 0 to 3
std::cout<<m[0]<<" "<<m[1]<<" "<<m[2]<<std::endl;
}
但是，此代碼僅適用于“正常”回圈，其中每個維度從0某個上限值運行。
在這篇文章中，我將嘗試將其應用于反對稱情況，其中m[i]<m[j]for i<j。鏈接代碼的基本思想保持不變，即創建一個類來保存回圈邊界并提供一個迭代器，該迭代器可用于基于范圍的 for 回圈。唯一的區別是我使用 astd::vector而不是 astd::array作為索引陣列型別：
#include <iostream>
#include <numeric>
#include <vector>
struct antisym_index_t
{
int upper_index;
int dim;
antisym_index_t(int upper_index, int dim) : upper_index(upper_index), dim(dim) {}
struct iterator
{
struct sentinel_t {};
int upper_index;
int dim;
std::vector<int> index_array = {};
bool _end = false;
iterator(int upper_index, int dim) : upper_index(upper_index), dim(dim), index_array(dim)
{
std::iota(std::begin(index_array), std::end(index_array),0);
}
auto& operator ()
{
for (int i = dim-1;i >= 0;--i)
{
if (index_array[i] < upper_index - 1 - (dim-1-i))
{
index_array[i];
for (int j = i 1;j < dim; j)
{
index_array[j] = index_array[j-1] 1;
}
return *this;
}
}
_end = true;
return *this;
}
auto& operator*()
{
return index_array;
}
bool operator!=(sentinel_t) const
{
return !_end;
}
};
auto begin() const
{
return iterator{ upper_index, dim };
}
auto end() const
{
return typename iterator::sentinel_t{};
}
};
auto antisym_index(int upper_index, int dim)
{
return antisym_index_t(upper_index, dim);
}
但是請注意，到目前為止，此代碼尚未經過測驗（寫在我的頭上）。您可以將其用作
for(auto m : antisym_index(5,3))
{
// now m[i] holds index of i-th loop
std::cout<<m[0]<<" "<<m[1]<<" "<<m[2]<<std::endl;
}
編輯：現在，我已經測驗并更正了代碼，請參見此處。給自己的備忘錄：不要發布未經測驗的代碼。
EDIT2：順便說一下，這在問題中回答了您的問題。我不清楚這對多任務處理有何幫助。
uj5u.com熱心網友回復：
我沒有完整的答案，但是有 2 個回圈的解決方案。我睡眠不足的頭腦無法將其概括為 3 個回圈，但也許其他人可以。
在 2D 中，問題變成了從展平的索引中找出三角矩陣的行和列索引。這使得很容易看出“逐漸變細”的一端包含在較大的一端。在 ASCII 藝術中是這樣的：
n
___________
|_ |
| |_ |
| |_ |
| | |_ |
| | |_ |
|___|_____|_|
i ^
|
binom(n-i, 2)
所以，讓我們定義
n回圈結束索引（矩陣行/列數）i外回圈計數器范圍 [0, n)。如圖：列索引j內回圈計數器范圍 [0, i)。如圖：自下而上的行索引a扁平化回圈計數器范圍 [0, binom(n, 2))
然后i可以從 計算binom(n, 2) - binom(n-i, 2) = a。通過 Wolfram Alpha 的一次往返為我們提供：
i = trunc(-0.5 * sqrt((1 - 2 n)**2 - 8 a) n - 0.5).
截斷（=cast to int）“向下舍入”到最后一列。所以行索引j可以計算為
j = a - (binom(n, 2) - binom(n-i, 2))j = a - i*(-i 2 n - 1) / 2
uj5u.com熱心網友回復：
另一個解決你的問題。正如評論中所說，您正在尋找的基本上是找到后繼者和組合的無排名。為此，我使用了 Kreher 和 Stinson 的“組合演算法”一書中的演算法。
這里是由兩個函式的相應的代碼next和unrank以及用于其在unranking功能所需的二項式系數的輔助：
int binomial ( int n, int k )
{
int mn = k;
if ( n - k < mn )
{
mn = n - k;
}
if ( mn < 0 ) { return 0; }
if ( mn == 0 ) { return 1; }
int mx = k;
if ( mx < n - k )
{
mx = n - k;
}
int value = mx 1;
for (int i = 2; i <= mn; i)
{
value = ( value * ( mx i ) ) / i;
}
return value;
}
auto unrank(int rank, int n, int k)
{
std::vector<int> t(k);
int x = 1;
for (int i = 1; i <= k; i)
{
while ( binomial ( n - x, k - i ) <= rank)
{
rank -= binomial ( n - x, k - i );
x;
}
t[i-1] = x;
x;
}
return t;
}
auto next(std::vector<int>& index, int n, int k)
{
for (int i = k-1; i >= 0; --i)
{
if (index[i] < n - k i)
{
index[i];
for (int j = i 1; j < k; j)
{
index[j] = index[j-1] 1;
}
return true;
}
}
return false;
}
然后的想法是從給定的起始地址生成初始索引配置，然后計算此索引(end-start)時間的后繼者。下面是一個例子：
int main()
{
int n = 7;
int k = 4;
int start = 3;
int end = 10;
auto index = unrank(start,n,k);
auto print_index = [&]()
{
for(auto const& ind : index)
{
std::cout<<ind<<" ";
}
std::cout<<std::endl;
};
print_index();
for(int i=start; i<end; i)
{
next(index, n, k);
print_index();
}
}
哪個列印
1 2 3 7
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
這是演示。享受！
uj5u.com熱心網友回復：
第三次嘗試：
我已經拿走了你的代碼，最后讓它正常運行（在 python 中）：
def get_k(n):
total = 0
for i in range(3, n):
for j in range(i 1, n):
for k in range(j 1, n):
total = 1
V = total // 2 # for 2 threads
V_tmp = 0
for i in range(3, n):
if(V_tmp > V):
return i
for j in range(i 1, n):
for k in range(j 1, n):
V_tmp = 1
def pseudo_thread(start, end, n):
counter = 0
for i in range(start, end):
for j in range(i 1, n):
for k in range(j 1, n):
counter = 1
print(counter)
n = 145
k = get_k(n)
pseudo_thread(3, k, n)
pseudo_thread(k, n, n)
這最終應該會給你一個相對較好的分割。即使 n=145，我們的計數器值也會得到 239260 和 227920。這顯然不是一個優雅的解決方案，也不完美，但它為您提供了正確的答案，而無需太多詳細的數學參考。
uj5u.com熱心網友回復：
根據您想要并行化的方式，您還可以使用原子結構并通過比較和交換操作實作迭代。大多數平臺上都有一個 16 位元組的 CAS。與-latomicGCC 上的鏈接。如果我們確保正確對齊，Clang 會行內 CAS 呼叫。
#include <atomic>
#include <type_traits>
#include <cstdio>
/**
* Index for a nested loop
*
* Index for loop in style
* for(i = 0; i < n; i)
* for(j = 0; j < i; j)
* for(k = 0; k < j; k);
*
* The total number of iterations is binom(n, 3)
*
* Indices are int for two reasons:
* 1. Keep overall size at or below 16 byte to allow atomic operations
* 2. The total number of iterations reaches 2^64 at n ~ 4.8 million
*/
struct Index {
int i, j, k;
constexpr Index() noexcept
: i(2), j(1), k(0)
{}
Index& operator () noexcept
{
if(k 1 < j) {
k;
return *this;
}
k = 0;
if(j 1 < i) {
j;
return *this;
}
j = 0;
i;
return *this;
}
};
/**
* Padds Index to power of 2 alignment up to 16 byte
*
* This improves atomic operation performance because it avoids
* split-locks. Not sure if GCC's std::atomic makes actual use of this
* but clang does.
*/
struct AlignedIndex
{
private:
static constexpr std::size_t alignment =
sizeof(Index) < 2 ? 1 :
sizeof(Index) < 3 ? 2 :
sizeof(Index) < 5 ? 4 :
sizeof(Index) < 9 ? 8 :
16;
public:
union {
std::aligned_storage<sizeof(Index), alignment>::type pod;
Index index;
};
constexpr AlignedIndex() noexcept
: index()
{}
};
Index increment(std::atomic<AlignedIndex>& index) noexcept
{
AlignedIndex last = index.load(std::memory_order_relaxed);
AlignedIndex next;
do {
next = last;
next.index;
} while(! index.compare_exchange_weak(last, next, std::memory_order_relaxed));
return last.index;
}
int main()
{
std::atomic<AlignedIndex> index(AlignedIndex{});
int n = 5;
for(Index cur; (cur = increment(index)).i < n; ) {
std::printf("%d %d %d\n", cur.i, cur.j, cur.k);
}
}
uj5u.com熱心網友回復：
不是從 1..binom(n, 3) 迭代，而是從 1..n^3 迭代（概念上是數字 1..n 與自身 2x 的笛卡爾積，而不是 3 個元素的組合，而不是重復）。這樣做，我們可以很容易地從 M 計算 i/j/k：
k = (M / N^0) % N = M % N
j = (M / N^1) % N
i = (M / N^2) % N = M / N^2
當然，這會導致重復，但我們不會一一跳過重復。一旦我們達到數，其中k>=j，我們需要增加b通過(N-k)*N^0 = N-k，以使其“環繞”來0一次。這同樣適用于j>=i-增量b的(N-j)*N^1，環繞。
這樣做時，我們只回傳原始數字集。除法和模數計算有一些開銷，每個變數最多可以重復一次（減去第一個變數），所以是的，對于恒定數量的變數，有一些開銷，但它是常數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/388572.html
上一篇：如何加速這個Python回圈