assembly MIPS中二叉树的MapReduce算法

使用MIPS实现一个mapreduce函数，该函数使用MapReduce方法来分析一组字符串。要处理的字符串存储在一个完整的二叉树中。在该树中，每个叶子包含一个指向字符串的指针。树的每个非叶子节点包含指向两个子节点的指针。
函数mapreduce应该返回一个整数，该整数的值是对给定的树应用map函数和reduce函数的结果。

指向包含要处理的字符串的二叉树根的指针。此指针永远不会为空。
Map函数的指针。
指向reduce函数的指针。

这里有一些map和reduce函数，所有的map函数都有一个指向以空值结尾的ASCII字符串的指针，并返回一个整数。你需要通过指针（jalr）来调用这些函数。

unit始终返回1，无论参数如何。
strlen返回参数字符串的长度。
sum会传回两个参数的总和。
min会传回两个参数中较小的一个。
max会传回两个参数中较大的一个。

mapreduce:
    # substitute your implementation here
    li $v0, 0
    jr $ra

strlen: 
    li $v0, 0
strlen_top:
    lbu $t0, 0($a0)
    beqz $t0, strlen_done
    addi $v0, $v0, 1
    addi $a0, $a0, 1
    b strlen_top
strlen_done:
    jr $ra

unit:
    li $v0, 1
    jr $ra

sum:    
    add $v0, $a0, $a1
    jr $ra

min:
    slt $t0, $a0, $a1
    beqz $t0, min_a1
    move $v0, $a0
    jr $ra
min_a1: move $v0, $a1
    jr $ra

max:
    slt $t0, $a1, $a0
    beqz $t0, max_a1
    move $v0, $a0
    jr $ra
max_a1: move $v0, $a1
    jr $ra

main:
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    # mapreduce(tiny,unit,sum) = 4
    la $a0, tiny
    la $a1, unit
    la $a2, sum
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,unit,sum) = 64
    la $a0, lorem
    la $a1, unit
    la $a2, sum
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(tiny,unit,min) = 1
    la $a0, tiny
    la $a1, unit
    la $a2, min
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,unit,min) = 1
    la $a0, lorem
    la $a1, unit
    la $a2, min
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(tiny,unit,max) = 1
    la $a0, tiny
    la $a1, unit
    la $a2, max
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,unit,max) = 1
    la $a0, lorem
    la $a1, unit
    la $a2, max
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(tiny,strlen,sum) = 16
    la $a0, tiny
    la $a1, strlen
    la $a2, sum
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,strlen,sum) = 354
    la $a0, lorem
    la $a1, strlen
    la $a2, sum
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(tiny,strlen,min) = 3
    la $a0, tiny
    la $a1, strlen
    la $a2, min
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,strlen,min) = 2
    la $a0, lorem
    la $a1, strlen
    la $a2, min
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(tiny,strlen,max) = 5
    la $a0, tiny
    la $a1, strlen
    la $a2, max
    jal mapreduce
    move $a0, $v0
    jal print_int

    # mapreduce(lorem,strlen,max) = 13
    la $a0, lorem
    la $a1, strlen
    la $a2, max
    jal mapreduce
    move $a0, $v0
    jal print_int
    
    # return
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

print_int:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    li $v0, 1
    syscall
    jal print_newline
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

print_string:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    li $v0, 4
    syscall
    jal print_newline
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra
    
print_newline:
    li $v0, 11
    li $a0, 10
    syscall
    jr $ra

    
.data
    
tiny:    .word 0 tinyL tinyR
tinyL:   .word 0 tinyLL tinyLR
tinyR:   .word 0 tinyRL tinyRR
tinyLL:  .word 1 tinyLL_str
tinyLR:  .word 1 tinyLR_str
tinyRL:  .word 1 tinyRL_str
tinyRR:  .word 1 tinyRR_str
tinyLL_str:  .asciiz "itty"
tinyLR_str:  .asciiz "bitty"
tinyRL_str:  .asciiz "word"
tinyRR_str:  .asciiz "set"

