Как из длинны массива и максильного количества потоков узнать индексы которые будет обрабатывать поток?

Question

[Catmengi]

Есть длинна структуры данных и условный define D_STRUCT_SERIALISER_THREADS, каждый такой поток обрабатывает элемент из хэш таблицы который он получает по ключу из keys[i] и передает в очередь обработанный элемент откуда ее берет другой поток и собирает в финальный char* массив. Будет ли быстрее если запустить этап обработки элемент в несколько потоков? Поток сборки простаивает мало. Я понял что надо как-то посчитать start и end для массива keys для каждого потока, НО размер keys не всегда четный. Какие есть варианты решения этой проблемы? Целесобразно ли вообще делать сериализацию в несколько потоков? Код текущего сериализатора

Answer 1

[Wataru]

Вам надо разбить массив на K как можно более равных частей?

Если длина массива N, то все куски будут длиной хотя бы floor(N/K), и ровно N%K будут иметь на 1 элемент больше. Вроде, если у вас 10 элементов надо на 3 потока разделить, то будут длины {4, 3, 3}. А если 15 на 4, то {4, 4, 4, 3}

Так что i-ый кусок будет начинаться с позиции (N/K)*i + min(i, N%K) и иметь длину N/K + ((i < N%K) ? 1 : 0).

Чуть проще формулы, если вы эти позиции явно в массиве получите, а не будете каждую отдельно считать:

int start[K], end[K];
int prev = -1;
for (int i = 0; i < K; ++i) {
  int len = N/K + ((i < N%K) ? 1 : 0);
  start[i] = prev + 1;
  end[i] = start[i] + len;
  prev = end[i];
}