分治算法总是能够获得更好的性能吗？

Question

分治算法总是能够获得更好的性能吗？

c++performancerecursiondivide-and-conquer

3

我目前正在测试一些分治算法和它们的常规实现。我对此还比较新，不确定在使用分治时是否总是能得到更好的性能表现。例如，我已经实现了一个算法来传统地转置矩阵并使用分治方法，但我仍然使用第一版获得了更好的性能。这可能是可能的，或者我漏掉了一些重要的东西吗？

这里是使用分治的代码：

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;
}

提前感谢！

- Adrisui3

你之前不是问过同样的问题吗？ - 463035818_is_not_a_number

我确实回复了，但是我没有添加代码，然后它就被关闭了。 - Adrisui3

为了比较两个算法的性能，我们需要查看这两个算法的代码。 - Jerry Jeremiah

2个回答

0

第一个函数预计性能更高，因为它不会进行任何额外的函数调用，这些调用是不免费的。

在我看来，如果：

您能够并行使用多个处理器--使用线程或类似MPI的环境，或者
函数的可读性得到改善（从而提高可维护性），或者
更高级别的算法可以在概念上分成较小的、可能可重用的函数。

您可以使用分治法。

- R Sahu

我知道所有的理论，但我看不到为什么分治算法表现不如基本算法好 :( - Adrisui3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rustyx · Accepted Answer

第一个版本做了更多的工作 - 它在原地转置片段，然后将它们交换到正确的位置。

第二个版本一次转置一个元素，但是已经将其转置到最终位置。

此外，在顺序过程中，分而治之仅在工作集不适合L3缓存（8MB或更多）时才有益，这相当于一个大小大于1000 * 1000的矩阵。

尽管并行化（在CPU级别）也不会有益，因为矩阵转置完全受DRAM限制。