lorem:   .word 0 loremL loremR
loremL:  .word 0 loremLL loremLR
loremR:  .word 0 loremRL loremRR
loremLL:     .word 0 loremLLL loremLLR
loremLR:     .word 0 loremLRL loremLRR
loremRL:     .word 0 loremRLL loremRLR
loremRR:     .word 0 loremRRL loremRRR
loremLLL:    .word 0 loremLLLL loremLLLR
loremLLR:    .word 0 loremLLRL loremLLRR
loremLRL:    .word 0 loremLRLL loremLRLR
loremLRR:    .word 0 loremLRRL loremLRRR
loremRLL:    .word 0 loremRLLL loremRLLR
loremRLR:    .word 0 loremRLRL loremRLRR
loremRRL:    .word 0 loremRRLL loremRRLR
loremRRR:    .word 0 loremRRRL loremRRRR
loremLLLL:   .word 0 loremLLLLL loremLLLLR
loremLLLR:   .word 0 loremLLLRL loremLLLRR
loremLLRL:   .word 0 loremLLRLL loremLLRLR
loremLLRR:   .word 0 loremLLRRL loremLLRRR
loremLRLL:   .word 0 loremLRLLL loremLRLLR
loremLRLR:   .word 0 loremLRLRL loremLRLRR
loremLRRL:   .word 0 loremLRRLL loremLRRLR
loremLRRR:   .word 0 loremLRRRL loremLRRRR
loremRLLL:   .word 0 loremRLLLL loremRLLLR
loremRLLR:   .word 0 loremRLLRL loremRLLRR
loremRLRL:   .word 0 loremRLRLL loremRLRLR
loremRLRR:   .word 0 loremRLRRL loremRLRRR
loremRRLL:   .word 0 loremRRLLL loremRRLLR
loremRRLR:   .word 0 loremRRLRL loremRRLRR
loremRRRL:   .word 0 loremRRRLL loremRRRLR
loremRRRR:   .word 0 loremRRRRL loremRRRRR
loremLLLLL:  .word 0 loremLLLLLL loremLLLLLR
loremLLLLR:  .word 0 loremLLLLRL loremLLLLRR
loremLLLRL:  .word 0 loremLLLRLL loremLLLRLR
loremLLLRR:  .word 0 loremLLLRRL loremLLLRRR
loremLLRLL:  .word 0 loremLLRLLL loremLLRLLR
loremLLRLR:  .word 0 loremLLRLRL loremLLRLRR
loremLLRRL:  .word 0 loremLLRRLL loremLLRRLR
loremLLRRR:  .word 0 loremLLRRRL loremLLRRRR
loremLRLLL:  .word 0 loremLRLLLL loremLRLLLR
loremLRLLR:  .word 0 loremLRLLRL loremLRLLRR
loremLRLRL:  .word 0 loremLRLRLL loremLRLRLR
loremLRLRR:  .word 0 loremLRLRRL loremLRLRRR
loremLRRLL:  .word 0 loremLRRLLL loremLRRLLR
loremLRRLR:  .word 0 loremLRRLRL loremLRRLRR
loremLRRRL:  .word 0 loremLRRRLL loremLRRRLR
loremLRRRR:  .word 0 loremLRRRRL loremLRRRRR
loremRLLLL:  .word 0 loremRLLLLL loremRLLLLR
loremRLLLR:  .word 0 loremRLLLRL loremRLLLRR
loremRLLRL:  .word 0 loremRLLRLL loremRLLRLR
loremRLLRR:  .word 0 loremRLLRRL loremRLLRRR
loremRLRLL:  .word 0 loremRLRLLL loremRLRLLR
loremRLRLR:  .word 0 loremRLRLRL loremRLRLRR
loremRLRRL:  .word 0 loremRLRRLL loremRLRRLR
loremRLRRR:  .word 0 loremRLRRRL loremRLRRRR
loremRRLLL:  .word 0 loremRRLLLL loremRRLLLR
loremRRLLR:  .word 0 loremRRLLRL loremRRLLRR
loremRRLRL:  .word 0 loremRRLRLL loremRRLRLR
loremRRLRR:  .word 0 loremRRLRRL loremRRLRRR
loremRRRLL:  .word 0 loremRRRLLL loremRRRLLR
loremRRRLR:  .word 0 loremRRRLRL loremRRRLRR
loremRRRRL:  .word 0 loremRRRRLL loremRRRRLR
loremRRRRR:  .word 0 loremRRRRRL loremRRRRRR
loremLLLLLL:     .word 1 loremLLLLLL_str
loremLLLLLR:     .word 1 loremLLLLLR_str
loremLLLLRL:     .word 1 loremLLLLRL_str
loremLLLLRR:     .word 1 loremLLLLRR_str
loremLLLRLL:     .word 1 loremLLLRLL_str
loremLLLRLR:     .word 1 loremLLLRLR_str
loremLLLRRL:     .word 1 loremLLLRRL_str
loremLLLRRR:     .word 1 loremLLLRRR_str
loremLLRLLL:     .word 1 loremLLRLLL_str
loremLLRLLR:     .word 1 loremLLRLLR_str
loremLLRLRL:     .word 1 loremLLRLRL_str
loremLLRLRR:     .word 1 loremLLRLRR_str
loremLLRRLL:     .word 1 loremLLRRLL_str
loremLLRRLR:     .word 1 loremLLRRLR_str
loremLLRRRL:     .word 1 loremLLRRRL_str
loremLLRRRR:     .word 1 loremLLRRRR_str
loremLRLLLL:     .word 1 loremLRLLLL_str
loremLRLLLR:     .word 1 loremLRLLLR_str
loremLRLLRL:     .word 1 loremLRLLRL_str
loremLRLLRR:     .word 1 loremLRLLRR_str
loremLRLRLL:     .word 1 loremLRLRLL_str
loremLRLRLR:     .word 1 loremLRLRLR_str
loremLRLRRL:     .word 1 loremLRLRRL_str
loremLRLRRR:     .word 1 loremLRLRRR_str
loremLRRLLL:     .word 1 loremLRRLLL_str
loremLRRLLR:     .word 1 loremLRRLLR_str
loremLRRLRL:     .word 1 loremLRRLRL_str
loremLRRLRR:     .word 1 loremLRRLRR_str
loremLRRRLL:     .word 1 loremLRRRLL_str
loremLRRRLR:     .word 1 loremLRRRLR_str
loremLRRRRL:     .word 1 loremLRRRRL_str
loremLRRRRR:     .word 1 loremLRRRRR_str
loremRLLLLL:     .word 1 loremRLLLLL_str
loremRLLLLR:     .word 1 loremRLLLLR_str
loremRLLLRL:     .word 1 loremRLLLRL_str
loremRLLLRR:     .word 1 loremRLLLRR_str
loremRLLRLL:     .word 1 loremRLLRLL_str
loremRLLRLR:     .word 1 loremRLLRLR_str
loremRLLRRL:     .word 1 loremRLLRRL_str
loremRLLRRR:     .word 1 loremRLLRRR_str
loremRLRLLL:     .word 1 loremRLRLLL_str
loremRLRLLR:     .word 1 loremRLRLLR_str
loremRLRLRL:     .word 1 loremRLRLRL_str
loremRLRLRR:     .word 1 loremRLRLRR_str
loremRLRRLL:     .word 1 loremRLRRLL_str
loremRLRRLR:     .word 1 loremRLRRLR_str
loremRLRRRL:     .word 1 loremRLRRRL_str
loremRLRRRR:     .word 1 loremRLRRRR_str
loremRRLLLL:     .word 1 loremRRLLLL_str
loremRRLLLR:     .word 1 loremRRLLLR_str
loremRRLLRL:     .word 1 loremRRLLRL_str
loremRRLLRR:     .word 1 loremRRLLRR_str
loremRRLRLL:     .word 1 loremRRLRLL_str
loremRRLRLR:     .word 1 loremRRLRLR_str
loremRRLRRL:     .word 1 loremRRLRRL_str
loremRRLRRR:     .word 1 loremRRLRRR_str
loremRRRLLL:     .word 1 loremRRRLLL_str
loremRRRLLR:     .word 1 loremRRRLLR_str
loremRRRLRL:     .word 1 loremRRRLRL_str
loremRRRLRR:     .word 1 loremRRRLRR_str
loremRRRRLL:     .word 1 loremRRRRLL_str
loremRRRRLR:     .word 1 loremRRRRLR_str
loremRRRRRL:     .word 1 loremRRRRRL_str
loremRRRRRR:     .word 1 loremRRRRRR_str
loremLLLLLL_str:     .asciiz "Lorem"
loremLLLLLR_str:     .asciiz "ipsum"
loremLLLLRL_str:     .asciiz "dolor"
loremLLLLRR_str:     .asciiz "sit"
loremLLLRLL_str:     .asciiz "amet,"
loremLLLRLR_str:     .asciiz "consectetur"
loremLLLRRL_str:     .asciiz "adipiscing"
loremLLLRRR_str:     .asciiz "elit,"
loremLLRLLL_str:     .asciiz "sed"
loremLLRLLR_str:     .asciiz "do"
loremLLRLRL_str:     .asciiz "eiusmod"
loremLLRLRR_str:     .asciiz "tempor"
loremLLRRLL_str:     .asciiz "incididunt"
loremLLRRLR_str:     .asciiz "ut"
loremLLRRRL_str:     .asciiz "labore"
loremLLRRRR_str:     .asciiz "et"
loremLRLLLL_str:     .asciiz "dolore"
loremLRLLLR_str:     .asciiz "magna"
loremLRLLRL_str:     .asciiz "aliqua."
loremLRLLRR_str:     .asciiz "Ut"
loremLRLRLL_str:     .asciiz "enim"
loremLRLRLR_str:     .asciiz "ad"
loremLRLRRL_str:     .asciiz "minim"
loremLRLRRR_str:     .asciiz "veniam,"
loremLRRLLL_str:     .asciiz "quis"
loremLRRLLR_str:     .asciiz "nostrud"
loremLRRLRL_str:     .asciiz "exercitation"
loremLRRLRR_str:     .asciiz "ullamco"
loremLRRRLL_str:     .asciiz "laboris"
loremLRRRLR_str:     .asciiz "nisi"
loremLRRRRL_str:     .asciiz "ut"
loremLRRRRR_str:     .asciiz "aliquip"
loremRLLLLL_str:     .asciiz "ex"
loremRLLLLR_str:     .asciiz "ea"
loremRLLLRL_str:     .asciiz "commodo"
loremRLLLRR_str:     .asciiz "consequat."
loremRLLRLL_str:     .asciiz "Duis"
loremRLLRLR_str:     .asciiz "aute"
loremRLLRRL_str:     .asciiz "irure"
loremRLLRRR_str:     .asciiz "dolor"
loremRLRLLL_str:     .asciiz "in"
loremRLRLLR_str:     .asciiz "reprehenderit"
loremRLRLRL_str:     .asciiz "in"
loremRLRLRR_str:     .asciiz "voluptate"
loremRLRRLL_str:     .asciiz "velit"
loremRLRRLR_str:     .asciiz "esse"
loremRLRRRL_str:     .asciiz "cillum"
loremRLRRRR_str:     .asciiz "dolore"
loremRRLLLL_str:     .asciiz "eu"
loremRRLLLR_str:     .asciiz "fugiat"
loremRRLLRL_str:     .asciiz "nulla"
loremRRLLRR_str:     .asciiz "pariatur."
loremRRLRLL_str:     .asciiz "Excepteur"
loremRRLRLR_str:     .asciiz "sint"
loremRRLRRL_str:     .asciiz "occaecat"
loremRRLRRR_str:     .asciiz "cupidatat"
loremRRRLLL_str:     .asciiz "non"
loremRRRLLR_str:     .asciiz "proident,"
loremRRRLRL_str:     .asciiz "sunt"
loremRRRLRR_str:     .asciiz "in"
loremRRRRLL_str:     .asciiz "culpa"
loremRRRRLR_str:     .asciiz "qui"
loremRRRRRL_str:     .asciiz "officia"
loremRRRRRR_str:     .asciiz "deserunt"

