Всегда ли Divide a Conquer дает лучшую производительность? - PullRequest
Новая
       63

Всегда ли Divide a Conquer дает лучшую производительность?

3 голосов
/ 01 апреля 2020

В настоящее время я тестирую некоторые алгоритмы «разделяй и властвуй» в сравнении с их обычными реализациями. Я довольно новичок в этом, и я не уверен, должен ли я всегда получать лучшую производительность при использовании разделяй и властвуй. Например, я реализовал алгоритм для традиционного транспонирования матрицы и использования метода «разделяй завоевателя», но я все еще получаю лучшую производительность, используя первую версию. Возможно ли это, или я упускаю что-то важное?

Вот код, использующий разделяй и властвуй 

void trasponer_DyV(Matriz &matriz)
{
    if (matriz.size() >= 2)
    {
        trasponer_DyV(matriz, 0, matriz.size(), 0, matriz.size());
    }
}

void trasponer_DyV(Matriz &matriz, int fil_inicio, int fil_fin, int col_inicio, int col_fin)
{
    int tam = fil_fin - fil_inicio;

    if (tam == 1)
        return;

    trasponer_DyV(matriz,fil_inicio, fil_inicio + tam / 2,col_inicio, col_inicio + tam / 2);
    trasponer_DyV(matriz, fil_inicio, fil_inicio + tam / 2, col_inicio + tam / 2, col_inicio + tam);
    trasponer_DyV(matriz, fil_inicio + tam / 2, fil_inicio + tam, col_inicio, col_inicio + tam / 2);
    trasponer_DyV(matriz, fil_inicio + tam / 2, fil_inicio + tam, col_inicio + tam / 2, col_inicio + tam);

    for (int i = 0; i < tam / 2; i++)
    {
        for (int j = 0; j < tam / 2; j++)
            swap(matriz[fil_inicio + i][col_inicio + tam / 2 + j], matriz[fil_inicio + tam / 2 + i][col_inicio + j]);
    }
}

А вот грубая сила: 

Matriz trasponer_fuerzabruta(const Matriz &matriz)
{
    Matriz ret;
    ret.resize(matriz.size());
    for (int i = 0; i < matriz.size(); ++i)
    {
        ret[i].resize(matriz.size());
    }

    // Todo lo que hacemos es sustituir filas por columnas.
    for (int fila = 0; fila < matriz.size(); ++fila)
    {
        for (int columna = 0; columna < matriz.size(); ++columna)
        {
            ret[columna][fila] = matriz[fila][columna];
        }
    }

    return ret;
}

Заранее спасибо!

Ответы [ 2 ]

1 голос
/ 01 апреля 2020

Первая версия выполняет больше работы - она ​​транспонирует фрагменты на месте, а затем заменяет их в нужном месте.

Вторая версия транспонирует один элемент за раз, но делает это уже до конечного места. .

Кроме того, в последовательном процессе функция «разделяй и властвуй» выгодна только тогда, когда рабочий набор не помещается в кэш L3 (8 МБ или более), что соответствует матрице размером> 1000 * 1000.

Хотя распараллеливание (на уровне ЦП) также не принесет пользы, поскольку транспонирование матрицы является операцией, полностью связанной с DRAM.

0 голосов
/ 01 апреля 2020

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

ИМХО, вы использовали бы «разделяй и властвуй», если:

  1. Вы можете использовать несколько процессоров параллельно - используя потоки или среду, подобную MPI, или

  2. Улучшена читаемость функции (в результате чего (повышает удобство обслуживания) или

  3. Алгоритм более высокого уровня может быть концептуально разделен на меньшие, потенциально многократно используемые функции.

...