MapReduce矩阵乘法复杂度

Question

假设我们有一个大文件，其中包含两个矩阵(A和B)的单元的描述:

+---------------------------------+
|  i  |  j  |  value  |   matrix  |
+---------------------------------+
|  1  |  1  |   10    |     A     |
|  1  |  2  |   20    |     A     |
|     |     |         |           |
| ... | ... |   ...   |    ...    |
|     |     |         |           |
|  1  |  1  |    5    |     B     |
|  1  |  2  |    7    |     B     |
|     |     |         |           |
| ... | ... |   ...   |    ...    |
|     |     |         |           |
+---------------------------------+

我们要计算这两个矩阵的乘积:C = A x B
定义:C_i_j = sum( A_i_k * B_k_j )

这里是一个两步MapReduce算法，用于计算这个乘积(我将提供一个伪代码):

第一步:

function Map (input is a single row of the file from above):
    i = row[0]
    j = row[1]
    value  = row[2]
    matrix = row[3]
    if(matrix == 'A')
        emit(i, {j, value, 'A'})
    else
        emit(j, {i, value, 'B'})

该Map函数的复杂度为O(1)

function Reduce(Key, List of tuples from the Map function):
    Matrix_A_tuples = 
        filter( List of tuples from the Map function, where matrix == 'A' )
    Matrix_B_tuples = 
        filter( List of tuples from the Map function, where matrix == 'B' )
    for each tuple_A from Matrix_A_tuples
        i = tuple_A[0]
        value_A = tuple_A[1]
        for each tuple_B from Matrix_B_tuples
            j = tuple_B[0]
            value_B = tuple_B[1]
            emit({i, j}, {value_A * value_b, 'C'})

该Reduce函数的复杂度为O(N^2)

在第一步之后，我们将得到如下文件(包含O(N^3)行):

+---------------------------------+
|  i  |  j  |  value  |   matrix  |
+---------------------------------+
|  1  |  1  |   50    |     C     |
|  1  |  1  |   45    |     C     |
|     |     |         |           |
| ... | ... |   ...   |    ...    |
|     |     |         |           |
|  2  |  2  |    70   |     C     |
|  2  |  2  |    17   |     C     |
|     |     |         |           |
| ... | ... |   ...   |    ...    |
|     |     |         |           |
+---------------------------------+

所以，我们所要做的-只是从包含相同值i和j的行中求和。

第二步:

function Map (input is a single row of the file, which produced in first step):
    i = row[0]
    j = row[1]
    value = row[2]
    emit({i, j}, value)

function Reduce(Key, List of values from the Map function)
    i = Key[0]
    j = Key[1]
    result = 0;
    for each Value from List of values from the Map function
        result += Value
    emit({i, j}, result)

在第二步之后，我们将获得包含矩阵C的单元格的文件。

所以问题是:

考虑到，在MapReduce集群中有多个实例-这是估计所提供算法复杂性的最正确方法?

首先想到的是:
当我们假设MapReduce集群中的实例数为K时。而且，由于在第一步之后生成的文件的行数是O(N^3)，因此总体复杂性可以估计为O((N^3)/K)。

但是这种估计没有考虑到许多细节:比如MapReduce集群实例之间的网络带宽，在不同距离之间分发数据的能力，以及在本地执行大部分计算等。

所以，我想知道哪种是估计所提供的MapReduce算法效率的最佳方法，以及使用Big-O符号来估计MapReduce算法的效率是否有意义?

Answer 1

正如你所说的Big-O估计计算复杂性，并没有考虑网络问题，如(带宽，拥塞，延迟…)

如果您想计算实例之间的通信效率，在这种情况下，您需要其他网络指标…

然而，我想告诉你一些事情，如果你的文件不够大，你不会看到执行速度的提高。这是因为MapReduce只有在处理大数据时才能有效地工作。此外，您的代码有两个步骤，这意味着两个任务。MapReduce从一个作业转到另一个作业，需要一定的时间上传文件并重新启动作业。这可能会轻微影响性能。

我认为你可以在速度和时间方面有效地计算，因为MapReduce方法在处理大数据时肯定更快。这是如果我们将其与顺序算法进行比较。

此外，效率可以与容错性有关。这是因为MapReduce可以自己处理故障。因此，程序员不需要处理实例故障或网络故障。