map函数、reduce函数和mapreduce函数的签名是什么？

map函数的签名是什么？
Map函数为unit和strlen。它们都可以通过函数指针调用，如下所示：

int (*map) (char *)

（unit()不会查看该参数）。
我们如何知道这一点？通过分析这两个函数的汇编代码，也就是说它们的寄存器用法，特别是$a0、$a1和$v0。这两个函数在返回之前都设置了$v0，因此这作为返回值出现;这两个函数都将一个整数放入$v0中，因此，看起来像int类型，但也可能是unsigned int。这两个函数都不使用$a1，但其中一个函数使用$a0作为指针，解引用该指针以获得char（尽管是无符号字符，因此这是一个更好的类型）。
reduce函数的签名是什么？
reduce函数为sum、min和max，可通过函数指针调用，如下所示：

int (*reduce) (int, int)

我们是怎么知道的呢？同样，通过分析这些函数的汇编代码。所有三个函数都访问$a0和$a1，所以看起来像两个参数--它们都像整数一样访问这些参数，并且它们都返回$v0中的整数。
函数mapreduce应该返回一个整数，该整数的值是对给定的树应用map函数和reduce函数的结果。

指向包含要处理的字符串的二叉树的根的指针。
Map函数的指针。
指向reduce函数的指针。

