sin(x)

Page 6 of 10

算法导论:斐波那契堆

斐波那契堆是一种理论上优于二向堆的数据结构,对比二向堆,斐波那契堆的优势在插入、合并、减值。不同于常见的二叉树、二向堆那样可以直观地计算出各种操作需要的时间复杂度,斐波那契堆的复杂度计算需要一些技巧。完整的斐波那契堆实现见Gist

操作 二向堆(最坏) 斐波那契堆(摊还)
创建 O(1) O(1)
插入 O(lgn) O(1)
访问最小值 O(1) O(1)
弹出最小值 O(lgn) O(lgn)
合并 O(n) O(1)
减值 O(lgn) O(1)
删除某个元素 O(lgn) O(lgn)

Continue reading

算法导论:B树

B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树:

B树当中每个节点存储着一组数据,数据的数量由B树的来决定。

B树中的节点包含以下内容:

  • 大小(size):用来记录当前节点中元素的个数;

  • 关键字(key):B树是有序集合,关键字是可比的,用于在集合中定位卫星数据;

  • 是否为叶子节点(leaf):节点类型可以分为内部节点和叶子节点。

  • 孩子节点(children):如果当前节点是一个内部节点的话,那么就有更加底层的孩子节点。如果是叶子节点。那就没有孩子节点。孩子节点的数量总是比数据的数量多一个。

Continue reading

Scheme解释器实现(四):优化

变量容器、运行环境、解析器、解释器都已经开发完毕,已经可以使用这些基础设施搭建一个Scheme解释器了。对于一个成熟的额解释器来说,性能式非常关键的,本文将对解释器进行简单的优化。

统计信息

在优化过程中,我们需要想办法衡量优化的效果,所有需要对解释过程中一些操作次数进行记录。statistic.hppstatistic.cpp实现了统计功能,提供了以下接口:

void createVariable();
void destroyVariable();
void copyVariable();
void traceVariable();
void finalizeVariable();
void printStatistic();
void applyStart();
void applyEnd();

Continue reading

Scheme解释器实现(三):解释

解释

一旦解析获得了S表达式,解释过程就可以实现了。表达式有以下几种:

  • 自求值:数字和字符串;
  • 符号:(quote <quoted>)
  • 变量:符号;
  • 定义:(define <var> <val>)或者(define (<var> <arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • 赋值:(set! <var> <val>)
  • 和:(and <exp1> <exp2> ... <expn>)
  • 或:(or <exp1> <exp2> ... <expn>)
  • 序列:(begin <exp1> <exp2> ... <expn>)
  • if:(if <predication> <consequence> <alternative>)
  • lambda:(lambda (<arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • cond:(cond (<condition> <consequence>) ... (else <consquence>))
  • let:(let ((<var1> <val1>) ... (<varn> <valn>)) <exp1> ... <expn>)
  • 过程调用:(<proc> <arg1> ... <argn>)

Continue reading

算法导论:红黑树

红黑树,一种平衡二叉树,最为著名的应用就是C++ STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质:

  1. 每个节点是红色或者黑色的;
  2. 根节点是黑色的;
  3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少);
  4. 如果一个节点是红色的,那么它的两个子节点是黑色的;
  5. 对于每一个节点,到后代所有叶节点所经过的黑色节点数目相同。

根据定义,可以写出红黑树节点的数据结构:

struct Node {
    enum Color { RED, BLACK };
    Color _color;
    Key _key;
    Value _value;
    Node *_parent, *_left, *_right;
    Node(): _color(BLACK) {}
    Node(const Key &key, const Value &value, Node *left, Node *right, Node *parent):
        _key(key), _value(value), _color(RED), _left(left), _right(right), _parent(parent) {}
};

本文省略了拷贝、析构、赋值等操作,完整源代码放在Gist上。

Continue reading

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