Pこの質問のために使用する例である、空間内の点の平均ペアワイズ距離を見つけることに概念的に似ている問題を効率的に解決したいと考えています。計算は十分に並列化できるので、Go で取り組みたいと思いました。i = 0...P-1シーケンシャル プログラムでは、外側のループと内側のループの 2 つのネストされたループを実行する必要がありますj = i+1...P-1。i次に、ポイントとの間の距離を計算し、jそれらをすべて合計し、最後にポイント ペアの数で割ります。したがって、計算では、可能なポイント ペアの組み合わせの「三角形」をカバーする必要があります。
Go での最初の試みは、同じロジックを使用することでしたが、チャネルを介してワーカー関数に計算を分散させました。私のアプローチは次のとおりです。
package main
import "math"
import "sync"
import "fmt"
import "math/rand"
import "github.com/schollz/progressbar"
const nProcs = 32
const nPoints = 30000
type Pair struct {
p1 [3]float64
p2 [3]float64
}
func square(f float64) (float64) {
return f * f
}
func progress(total int64, ch <-chan int) {
bar := progressbar.Default(total)
for i := range ch {
bar.Add(i)
}
}
func worker(idx int, sumBuffer []float64, in <-chan Pair, out chan<- int, wg *sync.WaitGroup) {
count := int64(0)
defer wg.Done();
for pair := range in {
dist := math.Sqrt(square(pair.p1[0]-pair.p2[0]) + square(pair.p1[1]-pair.p2[1]) + square(pair.p1[2]-pair.p2[2]))
sumBuffer[idx] += dist
count++
if count % (2<<15) == 0 {
out <- (2<<15)
}
}
}
func main() {
var sumBuffer [nProcs]float64
var points [nPoints][3]float64
var sum float64
for i := 0; i < nPoints; i++ {
for j := 0; j < 3; j++ {
points[i][j] = rand.Float64()
}
}
wg := &sync.WaitGroup{};
wg.Add(nProcs);
progressCh := make(chan int, 4 * nProcs)
pairCh := make(chan Pair, 4 * nProcs)
nPairs := int64(nPoints - 1) * int64(nPoints) / int64(2)
go progress(nPairs, progressCh)
for i := 0; i < nProcs; i++ {
go worker(i, sumBuffer[:], pairCh, progressCh, wg)
}
for i := int64(0); i < nPoints; i++ {
for j := int64(i+1); j < nPoints; j++ {
pairCh <- Pair{points[i], points[j]}
}
}
close(pairCh)
wg.Wait();
for i := 0; i < nProcs; i++ {
sum += sumBuffer[i]
}
sum /= float64(nPairs)
fmt.Println("Average distance:", sum)
}
ただし、このプログラムは、私が期待したほど速くは実行されませんでした。2 回目の試行では、タスクを分散するためのチャネルを取り除き、代わりに手動でワーカー間で計算を分割しました。次に、すべてのワーカーは最初に、「三角形」のどの部分をカバーする必要があるかを計算する必要がありますが、これは非常に面倒です。
package main
import "math"
import "sync"
import "fmt"
import "math/rand"
import "github.com/schollz/progressbar"
const nProcs = 32
const nPoints = 30000
func square(f float64) (float64) {
return f * f
}
func progress(total int64, ch <-chan int) {
bar := progressbar.Default(total)
for i := range ch {
bar.Add(i)
}
}
func worker(idx int, points [][3]float64, sumBuffer []float64, start int64, stop int64, out chan<- int, wg *sync.WaitGroup) {
count := start
length := int64(len(points))
defer wg.Done();
// Calculate start value for loop index i
iStart := int64(0)
pointCount := int64(0)
for k := length - 1; k >= 0; k-- {
if pointCount + k > start {
break
} else {
pointCount += k
iStart++
}
}
firstLoop := true
for i := int64(iStart); i < length && count < stop; i++ {
// Calculate start value for loop index j
var jStart int64
if firstLoop {
jStart = (i + 1) + (start - pointCount)
} else {
jStart = i + 1
}
for j := int64(jStart); j < length && count < stop; j++ {
dist := math.Sqrt(square(points[i][0]-points[j][0]) + square(points[i][1]-points[j][1]) + square(points[i][2]-points[j][2]))
sumBuffer[idx] += dist
count++
if count % (2<<15) == 0 {
out <- (2<<15)
}
}
firstLoop = false
}
}
func main() {
var sumBuffer [nProcs]float64
var points [nPoints][3]float64
var sum float64
for i := 0; i < nPoints; i++ {
for j := 0; j < 3; j++ {
points[i][j] = rand.Float64()
}
}
wg := &sync.WaitGroup{};
wg.Add(nProcs);
progressCh := make(chan int, 4 * nProcs)
nPairs := int64(nPoints - 1) * int64(nPoints) / int64(2)
go progress(nPairs, progressCh)
step := int64(math.Ceil(float64(nPairs) / float64(nProcs)))
for i := 0; i < nProcs; i++ {
go worker(i, points[:], sumBuffer[:], int64(i) * step, int64(i+1) * step, progressCh, wg)
}
wg.Wait();
for i := 0; i < nProcs; i++ {
sum += sumBuffer[i]
}
sum /= float64(nPairs)
fmt.Println("Average distance:", sum)
}
これで、2 番目のプログラムは約 100 倍高速になりました。ただし、そのバージョンでは Go の利点を利用することさえできず、同じプログラムを C++ で作成することもできました。チャネルを使用することによって導入されるオーバーヘッドがそれほど劇的にならないように、最初のプログラムをどのように改善できますか? それとも、これはチャネルの効率の限界に過ぎず、私のユースケースでは、チャネルは単に進むべき道ではないのでしょうか?
それとは別に、私はGoの初心者です。私のプログラムは、Go のイデオロギー的ではないと確信しています。私のスタイルを改善する方法についてのコメントは大歓迎です。