这使得

int mapreduce ( 
                    Tree *node,               // A pointer to binary tree
                    int (*map) (char *),      // A pointer to a map function
                    int (*reduce) (int, int)  // A pointer to a reduce function
                  )

给定的测试main执行以下调用以及其他测试：
mapreduce(tiny,unit,sum)，预期答案为4。
mapreduce(lorem,strlen,min)，预期答案为2。
在这里，我们还将给予表示Tree所需的类型，可以是：

enum TreeType { Branch, Leaf }; // Branch is 0, Leaf is 1

struct Tree;

struct LeafNode {
    TreeType tag;
    char *leafString;
};

struct BranchNode {
    TreeType tag;
    Tree *leftChild;
    Tree *rightChild;
};

struct Tree {
    union {
        TreeType tag;
        LeafNode leafNode;
        BranchNode branchNode;
    };
};

下面是一个接受Tree指针作为参数的函数，用来说明如何在C中操作Tree：

void printTreeNode ( Tree *p ) {
    // test the tag to see if Leaf or Branch
    if ( p->tag == Leaf ) {
        // print the string
        printf("%s\n", p->leafNode.leafString); 
    }
    else {
        // print the pointer addresses for the children
        printf("%p,%p\n", p->branchNode.leftChild, p->branchNode.rightChild);
    }
}

