1/ Duff's Device 从一个指针from向另一个指针to拷贝count个字节,你打算怎么做? 正常的做法是: 这段代码当中,这句--count > 0的会被判断count次。 那么真的需要判断这么多次么?让我们来看看Duff's Device的实现是怎么做的 这段代码巧妙地将switch和while杂糅在一起,不仅每次8个字节进行拷贝,而且对末尾不足8个字节的部分做了精巧的处理,通过循环展开减少了循环判断的次数,从而优化了性能。 2/ 尾递归 给你一个单链表的头结点,让你得到这条链表的长度是多少,要求用递归进行编写的话,你会怎么做呢? 正常的做法是 这段代码的问题在于什么呢?如果链表非常长的话,成百上千次的递归压栈将会耗尽栈空间,造成栈溢出。如果我们使用尾递归的话,就可以这样 尾递归与普通递归最大的区别在于,整个递归调用占据了整个return后面的部分。由于它在整个方法的最后才被调用,那么之前函数压栈保留的所有局部变量等等信息都不影响下一次递归调用,所以本次方法中栈内的信息可以被清空,让下次调用可以重复使用这段栈空间。 所以尾递归的本质,其实就是将这次递归方法当中的必要信息,传递到下次递归当中,从而保证return后面是一个完整的递归函数调用而不是一个表达式。 3/ 二级指针删除单向链表中结点 这个利用二级指针(pointers-to-pointers)优化单向链表当中的删除操作,是Linus在Linus Torvalds Answers Your Questions上就什么才是真正的“core low-level kind of coding”所提出的一个例子。当你要写一个单向链表当中根据某个特定条件来剔除结点的函数,你会怎么写呢? 正常的做法是 其中remove_fn是一个函数指针类型,表示判断是否删除结点的条件。这里的实现通过维护一个prev指针来进行结点的删除,需要判断prev是否为NULL来确定当前删除的结点是不是头结点。这种实现方式是被Linus所唾弃的“This person doesn’t understand pointers”。那么使用二级指针对上述代码进行优化的话,就是 上述代码的重点在于二级指针curr。循环开始时,二级指针curr指向头结点的指针。如果头结点是需要删除的结点的话,*curr=entry->next就相当于*head=(*head)->next,也即修改头结点的指针指向下一个结点。 如果要删除的节点不是头结点的话,由于curr是通过&entry->next更新的,所以要此时curr指向要删除的节点的上一个节点的next指针,而entry指向的是要当前要删除的指针,此时*curr=entry->next就相当于prev->next=entry->next,从而完成当前节点的删除。 |
|