Я пытаюсь распараллелить свой поиск по дереву, используя подпрограммы go, чтобы разделить рекурсивный поиск.
Моя структура Quadtree выглядит следующим образом:
type Quadtree struct {
Rectangle //Boundary of the quadtree
Points []Point
Ne *Quadtree
Se *Quadtree
Sw *Quadtree
Nw *Quadtree
Divided bool
Capacity int
Parent *Quadtree
}
У меня есть метод с именем QueryForNearestPoints, который принимает Point и searchRadius и возвращает все точки в пределах searcharea в Quadtree. Если в данном searchRadius точек не найдено, то значение searchRadius увеличивается и пробуется снова.
points - канал, на который отправляются точки в радиусе поиска. Я также использую sync.WaitGroup wg, чтобы дождаться завершения всех процедур.
func (q *Quadtree) QueryForNearestPoints(p Point, searchRadius float64) []QueryResult {
searcharea = Circle{p, searchRadius}
var testResults []QueryResult
for {
go func() {
loop:
for {
select {
case item, _ := <-points:
testResults = append(testResults, item)
case <-done:
break loop
}
}
}()
wg.Add(1)
go q.query(searcharea)
wg.Wait()
done <- true
if len(testResults) > 0 {
break
} else {
// Proportionally increase the search radius if no points are found.
searcharea = Circle{p, searcharea.Radius + searcharea.Radius*50/100}
}
}
return testResults
}
Метод запроса распараллеленного квадратного дерева:
func (q *Quadtree) query(area Circle) {
defer wg.Done()
if !q.overlapsCircle(area) {
return
}
if len(q.Points) > 0 {
for i, point := range q.Points {
if area.contains(point) {
points <- QueryResult{point, i, q}
}
}
}
if q.Divided {
wg.Add(4)
go q.Ne.parallelquery(area)
go q.Se.parallelquery(area)
go q.Sw.parallelquery(area)
go q.Nw.parallelquery(area)
}
}
(q *Quadtree) parallelquery метод:
func (q *Quadtree) parallelquery(area Circle) {
semaphore <- struct{}{}
defer func() {
<-semaphore
}()
q.query(area)
}
Если я не ошибаюсь, это рабочая нагрузка, связанная с процессором, так что выполнение тысяч подпрограмм не поможет, поэтому я использую буферизованный канал semaphore в качестве счетного семафора, чтобы убедиться, что при в любой точке активны только n количество подпрограмм (здесь я сделал n как 4, потому что у моего компьютера 4 процессора).
Единственная проблема заключается в том, что этот подход значительно медленнее, чем обычный не параллельный последовательный подход. Что мне здесь не хватает? Как я могу сделать это быстрее?