给定这些类型和签名，您可以在C中计算出mapreduce算法，如果您愿意，然后将其进行汇编。
在MIPS这样的汇编语言中，函数调用是一个复杂的主题，涉及到许多微妙的问题，包括遵循调用约定传递参数和返回值、保存值以便在函数调用后继续存在，以及通过函数指针进行调用，如果你已经有了其余的内容，这实际上是相当简单的。
当你在汇编语言中编写函数时，你会希望算法已经在运行（最好用C语言，但伪代码也可以），这样你就可以专注于一个有效算法的汇编实现。当你已经知道你要让函数做什么的时候，写汇编会更好。
(The另一种方法是尝试用你不懂的汇编语言来开发你也不懂的算法--这是一个巨大的、潜在的无法克服的问题。因此，解决这种困难的一种方法是将问题分解为以下两个部分：（a）用您熟悉语言编写的算法和（B）该算法的汇编实现。）
mapreduce函数可以是递归的，因为它将遍历递归数据结构（树），这是有意义的。递归虽然听起来很可怕，但与普通（即非递归）函数调用相比，它不会增加函数实现的复杂性（只要有一个支持递归的调用栈，MIPS就有一个）。这将是大约4-6行C代码。
（或者，可以使用迭代版本来避免递归，但是map和reduce的函数调用已经要求遵守调用约定，因此通过使用迭代来消除递归不会真正简化问题，事实上它会使事情复杂化，因为需要临时的堆栈数据结构。）

assembly MIPS中二叉树的MapReduce算法

1条答案

相关问题

热门标签

最新问答