Как разделить сравнение «все против всех» на куски одинакового размера для распараллеливания?

Question

Я знаю, что это должно быть довольно простой вариант использования, но я не знаю, какие ключевые слова искать.

Учитывая вложенный цикл вроде этого:

for (i = 0; i < size; i++) {
  for (j = i+1; j < size; j++) {
    doComparision(i, j);
  }
}

Я знаю, что могу вычислить общее количество сравнений с n = size * (size-1) / 2.

Проблема в том, что я хочу распараллелить этот цикл.Каждый поток должен выполнять только определенный диапазон внешнего цикла for:

for (i = beginOffset; i <= endOffset; i++) {
  for (j = i+1; j < size; j++) {
    doComparision(i, j);
  }
}

Как рассчитать количество сравнений в таких циклах?

В конце я хочу убедиться, что каждый поток выполняет примерно одинаковый объем работы.

Answer 1

Можно упростить это, но вот уравнение, которое должно работать:

n = (end-begin+1)*(size-begin-1) - (end-begin+1)*(end-begin)/2

Вот описание каждого термина, которое может помочь понять, почему это работает:

• (end-begin+1): итерации внешнего цикла
• (size-begin-1): максимальное количество итераций внутреннего цикла
• (end-begin+1)*(end-begin)/2: 1 + 2 + ... + (конец - начало)